시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB522100.000%

문제

Kevin is playing cards and now he needs to shuffle cards 𝑚m times. Now let's describe the rule of the ith shuffle.

For the ith shuffle:

  1. Kevin will take out Ai cards from the top and make it a new pile. Now there are two piles of cards. One is the original top Ai cards and the other is the rest nAi cards. The relative order in these two piles remains unchanged. Note that when Ai 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 piles has Y cards. With probability 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 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 to either i or i2.

입력

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

The following line contains m integers A1Am.

The following line contains an integer Q.

In the following Q lines, each line contains an integer ci (1 ≤ cin), indicating that Kevin wants to know the expected score of the ci position from top.

출력

For each query, output a single integer on a single line as the answer. If the answer is A/B, please print C (0 ≤ C < 998244353) where AC × B (mod 998244353).

제한

For all test cases, 3 ≤ n ≤ 107, 1 ≤ m, Q ≤ 5 × 105, 0 ≤ Ain, type ∈ [1,2].

예제 입력 1

4 1 1
3
1
1

예제 출력 1

249561090