게임

이 녀석들은 확실히 짜고 있다.

번호가 0부터 $n-1$까지인 $n$명의 플레이어가 게임을 한다. 처음에 값이 0인 수 $x$가 있다. 게임의 라운드 사이에 바뀔 수 있는 수 $n$개 $a_i$ ($0 \leq i, a_i \leq n - 1$)가 있다. 게임은 다음과 같이 진행된다.

1. 0번 플레이어는 차례를 넘기거나, $x$를 $(x + a_0) \bmod n$으로 바꾼다.
2. 1번 플레이어는 차례를 넘기거나, $x$를 $(x + a_1) \bmod n$으로 바꾼다.
3. $\ldots$
4. $n-1$번 플레이어는 차례를 넘기거나, $x$를 $(x + a_{n-1}) \bmod n$으로 바꾼다.

이 과정이 끝나면 번호가 $x$인 플레이어가 이긴다.

각 플레이어는 움직이면(즉 $x$를 바꾸면) 이기고, 움직이지 않으면 이기지 못하는 경우에만 움직인다. 모든 플레이어가 이 전략에 따라 게임한다는 것을 플레이어들은 안다.

$q$개의 질의에 답해야 한다. 질의마다 $a_x$를 $y$로 바꾸면 누가 게임에서 이기는가? 변경 사항은 질의가 끝난 뒤에도 되돌리지 않는다.

입력의 첫 줄에 정수 $n$ ($1 \leq n \leq 10^5$)이 주어진다. 플레이어의 수이다.

둘째 줄에는 $a_i$의 초깃값인 정수 $n$개가 주어진다 ($0 \leq a_i \leq n - 1$).

셋째 줄에 정수 $q$ ($0 \leq q \leq 10^5$)가 주어진다. 질의의 수이다.

이어지는 $q$개의 줄에는 각각 두 정수 $x_i$, $y_i$ ($0 \leq x_i, y_i \leq n - 1$)가 주어진다. 이는 이 질의부터 $a_{x_i}$가 $y_i$가 됨을 뜻한다.

$q+1$개의 정수를 출력한다. $i$번째 정수는 질의 $i-1$개를 처리한 뒤의 게임 승자 번호이다.