27176번 - Интересные выходные 서브태스크다국어

Петя и его младший брат Коля пришли в аквапарк. Коля любит кататься с горки, которую можно схематически изобразить как часть треугольной сетки, вершины которой --- узлы горки. В каждом узле можно выбрать, по какой трубе ехать дальше --- влево-вниз или вправо-вниз.

Уровни горки нумеруются сверху вниз, начиная с $0$. На нулевом уровне у горки один узел --- начало поездки, на первом уровне --- два узла, \ldots, на $i$-м уровне --- $i + 1$ узлов. Всего у горки $n + 1$ уровней. Каждая поездка сверху вниз проходит ровно по $n$ трубам. У каждого узла есть координаты: два числа $(r, c)$ задают $c$-й слева узел на уровне $r$ ($0 \leq c \leq r \leq n$). Обратите внимание, что и уровни, и узлы на каждом уровне нумеруются с $0$. Если Коля находится в узле $(r, c)$ и поедет влево-вниз, он попадет в узел $(r + 1, c)$, а если он поедет вправо-вниз, он попадет в узел $(r + 1, c + 1)$.

Пример горки в аквапарке с 5 уровнями:

Коля хочет скатиться с горки ровно $n + 1$ раз. Перед каждым спуском Петя будет выдавать ему инструкцию, как надо спуститься по горке. Каждая инструкция состоит ровно из $n$ команд <<влево-вниз>> или <<вправо-вниз>> --- куда Коля должен ехать из очередного узла.

Первая инструкция состоит только из команд <<вправо-вниз>>. Пете лень придумывать новые инструкции, поэтому инструкции для двух соседних спусков отличаются только одной командой: чтобы получить инструкцию $i + 1$ из инструкции $i$, надо изменить $a_i$-ю команду с <<вправо-вниз>> на <<влево-вниз>> ($1 \leq a_i \leq n$). Заметим, что каждая команда будет изменена таким образом ровно один раз. В результате, $(n + 1)$-я инструкция будет состоять только из команд <<влево-вниз>>. Можно показать, что каждый узел будет посещен Колей хотя бы в одном из спусков.

На обратном пути из аквапарка у Коли возникло несколько вопросов следующего вида. Рассмотрим множество всех труб, по которым он проехал хотя бы один раз. Коля называет координаты двух узлов: $(r_1, c_1)$ и $(r_2, c_2)$. Вы должны определить координаты такого узла $(r_3, c_3)$, что из него по рассматриваемым трубам достижимы узлы $(r_1, c_1)$ и $(r_2, c_2)$, и среди всех таких узел $(r_3, c_3)$ является наиболее низким, то есть с максимальным возможным значением $r_3$. Можно показать, что такой узел всегда существует и единственен.

Ответьте на все его вопросы!

В первой строке дано одно целое число $n$ ($1 \leq n \leq 500\,000$).

В следующей строке даны $n$ целых чисел $a_1$, $a_2$, \ldots $a_n$ ($1 \leq a_i \leq n$), где $a_i$ --- номер команды, которая изменится после $i$-го спуска. Гарантируется, что все $a_i$ различны.

В следующей строке дано одно целое число $q$ ($1 \leq q \leq 500\,000$) --- количество вопросов Коли.

В каждой из следующих $q$ строк даны четыре целых числа $r_{i,1}$, $c_{i,1}$, $r_{i,2}$ и $c_{i,2}$ ($0 \leq r_{i,1}, r_{i,2} \leq n$; $0 \leq c_{i,1} \leq r_{i,1}$; $0 \leq c_{i,2} \leq r_{i,2}$) --- координаты первого и второго узлов из $i$-го вопроса.

Выведите $q$ строк, в $i$-й строке выведите два целых числа $r_{i,3}$ и $c_{i, 3}$ --- координаты узла, являющегося ответом на $i$-й вопрос.

В первом примере спуски Коли выглядят следующим образом:

(a) Спуск 1	(b) Спуск 2	(c) Спуск 3	(d) Спуск 4

Если отметить все трубы, по которым проехал Коля в первом примере, то получится следующее: