Little G and Little H were originally planning to go out for a meal, but since it was too complicated, the problem is simplified as follows:

There are $n$ items arranged in a circle on a turntable (numbered 1 to $n$), where the $i$-th item appears at time $T_i$.

At time 0, Little G can choose any one of the $n$ items, let its number be $s_0$. If at time $i$ the item $s_i$ is chosen, then at time $i+1$, one can continue to choose the current item or choose the next item. When $s_i$ is $n$, the next item is item 1; otherwise, the next item is $s_i + 1$. At any time (including time 0), if the item chosen by Little G has already appeared, Little G will mark it. Little H wants to know, under the optimal strategy for choosing items, when can Little G mark all items?

The trouble is that the appearance times of the items are modified from time to time. We describe this as $m$ modifications, where each modification changes the appearance time of one item. After each modification, you also need to find the answer for the current situation. For some test cases, Little H has also added a requirement for online processing.

Input

The first line contains three non-negative integers $n$, $m$, and $p$, representing a total of $n$ items and $m$ modifications. $p$ can only be 0 or 1. When $p=1$, it is forced online; otherwise, $p=0$. This section will explain how to use $p$ later.

The next line contains $n$ space-separated non-negative integers, where the $i$-th number $T_i$ represents the appearance time of item $i$.

The next $m$ lines each contain two non-negative integers $x$ and $y$, representing a modification and a query. The modification method is as follows:

(1) If $p=0$, it means the appearance time $T_x$ of item $x$ is modified to $y$.

(2) If $p=1$, first obtain $x'$ and $y'$ by XORing $x$ and $y$ with $LastAns$: $x' = x \oplus LastAns$, $y' = y \oplus LastAns$. Then, modify the appearance time $T_{x'}$ of item $x'$ to $y'$. Here, $LastAns$ is the answer to the previous query; specifically, for the first modification, $LastAns$ is the answer for the initial situation. $\oplus$ denotes the bitwise XOR operation; for example, $1 \oplus 2 = 3$, $4 \oplus 5 = 1$, $6 \oplus 11 = 13$.

The input is guaranteed to be valid.

Output

The first line contains an integer representing the answer for the initial situation.

The next $m+1$ lines each contain an integer representing the answer after each modification.

Examples

Input 1

5 3 0
1 2 3 4 5
3 5
5 0
1 4

Output 1

5
7
6
7

Note

The first query is: for 5 items with appearance times 1, 2, 3, 4, 5, when is the earliest time to mark all items? One optimal strategy is: choose item 1 at time 0 and 1, and choose the next item at times 2~5. At time 0, the chosen item 1 has not appeared yet, so it cannot be marked.

The third query is: for 5 items with appearance times 1, 2, 5, 4, 0, when is the earliest time to mark all items? One optimal strategy is: choose items 4, 5, 1, 2, 3, 3, 4 at times 0 to 6 respectively. At time 0 and time 4, the chosen items have not appeared yet; at other times, the chosen items can be marked.

Constraints

For all data, it is guaranteed that $3 \le n \le 10^5$, $0 \le m \le 10^5$, $0 \le T_i/T_x \le 10^5$.