小 S está jugando con 小 F a un juego llamado «斗地主».
El pobre 小 S ha descubierto que no puede ganar a 小 F jugando a las cartas, así que quiere hacer trampas al barajar.
La baraja tiene $n$ cartas en total, numeradas del $1$ al $n$ de arriba abajo. La puntuación de la carta $i$ es $f(i)$. En este problema, $f(i)$ solo tiene dos posibilidades: $f(i)=i$ o $f(i)=i^2$.
La forma de barajar se parece a la que utilizamos en la vida cotidiana. A continuación la definimos formalmente.
El proceso consta de $m$ rondas de barajado que se realizan en orden. En la ronda $i$:
- 小 S retira las primeras $A_i$ cartas contando desde arriba. La baraja queda dividida en dos montones: el primero contiene las $A_i$ cartas superiores y el segundo las $n-A_i$ restantes. El orden relativo dentro de cada montón se conserva. En particular, cuando $A_i=n$ o $A_i=0$, uno de los montones está vacío.
- A continuación se combinan ambos montones para formar un tercer montón nuevo. Cuando quedan $X$ cartas en el primero e $Y$ en el segundo, con probabilidad $\frac{X}{X+Y}$ se retira la carta inferior del primer montón y se coloca encima del nuevo tercer montón; con probabilidad $\frac{Y}{X+Y}$ se retira la carta inferior del segundo montón y se coloca encima del nuevo tercer montón.
- Se repite la operación 2 hasta que los dos montones estén vacíos. Así termina una ronda de barajado.
Como el barajado es aleatorio, 小 S no puede saber qué carta concreta quedará en una posición. Pero quiere preguntarte cuál es la puntuación esperada de la carta de una posición después de estas $m$ rondas. Te hará $Q$ consultas de este tipo.
Entrada
Los datos se leen del archivo landlords.in.
La primera línea contiene tres enteros positivos $n,m,type$, que representan el número de cartas, el número de rondas de barajado y el tipo de $f(i)$, respectivamente. Si $type=1$, $f(i)=i$. Si $type=2$, $f(i)=i^2$.
La siguiente línea contiene $m$ enteros, que representan $A_1,\ldots,A_m$.
La siguiente línea contiene un entero positivo $Q$, el número de consultas de 小 S.
Cada una de las siguientes $Q$ líneas contiene un entero positivo $c_i$. 小 S quiere conocer la puntuación esperada de la carta situada en la posición $c_i$ contando desde arriba. Se garantiza que $1\le c_i\le n$.
Salida
La salida se escribe en el archivo landlords.out.
Escribe $Q$ líneas con un entero cada una: el valor de la respuesta correspondiente módulo $998244353$.
Es decir, si la respuesta expresada como fracción irreducible es $\frac ab$, donde $a,b$ son coprimos, escribe el entero $x$ tal que $bx\equiv a\pmod{998244353}$ y $0\le x<998244353$. Se puede demostrar que ese entero $x$ es único.
Ejemplos
Entrada 1
4 1 1 3 1 1
Salida 1
249561090
Nota
Con probabilidad $\frac14$, el resultado final de arriba abajo es $\{1,2,3,4\}$.
Con probabilidad $\frac14$, el resultado final de arriba abajo es $\{1,2,4,3\}$.
Con probabilidad $\frac14$, el resultado final de arriba abajo es $\{1,4,2,3\}$.
Con probabilidad $\frac14$, el resultado final de arriba abajo es $\{4,1,2,3\}$.
Por tanto, con probabilidad $\frac14$ la primera posición contiene el $4$ y con probabilidad $\frac34$ contiene el $1$. La puntuación esperada de la primera posición es $\frac74$.
Para ayudarte a comprender mejor el barajado, la figura siguiente muestra el proceso que produce el resultado $\{1,4,2,3\}$.
Ejemplo 2
Consulta landlords/landlords2.in y landlords/landlords2.ans en el directorio de los participantes.
Ejemplo 3
Consulta landlords/landlords3.in y landlords/landlords3.ans en el directorio de los participantes.
Restricciones
Para todos los casos de prueba: $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$ y $type\in\{1,2\}$.
Las restricciones específicas de cada caso aparecen en la tabla siguiente:
| Caso de prueba | $n$ | $m$ | $type=$ | Otras propiedades |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | Ninguna |
| $2$ | $\le80$ | $\le80$ | ||
| $3$ | $2$ | |||
| $4$ | $\le100$ | $\le5\times10^5$ | Todos los $A_i$ son iguales | |
| $5$ | $\le10^7$ | $1$ | Ninguna | |
| $6$ | ||||
| $7$ | ||||
| $8$ | $2$ | |||
| $9$ | ||||
| $10$ |
Ten en cuenta que no se garantiza que $Q\le n$.
A continuación damos la definición de la esperanza $\mathbb E[x]$ de una variable aleatoria discreta $X$.
Sean $X_1,X_2,\ldots,X_k$ los valores posibles de la variable aleatoria discreta $X$, y sean $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ las probabilidades de que $X$ tome los valores correspondientes. La esperanza de $X$ es:
$$\mathbb E[x]=\sum_{i=1}^{k}X_i\Pr[X_i].$$