#P51178. [NOI2019] Landdrol

[NOI2019] Landdrol

Description

Alice and Bob are playing card games, but Alice found that she can never win Bob, so she plans to cheat in the shuffling session.

There are nn cards in total, numbered from 11 to nn from top to bottom. The card with index ii has a score of f(i)f(i). In this problem, f(i)=if(i) = i or f(i)=i2f(i) = i^2 always holds.

The whole shuffling session can be devided into mm rounds. During the ii-th round:

  • Alice will take AiA_i cards from the top, then all the cards are divided into 2 piles: the first contains AiA_i cards from the top, the second contains the remaining nAin - A_i cards.
    • In particular, when Ai=0A_i = 0 or Ai=nA_i = n, one of the piles will be empty.
  • Then Alice will merge the two piles in the following way. When there are XX cards left in the first pile and YY in the second, she will take the card at the bottom of the first pile with the probability of XX+Y\frac{X}{X + Y}, and put it on the top of the new pile; otherwise she will take the card at the bottom of the second pile and put it on the top of the new pile.

Since the shuffling session is random, Alice can't know which card it is at a certain position. But Alice wants to know the expected score of the card at a certain position after mm rounds of shuffling.

Input

The first line contains 33 integers n,m,typen, m, \text{type}. When type=1\text{type} = 1, f(i)=if(i) = i, otherwise f(i)=i2f(i) = i^2.

The second line contains mm integers A1,A2,,AmA_1, A_2, \cdots, A_m.

The third line contains a single integer QQ — the number of queries.

Each of the next QQ lines contains a single integer cic_i.

Output

You should print QQ lines, the ii-th line contains the expected score of the cic_i-th card from top to bottom.

You should print the answer module 998244353998244353, that is, if the answer is ab\frac{a}{b}, where (a,b)=1(a, b) = 1, you should print an integer xx such that bxa(mod998244353)bx \equiv a \pmod{998244353} and 0x<9982443530 \leq x < 998244353. One can prove that such xx is unique.

Sample 1

4 1 1
3
1
1
249561090

After shuffling, the cards will become:

  • {1,2,3,4}\{1, 2, 3, 4\} from top to bottom with the probability of 14\frac{1}{4}
  • {1,2,4,3}\{1, 2, 4, 3\} from top to bottom with the probability of 14\frac{1}{4}
  • {1,4,2,3}\{1, 4, 2, 3\} from top to bottom with the probability of 14\frac{1}{4}
  • {4,1,2,3}\{4, 1, 2, 3\} from top to bottom with the probability of 14\frac{1}{4}

So the expected score of the first place is 14(1+1+1+4)=74\frac{1}{4}(1 + 1 + 1 + 4) = \frac{7}{4}.

The picture below illustrates the whole process to the answer {1,4,2,3}\{1, 4, 2, 3\}:

No.3160.EN.png

Sample 2

See landlords/landlords2.in and landlords/landlords2.ans in the additional files.

Sample 3

See landlords/landlords3.in and landlords/landlords3.ans in the additional files.

Limits And Hints

  • 3n1073 \leq n \leq 10^7
  • 1m,Q5×1051 \leq m, Q \leq 5 \times 10^5
  • 0Ain0 \leq A_i \leq n
  • type{1,2}\text{type} \in \{1, 2\}

Specific constraints of each cases are listed below:

Subtask # nn mm type=\text{type}= Other constraints
11 10\le 10 1\le 1 11 No
22 80\le 80 80\le 80
33 80\le 80 80\le 80 22
44 100\le 100 5×1055\times 10^5 All AiA_i are equal
55 10710^7 11 No
66
77
88 22
99
1010

WARNING: THERE IS NO GUARANTEE that QnQ \le n.