F. Binary Not Search and Queries
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For a sequence $$$b$$$ consisting of $$$m$$$ integers, the set $$$S(b)$$$ is defined as the set of tuples $$$(i,j,k)$$$ that satisfy the following conditions:

  • $$$i$$$, $$$j$$$, $$$k$$$ are integers;
  • $$$1 \le k \lt m$$$;
  • $$$1 \le i \lt j \le m-k+1$$$;
  • For every element $$$v$$$ in $$$b$$$, $$$v$$$ appears the same number of times in $$$[b_i,b_{i+1},\ldots,b_{i+k-1}]$$$ and $$$[b_j,b_{j+1},\ldots,b_{j+k-1}]$$$.

For example, when $$$b=[1,2,1,2]$$$, the tuple $$$(1,3,2)$$$ is an element of $$$S(b)$$$ because $$$1$$$ and $$$2$$$ both appear once in $$$[b_1,b_2]$$$ and $$$[b_3,b_4]$$$.

Additionally, we define two functions over sequences of positive integers:

  • $$$k_\max(b)$$$ is defined as the maximum value of $$$k$$$ over all elements $$$(i,j,k)$$$ of $$$S(b)$$$;
  • $$$f(b)$$$ is defined as the number of different elements $$$(i,j,k)$$$ of $$$S(b)$$$ such that $$$k=k_\max(b)$$$.

Exceptionally, when the set $$$S(b)$$$ is empty, they are defined as $$$k_\max(b)=0$$$ and $$$f(b)=0$$$.

You are given a sequence $$$a$$$ of $$$n$$$ integers. Please answer $$$q$$$ queries of the following kind:

  • $$$i\;x$$$: Change the value of $$$a_i$$$ to $$$x$$$. Then, find the values of $$$k_\max(a)$$$ and $$$f(a)$$$.

Do note that the updates are persistent. In other words, the update from one query affects the later queries as well.

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 integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 100\,000$$$).

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

Each of the following $$$q$$$ lines contains two integers $$$i_j$$$ and $$$x_j$$$ denoting the $$$j$$$-th query ($$$1 \le i_j,x_j \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$100\,000$$$.

Output

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

On the $$$j$$$-th line, you must output the values of $$$k_\max(a)$$$ and $$$f(a)$$$ for the $$$j$$$-th query.

It can be shown that both values will never exceed $$$10^{11}$$$ under the constraints of this problem.

Example
Input
4
5 3
1 2 3 4 5
3 2
4 1
5 2
4 3
1 2 1 1
4 2
3 2
2 1
5 2
1 3 2 4 5
5 3
5 5
8 3
1 2 3 4 1 2 5 4
7 3
7 4
2 1
Output
1 1
3 1
3 3
2 3
2 1
1 2
3 1
0 0
4 10
4 4
4 2
Note

Immediately after the first query of the second test case, $$$a=[1,2,1,2]$$$. The elements of the set $$$S(a)$$$ are as follows:

  • $$$(1,3,1)$$$: $$$[\color{red}{1},2,\color{blue}{1},2]$$$;
  • $$$(2,4,1)$$$: $$$[1,\color{red}{2},1,\color{blue}{2}]$$$;
  • $$$(1,2,2)$$$: $$$[\color{red}{1},\color{magenta}{2},\color{blue}{1},2]$$$;
  • $$$(1,3,2)$$$: $$$[\color{red}{1},\color{red}{2},\color{blue}{1},\color{blue}{2}]$$$;
  • $$$(2,3,2)$$$: $$$[1,\color{red}{2},\color{magenta}{1},\color{blue}{2}]$$$.

Therefore, $$$k_\max(a)=2$$$, and $$$f(a)=3$$$ because there are three elements $$$(i,j,k)$$$ where $$$k=k_\max(a)=2$$$.

Immediately after the second query of the third test case, $$$a=[1,3,2,4,5]$$$. The set $$$S(a)$$$ is empty at this point.

By definition, you should output $$$k_\max(a)=0$$$ and $$$f(a)=0$$$ because $$$S(a)$$$ is currently empty.