Little S is playing a game called "Landlords" with Little F. Poor Little S finds that he cannot beat Little F at cards, so he wants to tamper with the shuffling process.

A deck of cards has $n$ cards, labeled $1$ to $n$ from top to bottom. The score of the card with label $i$ is $f(i)$. In this problem, $f(i)$ has exactly two possibilities: $f(i) = i$ or $f(i) = i^2$.

The shuffling method is similar to what we see in daily life, and we define it formally as follows: The shuffling process consists of $m$ rounds, which are performed sequentially. In the $i$-th round of shuffling: 1. Little S takes the top $A_i$ cards. This divides the deck into two piles: the first pile consists of the top $A_i$ cards, and the second pile consists of the remaining $n - A_i$ cards, with the relative order of cards within each pile remaining unchanged. Specifically, when $A_i = n$ or $A_i = 0$, one pile is empty. 2. Next, the two piles are merged to form a new third pile. When there are $X$ cards remaining in the first pile and $Y$ cards remaining in the second pile, the card at the bottom of the first pile is moved to the top of the new third pile with probability $\frac{X}{X+Y}$, and the card at the bottom of the second pile is moved to the top of the new third pile with probability $\frac{Y}{X+Y}$. 3. Repeat step 2 until both piles are empty. This completes one round of shuffling.

Because the shuffling process is random, Little S finds that he cannot know exactly which card is at a specific position. However, Little S wants to ask you, after these $m$ rounds of shuffling, what is the expected score of the card at a certain position? Little S will ask you $Q$ such questions in total.

Input

The first line contains three positive integers $n, m, type$, representing the number of cards, the number of shuffling rounds, and the type of $f(i)$, respectively. When $type = 1$, $f(i) = i$. When $type = 2$, $f(i) = i^2$. The next line contains $m$ integers, representing $A_1 \sim A_m$. The next line contains a positive integer $Q$, representing the number of queries from Little S. The next $Q$ lines each contain a positive integer $c_i$, representing the position from the top (1-indexed) that Little S wants to know the expected score for. It is guaranteed that $1 \le c_i \le n$.

Output

Output $Q$ lines, each containing an integer representing the answer modulo $998244353$. That is, if the answer is expressed as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are coprime, output an integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \le x < 998244353$. It can be proven that such an integer $x$ is unique.

Examples

Input 1

4 1 1
3
1
1

Output 1

249561090

Note 1

There is a $\frac{1}{4}$ probability that the final order from top to bottom is $\{1, 2, 3, 4\}$. There is a $\frac{1}{4}$ probability that the final order from top to bottom is $\{1, 2, 4, 3\}$. There is a $\frac{1}{4}$ probability that the final order from top to bottom is $\{1, 4, 2, 3\}$. There is a $\frac{1}{4}$ probability that the final order from top to bottom is $\{4, 1, 2, 3\}$. Therefore, there is a $\frac{1}{4}$ probability that the first position is 4, and a $\frac{3}{4}$ probability that the first position is 1, so the expected score of the first position is $\frac{7}{4}$.

Examples

Input 2

See the file landlords/landlords2.in in the contestant directory.

Output 2

See the file landlords/landlords2.ans in the contestant directory.

Input 3

See the file landlords/landlords3.in in the contestant directory.

Output 3

See the file landlords/landlords3.ans in the contestant directory.

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\}$. The specific constraints for each test case are shown in the table below:

Please note that we do NOT guarantee $Q \le n$. Here we provide the definition of the expectation $\mathbb{E}[X]$ for a discrete random variable $X$: Let the possible values of the discrete random variable $X$ be $X_1, X_2, \dots, X_k$, and $\Pr[X_1], \Pr[X_2], \dots, \Pr[X_k]$ be the probabilities that $X$ takes the corresponding values. Then the expectation of $X$ is: $$\mathbb{E}[X] = \sum_{i=1}^{k} X_i \Pr[X_i]$$

Figure 1. Illustration of the shuffling process