小S gra z 小F w grę o nazwie „斗地主”.
Biedny 小S odkrył, że nie potrafi pokonać 小F w kartach, więc chce pokombinować podczas tasowania.
Talia zawiera $n$ kart, ponumerowanych od góry do dołu od $1$ do $n$. Karta o numerze $i$ ma wartość punktową $f(i)$. W tym zadaniu możliwe są dokładnie dwa warianty: $f(i)=i$ albo $f(i)=i^2$.
Tasowanie przypomina to stosowane na co dzień. Poniżej definiujemy je formalnie:
Tasowanie składa się z $m$ kolejnych rund. W rundzie $i$:
- 小S wyjmuje $A_i$ kart z góry talii. Powstają dwa stosy: pierwszy zawiera górne $A_i$ kart, a drugi pozostałe $n-A_i$ kart. Względna kolejność kart w każdym stosie pozostaje bez zmian. W szczególności dla $A_i=n$ lub $A_i=0$ jeden ze stosów jest pusty.
- Następnie łączy oba stosy, tworząc nowy, trzeci stos. Gdy w pierwszym stosie pozostaje $X$ kart, a w drugim $Y$ kart, z prawdopodobieństwem $\frac{X}{X+Y}$ bierze najniższą kartę pierwszego stosu i kładzie ją na wierzchu nowego trzeciego stosu. Z prawdopodobieństwem $\frac{Y}{X+Y}$ bierze najniższą kartę drugiego stosu i również kładzie ją na wierzchu nowego trzeciego stosu.
- Powtarza krok 2, aż oba stosy będą puste. Kończy to jedną rundę tasowania.
Ponieważ tasowanie jest losowe, 小S nie może ustalić, która dokładnie karta znajdzie się na danej pozycji. Chce jednak zapytać cię o oczekiwaną wartość punktową karty na pewnej pozycji po $m$ rundach tasowania. Zada łącznie $Q$ takich pytań.
Wejście
Dane należy odczytać z pliku landlords.in.
Pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n,m,\mathrm{type}$, oznaczające liczbę kart, liczbę rund tasowania oraz typ funkcji $f(i)$. Dla $\mathrm{type}=1$ mamy $f(i)=i$, a dla $\mathrm{type}=2$ mamy $f(i)=i^2$.
Następny wiersz zawiera $m$ liczb całkowitych $A_1,\ldots,A_m$.
Kolejny wiersz zawiera jedną dodatnią liczbę całkowitą $Q$, oznaczającą liczbę pytań 小S.
Każdy z kolejnych $Q$ wierszy zawiera jedną dodatnią liczbę całkowitą $c_i$. 小S chce poznać oczekiwaną wartość punktową karty na pozycji $c_i$, licząc od góry do dołu. Gwarantuje się $1\le c_i\le n$.
Wyjście
Wynik należy zapisać do pliku landlords.out.
Wypisz $Q$ wierszy, każdy z jedną liczbą całkowitą, będącą odpowiedzią modulo $998244353$.
Dokładniej, niech odpowiedź po skróceniu do ułamka nieskracalnego ma postać $\frac ab$, gdzie $a,b$ są względnie pierwsze. Wypisz liczbę całkowitą $x$ spełniającą $bx\equiv a\pmod{998244353}$ oraz $0\le x<998244353$. Można udowodnić, że taka liczba całkowita $x$ jest jednoznacznie wyznaczona.
Przykład
Wejście 1
4 1 1 3 1 1
Wyjście 1
249561090
Uwagi
Z prawdopodobieństwem $\frac14$ końcowa kolejność od góry do dołu to $\{1,2,3,4\}$.
Z prawdopodobieństwem $\frac14$ końcowa kolejność od góry do dołu to $\{1,2,4,3\}$.
Z prawdopodobieństwem $\frac14$ końcowa kolejność od góry do dołu to $\{1,4,2,3\}$.
Z prawdopodobieństwem $\frac14$ końcowa kolejność od góry do dołu to $\{4,1,2,3\}$.
Zatem na pierwszej pozycji z prawdopodobieństwem $\frac14$ znajduje się $4$, a z prawdopodobieństwem $\frac34$ znajduje się $1$. Oczekiwana wartość punktowa pierwszej pozycji wynosi więc $\frac74$.
Aby ułatwić zrozumienie tasowania, poniżej pokazano przebieg prowadzący do wyniku $\{1,4,2,3\}$.
Przykład 2
Zobacz pliki landlords/landlords2.in i landlords/landlords2.ans w katalogu zawodnika.
Przykład 3
Zobacz pliki landlords/landlords3.in i landlords/landlords3.ans w katalogu zawodnika.
Ograniczenia
Dla wszystkich testów: $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$, $\mathrm{type}\in\{1,2\}$.
Szczegółowe ograniczenia poszczególnych testów przedstawiono w tabeli:
| Numer testu | $n$ | $m$ | $\mathrm{type}=$ | Pozostałe własności |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | Brak |
| $2$ | $\le80$ | $\le80$ | $1$ | Brak |
| $3$ | $\le80$ | $\le80$ | $2$ | Brak |
| $4$ | $\le100$ | $\le5\times10^5$ | $2$ | Wszystkie $A_i$ są takie same |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Brak |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Brak |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Brak |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Brak |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Brak |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Brak |
Uwaga: nie gwarantuje się, że $Q\le n$.
Poniżej podajemy definicję wartości oczekiwanej $\mathbb E[x]$ dyskretnej zmiennej losowej $X$.
Niech możliwe wartości dyskretnej zmiennej losowej $X$ to $X_1,X_2,\ldots,X_k$, a $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ oznaczają prawdopodobieństwa przyjęcia przez $X$ poszczególnych wartości. Wartość oczekiwana $X$ wynosi wtedy
$$\mathbb E[x]=\sum_{i=1}^{k}X_i\Pr[X_i].$$