小 S 在和小 F 玩一個叫「斗地主」的遊戲。

可憐的小 S 發現自己打牌並打不過小 F，所以他想要在洗牌環節動動手腳。

一副牌一共有 $n$ 張牌，從上到下依次標號為 $1 \sim n$。標號為 $i$ 的牌分數是 $f(i)$。在本題，$f(i)$ 有且僅有兩種可能：$f(i)=i$ 或 $f(i)=i^2$。

洗牌的方式和我們日常生活中的比較類似，以下我們用形式化的語言來定義：

洗牌環節一共分 $m$ 輪，這 $m$ 輪洗牌依次進行。第 $i$ 輪洗牌時：

1. 小 S 會拿出從最上面往下數的前 $A_i$ 張牌。這樣這副牌就被分成了兩堆：第一堆是最上面的 $A_i$ 張牌，第二堆是剩下的 $n-A_i$ 張牌，且這兩堆牌內相對順序不變。特別地，當 $A_i=n$ 或 $A_i=0$ 時，有一堆牌是空的。
2. 接下來對兩堆牌進行合併，從而產生新的第三堆牌。當第一堆牌還剩下 $X$ 張，第二堆牌還剩下 $Y$ 張的時候，以 $\frac{X}{X+Y}$ 的機率取出第一堆牌的最下面的牌，並將它放入新的第三堆牌的最上面；以 $\frac{Y}{X+Y}$ 的機率取出第二堆牌的最下面的牌，並將它放入新的第三堆牌的最上面。
3. 重複操作 2，一直取到兩堆牌都為空為止。這樣我們就完成了一輪洗牌。

因為洗牌過程是隨機的，所以小 S 發現自己沒法知道某個位置上具體是哪張牌。但小 S 想問你在經歷了這 $m$ 輪洗牌後，某個位置上的牌的期望分數是多少。小 S 一共會問你 $Q$ 個這樣的問題。

輸入格式

從檔案 landlords.in 中讀入資料。

輸入的第一行包含三個正整數 $n, m, type$，分別表示牌的數量、洗牌的輪數與 $f(i)$ 的類型。當 $type=1$ 時，$f(i)=i$。當 $type=2$ 時，$f(i)=i^2$。

接下來一行，一共 $m$ 個整數，表示 $A_1 \sim A_m$。

接下來一行一個正整數 $Q$，表示小 S 的詢問個數。

接下來 $Q$ 行，每行一個正整數 $c_i$，表示小 S 想要知道從上往下第 $c_i$ 個位置上的牌的期望分數。保證 $1 \le c_i \le n$。

輸出格式

輸出到檔案 landlords.out 中。

輸出一共 $Q$ 行，每行一個整數，表示答案在模 $998244353$ 意義下的取值。

即設答案化為最簡分式後的形式為 $\frac{a}{b}$，其中 $a$ 和 $b$ 互質。輸出整數 $x$ 使得 $bx \equiv a \pmod{998244353}$ 且 $0 \le x < 998244353$。可以證明這樣的整數 $x$ 是唯一的。

範例

輸入格式 1

4 1 1
3
1
1

輸出格式 1

249561090

說明

有 $\frac14$ 的機率從上到下的最終結果是 $\{1,2,3,4\}$。

有 $\frac14$ 的機率從上到下的最終結果是 $\{1,2,4,3\}$。

有 $\frac14$ 的機率從上到下的最終結果是 $\{1,4,2,3\}$。

有 $\frac14$ 的機率從上到下的最終結果是 $\{4,1,2,3\}$。

所以最終有 $\frac14$ 的機率第一個位置是 $4$，有 $\frac34$ 的機率第一個位置是 $1$，所以第一個位置的期望分數是 $\frac74$。

為了幫助你們更直觀地了解洗牌的過程，我們在下面畫出了結果是 $\{1,4,2,3\}$ 的過程。

範例 2

見選手目錄下的 landlords/landlords2.in 與 landlords/landlords2.ans。

範例 3

見選手目錄下的 landlords/landlords3.in 與 landlords/landlords3.ans。

資料範圍

對於所有的測試點：$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\}$。

每個測試點的具體限制見下表：

請注意我們並沒有保證 $Q \le n$。

這裡我們給出離散型隨機變數 $X$ 的期望 $\mathrm{E}[x]$ 的定義：

設離散隨機變數 $X$ 的可能值是 $X_1, X_2, \cdots, X_k$，$\Pr[X_1], \Pr[X_2], \cdots, \Pr[X_k]$ 為 $X$ 取對應值的機率。則 $X$ 的期望為

$$ \mathrm{E}[x] = \sum_{i=1}^k X_i \Pr[X_i] $$