Problem Description

ACM (ACMers' Chatting Messenger) is a famous instant messaging software developed by Marjar Technology Company. To attract more users, Edward, the boss of Marjar Company, has recently added a new feature to the software. The new feature can be described as follows:

If two users, $A$ and $B$, have been sending messages to each other on the last m consecutive days, the "friendship point" between them will be increased by $1$ point.

More formally, if user A sent messages to user B on each day between the $(i - m + 1)$-th day and the $i$-th day (both inclusive), and user $B$ also sent messages to user $A$ on each day between the $(i - m + 1)$-th day and the $i$-th day (also both inclusive), the "friendship point" between $A$ and $B$ will be increased by $1$ at the end of the i-th day.

Given the chatting logs of two users $A$ and $B$ during $n$ consecutive days, what's the number of the friendship points between them at the end of the $n$-th day (given that the initial friendship point between them is $0$)?

Input

There are multiple test cases. The first line of input contains an integer $T$ $(1 ≤ T ≤ 10)$, indicating the number of test cases. For each test case:

The first line contains $4$ integers $n$ $(1 ≤ n ≤ 10^9)$, $m$ $(1 ≤ m ≤ n)$,$x$ and $y$ $(1 ≤ x, y ≤ 100)$. The meanings of $n$ and $m$ are described above, while $x$ indicates the number of chatting logs about the messages sent by $A$ to $B$, and $y$ indicates the number of chatting logs about the messages sent by $B$ to $A$.

For the following $x$ lines, the $i$-th line contains $2$ integers $l_{a, i}$ and $r_{a, i} (1 ≤ l_{a, i} ≤ r_{a, i} ≤ n)$, indicating that $A$ sent messages to $B$ on each day between the $l_{a, i}$-th day and the $r_{a, i}$-th day (both inclusive).

For the following $y$ lines, the $i$-th line contains $2$ integers $l_{b, i}$ and $r_{b, i} (1 ≤ l_{b, i} ≤ r_{b, i} ≤ n)$, indicating that $B$ sent messages to $A$ on each day between the $l_{b, i}$-th day and the $r_{b, i}$-th day (both inclusive).

It is guaranteed that for all $1 ≤ i < x$, $r_{a, i} + 1 < l_{a, i+1} $ and for all $1 ≤ i < y, r_{b, i} + 1 < l_{b, i + 1}$.

Output

For each test case, output one line containing one integer, indicating the number of friendship points between $A$ and $B$ at the end of the $n$-th day.

Sample Input

2
10 3 3 2
1 3
5 8
10 10
1 8
10 10
5 3 1 1
1 2
4 5

Sample Output

3
0

Hint

For the first test case, user $A$ and user $B$ send messages to each other on the $1st$, $2nd$, $3rd$, $5th$, $6th$, $7th$, $8th$ and $10th$ day. As $m = 3$, the friendship points between them will be increased by $1$ at the end of the $3rd$, $7th$ and $8th$ day. So the answer is $3$.

Problem Link

vjudge_ZOJ-3961-Let's Chat

Thoughts

一个求交集的问题，把区间表示出来就好

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX 100+10
typedef long long  LL;
struct cbc
{
    LL l,r;
}AtoB[MAX],BtoA[MAX];
LL max(LL a,LL b)
{
    return a>b ? a:b; 
}
LL min (LL a,LL b)
{
    return a<b? a:b; 
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL N;
        int m,x,y;
        int friendshippoint=0;
        scanf("%lld%d%d%d",&N,&m,&x,&y);
        int i;
        for(i=0;i<x;i++)
            scanf("%lld%lld",&AtoB[i].l,&AtoB[i].r);
        for(i=0;i<y;i++)
            scanf("%lld%lld",&BtoA[i].l,&BtoA[i].r);
        for(i=0;i<x;i++)
        {
            int i1;
            for(i1=0;i1<y;i1++)
            {
                int l,r;
                l=max(AtoB[i].l,BtoA[i1].l);
                r=min(AtoB[i].r,BtoA[i1].r);
                if(l>r || r-l+1<m)
                    continue;
                else
                    friendshippoint+=r-l+1-m+1;
            }
        }
        printf("%d\n",friendshippoint);
    }
 
    return 0;
}