题目描述

在 \([0,n]\) 中给出区间集合 \(A\) 和 \(B\)，分别包含 \(x\) 个区间和 \(y\) 个区间，求出它们长度为 \(m\) 的公共子区间个数。注意，这里符合条件的公共子区间有 \(m\) 个点（包含起点和终点），其长度实际上是 \(m-1\)，且允许重叠，具体参看样例。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；每组数据中，第一行为正整数 \(n,m,x,y\)；接下来 \(x\) 行，每行两个正整数 \(s_i,e_i\)，表示 \(x\) 个子区间的起点和终点；接下来 \(y\) 行，每行两个正整数 \(s_j,e_j\) 表示 \(y\) 个子区间的起点和终点。其中，\(m≤n≤1000000000,x,y≤10000,s_i≤e_i≤n,s_j≤e_j≤n\)。数据保证 \(x\) 个子区间互相不交叉，\(y\) 个子区间互相不交叉。

输出格式

对于每组数据，输出符合条件的公共子区间个数。

样例1

样例输入1

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

样例输出1

3
0

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T5\)