D. Perfect Prefix
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An integer array $$$b$$$ containing $$$m$$$ elements is called perfect-prefix array, if it satisfies the following condition :

  • For every $$$i(1 \le i \le m)$$$, $$$\sum_{j = 1}^i b_j \gt 0$$$.

You can do the following operation on $$$b$$$ any number of times (possibly zero) :

  • Choose $$$i,j(1 \le i \le j \le m)$$$ and swap $$$a_i$$$ and $$$a_j$$$.

Let $$$f(b)$$$ be the minimum number of operations required to turn $$$b$$$ into perfect-prefix array. If it is not possible to turn $$$b$$$ into perfect-prefix array then $$$f(b) = -1$$$.

You are given an integer array $$$a$$$ containing $$$n$$$ elements where each element is either $$$1$$$ or $$$-1$$$.

Now your task is to answer $$$q$$$ queries of following type :

  • 1 l r : Find the value of $$$f(a[l \cdots r])$$$.
  • 2 x : Multiply $$$a_x$$$ with $$$-1$$$.
Input

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

The first line of each test case contains two integers $$$n,q$$$ ($$$1 \le n,q \le 5 \cdot 10^5$$$) — the size of the array and the number of queries.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$-1 \le a_{i} \le 1$$$ , $$$a_i ≠ 0$$$).

The next $$$q$$$ lines contain one of the two forms:

  • 1 l r $$$(1 \le l \le r \le n)$$$ ;
  • 2 x $$$(1 \le x \le n)$$$.

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

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

Output

For each test case, print the required answer for the $$$1$$$-st type query.

Example
Input
2
5 5
1 1 -1 1 -1
1 1 4
1 2 4
2 3
1 1 4
1 4 5
11 6
1 1 1 1 -1 -1 -1 1 1 -1 -1
1 7 9
1 1 11
2 5
2 6
1 1 7
1 7 10
Output
0
1
0
-1
1
0
0
-1