Description

On a straight road, there are $n$ hotels. The coordinate of the $i$-th hotel is $i$. Every morning, you start from a hotel and can walk a maximum distance of $m$. You are also given a fixed constant $k$.

You are given $q$ queries. In each query, given $u, v$, find the number of plans to start in the morning from hotel $u$ to hotel $v$, passing through at most $k$ hotels (excluding the start point $u$) and keeping the walking direction unchanged. Two plans are different if and only if there exists a different choice of a hotel. The answer should be taken modulo $998244353$.

For all testdata, $n, q \leq 10^5$, $m, k \leq 10^4$, $mk \leq 10^5$, and $u, v \leq n$.

Input Format

The input has $q + 1$ lines.

The first line contains $4$ positive integers $n, m, k, q$.

The next $q$ lines each contain $2$ positive integers $u, v$, representing a query.

Output Format

Output $q$ lines, each containing $1$ integer, representing the answer.

3 2 2 2
1 3
2 3

2
1

2077 30 200 3
1949 2021
1969 2077
1970 2004

360658315
804081653
603979748

Hint

Translated by ChatGPT 5