Problem Description

Translated from ROI 2022 D1T3.

Peppa and her little brother George came to a water park. George likes sliding down a slide. This slide can be described as a part of a triangular grid, where the vertices are nodes of the slide. At each node, you can choose which pipe to go through next—down-left or down-right. The slide is numbered from top to bottom, starting from level $0$. At level $0$, the slide has only one node; at level $1$, it has two nodes; at level $i$, it has $i + 1$ nodes. In total, there are $n + 1$ levels. Each ride from top to bottom goes through exactly $n$ pipes. Each node has coordinates, represented by two numbers $(r, c)$, meaning the $c$-th node from the left on level $r$ ($0 \le c \le r \le n$). Note that both the levels and the nodes within each level are numbered starting from $0$. If George is at node $(r, c)$ and slides down-left, he will move to node $(r + 1, c)$. If he slides down-right, he will move to node $(r + 1, c + 1)$.

Here is a slide with $5$ levels ($n = 4$):

George wants to slide down the slide $n + 1$ times. Before each ride, Peppa gives him an instruction telling him how to slide along the slide. Each instruction consists of exactly $n$ commands, each being either “down-left” or “down-right”. George follows Peppa’s commands, moving from his current node to the next node. The first instruction contains only “down-right” commands. Peppa is too lazy to come up with new instructions, so the instructions for two consecutive rides differ in exactly one command: to get from the $i$-th instruction to the $(i + 1)$-th instruction, you need to change the $a_i$-th (not the $i$-th) command from “down-right” to “down-left”. Each command is changed exactly once. In the end, the $(n + 1)$-th instruction will contain only “down-left” commands. It can be proven that during these $n + 1$ rides, George will pass through every node of the slide (but not every pipe).

On the way back from the water park, George encountered the following problem. First, consider the set of all pipes that he has slid through. You are given the coordinates of two nodes: $(r_1, c_1)$ and $(r_2, c_2)$. You need to determine the coordinates of a node $(r_3, c_3)$ such that starting from this node, using only the pipes he slid through, it is possible to reach both node $(r_1, c_1)$ and node $(r_2, c_2)$. Among all such nodes, it must be the lowest one, i.e. the value of $r_3$ is as large as possible. It can be proven that such a node always exists and is unique.

George has many queries, but since he has already left the water park, he cannot touch this slide anymore. He needs your help to answer all his queries.

Input Format

The first line contains an integer $n$ ($1 \le n \le 500 000$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the index of the command that will be changed after the $i$-th ride. It is guaranteed that all $a_i$ are distinct.

The third line contains an integer $q$ ($1 \le q \le 500 000$), the number of George’s queries.

Each of the next $q$ lines contains four integers $r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2}$ ($0 \le r_{i,1}, r_{i,2} \le n$, $0 \le c_{i,1} \le r_{i,1}$, $0 \le c_{i,2} \le r_{i,2}$), representing the coordinates of the two nodes in the $i$-th query.

Output Format

Output $q$ lines. For each query, output two integers $r_{i,3}$ and $c_{i,3}$, the coordinates of the answer node for the $i$-th query.

3
2 3 1
5
3 3 3 0
2 2 2 1
1 0 3 1
3 1 3 2
2 2 2 2

0 0
1 1
0 0
2 1
2 2

Hint

Sample Explanation:

The routes of George’s four rides are as follows:

So the set of all pipes he passed through is as follows:

The answers to the five queries can be easily obtained from the figure.

Constraints:

In Subtask $4$, the array $a$ has the form $1, 2, 3, \dots, k, n, n - 1, n - 2, \dots, k + 1$, where $0 \le k \le n$.

Translated by ChatGPT 5