Постановочное фото

Перед общим фотографированием участников всероссийской олимпиады школьников по информатике главный фотограф решил сделать постановочное фото для своих подписчиков в социальной сети 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$).

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