Description

一条笔直的公路上有 $n$ 个旅店，第 $i$ 个旅店的坐标是 $i$，每一天早上从旅店出发走最多 $m$ 个距离，同时固定给你一个常数 $k$。

给定 $q$ 组询问，每次给定 $u,v$，求早上从旅店 $u$ 出发到旅店 $v$，途径不超过 $k$ 个旅店（不含起点 $u$）且行走方向不变的方案数。两种方案不同当且仅当存在一个不同的旅店选择，答案对 $998244353$ 取模。

对于所有数据，$n,q\leq 10^5$，$m,k\leq 10^4$，$mk\leq 10^5$，$u,v\leq n$。

Input Format

输入共 $q+1$ 行。

第一行输入 $4$ 个正整数 $n,m,k,q$。

接下来 $q$ 行，每行输入 $2$ 个正整数 $u,v$，表示一组询问。

Output Format

输出共 $q$ 行，每行输入 $1$ 个整数表示答案。

3 2 2 2
1 3
2 3

2
1

2077 30 200 3
1949 2021
1969 2077
1970 2004

360658315
804081653
603979748