Points In Segments

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Team        : BRACU Byteheads
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define Size 150005

struct vert{
    int sum;
    int prop;
    int child;
};
vert tree[Size*4];

void build_tree(int cur,int Start,int End){
    if(Start == End){
        tree[cur].sum = 0;
        tree[cur].prop = 0;
        tree[cur].child = 1;
        return;
    }
    int left = cur*2;
    int right = left+1;
    int mid = (Start+End)/2;
    build_tree(left,Start,mid);
    build_tree(right,mid+1,End);
    tree[cur].sum = 0;
    tree[cur].prop = 0;
    tree[cur].child = tree[left].child + tree[right].child;
}

void update_child(int cur,int left,int right){
    tree[left].sum += tree[left].child*tree[cur].prop;
    tree[left].prop += tree[cur].prop;
    tree[right].sum += tree[right].child*tree[cur].prop;
    tree[right].prop += tree[cur].prop;
    tree[cur].prop = 0;
}

void update_tree(int cur,int Start,int End,int u,int v,int value){
    if(End < u || Start > v) return;
    if(Start >= u && End <= v){
        tree[cur].sum += tree[cur].child*value;
        tree[cur].prop += value;
        return;
    }
    int left = cur*2;
    int right = left+1;
    int mid = (Start+End)/2;

    if(tree[cur].prop != 0){
        update_child(cur,left,right);
    }

    update_tree(left,Start,mid,u,v,value);
    update_tree(right,mid+1,End,u,v,value);
}

int tree_query(int cur,int Start,int End,int u,int v){
    if(End < u || Start > v){
        return 0;
    }
    if(Start >= u && End <= v){
        return tree[cur].sum;
    }
    int left = cur*2;
    int right = left+1;
    int mid = (Start+End)/2;

    if(tree[cur].prop != 0){
        update_child(cur,left,right);
    }

    int s1 = tree_query(left,Start,mid,u,v);
    int s2 = tree_query(right,mid+1,End,u,v);
    return (s1+s2);
}

int S[Size];
int T[Size];
int Q[Size];
vector<int> Values;
map<int,int> Map;
int Range,qry,u,v,val,N;

void data_compress(){
    sort(Values.begin(),Values.end());
    Map.clear();
    int SS = (int)Values.size(),id = 0;
    for(int i = 0;i<SS;i++){
        Map[Values[i]] = ++id;
    }
    for(int i = 0;i<Range;i++){
        S[i] = Map[S[i]];
        T[i] = Map[T[i]];
    }
    for(int i = 0;i<qry;i++){
        Q[i] = Map[Q[i]];
    }
    N = id;
    /*
    for(int i = 0;i<SS;i++){
        printf("Map %d = %d\n",Values[i],Map[Values[i]]);
    }
    */
}

int main() {
    int nCase;
    scanf("%d",&nCase);
    for(int cs = 1;cs<= nCase;cs++){
        scanf("%d %d",&Range,&qry);
        Map.clear();
        Values.clear();
        for(int i = 0;i<Range;i++){
            scanf("%d %d",&S[i],&T[i]);
            if(Map[S[i]] == 0) Values.push_back(S[i]);
            Map[S[i]] = 1;
            if(Map[T[i]] == 0) Values.push_back(T[i]);
            Map[T[i]] = 1;
        }
        for(int i = 0;i<qry;i++){
            scanf("%d",&Q[i]);
            if(Map[Q[i]] == 0) Values.push_back(Q[i]);
            Map[Q[i]] = 1;
        }
        data_compress();
        build_tree(1,1,N);
        printf("Case %d:\n",cs);
        for(int i = 0;i<Range;i++){
            //printf("Range: %d - %d\n",S[i],T[i]);
            update_tree(1,1,N,S[i],T[i],1);
        }
        for(int i = 0;i<qry;i++){
            //printf("Range: %d\n",Q[i]);
            int sum = tree_query(1,1,N,Q[i],Q[i]);
            printf("%d\n",sum);
        }
    }
    return 0;
}