Задача №114125. Постановочное фото
Перед общим фотографированием участников всероссийской олимпиады школьников по информатике главный фотограф решил сделать постановочное фото для своих подписчиков в социальной сети 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\)).
Если существует несколько решений, выведите любое из них.
7 10 10 5 5 10 4 2 4
4 10 1 4 4 5 7 2 6 6 5 2 3
5 2 1 2 1 2 1
-1