Ramen Seasoning Transformation

Jiutiao Kelian is a girl who loves to eat ramen. One day, she goes to a ramen shop and finds that the chef has pulled out a noodle of even length \(n\). Initially, the \(i\)-th position of the noodle has \(a_i\) units of seasoning.

A ramen process is defined as follows:

1. Fold the noodle in half so that its length becomes \(\frac{n}{2}\). For \(1 \le i \le \frac{n}{2}\), the new seasoning quantity at position \(i\) becomes \[ b_i = a_i + a_{n-i+1}, \] where \(a_i\) and \(a_{n-i+1}\) are the seasoning quantities from the original noodle.
2. Stretch the noodle back to its original length \(n\). Each position in the folded noodle now becomes two positions, and the seasoning is divided equally. In other words, if after stretching the seasoning at position \(i\) becomes \(a'_i\) then \[ a'_i = \frac{1}{2} \times b_{\left\lceil \frac{i}{2} \right\rceil}. \]

This whole operation is called one "ramen process". Now, for a fixed position \(x\) and given \(q\) queries, each query gives a number \(k\). You need to compute the seasoning quantity at the \(x\)-th position after applying the ramen process \(k\) times. Since the answer is a rational number \(\frac{a}{b}\) (in lowest terms), output \(a \times b^{-1} \bmod 998244353\), where \(b^{-1}\) is the modular inverse of \(b\) modulo \(998244353\).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(q\), and \(x\) \((2 \le n \le 10^5,\ n \text{ is even},\ 1 \le x \le n)\) — the length of the noodle, the number of queries, and the fixed position to query.

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) \((0 \le a_i < 998244353)\) representing the initial amount of seasoning at each position.

Then \(q\) lines follow, each containing a single non-negative integer \(k\) \((0 \le k \le 10^5)\) indicating the number of times the ramen process is applied.

outputFormat

For each query, output a single line containing the seasoning amount at position \(x\) after \(k\) ramen processes, modulo \(998244353\). The answer should be computed as \(a \times b^{-1} \bmod 998244353\) if the answer in lowest terms is \(\frac{a}{b}\).

sample

6 3 1
1 2 3 4 5 6
0
1
2

1
499122180
499122180