19906번 - Постановочное фото 서브태스크스페셜 저지다국어

Перед общим фотографированием участников всероссийской олимпиады школьников по информатике главный фотограф решил сделать постановочное фото для своих подписчиков в социальной сети Innogram. 

В олимпиаде принимают участие школьники из $n$ регионов, каждая делегация состоит из $m$ школьников. Делегация каждого региона хочет подчеркнуть свою индивидуальность, поэтому надела фирменные футболки своего цвета, который не совпадает с цветом футболок никакого другого региона. Обозначим цвет футболки, который надели школьники $i$-го региона, числом $i$.

Для организации постановочного фото фотограф планирует действовать следующим образом. На сцене в ряд расположены места, куда могут вставать школьники, они пронумерованы вдоль сцены от $1$ до $m$. Фотограф планирует по очереди обратиться к руководителям некоторых делегаций с просьбой нескольким школьникам этой делегации выйти на сцену. При этом он указывает два числа: $L$ и $R$. Школьники выбранной делегации выходят на сцену и занимают все места от $L$-го до $R$-го, включительно. Если на каких-либо из этих мест уже стоят школьники других делегаций, то они уходят со сцены, а их места занимают школьники новой делегации. Фотограф может обратиться к руководителю каждой делегации не более одного раза.

Для цветовой гармонии на получившемся снимке фотограф хочет, чтобы на фотографии стояли $m$ школьников, причём цвета надетых на них футболок должны следовать в строго определенном порядке. Теперь он хочет понять, каким образом он может получить желаемую фотографию.

Требуется написать программу, которая по заданному порядку цветов футболок на фотографии определяет, в каком порядке следует попросить руководителей делегаций отправить школьников на сцену, и какие места им следует занять, чтобы сделать желаемое фото, либо выясняет, что это невозможно. 

Первая строка входных данных содержит два целых числа: $m$ и $n$ ($1 \le m \le 3 \cdot 10^5$, $1 \le n \le 3 \cdot 10^5$). Вторая строка содержит $m$ целых чисел $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$) --- цвета футболок в том порядке, в котором фотограф хочет получить их на фотографии.

Первая строка выходных данных должна содержать одно целое число $k$. Если сделать желаемое фото невозможно, это число должно быть равно $-1$. В противном случае оно должно быть равно количеству делегаций, к руководителям которых фотограф должен обратиться, чтобы сделать желаемое фото. 

В этом случае следующие $k$ строк должны описывать просьбы фотографа в том порядке, в котором их следует сделать. Его $i$-я просьба задается тремя целыми числами: $c_i$, $L_i$ и $R_i$, где $c_i$ -- номер делегации, к которой следует обратиться, $L_i$ и $R_i$ --- номера первого и последнего места на сцене, соответственно, которые необходимо занять школьникам делегации $c_i$ ($1 \le c_i \le n$, все $c_i$ должны быть различны, $1 \le L_i \le R_i \le m$).

Если существует несколько решений, выведите любое из них.