Страшные дела творятся в Ромашковой долине.
Железная няня активируется в точке $$$(0, 0)$$$ и начинает искать бодрствующих смешариков. Смешарики прячутся в каких-то точках и не меняют свою позицию.
Далее происходят $$$q$$$ событий, события бывают двух видов:
- Железная няня обнаруживает бодрствующего смешарика в точке $$$(x, y)$$$, при этом остаётся на месте;
- Железная няня перемещается в ближайшую точку с бодрствующим смешариком и укладывает его спать; если таких точек несколько, Железная няня перемещается в лексикографически минимальную.
Ближайшей к точке $$$(x_1, y_1)$$$ называется точка $$$(x_2, y_2)$$$, которая минимизирует величину $$$|x_1 - x_2| + |y_1 - y_2|$$$ (Манхэттенское расстояние).
Определите точки, в которых смешарики будут уложены спать.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора дано целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество событий.
В следующих $$$q$$$ строках каждого набора даны события:
- $$$1$$$ $$$x$$$ $$$y$$$ ($$$1 \le x, y \le 10^5$$$) — Железная няня обнаруживает нового бодрствующего смешарика;
- $$$2$$$ — Железная няня укладывает спать ближайшего бодрствующего смешарика.
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Также гарантируется, что в одном наборе входных данных в событиях первого типа все точки $$$(x, y)$$$ попарно различны.
Также гарантируется, что перед любым событием второго типа известно положение хотя бы одного бодрствующего смешарика.
Для каждого события второго типа выведите точку, в которую переместилась Железная няня.
191 1 21 2 121 4 11 3 221 2 422
1 22 13 24 1
Изначально няня находится в точке $$$(0,0)$$$.
Перед первым удалением бодрствующие смешарики находятся в точках $$$(1,2)$$$ и $$$(2,1)$$$. Они равноудалены от няни, поэтому выбирается лексикографически минимальная точка $$$(1,2)$$$.
Перед вторым удалением бодрствующие смешарики находятся в точках $$$(2,1)$$$, $$$(3,2)$$$ и $$$(4,1)$$$. Ближайшие точки — $$$(2,1)$$$ и $$$(3,2)$$$, поэтому выбирается $$$(2,1)$$$.
Перед третьим удалением бодрствующие смешарики находятся в точках $$$(2,4)$$$, $$$(3,2)$$$ и $$$(4,1)$$$. Выбирается $$$(3,2)$$$.
Перед четвёртым удалением бодрствующие смешарики находятся в точках $$$(2,4)$$$, $$$(4,1)$$$. Выбирается $$$(4,1)$$$.
