题目描述

一轮正在玩小钢珠，规则如下：

在一个以左下角为原点 $（0，0）$ ， $n$ 行 $m$ 列的竖着的屏幕上，小钢珠会随机的从点$（i，n）$处垂直往下掉落$（1 \le i \le m-1）$。

某些行上的某些位置有小柱子，当小钢珠撞到小柱子之后会随机的往左一格或者往右一格继续垂直往下掉落。

例如小钢珠在$（ 4 ， 4 ）$撞到了小柱子，则可能到$（ 5 ， 3 ）$或者$（ 3 ， 3 ）$之后继续垂直往下落，如果是在屏幕边界$（ 1 和 m-1）$则只会往远离屏幕边界的方向掉落。（具体的看样例解释）

一轮想知道：对于每个询问区间$[ l ， r ]$，所有从顶部入口放下小钢珠，最终落到底部第 $0$ 行的区间 $[ l ， r ]$内的可能路径数（考虑所有可能的随机结果）。

由于答案可能很大，输出答案对 $998244353$ 取模的结果。

输入格式

第一行包括四个整数 $n，m，k，p$ ，分别表示行高，列宽，小柱子的个数和一轮查询区间的询问个数。

接下来k行，每行两个整数 $x，y$，表示小柱子的位置$（x，y）$。（保证每个小柱子的位置互不相同）

接下来p行，每行两个整数 $l，r$，表示一轮询问的区间范围$[ l ， r ]$。

输出格式

共p行，每行一个整数，表示此次查询可能路径数。

6 5 3 2
1 4
2 4
3 3
1 4
3 3

7
0

解释 #1

数据范围

$2 \le n \le 10^9 ，3 \le m \le 10^5，1 \le k，p \le 10^5。$

$1 \le x \le m-1 ，1 \le y \le n-1。$

$1 \le l \le r \le m-1。$