题目描述

一条走廊有 $n$ 个位置，编号为 $1$ 到 $n$。有 $m$ 盏灯，每盏灯照亮一个连续区间，包含区间两端。

若一个位置同时被至少 $K$ 盏灯照亮，就称它为合格位置。

所有灯安装完毕后，有 $q$ 次询问：区间 $[l,r]$ 内有多少个合格位置？所有灯在询问期间都保持不变。

输入格式

第一行四个整数 $n,m,K,q$。

接下来 $m$ 行，每行两个整数 $L,R$，表示一盏灯照亮的位置区间。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问中的合格位置数量。

8 3 2 3
1 4
3 6
5 8
1 8
2 5
7 8

4
3
0

1 1 1 1
1 1
1 1

1

样例 1 解释

各位置的照明次数为 $1,1,2,2,2,2,1,1$，合格位置是 $3,4,5,6$。三个询问的答案分别为 $4,3,0$。

样例 2 解释

唯一的位置被一盏灯照亮，达到要求。

数据范围与提示

对于所有测试点：$1\le n,m,q\le200000$，$1\le K\le m$。

所有照明区间与询问区间均满足 $1\le L\le R\le n$ 或 $1\le l\le r\le n$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$n,m,q\le30$
6—10	$n,m,q\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。