Background

In the 21st century, which is called the future, only unease and a little fantasy remain.

O sinners of eternity and instant, the Noah's Ark of the 20th century carries expectations and unease and flies toward the sky!

And you, as hope, on this journey that is not eternal, how will you move forward?

Problem 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