F. MEX OR Mania
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

An integer sequence $$$b_1, b_2, \ldots, b_n$$$ is good if $$$\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$$$. Here, $$$\operatorname{mex(c)}$$$ denotes the MEX$$$^{\text{∗}}$$$ of the collection $$$c$$$, and $$$|$$$ is the bitwise OR operator.

Shohag has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He will perform the following $$$q$$$ updates on $$$a$$$:

  • $$$i$$$ $$$x$$$ — increase $$$a_i$$$ by $$$x$$$.

After each update, help him find the length of the longest good subarray$$$^{\text{†}}$$$ of $$$a$$$.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$y$$$ which does not occur in the collection $$$c$$$.

$$$^{\text{†}}$$$An array $$$d$$$ is a subarray of an array $$$f$$$ if $$$d$$$ can be obtained from $$$f$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

The next $$$q$$$ lines of each test case are of the following form:

  • $$$i$$$ $$$x$$$ ($$$1 \le i, x \le n$$$) — it means you should increase $$$a_i$$$ by $$$x$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$ and the sum of $$$q$$$ doesn't exceed $$$10^5$$$.

Output

For each test case, output $$$q$$$ lines — on the $$$i$$$-th line output the length of the longest good subarray of $$$a$$$ after the $$$i$$$-th update.

Example
Input
2
6 3
0 0 1 0 1 0
6 1
3 2
6 3
3 1
1 3 1
1 1
Output
6
3
2
0
Note

In the first test case, after the first update, the array becomes $$$[0, 0, 1, 0, 1, 1]$$$, and here the whole array is good because $$$\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1$$$.

After the second update, the array becomes $$$[0, 0, 3, 0, 1, 1]$$$, and here the subarray $$$[0, 1, 1]$$$ has the maximum length among all the good subarrays.

Finally, after the third update, the array becomes $$$[0, 0, 3, 0, 1, 4]$$$, and here the subarrays $$$[0, 0]$$$ and $$$[0, 1]$$$ both have the maximum length among all the good subarrays.