Обернене дерево Фенвіка

Обмеження: 3 сек., 512 МіБ

Зеник цікавиться, як же розв’язувати задачі деревом Фенвіка з запитами на максимум. Для цього він розв’язує наступну задачу.

Дано масив \(a\) з \(n\) елементів, початково заповнений нулями. Потрібно виконати послідовність запитів, кожен з яких є одним з двох типів:

1. Задано \(x\) та \(y\), потрібно змінити \(a[x]\) на \(max(a[x], y)\);

2. Задано \(p\), потрібно знайти найбільше значення на префіксі \([1, p]\), тобто \(max(a_1, a_2, \dots, a_p)\).

Зеник розв’язав задачу та залишив дані про запити другого типу – для кожного запиту відомо префікс \(p\) та яке значення максимуму \(v\) було на цьому префіксі. Всі ці результати відомі в правильному хронологічному порядку. Марічка побачила ці результати та їй стало цікаво, яку ж мінімальну кількість запитів першого типу міг зробити Зеник.

Вхідні дані

В першому рядку задано 2 цілих числа \(k\) та \(n\) – кількість запитів 2 типу та довжина масиву.

В наступних \(k\) рядках задано по 2 цілих числа \(p\) та \(v\) – відомо, що на префіксі \([1, p]\) найбільше значення було рівне \(v\).

Вихідні дані

В першому рядку виведіть мінімальну кількість запитів першого типу, яку міг виконати Зеник. Якщо ж Зеник припустився помилки й результати запитів неможливі, виведіть -1.

Якщо відповідь існує, в наступних рядках виведіть можливу послідовність запитів першого типу. В кожному рядку виведіть 3 цілих числа \(c\), \(x\), \(y\), де \(c\) – скільки запитів другого типу відбулось перед даним запитом першого типу, запит змінює \(a[x]\) на \(max(a[x], y)\).

Повинно виконуватись \(0 \le c \le k\), \(1 \le x \le n\), \(1 \le y \le 10^6\).

Запити можна виводити у будь-якому порядку. Якщо існує декілька послідовностей запитів, виведіть будь-яку.

Обмеження

\(1 \le k \le 2 \cdot 10^5\),

\(1 \le n \le 10^6\),

\(1 \le p_i \le n\),

\(1 \le v_i \le 10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 7 4 7 4 10 3 7 6 47	3 0 5 47 0 2 7 1 4 10

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 1 1 7 1 4	-1

Примітки

У першому прикладі можливо спершу поставити 47 на позицію 5 і 7 на позицію 2, масив стає рівним [0, 7, 0, 0, 47, 0, 0].

Після цього виконуємо запит другого типу і на префіксі довжини 4 максимальне значення рівне 7. Після цього встановлюємо на позицію 4 значення 10 та проводимо решту запитів другого типу, для кожного з них отримуємо правильний результат.

У другому прикладі значення на першій позиції повинне спершу бути рівним 7, а потім 4, що неможливо, адже ми не можемо зменшувати значення.