D. Animal Circus
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are the manager of the animal circus show. You have $$$N$$$ types of animals in your storage; you have $$$a_i$$$ animals of $$$i^{th}$$$ type. You have to group the animals into a cage such that each cage has exactly $$$k$$$ animals, and for some reason, having the same type of animal in one cage is kind of boring for the visitors, so you should never put the same type of animal in the same cage. The problem is that the animal circus show lasts for $$$Q$$$ days, and on the $$$i^{th}$$$ day, the animal of type $$$x_i$$$ got changed by $$$y_i$$$ (if $$$y_i$$$ is positive, the number of animals of type $$$x_i$$$ increases by $$$y_i$$$, otherwise, the number of animals of type $$$x_i$$$ decreases by $$$-y_i$$$)

Your job is to find the maximum number of cages you can bring to the show each day.

In this problem, the last answer will affect the next question by equation $$$ x_{new} = (answer \oplus x_{i}) \%\ N + 1 $$$ where $$$x_{new}$$$ is the $$$x$$$ of the next question, $$$answer$$$ is the latest output, and $$$x_i$$$ is the new input.

where $$$\oplus$$$ representing Bitwise XOR

and $$$\%$$$ representing Modulo

Input

The first line contains an integer $$$N$$$ and $$$k\ (1 \leq k \leq N \leq 10^5)$$$ — the number of types of animals and the number of animals required in one cage.

The second line contains $$$N$$$ integers $$$a_1, a_2, …, a_N\ (0 \leq a_1, a_2, …, a_N \leq 10^9)$$$ — the number of animals for each type.

The third line contains an integer $$$Q\ (1 \leq Q \leq 10^5)$$$ — the number of days in a circus show.

The $$$(3 + i)^{th}$$$ line $$$(1 \leq i \leq Q)$$$ contains an integer $$$x_i\ (1 \leq x_i \leq N)$$$ and $$$y_i\ (-10^9 \leq y_i \leq 10^9)$$$ — the animal type and number of animals that got changed in $$$i^{th}$$$ day.

The $$$x_i\ (1 \leq i \leq Q)$$$ has to pass the equation: $$$ x_{new} = (answer \oplus x_{i}) \%\ N + 1 $$$ where $$$x_{new}$$$ is the $$$x_i$$$ of the next question, $$$answer$$$ is the latest output. Initially, $$$answer$$$ is set as zero.

You can assume that you will never have a negative number of animals (i.e., the number of animals of each type will never go negative).

Output

The output should have $$$Q$$$ line. The $$$i^{th}$$$ line contains the maximum number of cages you can bring to the show on the $$$i^{th}$$$ day.

Example
Input
4 3
3 1 1 1
2
2 1
4 2
Output
2
2
Note

Bitwise XOR

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$1$$$ if only one of the bits is $$$1$$$, but will be $$$0$$$ if both are $$$0$$$ or both are $$$1$$$. In this we perform the comparison of two bits, being $$$1$$$ if the two bits are different, and $$$0$$$ if they are the same. For example:

         $$$0101$$$ (decimal $$$5$$$)

XOR $$$0011$$$ (decimal $$$3$$$)

$$$=$$$      $$$0110$$$ (decimal $$$6$$$))