小 S грає з 小 F у гру «斗地主».
Бідолашний 小 S зрозумів, що не може перемогти 小 F у картах, тому хоче схитрувати під час тасування.
Колода містить $n$ карт, пронумерованих згори донизу від $1$ до $n$. Карті з номером $i$ відповідає кількість очок $f(i)$. У цій задачі можливі рівно два варіанти: $f(i)=i$ або $f(i)=i^2$.
Спосіб тасування подібний до звичного нам; нижче наведено його формальний опис.
Тасування складається з $m$ раундів, які виконуються послідовно. У раунді $i$:
- 小 S забирає верхні $A_i$ карт. Таким чином колода ділиться на дві стопки: перша містить верхні $A_i$ карт, а друга — решту $n-A_i$ карт. Відносний порядок карт у кожній стопці зберігається. Зокрема, якщо $A_i=n$ або $A_i=0$, одна зі стопок порожня.
- Далі ці дві стопки об'єднуються в нову, третю стопку. Коли в першій стопці залишилося $X$ карт, а в другій — $Y$, з імовірністю $\frac{X}{X+Y}$ забирають найнижчу карту першої стопки та кладуть її нагору нової третьої стопки; з імовірністю $\frac{Y}{X+Y}$ так само забирають найнижчу карту другої стопки та кладуть її нагору третьої.
- Крок 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$ рядків, кожен з одним цілим числом — значенням відповіді за модулем $998\,244\,353$.
Тобто нехай відповідь у вигляді нескоротного дробу дорівнює $\frac ab$, де $a,b$ взаємно прості. Виведіть ціле число $x$, для якого $bx\equiv a\pmod{998\,244\,353}$ та $0\le x<998\,244\,353$. Можна довести, що таке ціле число $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\}$.
Детальні обмеження кожного тесту наведено в таблиці:
| Номер тесту | $n$ | $m$ | $type=$ | Інші властивості |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | Немає |
| $2$ | $\le80$ | $\le80$ | $1$ | Немає |
| $3$ | $\le80$ | $\le80$ | $2$ | Немає |
| $4$ | $\le100$ | $\le5\times10^5$ | $2$ | Усі $A_i$ однакові |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Немає |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Немає |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Немає |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Немає |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Немає |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Немає |
Зверніть увагу: не гарантується, що $Q\le n$.
Наведемо визначення математичного сподівання $\mathbb E[x]$ дискретної випадкової величини $X$.
Нехай дискретна випадкова величина $X$ може набувати значень $X_1,X_2,\cdots,X_k$, а $\Pr[X_1],\Pr[X_2],\cdots,\Pr[X_k]$ — імовірності відповідних значень. Тоді математичне сподівання $X$ дорівнює
$$\mathbb E[x]=\sum_{i=1}^k X_i\Pr[X_i].$$