B. Игра на отрезках
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в следующую игру. У Алисы есть набор непересекающихся отрезков целых чисел $$$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$$$, которое выбирал Боб.

Можно показать, что по данному списку отрезков всегда существует ровно один способ восстановить числа Боба.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), обозначающих, что Алиса в какой-то момент игры выбрала отрезок $$$[l, r]$$$.

Обратите внимание, что отрезки даны в произвольном порядке.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$, а отрезки в каждом наборе входных данных соответствуют корректной игре.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ строк. Каждая строка должна содержать три целых числа $$$l$$$, $$$r$$$ и $$$d$$$, обозначающих, что для отрезка Алисы $$$[l, r]$$$ Боб выбрал число $$$d$$$.

Вы можете выводить эти строки в любом порядке. Можно показать, что ответ единственный.

Не обязательно выводить пустую строку между различными входными данными. В примере эти пустые строки сделаны только для удобства.

Пример
Входные данные
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
Примечание

В первом примере есть только один отрезок $$$[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$$$$$$ \{ \} $$$ (пустой набор)