Петя решил попробовать себя в роли инженера. Недавно он придумал очень сложный механизм. Настолько сложный, что ему самому не удалось в нём разобраться. Поэтому он обратился к Вам за помощью.
Устройство состоит из $$$n$$$ отрезков на числовой прямой. Отрезки заданы координатами начала и конца, причем эти координаты целые. Гарантируется, что длины всех отрезков положительные. Помимо этого известно, что все отрезки изначально имеют одинаковую длину.
Далее, устройство может производить следующие операции-запросы с этими отрезками:
1. Выбрать отрезок с номером $$$i$$$ и сдвинуть его влево или вправо на $$$d$$$. Например, если сдвинуть отрезок $$$[3; 7]$$$ на $$$4$$$ вправо, то получится $$$[7; 11]$$$.
2. Выбрать отрезки с номерами с $$$i$$$-го по $$$j$$$-й и расширить их все влево или вправо ровно в два раза. То есть фиксируется левый или правый конец, а противоположный сдвигается так, что длина отрезка увеличивается в два раза. Например, если отрезки $$$[3;5]$$$ и $$$[8; 12]$$$ расширить влево, то получатся отрезки $$$[1; 5]$$$ и $$$[4; 12]$$$, а если вправо — $$$[3; 7]$$$ и $$$[8; 16]$$$.
3. Выбрать отрезок с номером $$$i$$$ и вывести любой отрезок из имеющихся, содержащий $$$i$$$-й. Координата начала искомого отрезка должна быть строго меньше координаты начала $$$i$$$-го, а координата конца строго больше координаты конца $$$i$$$-го. Петю не интересует номер найденного отрезка, он хочет знать только координаты начала и конца. Например, отрезок $$$[6; 8]$$$ содержится в отрезке $$$[5; 10]$$$, но отрезки $$$[5; 9]$$$ и $$$[8; 10]$$$ не содержатся в отрезке $$$[5; 10]$$$.
Согласно Петиным расчётам, гарантируется, что координаты начала и конца любого из отрезков в течение всех операций являются положительными и не превосходят $$$10^9$$$.
Помогите Пете с реализацией устройства и выведите ответы на все запросы третьего типа.
В первой строке находится целое число $$$n\ (1 \leqslant n \leqslant 10^5)$$$ — число отрезков.
Далее в $$$n$$$ строках вводятся пары чисел — $$$a_i$$$ и $$$b_i\ (1 \leqslant a_i, b_i \leqslant 10^9)$$$ — координаты начала и конца отрезка $$$i$$$. Гарантируется, что все отрезки имеют одинаковую длину.
В следующей строке вводится число $$$q\ (1 \leqslant q \leqslant 10^5)$$$ — количество операций.
Далее в $$$q$$$ строках даны запросы. Первое число в строке $$$t\ (t \in \{1, 2, 3\})$$$ — тип операции.
Если $$$t = 1$$$, то далее идёт два числа $$$i\ (1 \leqslant i \leqslant n)$$$ и $$$d\ (0 \leqslant d \leqslant 10^9)$$$, а также символ «l» или «r». «l» означает сдвиг влево, а «r» — вправо.
Если $$$t = 2$$$, то далее идёт два числа $$$i$$$ и $$$j\ (1 \leqslant i \leqslant j \leqslant n)$$$, а также символ «l» или «r». «l» означает расширение влево, а «r» — вправо.
Если $$$t = 3$$$, то далее идёт число $$$i\ (1 \leqslant i \leqslant n)$$$.
Для каждого запроса третьего типа, если искомый отрезок найден, необходимо вывести два числа — координату начала и конца найденного отрезка через пробел. Если искомых отрезков несколько, можно вывести любой из них. В случае, если такого отрезка нет, выведите одно число $$$-1$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обратите внимание, что подзадачи 4 и 5 не требуют прохождения теста из условия.
Здесь $$$C$$$ — ограничение на правую границу отрезка после каждого запроса. Например, если $$$C \leqslant 100$$$, то правая граница каждого отрезка не будет превосходить $$$100$$$ после каждого запроса.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Комментарий |
| $$$0$$$ | $$$0$$$ | — | — | Тесты из условия |
| $$$1$$$ | $$$10$$$ | $$$n \leqslant 100, C \leqslant 100$$$ | $$$0$$$ | — |
| $$$2$$$ | $$$10$$$ | $$$n \leqslant 1000, C \leqslant 1000$$$ | $$$1$$$ | — |
| $$$3$$$ | $$$10$$$ | $$$n \leqslant 1000, C \leqslant 10^9$$$ | $$$2$$$ | — |
| $$$4$$$ | $$$15$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | — | Нет запросов первого типа |
| $$$5$$$ | $$$15$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | — | Нет запросов второго типа |
| $$$6$$$ | $$$40$$$ | $$$n \leqslant 10^5, C \leqslant 10^9$$$ | $$$3, 4, 5$$$ | — |
31 43 610 1353 12 2 2 r1 2 1 l2 2 2 r3 3
-1 2 14
В тесте из условия изначально у нас имеются отрезки $$$[1; 4], [3; 6], [10; 13]$$$ и поступает 5 запросов.
- Первый запрос требует от нас найти отрезок, содержащий в себе первый, т.е. $$$[1; 4]$$$. Такого отрезка нет, поэтому ответ на запрос $$$-1$$$.
- Второй запрос расширяет отрезок номер два вправо, он становится равным $$$[3; 9]$$$.
- Третий запрос сдвигает отрезок номер два влево на $$$1$$$, он становится равным $$$[2; 8]$$$.
- Четвертый запрос расширяет отрезок номер два вправо, он становится равным $$$[2; 14]$$$.
- Пятый запрос требует от нас найти отрезок, содержащий в себе третий, т.е. $$$[10; 13]$$$. Это отрезок $$$[2; 14]$$$, мы выводим его в качестве ответа на запрос.
| Name |
|---|