Задача №114805. Магниты
У вас есть квадратная магнитная доска размера \(10^9 \times 10^9\), в левом нижнем углу которой расположено начало системы координат. Также на доске расположены \(n\) магнитов, пронумерованных от \(1\) до \(n\). Каждый магнит представляет собой квадрат \(1 \times 1\) . Изначально магниты расположены таким образом, что правый нижний угол \(i\)-го магнита имеет координату \((i, 0)\).
Вам поступает \(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\).
Для каждого запроса типа \(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