흥미로운 주말

Petya와 동생 Kolya가 워터파크에 왔습니다. Kolya는 미끄럼틀 타기를 좋아합니다. 이 미끄럼틀은 삼각형 격자의 일부로 나타낼 수 있으며, 격자의 꼭짓점이 미끄럼틀의 노드입니다. 각 노드에서 왼쪽 아래 관과 오른쪽 아래 관 중 하나를 골라 다음 노드로 이동합니다.

층은 위에서 아래로 0번부터 번호가 붙습니다. 0층에는 노드가 하나 있으며 이것이 출발점입니다. 1층에는 노드가 두 개이고, 이런 식으로 $i$층에는 $i + 1$개의 노드가 있습니다. 미끄럼틀은 총 $n + 1$개의 층으로 이루어집니다. 한 번의 하강은 정확히 $n$개의 관을 지납니다. 노드 $(r, c)$는 $r$층에서 왼쪽부터 $c$번째 노드를 뜻하며, $0 \leq c \leq r \leq n$입니다. 층과 노드 번호는 모두 0부터 시작합니다. Kolya가 노드 $(r, c)$에 있을 때 왼쪽 아래로 가면 $(r + 1, c)$에 도착하고, 오른쪽 아래로 가면 $(r + 1, c + 1)$에 도착합니다.

층이 5개인 미끄럼틀의 예시는 다음과 같습니다.

Kolya는 정확히 $n + 1$번 미끄러져 내려오려 합니다. 매번 내려오기 전에 Petya가 경로를 적은 지시문을 줍니다. 지시문은 정확히 $n$개의 명령으로 이루어지며, 각 명령은 현재 노드에서 왼쪽 아래로 갈지 오른쪽 아래로 갈지를 나타냅니다.

첫 번째 지시문은 오른쪽 아래 명령만으로 이루어집니다. Petya는 새 지시문을 만드는 것이 귀찮아서, $i + 1$번째 지시문은 $i$번째 지시문에서 $a_i$번째 명령 하나만 오른쪽 아래에서 왼쪽 아래로 바꿔서 만듭니다 ($1 \leq a_i \leq n$). 모든 명령은 정확히 한 번씩 바뀝니다. 따라서 $(n + 1)$번째 지시문은 왼쪽 아래 명령만으로 이루어집니다. 모든 노드는 적어도 한 번의 하강에서 Kolya가 방문한다는 것을 보일 수 있습니다.

돌아오는 길에 Kolya는 몇 가지 질문을 떠올렸습니다. Kolya가 한 번이라도 지난 관들의 집합을 생각해 봅시다. Kolya는 두 노드 $(r_1, c_1)$과 $(r_2, c_2)$의 좌표를 말합니다. 여러분은 그 관들을 따라 $(r_1, c_1)$과 $(r_2, c_2)$에 모두 도달할 수 있는 노드 $(r_3, c_3)$의 좌표를 찾아야 합니다. 이런 노드 중에서 가장 낮은 노드, 즉 $r_3$ 값이 최대인 노드를 찾습니다. 이런 노드는 항상 존재하며 유일하다는 것이 증명되어 있습니다.

Kolya의 모든 질문에 답하세요.

첫 번째 줄에 정수 $n$($1 \leq n \leq 500\,000$)이 주어집니다.

두 번째 줄에 정수 $a_1, a_2, \ldots, a_n$($1 \leq a_i \leq n$)이 주어집니다. 모든 $a_i$는 서로 다릅니다.

다음 줄에 정수 $q$($1 \leq q \leq 500\,000$)가 주어집니다. 이는 Kolya의 질문 수입니다.

이어지는 $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$번째 줄에는 $i$번째 질문의 답이 되는 노드의 좌표 $r_{i,3}$과 $c_{i,3}$을 공백으로 구분하여 출력합니다.

첫 번째 예시에서 Kolya의 하강은 다음과 같습니다.

(a) 1번 하강:

(b) 2번 하강:

(c) 3번 하강:

(d) 4번 하강:

첫 번째 예시에서 Kolya가 지난 모든 관에 표시하면 다음 그림이 됩니다.