这些家伙绝对是在组队。

有 $n$ 名编号从 $0$ 到 $n-1$ 的玩家正在进行一场游戏。有一个数字 $x$，初始值为 $0$。有 $n$ 个数字 $a_i$ ($0 \le a_i \le n-1$)，它们在游戏轮次之间可能会发生变化。游戏过程如下：

1. 玩家 $0$ 可以选择跳过他的回合，或者将 $x$ 变为 $(x + a_0) \pmod n$。
2. 玩家 $1$ 可以选择跳过他的回合，或者将 $x$ 变为 $(x + a_1) \pmod n$。
3. ...
4. 玩家 $n-1$ 可以选择跳过他的回合，或者将 $x$ 变为 $(x + a_{n-1}) \pmod n$。

在此过程结束后，编号为 $x$ 的玩家获胜。

每位玩家仅在以下情况下才会采取行动（即改变 $x$）：如果他采取行动后会获胜，且如果不采取行动则不会获胜。玩家们知道每个人都遵循这一策略。

你需要回答 $q$ 个询问：如果我们修改 $a_x$ 为 $y$，谁会赢得游戏？注意，每次询问后的修改不会被撤销。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示玩家数量。 第二行包含 $n$ 个整数，表示 $a_i$ 的初始值 ($0 \le a_i \le n-1$)。 第三行包含一个整数 $q$ ($0 \le q \le 10^5$)，表示询问次数。 接下来的 $q$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le n-1$)，表示从该次询问开始，$a_{x_i}$ 的值变为 $y_i$。

输出格式

输出 $q+1$ 个整数。第 $i$ 个整数表示在经过 $i-1$ 次修改后，游戏的获胜者编号。

样例

样例输入 1

2
0 0
1
1 1

样例输出 1

0
1

样例输入 2

3
2 1 2
3
2 1
1 2
2 2

样例输出 2

1
0
0
2

样例输入 3

4
0 1 1 3
2
3 2
2 2

样例输出 3

3
0
2