Description

可怜的公主陷入困境，马里奥需要拯救他的情人。把通往城堡的道路视为一条线（长度为$n$ ），在每个整数点$i$ 上都有一块高度为$h_i$ 的砖，马里奥可以跳的最大高度是$H$ ，求他在$[L , R ]$区间可以跳过多少砖块。

Input

第$1$行是整数$T$，表示测试用例的数量。每个测试用例的第1行都包含两个整数$n、m （1≤n ，m ≤10^5 ）$，$n$ 是道路的长度，$m$ 是查询的数量。下一行包含$n$ 个整数，表示每个砖的高度（范围是$[0,10^9 ]）$。接下来的$m$ 行，每行都包含三个整数$L 、R 、H （0≤L ≤R<n ，0≤H ≤10^9 ）$。

Output

对每种情况都输出“Case X ：”（X 是从1开始的案例编号），后跟$m$ 行，每行都包含一个整数。第$i$ 个整数是第$i$ 个查询中马里奥跳过的砖块数。

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

来源

HDU4417