小 S joue avec 小 F à un jeu appelé « 斗地主 ».
Le pauvre 小 S constate qu'il n'arrive pas à battre 小 F aux cartes ; il veut donc tricher au moment de les mélanger.
Un paquet contient $n$ cartes, numérotées initialement de $1$ à $n$ du haut vers le bas. La valeur de la carte $i$ est $f(i)$. Dans ce problème, il n'y a que deux possibilités : $f(i)=i$ ou $f(i)=i^2$.
Le mélange ressemble à celui que nous effectuons dans la vie courante. Nous le définissons formellement ci-dessous.
Il comporte $m$ tours, effectués successivement. Au $i$-ème tour :
- 小 S prend les $A_i$ premières cartes depuis le haut. Le paquet est ainsi séparé en deux piles : les $A_i$ cartes du dessus et les $n-A_i$ restantes. L'ordre relatif des cartes de chaque pile ne change pas. En particulier, si $A_i=n$ ou $A_i=0$, l'une des piles est vide.
- On fusionne ensuite ces deux piles pour former une nouvelle troisième pile. Lorsqu'il reste $X$ cartes dans la première et $Y$ dans la deuxième, on prend la carte du dessous de la première pile avec probabilité $\frac{X}{X+Y}$ et la pose au-dessus de la troisième pile ; avec probabilité $\frac{Y}{X+Y}$, on fait de même avec la carte du dessous de la deuxième pile.
- Répéter l'opération 2 jusqu'à ce que les deux piles soient vides. Un tour de mélange est alors terminé.
Le mélange étant aléatoire, 小 S ne peut pas savoir quelle carte occupera exactement une position donnée. Il vous demande cependant l'espérance de la valeur de la carte à une certaine position après les $m$ tours de mélange. Il vous posera $Q$ questions de ce type.
Entrée
Lire les données dans le fichier landlords.in.
La première ligne contient trois entiers strictement positifs $n,m,\mathit{type}$ : le nombre de cartes, le nombre de tours de mélange et le type de $f(i)$. Si $\mathit{type}=1$, $f(i)=i$ ; si $\mathit{type}=2$, $f(i)=i^2$.
La ligne suivante contient $m$ entiers $A_1,\ldots,A_m$.
La ligne suivante contient un entier strictement positif $Q$, le nombre de requêtes de 小 S.
Chacune des $Q$ lignes suivantes contient un entier strictement positif $c_i$. 小 S veut connaître l'espérance de la valeur de la carte à la $c_i$-ème position depuis le haut. Il est garanti que $1\le c_i\le n$.
Sortie
Écrire dans le fichier landlords.out.
Afficher $Q$ lignes contenant chacune un entier, la réponse modulo $998244353$.
Plus précisément, si la réponse sous forme de fraction irréductible vaut $\frac ab$, où $a,b$ sont premiers entre eux, afficher l'entier $x$ tel que $bx\equiv a\pmod{998244353}$ et $0\le x<998244353$. On peut prouver qu'un tel entier $x$ est unique.
Exemples
Entrée 1
4 1 1 3 1 1
Sortie 1
249561090
Remarque
Avec probabilité $\frac14$, l'ordre final du haut vers le bas est $\{1,2,3,4\}$.
Avec probabilité $\frac14$, l'ordre final du haut vers le bas est $\{1,2,4,3\}$.
Avec probabilité $\frac14$, l'ordre final du haut vers le bas est $\{1,4,2,3\}$.
Avec probabilité $\frac14$, l'ordre final du haut vers le bas est $\{4,1,2,3\}$.
La première position contient donc $4$ avec probabilité $\frac14$ et $1$ avec probabilité $\frac34$ ; l'espérance de sa valeur est $\frac74$.
Pour vous aider à mieux visualiser le mélange, le schéma ci-dessous montre le processus donnant $\{1,4,2,3\}$.
Exemple 2
Voir les fichiers landlords/landlords2.in et landlords/landlords2.ans dans le répertoire des candidats.
Exemple 3
Voir les fichiers landlords/landlords3.in et landlords/landlords3.ans dans le répertoire des candidats.
Contraintes et indications
Pour tous les tests, $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$ et $\mathit{type}\in\{1,2\}$.
Les restrictions propres à chaque test figurent dans le tableau suivant :
| Test | $n$ | $m$ | $\mathit{type}=$ | Autres propriétés |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | Aucune |
| $2$ | $\le80$ | $\le80$ | $1$ | Aucune |
| $3$ | $\le80$ | $\le80$ | $2$ | Aucune |
| $4$ | $\le100$ | $\le80$ | $2$ | Tous les $A_i$ sont identiques |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Aucune |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Aucune |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Aucune |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Aucune |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Aucune |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Aucune |
Attention : nous ne garantissons pas que $Q\le n$.
Voici la définition de l'espérance $\mathbb E[x]$ d'une variable aléatoire discrète $X$.
Si les valeurs possibles de $X$ sont $X_1,X_2,\ldots,X_k$ et que $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ sont les probabilités correspondantes, l'espérance de $X$ est
$$\mathbb E[x]=\sum_{i=1}^{k}X_i\Pr[X_i].$$