Kevin is playing cards and now he needs to shuffle cards ~m~ times. Now let's describe the rule of the ~i^{th}~ shuffle.

For the ~i^{th}~ shuffle:

1. Kevin will take out ~A_i~ cards from the top and make it a new pile. Now there are two piles of cards. One is the original top ~A_i~ cards and the other is the remaining ~n-A_i~ cards. The relative order in these two piles remains unchanged. Note that when ~A_i~ is ~n~ or ~0~, there is one pile which has no card at all.

2. Now let's merge those two piles of cards into a new pile. Suppose the first pile has ~X~ cards and the second pile has ~Y~ cards. With probability ~\frac{X}{X+Y}~, we select the bottom card of the first pile and put the selected card to the top of the new pile. Then, with probability ~\frac{Y}{X+Y}~, we select the bottom card of the second pile and then put the selected card to the top of the new pile.

3. Repeat 2 until both piles are empty.

Now we have ~Q~ questions for you. You have to tell us after ~m~ times of shuffles, what's the expected score of some specific positions' card. Note that for card ~i~, let's denote its score as ~f(i)~. In this problem, ~f(i)~ equals either ~i~ or ~i^2~.

Input Specification

The first line contains three integers ~n,m,type~. When ~type = 1~, ~f(i) = i~. When ~type = 2~, ~f(i) = i^2~.

The following line contains ~m~ integers ~A_1, \dots, A_m~.

The following line contains an integer ~Q~.

In the following ~Q~ lines, each line contains an integer ~c_i~ ~(1 \le c_i \le n)~, indicating that Kevin wants to know the expected score of the ~c_i~ position from the top.

Constraints

For all test cases, ~3 \le n \le 10^7~, ~1 \le m,Q \le 5 \times 10^5~, ~0 \le A_i \le n~, ~type \in \{1,2\}~.

Test Case	~n~	~m~	Type	Additional Constraints
1	~\le 10~	~\le 1~	1	None
2	~\le 80~	~\le 80~
3			2
4	~\le 100~	~\le 5 \times 10^5~		All ~A_i~ are equal
5	~\le 10^7~		1	None
6
7
8			2
9
10

Output Specification

For each query, output a single integer on a single line as the answer. If the answer is ~\frac{A}{B}~, please print ~C~ ~(0 \le C < 998\,244\,353)~ where ~A \equiv C \times B \pmod{998\,244\,353}~.

Sample Input 1

4 1 1
3
1
1

Sample Output 1

249561090