D. The Disastrous Mex Problem for Saiki K
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kusuo had been trapped inside a cage by Kusuke. To free himself, he needs to solve Kusuke's problem and to do it, he requires your help—

…wait, never mind. He already freed himself. Looks like he didn't need your help after all. Anyway, here's the problem if you still want to give it a try.

Let $$$n$$$ be an even integer. You are given a permutation $$$ p = [p_1, p_2, \dots, p_n] $$$ of the integers from $$$0$$$ to $$$n-1$$$.

Define an $$$n \times n$$$ matrix $$$a = [a_{i,j}]$$$ as $$$$$$ a_{i,j} = \begin{cases} \mathrm{mex}(p[i..j]), & i \le j, \\ a_{j,i}, & i \gt j, \end{cases} $$$$$$ — where $$$\mathrm{mex}(p[i..j])$$$$$$^{\text{∗}}$$$ is the minimum excluded element of the subarray $$$[p_i, p_{i+1}, \dots, p_j]$$$.

The score of the permutation $$$p$$$ is defined as $$$ f(p) = \det(a) $$$ (the determinant of $$$a$$$)$$$^{\text{†}}$$$.

To make the problem harder, Kusuke added $$$q$$$ queries. In each query, two indices $$$x$$$ and $$$y$$$ are given, and you swap $$$p_x$$$ and $$$p_y$$$.

The queries are persistent, meaning each swap permanently modifies the permutation and affects all subsequent queries.

After each query, output the score of the current permutation.

$$$^{\text{∗}}$$$$$$\mathrm{mex}$$$ (minimum excluded value) of a set of integers is the smallest non-negative integer that does not appear in the set.

$$$^{\text{†}}$$$The determinant is a value associated with a square matrix.

Input

The first line contains a single integer $$$t$$$ — the number of test cases $$$(1 \le t \le 10^4)$$$.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(4 \le n \le 10^6,\; 1 \le q \le 10^6,\; n \text{ is even})$$$ — the size of the permutation and the number of queries.

The second line contains $$$n$$$ integers $$$ p_1, p_2, \dots, p_n $$$ — a permutation of the integers from $$$1$$$ to $$$n$$$.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ $$$(1 \le x, y \le n)$$$ — the indices whose values should be swapped.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output $$$q$$$ lines.

After each query, print a single integer — the score of the current permutation.

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

Initially, $$$ p = [1,0,2,3]. $$$

Query 1: swap $$$p_1$$$ and $$$p_4$$$.

The permutation becomes $$$ p = [3,0,2,1]. $$$

The matrix $$$a$$$ becomes $$$$$$ a = \begin{bmatrix} 0 & 1 & 1 & 4 \\ 1 & 1 & 1 & 3 \\ 1 & 1 & 0 & 0 \\ 4 & 3 & 0 & 0 \end{bmatrix}. $$$$$$

The determinant of $$$a$$$ is $$$ \det(a)=1. $$$

Query 2: swap $$$p_1$$$ and $$$p_2$$$.

The permutation becomes $$$ p = [0,3,2,1]. $$$

The matrix $$$a$$$ becomes $$$$$$ a = \begin{bmatrix} 1 & 1 & 1 & 4 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 \end{bmatrix}. $$$$$$

The determinant of $$$a$$$ is $$$ \det(a)=0. $$$