У вас есть квадратная магнитная доска размера $$$10^9 \times 10^9$$$, в левом нижнем углу которой расположено начало системы координат. Также на доске расположены $$$n$$$ магнитов, пронумерованных от $$$1$$$ до $$$n$$$. Каждый магнит представляет собой квадрат $$$1 \times 1$$$ . Изначально магниты расположены таким образом, что правый нижний угол $$$i$$$-го магнита имеет координату $$$(i, 0)$$$.
Пример начального состояния для $$$n=5$$$ Вам поступает $$$q$$$ запросов двух типов:
- запрос типа $$$1$$$ характеризуется двумя целыми числами $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$): взять магниты с номерами от $$$l$$$ до $$$r$$$ включительно и повернуть их на $$$90^{\circ}$$$. Если выбранные магниты образовывали горизонтальный отрезок, то поворот следует осуществить против часовой стрелки на $$$90^{\circ}$$$, так они превратятся в вертикальный отрезок. Если выбранные магниты образовывали вертикальный отрезок, то поворот следует осуществить по часовой стрелке на $$$90^{\circ}$$$, так они превратятся в горизонтальный отрезок. Все повороты производятся относительно магнита с наименьшим номером. В данном запросе гарантируется, что магниты с номерами от $$$l$$$ до $$$r$$$ включительно в момент обработки запроса образуют непрерывный горизонтальный или вертикальный отрезок.
- запрос типа $$$2$$$ характеризуется одним целым числом $$$j$$$ ($$$1 \leq j \leq n$$$): вывести координаты $$$(x, y)$$$ правого нижнего угла магнита с номером $$$j$$$.
Ниже приведены состояния доски для $$$n=6$$$ и серии запросов первого типа: $$$(l_1=2,r_1=5)$$$, $$$(l_2=3,r_2=4)$$$, $$$(l_3=2,r_3=3)$$$, $$$(l_4=6,r_4=6)$$$.
Начальное состояние для $$$n=6$$$.
После обработки запроса первого типа $$$(l_1=2,r_1=5)$$$.
После обработки запроса первого типа $$$(l_2=3,r_2=4)$$$.
После обработки запроса первого типа $$$(l_3=2,r_3=3)$$$.
После обработки запроса первого типа $$$(l_4=6,r_4=6)$$$.
Для каждого запроса типа $$$2$$$ необходимо вывести координаты магнита с соответствующим номером.
В первой строке находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — количество магнитов на доске и количество запросов, соответственно.
В следующих $$$q$$$ строках находится по одному запросу $$$1$$$ или $$$2$$$ типа. Запрос $$$1$$$ типа состоит из $$$3$$$ целых чисел $$$1$$$ $$$l$$$ $$$r$$$ $$$(1 \le l \le r \le n)$$$, запрос $$$2$$$ типа состоит из $$$2$$$ целых чисел $$$2$$$ $$$j$$$ $$$(1 \le j \le n)$$$.
Для каждого запроса типа $$$2$$$ выведите $$$x$$$ и $$$y$$$ — координаты правого нижнего угла магнита с номером $$$j$$$ в момент обработки соответствующего запроса.
6 8 1 2 5 2 5 1 3 4 2 4 1 2 3 2 6 1 6 6 2 1
2 3 3 1 6 0 1 0
7 7 1 3 6 1 3 4 1 5 6 2 3 2 4 2 5 2 6
3 0 4 0 3 2 4 2
