U456182 小明选武器

## 小明要准备去战斗了。

小明选好了子弹，接下来该选武器了。但小明有选择困难症，而且他有整整 $n$ 把枪，所以他想听听别人的意见。 一共有 $m$ 个人向他提意见，每个人认为从第 $l_i$ 到第 $r_i$ 把枪好用。 小明认为一把枪至少有 $k$ 个人认为它好用的，那么这把枪就是好用的。 同样是萌新的小方有 $q$ 个问题，第 $i$ 个问题为第 $a$ 把枪到第 $b$ 把枪有几把枪好用。 小明有点想不起来调查结果了，你能帮帮他吗？

第一行输入四个整数 $n,m,k,q$。 之后 $m$ 行，每行输入两个整数 $l_i,r_i$。 之后 $q$ 行，每行输入两个整数 $a,b$。

输出共q行，每行一个答案。

小明认为的好枪有 $1,2,5,6,8,9$ 号。 对于 $30\%$ 的数据，$1\le n,m,q\le 100$。 对于 $60\%$ 的数据，$1\le n,m,q\le2000$。 对于 $100\%$ 的数据，$1\le n,m,q\le10^5,1\le k\le m$。 ### 保证有一组数据输出都是0。