Inns on the Road

You are given a straight road with n inns. The i-th inn is located at coordinate i on the road. Every morning, from whichever inn you are at, you may walk in one direction (i.e. without reversing direction) at most a distance of m (in units), and you are also given a constant k.

For each query, you are given two integers u and v. You have to count the number of distinct ways to travel from inn u to inn v in the morning such that you visit at most k inns (excluding the starting inn u) and the walking direction remains unchanged.

In each move, if you are moving in the increasing direction (which will be the case if u<v) then you may jump from your current inn at position i to any inn at position j where

and similarly if you are moving in the decreasing direction (i.e. when u > v), you may jump so that

A valid travel plan is defined by a sequence of moves such that the sum of the distances of the moves equals \(|v-u|\) (note that \(|v-u|\) is the absolute distance to be covered) and the number of moves is between 1 and k. In addition, note that if u = v, you are already at the destination; in this case, count 1 valid plan.

Since the answers can be large, output them modulo 998244353.

inputFormat

The first line contains four integers n, m, k and q (n,q ≤ 10⁵, m,k ≤ 10⁴ and m*k ≤ 10⁵), representing the number of inns, the maximum distance you may walk in one move, the maximum number of inns (excluding the starting inn) you are allowed to visit, and the number of queries.

Each of the next q lines contains two integers u and v (1 ≤ u,v ≤ n), representing a query asking the number of travel plans from inn u to inn v.

outputFormat

For each query, output a single integer — the number of valid travel plans modulo 998244353.

sample

5 2 2 3
1 3
3 5
4 2

2
2
2