К вам в город прилетел известный художник. Он хочет превратить здания, расположенные на главной улице вашего города, в удивительный арт-объект. Здания на главной улице выстроены в одну линию, поэтому для простоты художник пронумеровал их последовательными

К вам в город прилетел известный художник. Он хочет превратить здания, расположенные на главной улице вашего города, в удивительный арт-объект. Здания на главной улице выстроены в одну линию, поэтому для простоты художник пронумеровал их последовательными целыми числами от 1
до N
. У художника есть M
красок различных цветов, каждый цвет имеет свой уникальный номер от 1
до M
. Художник планирует раскрасить все дома на улице, несколько раз применив следующий алгоритм:

Выбрать целые числа li
и ri
(1≤li≤ri≤N)
.
Покрасить все дома с li
-го по ri
-й включительно в цвет ci
, потратив на это всю краску данного цвета (т.е. художник не сможет использовать эту краску в дальнейшем). Если дом ранее уже был покрашен, то художник перекрасит его в цвет ci
.
Перед тем как начать работу, художник просит вас помочь ему и сказать, возможно ли, несколько раз применив описанный алгоритм, получить итоговую раскраску s
, которую он задумал. А также, если это возможно, нужно подсказать художнику правильную последовательность действий.

Входные данные
Первая строка содержит целые числа N
и M
— количество зданий на главной улице и количество красок у художника (1≤N,M≤3⋅105)
.

Вторая строка содержит целые числа s1
, ..., sN
— цвета домов в раскраске, которую задумал художник (1≤si≤M)
.

Выходные данные
Выведите −1
, если получить раскраску s
невозможно.

В противном случае в первой строке выведите целое число q
— количество применений алгоритма покраски (1≤q≤M)
. В следующих q
строках опишите последовательность применений алгоритма, приводящую к итоговой раскраске s
. В i
-й из этих строк нужно вывести целые числа ci
, li
и ri
, описывающих i
-е применение алгоритма (1≤ci≤M
; 1≤li≤ri≤N
). Все числа ci
должны быть попарно различными.

Если существуют разные способы получить итоговую раскраску s
, вы можете описать любой из них.