小 S играет с 小 F в игру «斗地主».

Бедный 小 S обнаружил, что не может обыграть 小 F в карты, и решил схитрить при тасовании.

Колода содержит $n$ карт, пронумерованных сверху вниз числами от $1$ до $n$. Карта с номером $i$ имеет стоимость $f(i)$. В этой задаче возможны ровно два варианта: $f(i)=i$ или $f(i)=i^2$.

Тасование похоже на привычное нам; ниже приведено его формальное определение.

Тасование состоит из $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 не может узнать, какая именно карта окажется в определённой позиции. Но он хочет спросить у вас математическое ожидание стоимости карты в некоторой позиции после $m$ раундов тасования. Всего 小 S задаст $Q$ таких вопросов.

Входные данные

Данные считываются из файла landlords.in.

Первая строка содержит три положительных целых числа $n,m,type$ — количество карт, количество раундов тасования и тип функции $f(i)$. При $type=1$ имеем $f(i)=i$, а при $type=2$ имеем $f(i)=i^2$.

Следующая строка содержит $m$ целых чисел $A_1,\ldots,A_m$.

Следующая строка содержит положительное целое число $Q$ — количество вопросов 小 S.

Каждая из следующих $Q$ строк содержит одно положительное целое число $c_i$: 小 S хочет узнать математическое ожидание стоимости карты в позиции $c_i$, считая сверху вниз. Гарантируется $1\le c_i\le n$.

Выходные данные

Результаты выводятся в файл landlords.out.

Выведите $Q$ строк, в каждой — одно целое число, представляющее ответ по модулю $998244353$.

То есть, если ответ в виде несократимой дроби равен $\frac ab$, где $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\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$, $type\in\{1,2\}$.

Ограничения отдельных тестов приведены в таблице:

Обратите внимание: условие $Q\le n$ не гарантируется.

Приведём определение математического ожидания $\mathbb E[x]$ дискретной случайной величины $X$.

Пусть возможные значения $X$ равны $X_1,X_2,\ldots,X_k$, а $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ — вероятности соответствующих значений. Тогда математическое ожидание $X$ равно

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