小 S spielt mit 小 F ein Spiel namens „斗地主“.
Der arme 小 S stellt fest, dass er 小 F beim Kartenspielen nicht besiegen kann. Deshalb möchte er beim Mischen ein wenig tricksen.
Ein Kartenspiel besteht aus $n$ Karten, die von oben nach unten mit $1$ bis $n$ beschriftet sind. Die Karte mit der Nummer $i$ hat den Wert $f(i)$. In dieser Aufgabe gibt es für $f(i)$ genau zwei Möglichkeiten: $f(i)=i$ oder $f(i)=i^2$.
Die Mischmethode ähnelt der im Alltag üblichen. Wir definieren sie im Folgenden formal:
Das Mischen besteht aus $m$ Runden, die nacheinander ausgeführt werden. In Runde $i$ geschieht Folgendes:
- 小 S nimmt die obersten $A_i$ Karten ab. Dadurch entstehen zwei Stapel: Der erste enthält die obersten $A_i$ Karten, der zweite die übrigen $n-A_i$ Karten. Die relative Reihenfolge innerhalb jedes Stapels bleibt unverändert. Insbesondere ist für $A_i=n$ oder $A_i=0$ einer der Stapel leer.
- Anschließend werden beide Stapel zu einem neuen dritten Stapel zusammengeführt. Enthält der erste Stapel noch $X$ Karten und der zweite noch $Y$ Karten, wird mit Wahrscheinlichkeit $\frac{X}{X+Y}$ die unterste Karte des ersten Stapels genommen und oben auf den neuen dritten Stapel gelegt. Mit Wahrscheinlichkeit $\frac{Y}{X+Y}$ wird stattdessen die unterste Karte des zweiten Stapels genommen und oben auf den dritten Stapel gelegt.
- Wiederhole Schritt $2$, bis beide Stapel leer sind. Damit ist eine Mischrunde abgeschlossen.
Da das Mischen zufällig abläuft, kann 小 S nicht wissen, welche Karte sich an einer bestimmten Position befinden wird. Er möchte dich aber nach dem Erwartungswert des Kartenwerts an einer bestimmten Position nach diesen $m$ Mischrunden fragen. 小 S stellt insgesamt $Q$ solche Fragen.
Eingabe
Lies die Daten aus der Datei landlords.in.
Die erste Zeile enthält drei positive ganze Zahlen $n,m,\mathrm{type}$: die Anzahl der Karten, die Anzahl der Mischrunden und den Typ von $f(i)$. Für $\mathrm{type}=1$ gilt $f(i)=i$, für $\mathrm{type}=2$ gilt $f(i)=i^2$.
Die nächste Zeile enthält insgesamt $m$ ganze Zahlen $A_1$ bis $A_m$.
Die nächste Zeile enthält eine positive ganze Zahl $Q$, die Anzahl der Fragen von 小 S.
Die nächsten $Q$ Zeilen enthalten jeweils eine positive ganze Zahl $c_i$. 小 S möchte den Erwartungswert des Werts der Karte an der $c_i$-ten Position von oben wissen. Es gilt $1\le c_i\le n$.
Ausgabe
Schreibe die Ausgabe in die Datei landlords.out.
Gib insgesamt $Q$ Zeilen mit jeweils einer ganzen Zahl aus, dem Wert der Antwort modulo $998244353$.
Sei die vollständig gekürzte Form der Antwort $\frac{a}{b}$, wobei $a$ und $b$ teilerfremd sind. Gib die ganze Zahl $x$ aus, für die $bx\equiv a\pmod{998244353}$ und $0\le x<998244353$ gelten. Man kann beweisen, dass diese ganze Zahl $x$ eindeutig ist.
Beispiele
Eingabe 1
4 1 1 3 1 1
Ausgabe 1
249561090
Hinweis
Mit Wahrscheinlichkeit $\frac14$ ist die endgültige Reihenfolge von oben nach unten $\{1,2,3,4\}$.
Mit Wahrscheinlichkeit $\frac14$ ist die endgültige Reihenfolge von oben nach unten $\{1,2,4,3\}$.
Mit Wahrscheinlichkeit $\frac14$ ist die endgültige Reihenfolge von oben nach unten $\{1,4,2,3\}$.
Mit Wahrscheinlichkeit $\frac14$ ist die endgültige Reihenfolge von oben nach unten $\{4,1,2,3\}$.
Somit befindet sich an der ersten Position mit Wahrscheinlichkeit $\frac14$ die Karte $4$ und mit Wahrscheinlichkeit $\frac34$ die Karte $1$. Der Erwartungswert des Kartenwerts an der ersten Position beträgt also $\frac74$.
Um den Mischvorgang anschaulicher zu machen, ist unten der Ablauf dargestellt, der zum Ergebnis $\{1,4,2,3\}$ führt.
Beispiel 2
Siehe landlords/landlords2.in und landlords/landlords2.ans im Teilnehmerverzeichnis.
Beispiel 3
Siehe landlords/landlords3.in und landlords/landlords3.ans im Teilnehmerverzeichnis.
Beschränkungen
Für alle Testpunkte gilt $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$ und $\mathrm{type}\in\{1,2\}$.
Die genauen Einschränkungen jedes Testpunkts stehen in der folgenden Tabelle:
| Testpunkt | $n$ | $m$ | $\mathrm{type}=$ | Weitere Eigenschaften |
|---|---|---|---|---|
| 1 | $\le10$ | $\le1$ | $1$ | Keine |
| 2 | $\le80$ | $\le80$ | ||
| 3 | $2$ | |||
| 4 | $\le100$ | $\le5\times10^5$ | Alle $A_i$ sind gleich | |
| 5 | $\le10^7$ | $1$ | Keine | |
| 6 | ||||
| 7 | ||||
| 8 | $2$ | |||
| 9 | ||||
| 10 |
Beachte, dass nicht garantiert ist, dass $Q\le n$ gilt.
Hier geben wir die Definition des Erwartungswerts $\mathbb E[x]$ einer diskreten Zufallsvariablen $X$ an:
Seien $X_1,X_2,\ldots,X_k$ die möglichen Werte der diskreten Zufallsvariablen $X$ und $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ die Wahrscheinlichkeiten, mit denen $X$ den jeweiligen Wert annimmt. Dann ist der Erwartungswert von $X$:
$$ \mathbb E[x]=\sum_{i=1}^{k}X_i\Pr[X_i]. $$