小 S está a jogar com 小 F um jogo chamado “斗地主”.
O pobre 小 S percebeu que não consegue vencer 小 F a jogar às cartas e quer, por isso, fazer batota durante o baralhamento.
Um baralho tem $n$ cartas, inicialmente numeradas de $1$ a $n$, de cima para baixo. A carta de número $i$ tem pontuação $f(i)$. Neste problema, existem exatamente duas possibilidades: $f(i)=i$ ou $f(i)=i^2$.
O método de baralhar é semelhante ao usado no dia a dia. Vamos defini-lo formalmente:
O baralhamento tem $m$ rondas, realizadas por ordem. Na ronda $i$:
- 小 S retira as primeiras $A_i$ cartas, a contar de cima. O baralho fica dividido em duas pilhas: a primeira contém as $A_i$ cartas superiores e a segunda as restantes $n-A_i$ cartas. A ordem relativa dentro de cada pilha não muda. Em particular, se $A_i=n$ ou $A_i=0$, uma das pilhas está vazia.
- As duas pilhas são depois intercaladas para formar uma terceira pilha nova. Quando restam $X$ cartas na primeira pilha e $Y$ na segunda, com probabilidade $\frac{X}{X+Y}$ retira-se a carta do fundo da primeira pilha e coloca-se no topo da terceira pilha; com probabilidade $\frac{Y}{X+Y}$ retira-se a carta do fundo da segunda pilha e coloca-se no topo da terceira pilha.
- Repete-se a operação 2 até ambas as pilhas ficarem vazias. Assim se conclui uma ronda de baralhamento.
Como o processo é aleatório, 小 S percebe que não consegue saber qual é exatamente a carta numa certa posição. Porém, quer perguntar-te qual é a pontuação esperada da carta numa determinada posição depois das $m$ rondas. Fará $Q$ perguntas deste tipo.
Entrada
Leia os dados do ficheiro landlords.in.
A primeira linha contém três inteiros positivos $n,m,\mathrm{type}$, respetivamente o número de cartas, o número de rondas de baralhamento e o tipo de $f(i)$. Se $\mathrm{type}=1$, $f(i)=i$. Se $\mathrm{type}=2$, $f(i)=i^2$.
A linha seguinte contém $m$ inteiros, $A_1,\ldots,A_m$.
A linha seguinte contém um inteiro positivo $Q$, o número de consultas de 小 S.
Seguem-se $Q$ linhas, cada uma contendo um inteiro positivo $c_i$. 小 S quer saber a pontuação esperada da carta na posição $c_i$, a contar de cima. É garantido que $1\le c_i\le n$.
Saída
Escreva a saída no ficheiro landlords.out.
Imprima $Q$ linhas, cada uma com um inteiro: a resposta módulo $998\,244\,353$.
Isto é, supondo que a resposta na forma de fração irredutível é $\frac ab$, com $a,b$ primos entre si, imprima o inteiro $x$ tal que $bx\equiv a\pmod{998\,244\,353}$ e $0\le x<998\,244\,353$. Pode demonstrar-se que este inteiro $x$ é único.
Exemplos
Entrada 1
4 1 1 3 1 1
Saída 1
249561090
Nota
Com probabilidade $\frac14$, o resultado final de cima para baixo é $\{1,2,3,4\}$.
Com probabilidade $\frac14$, o resultado final de cima para baixo é $\{1,2,4,3\}$.
Com probabilidade $\frac14$, o resultado final de cima para baixo é $\{1,4,2,3\}$.
Com probabilidade $\frac14$, o resultado final de cima para baixo é $\{4,1,2,3\}$.
Assim, com probabilidade $\frac14$ a primeira posição contém $4$, e com probabilidade $\frac34$ contém $1$. A pontuação esperada da primeira posição é, portanto, $\frac74$.
Para ajudar a compreender o baralhamento de forma mais intuitiva, mostramos abaixo o processo que produz $\{1,4,2,3\}$.
Exemplo 2
Consulte landlords/landlords2.in e landlords/landlords2.ans no diretório do participante.
Exemplo 3
Consulte landlords/landlords3.in e landlords/landlords3.ans no diretório do participante.
Restrições e observações
Para todos os casos de teste: $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$ e $\mathrm{type}\in\{1,2\}$.
As restrições específicas de cada caso de teste estão na tabela seguinte:
| Caso de teste | $n$ | $m$ | $\mathrm{type}=$ | Outras propriedades |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | Nenhuma |
| $2$ | $\le80$ | $\le80$ | $1$ | Nenhuma |
| $3$ | $\le80$ | $\le80$ | $2$ | Nenhuma |
| $4$ | $\le100$ | $\le5\times10^5$ | $2$ | Todos os $A_i$ são iguais |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Nenhuma |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Nenhuma |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | Nenhuma |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Nenhuma |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Nenhuma |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | Nenhuma |
Atenção: não é garantido que $Q\le n$.
Damos aqui a definição da esperança $\mathbb E[x]$ de uma variável aleatória discreta $X$:
Se os valores possíveis de $X$ forem $X_1,X_2,\ldots,X_k$, e $\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ forem as probabilidades de $X$ assumir os respetivos valores, então a esperança de $X$ é
$$ \mathbb E[x]=\sum_{i=1}^k X_i\Pr[X_i] $$