Given an $n+1$ layer triangular grid, the points in the $i$-th layer ($0 \le i \le n$) are numbered $(i, 0), \dots, (i, i)$.

For every point $(i, j)$ except for those in the last layer, there are two edges leading to the next layer: the left edge $(i, j) \to (i+1, j)$ and the right edge $(i, j) \to (i+1, j+1)$.

There is a ball at $(0, 0)$, which will choose $n+1$ different paths to reach the last layer. Initially, the chosen path is to always move to the right to reach the next layer, i.e., $(0, 0) \to (1, 1) \to \dots \to (n, n)$. For $1 \le i \le n$, the $i$-th path and the $(i-1)$-th path differ only in the direction chosen when reaching the $a_i$-th layer. For example, if $a_1 = 2$, the second path is $(0, 0) \to (1, 1) \to (2, 1) \to \dots \to (n, n-1)$.

Given a permutation $a_1, \dots, a_n$ of $1 \dots n$, it can be observed that all $n+1$ paths reach exactly all nodes in the $n$-th layer, and all points in the grid form a rooted tree structure. There are $q$ queries, each providing two points $(x_1, y_1)$ and $(x_2, y_2)$ in the grid. Find the lowest common ancestor of these two points in the rooted tree.

Input

• $n$
• $a_1 \ a_2 \ \dots \ a_n$
• $q$
• $x_1 \ y_1 \ x_2 \ y_2$
• $\dots$

Output

• $x \ y$
• $\dots$

Examples

Input 1

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

Output 1

0 0
1 1
0 0
2 1
2 2

Note

Subtasks