Zadanie

Farebný pásik

Počet bodov: 40

Máš pásik papiera. Tento pásik má \(p\) políčok. Na začiatku sú všetky políčka biele (majú farbu 0). Políčka si za radom očíslujeme od 1 po \(p\).

Máš \(f\) kapsúl s rôznymi farbami. Tieto farby sú očíslované od 1 po \(f\).

Máš tiež vysnívaný vzhľad svojho pásika: postupnosť farieb \(a_1, \dots, a_p\), ktorú majú mať jednotlivé políčka. (Všetky \(a_i\) sú od 1 po \(f\), žiadne políčko teda nemá ostať biele.)

Farbu z kapsuly na pásik nevieš dostať ručne, musíš na to použiť mašinu. Mašina funguje tak, že do nej vložíš kapsulu s farbou, zadáš jej dve políčka \(\ell\) a \(r\), zasunieš do nej začiatok pásika a spustíš ju. Mašina potom vcucne pásik a všetky políčka, ktorých čísla ležia v intervale \([\ell, r]\), prefarbí na farbu z kapsuly.

Každú kapsulu vieš použiť len raz.

Zisti, či sa vysnívaný pásik dá vyrobiť. Ak áno, nájdi ľubovoľnú jednu postupnosť použití mašiny, ktorá ho vyrobí.

Vstup a výstup

V prvom riadku vstupu sú čísla \(p\) a \(f\).

V prvej sade platí \(1 \leq p, f \leq 100\). V druhej sade platí \(1 \leq p, f \leq 10\,000\). V tretej sade platí \(1 \leq p, f \leq 300\,000\).

V druhom riadku vstupu sú čísla \(a_1, \dots, a_p\). Platí \(\forall i: 1 \leq a_i \leq f\).

Ak sa pásik vyrobiť nedá, vypíšte jediný riadok a v ňom číslo -1.

Ak sa pásik vyrobiť dá, vypíšte niekoľko riadkov. V prvom riadku uveďte počet \(k\) použití mašiny. Následne vypíšte \(k\) riadkov popisujúcich jednotlivé použitia mašiny v chronologickom poradí. Každý riadok musí mať tvar xi li ri, kde \(x_i\) je farba použitej kapsuly a \(\ell_i \leq r_i\) sú čísla začiatku a konca súvislého úseku políčok, ktoré má mašina touto farbou ofarbiť.

Pripomíname, že všetky \(x_i\) musia byť navzájom rôzne.

Príklady

Input:

7 10
10 5 5 10 4 2 4

Output:

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

Sedempolíčkový pásik, desať farieb. Návod najskôr ofarbí celý pásik farbou 4, potom tri políčka farbou 7, potom štyri políčka farbou 10, a tak ďalej.

Input:

5 2
1 2 1 2 1

Output:

-1