E. Innocent Students
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a class, a test has happened and $$$n$$$ students participated in it. In this test, there is only one question and the answer to the question is an integer $$$x$$$. All the students gave their answers as integers, i.e., $$$a_i$$$ is the answer of the $$$i$$$-th$$$(1 \le i \le n)$$$ student. Student $$$i$$$ will pass the exam if |$$$x-a_i$$$| is the minimum possible among all the students who attended the exam.

Now your task is to answer $$$q$$$ queries of two types :

  1. 1 l r x : How many students will pass the exam if students $$$l, l+1, ... , r-1, r$$$ attended the exam and the answer to the question is $$$x$$$;
  2. 2 i val : Student at the $$$i$$$-th position changes his answer to $$$val$$$.
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 2 \cdot 10^5$$$) — the number of students and the number of queries.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$-10^9 \le a_{i} \le 10^9$$$) — the answer from the $$$i$$$-th student.

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

  1. 1 l r x $$$(1 \le l \le r \le n)$$$ and $$$(-10^9 \le x \le 10^9)$$$;
  2. 2 i val $$$(1 \le i \le n)$$$ and $$$(-10^9 \le val \le 10^9)$$$.

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

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

Output

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

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