Before the group photo of the participants of the All-Russian Olympiad in Informatics, the head photographer decided to take a staged photo for their followers on the social network Innogram.

The Olympiad involves students from $n$ regions, and each delegation consists of $m$ students. Each region's delegation wants to emphasize its individuality, so they wear branded T-shirts of their own color, which does not match the color of the T-shirts of any other region. Let us denote the color of the T-shirt worn by the students of the $i$-th region by the number $i$.

To organize the staged photo, the photographer plans to act as follows. There are seats arranged in a row on the stage where students can stand, numbered along the stage from 1 to $m$. The photographer plans to approach the leaders of some delegations one by one with a request for several students of that delegation to come onto the stage. When doing so, they specify two numbers: $L$ and $R$. The students of the chosen delegation come onto the stage and occupy all seats from the $L$-th to the $R$-th, inclusive. If students from other delegations are already standing in any of these seats, they leave the stage, and their places are taken by the students of the new delegation. The photographer can approach the leader of each delegation no more than once.

For color harmony in the resulting shot, the photographer wants $m$ students to be standing in the photo, and the colors of the T-shirts they are wearing must follow a strictly defined order. Now, they want to understand how they can obtain the desired photo.

You are required to write a program that, given the order of T-shirt colors in the photo, determines the order in which the delegation leaders should be asked to send students to the stage and which seats they should occupy to create the desired photo, or determines that it is impossible.

Input

The first line of the input contains two integers: $m$ and $n$ ($1 \leqslant m \leqslant 3 \cdot 10^5$, $1 \leqslant n \leqslant 3 \cdot 10^5$). The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \leqslant a_i \leqslant n$) — the colors of the T-shirts in the order in which the photographer wants to obtain them in the photo.

Output

The first line of the output must contain a single integer $k$. If it is impossible to create the desired photo, this number must be equal to $-1$. Otherwise, it must be equal to the number of delegations the photographer must approach to create the desired photo.

In this case, the following $k$ lines must describe the photographer's requests in the order they should be made. The $i$-th request is given by three integers: $c_i$, $L_i$, and $R_i$, where $c_i$ is the number of the delegation to be approached, and $L_i$ and $R_i$ are the numbers of the first and last seats on the stage, respectively, that the students of delegation $c_i$ must occupy ($1 \leqslant c_i \leqslant n$, all $c_i$ must be distinct, $1 \leqslant L_i \leqslant R_i \leqslant m$).

If there are multiple solutions, output any of them.

Examples

Input 1

7 10
10 5 5 10 4 2 4

Output 1

5
4 1 7
7 2 4
10 1 4
5 2 3
2 6 6

Input 2

5 2
1 2 1 2 1

Output 2

-1

Subtasks