<span style="color:#6633ff;">/*

G - 二分

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu

Submit

Status

Description

Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point pi will lie in a segment A B if A ≤ pi ≤ B.

For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 108].

Each of the next q lines contains two integers Ak Bk (0 ≤ Ak ≤ Bk ≤ 108) denoting a segment.

Output

For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.

Sample Input

1

5 3

1 4 6 8 10

0 5

6 10

7 100000

Sample Output

Case 1:

2

3

2

Hint

Dataset is huge, use faster I/O methods.

By Grant Yuan

2014.7.16

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int t;

long long low,high,mid,ans;

int n,m;

int a[100005];

long long x,y;

int ct=1;

int main()

{int l,r;

    scanf("%d",&t);

    while(t--){

    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)

      {

      scanf("%d",&a[i]);

        }

         printf("Case %d:\n",ct++);

    while(m--){

         scanf("%d%d",&x,&y);

         if(x<a[0]) l=0;

         else {l=lower_bound(a,a+n,x)-a;

         }

         if(y>a[n-1]) r=n;

         else {r=upper_bound(a,a+n,y)-a;

         }

         printf("%d\n",r-l);}}

         return 0;

}

</span>