Description

http://acm.hdu.edu.cn/showproblem.php?pid=4417

给定一个长度为n的区间，同时给出m个询问，每次询问在区间[l,r]中有多少个数小于或等于k

Format

Input

The first line follows an integer T, the number of test data. For each test data:

The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.

Next line contains n integers, the height of each brick, the range is [0, 1000000000].

Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.

Samples

1
10 10
0 5 2 7 5 4 3 8 7 7 
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

Case 1:
4
0
0
3
1
2
0
1
5
1