zoto

Problem Description

You are given an array $fx$. For each $i (1<= i <=n)$ , we use a point $(i, fx[i])$ in $XoY$ coordinate plane to described it. You are asked to answer $m$ queries, in each query there will be a rectangle and you need to count how many different y-cooordinate (of the points mentioned above) in the queried rectangle.

Input

The first line contains an integer $T (1<= T <=5)$ representing the number of test cases. For each test case , there are two integers $n,m(1<=n<=100000,1<=m<=100000)$ in the first line. Then one line contains n integers $fx[i] (0<=fx[i]<=100000)$ Each of the next m lines contain four integers $x_0,y_0,x_1,y_1(1<=x_0<=x_1<=n,0<=y_0<=y_1<=100000)$ which means matrix's lower-leftmost cell is $(x0,y0)$ and upper-rightest cell is $(x1,y1)$.

Output

For each test case print a single integer in a new line.

Sample Input

1

4 2

1 0 3 1

1 0 4 3

1 0 4 2

Sample Output

3

2

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）