Boring Counting

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

    In this problem you are given a number sequence P consisting of N integer and Pi is the ith element in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Pi is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of Pi (L <= i <= R,  A <= Pi <= B).

Input

     In the first line there is an integer T (1 < T <= 50), indicates the number of test cases. 
     For each case, the first line contains two numbers N and M (1 <= N, M <= 50000), the size of sequence P, the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9), the number sequence P. Then there are M lines, each line contains four number L, R, A, B(1 <= L, R <= n, 1 <= A, B <= 10^9)

Output

    For each case, at first output a line ‘Case #c:’, c is the case number start from 1. Then for each query output a line contains the answer.

Sample Input

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

Sample Output

Case #1:
13
7
3
6
9

Hint

 

Source

2013年山东省第四届ACM大学生程序设计竞赛