Алиса и Боб играют в следующую игру. У Алисы есть набор непересекающихся отрезков целых чисел \(S\), изначально содержащий только один отрезок \([1, n]\). За один ход Алиса выбирает некоторый отрезок \([l, r]\) из набора \(S\), а Боб выбирает некоторое число \(d\) из этого отрезка (\(l \le d \le r\)). Затем Алиса убирает \([l, r]\) из \(S\), и добавляет в \(S\) отрезки \([l, d - 1]\) (если \(l \le d - 1\)) и \([d + 1, r]\) (если \(d + 1 \le r\)). Игра заканчивается, когда \(S\) становится пустым. Можно показать, что количество шагов в такой игре всегда ровно \(n\).
После того, как игра была сыграна, Алиса запомнила все отрезки \([l, r]\), которые она доставала из набора \(S\), но Боб не запомнил ни одного числа, которые он выбирал. Но Боб умный и понимает, что числа \(d\) можно восстановить, используя отрезки, которые помнит Алиса, и просит вас помочь запрограммировать это.
По данному списку отрезков, которые Алиса доставала (\([l, r]\)) восстановите для каждого отрезка число \(d\), которое выбирал Боб.
Можно показать, что по данному списку отрезков всегда существует ровно один способ восстановить числа Боба.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк. Каждая строка должна содержать три целых числа \(l\), \(r\) и \(d\), обозначающих, что для отрезка Алисы \([l, r]\) Боб выбрал число \(d\).
Вы можете выводить эти строки в любом порядке. Можно показать, что ответ единственный.
Не обязательно выводить пустую строку между различными входными данными. В примере эти пустые строки сделаны только для удобства.
Примечание
В первом примере есть только один отрезок \([1, 1]\). Алиса выбирала только один отрезок \([1, 1]\), и Боб мог выбрать только число \(1\).
Во втором примере \(n = 3\). Изначально в наборе находится один отрезок \([1, 3]\).
- Алиса выбирает отрезок \([1, 3]\). Боб выбирает число \(1\). Алиса добавляет в набор отрезок \([2, 3]\), и после этого хода это единственный отрезок в наборе.
- Алиса выбирает отрезок \([2, 3]\). Боб выбирает число \(3\). Алиса добавляет в набор отрезок \([2, 2]\).
- Алиса выбирает отрезок \([2, 2]\). Боб выбирает число \(2\). Игра заканчивается.
В четвертом наборе игра начинается с \(n = 5\). Изначально в наборе находится только отрезок \([1, 5]\). Ходы в игре показаны в следующей таблице.
| Номер хода | Отрезок, выбранный Алисой | Число, выбранное Бобом | Набор отрезков после хода |
| Перед началом | | | \( \{ [1, 5] \} \) |
| 1 | \([1, 5]\) | \(3\) | \( \{ [1, 2], [4, 5] \}\) |
| 2 | \([1, 2]\) | \(1\) | \( \{ [2, 2], [4, 5] \} \) |
| 3 | \([4, 5]\) | \(5\) | \( \{ [2, 2], [4, 4] \} \) |
| 4 | \([2, 2]\) | \(2\) | \( \{ [4, 4] \} \) |
| 5 | \([4, 4]\) | \(4\) | \( \{ \} \) (пустой набор) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1 1
3
1 3
2 3
2 2
6
1 1
3 5
4 4
3 6
4 5
1 6
5
1 5
1 2
4 5
2 2
4 4
|
1 1 1
1 3 1
2 2 2
2 3 3
1 1 1
3 5 3
4 4 4
3 6 6
4 5 5
1 6 2
1 5 3
1 2 1
4 5 5
2 2 2
4 4 4
|