Specijacija

양의 정수 $n$과 양의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어진다. 각 $i$에 대해 $\frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2}$를 만족한다.

이 수열은 정점이 $\frac{(n+1)(n+2)}{2}$개인 트리를 정한다. 트리는 $n+1$개의 층으로 이루어지며, 층마다 정점이 $1, 2, \dots, n+1$개 있다.

$a = (1, 2, 6)$으로 정해지는 트리다.

$i$번째 층에는 번호가 $\frac{i(i-1)}{2} + 1$부터 $\frac{i(i+1)}{2}$까지인 정점이 있다. 정점 $a_i$는 자식을 두 개 가지고, 같은 층의 나머지 정점은 자식을 하나씩 가진다.

$q$개의 질의에 답해야 한다. 각 질의는 두 정점 $x$와 $y$의 가장 큰 공통 조상, 즉 두 정점의 조상이면서 번호가 가장 큰 정점을 구한다.

첫 줄에 정수 $n$, $q$, $t$가 주어진다 ($1 \le n, q \le 200\,000$, $t \in \{0, 1\}$). 각각 매개변수의 개수, 질의의 개수, 질의 번호를 계산하는 데 쓰는 값이다.

둘째 줄에는 트리를 정하는 정수 $n$개 $a_i$가 주어진다 ($\frac{i(i-1)}{2} \le a_i \le \frac{i(i+1)}{2}$).

이어지는 $q$개 줄에는 정수 $\tilde{x}_i$와 $\tilde{y}_i$가 주어진다 ($1 \le \tilde{x}_i, \tilde{y}_i \le \frac{(n+1)(n+2)}{2}$). 질의의 실제 정점은 다음과 같이 계산한다.

$x_i = \left(\left(\tilde{x}_i - 1 + t \cdot z_{i-1}\right) \bmod \frac{(n+1)(n+2)}{2}\right) + 1$

$y_i = \left(\left(\tilde{y}_i - 1 + t \cdot z_{i-1}\right) \bmod \frac{(n+1)(n+2)}{2}\right) + 1$

여기서 $z_i$는 $i$번째 질의의 답이며, $z_0 = 0$이다. mod는 나눗셈의 나머지를 뜻한다.

$t = 0$이면 $x_i = \tilde{x}_i$, $y_i = \tilde{y}_i$이므로 모든 질의를 입력만으로 알 수 있다. $t = 1$이면 각 질의가 이전 질의의 답에 따라 정해지므로 미리 알 수 없다.

$q$개 줄을 출력한다. $i$번째 줄에는 $x_i$와 $y_i$의 가장 큰 공통 조상을 출력한다.

그림은 $a = (1, 2, 6)$으로 정해지는 트리를 나타낸다.