Yesterday, Bob was invited to a game show! At which, Bob played but one game. The game was as follows:

You are given \(N\) coins each with a value \(a_i\). For each of \(K\) rounds, you either pick a coin, or skip the round. If a coin is chosen, it is added to your stash and is then replaced with a coin of the exact same value. All coins of the same value, regardless of round chosen, are considered identical. At the end of the \(K\) rounds, you are to report the sum of the chosen coins. If you answer correctly, you are allowed to keep the chosen coins. If you are incorrect, you return all the coins and receive no prize.

Unfortunately, Bob came home empty handed!

To let out his rage, Bob gives Seyon a replica of the game with identical rules. He then gives Seyon \(Q\) queries, each consisting of two integers \(L_i\) and \(R_i\). For each of the queries, Seyon is to report the number of different ways to acquire coins, modulo \(998244353\), such that their sum is an element of the interval \([L_i, R_i]\). Two ways are considered different if there exists a coin \(x\) such that the frequency of \(x\) in one way is different from the frequency of \(x\) in the other way.

Unfortunately, Seyon didn't listen in CS this semester and comes to you for assistance. Can you help him?

Constraints

\(1 \le N \le 5 \times 10^5\)

\(1 \le a_i \le 10^5\)

\(1 \le K \le 10^{18}\)

\(1 \le Q \le 10^5\)

\(0 \le L_i \le R_i \le 10^5\)

Input Specification

On the first line, there will be three space separated integers: \(N\), the number of coins; \(K\), the number of rounds; and \(Q\), the number of queries.

On the second line, there will be \(N\) space separated integers, representing the values of the \(N\) coins.

On the next \(Q\) lines, there will be two space separated integers: \(L\), the left bound of the target sum, and \(R\), the inclusive right bound of the target sum.

Ouput Specification

Output \(Q\) lines, with the \(ith\) line containing the answer, modulo \(998244353\), to \(Q_i\), the \(ith\) query.

Sample Input

2 2 2
1 2
1 2
0 4

Sample Output

5
9