26408번 - Game 다국어

Those guys are definitely teaming.

$n$ players numbered from 0 to $n-1$ are playing a game. There is a number $x$, which is initially equal to 0. There are $n$ numbers $a_i$ ($0 \leq i, a_i \leq n - 1$) that are subject to change between the rounds of the game. The game proceeds as follows:

1. Player 0 either skips his turn or makes $x$ equal to $(x + a_0) \bmod n$.
2. Player 1 either skips his turn or makes $x$ equal to $(x + a_1) \bmod n$.
3. $\ldots$
4. Player $n - 1$ either skips his turn or makes $x$ equal to $(x + a_{n-1}) \bmod n$.

After this process, the player with the number $x$ wins.

Each player makes a move (that is, changes $x$) if and only if he will win if he makes a move, but won't win if he doesn't. Players know that everyone plays according to this strategy.

You have to answer $q$ queries: if we change $a_x$ to $y$ who will win the game? Note that the changes are not reverted after each query.

The first line of input contains a single integer $n$ ($1 \leq n \leq 10^5$) --- the number of players.

The second line contains $n$ integers --- initial values of $a_i$ ($0 \leq a_i \leq n - 1$).

The third line contains a single integer $q$ ($0 \leq q \leq 10^5$) --- the number of queries.

$q$ lines follow. $i$-th of them contains two integers $x_i$ and $y_i$ ($0 \leq x_i, y_i \leq n - 1$) meaning that $a_{x_i}$ is equal to $y_i$ from this query onwards.

Output $q+1$ integers. $i$-th them should be the number of the winner of the game after $i-1$ queries.