小 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

說明

由上至下嘅最後結果係 $\{1,2,3,4\}$ 嘅概率係 $\frac14$。

由上至下嘅最後結果係 $\{1,2,4,3\}$ 嘅概率係 $\frac14$。

由上至下嘅最後結果係 $\{1,4,2,3\}$ 嘅概率係 $\frac14$。

由上至下嘅最後結果係 $\{4,1,2,3\}$ 嘅概率係 $\frac14$。

所以，最後第一個位置係 $4$ 嘅概率係 $\frac14$，第一個位置係 $1$ 嘅概率係 $\frac34$，因此第一個位置嘅期望分數係 $\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$ 嘅期望 $\mathbb{E}[x]$ 嘅定義：

設離散隨機變數 $X$ 嘅可能值係 $X_1,X_2,\cdots,X_k$，$\Pr[X_1],\Pr[X_2],\cdots,\Pr[X_k]$ 係 $X$ 取對應值嘅概率。咁 $X$ 嘅期望就係：

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