Movimentação Assustadora à Distância

Charles é um grande físico, criptógrafo e cientista da computação, sendo responsável por grandes contribuições que incluem trabalhos fundamentais sobre a relação entre física e informação. Durante seus estudos sobre teletransporte quântico, Charles descobriu um campo quântico com $N$ posições numeradas de 1 até $N$. Em um experimento, Charles pode colocar uma partícula inicialmente em qualquer posição do campo quântico. Em cada instante de tempo, a partícula pode decidir se teletransportar para uma posição maior do que a sua posição atual ou permanecer parada e finalizar o trajeto. Desta forma, existem $2^{N}-1$ trajetos possíveis.

Seja um trajeto uma sequência de posições visitadas por uma partícula em um experimento. Cada posição $i$ ($1 \le i \le N$) do campo quântico possui um coeficiente $A_i$ associado. Charles define a beleza de um trajeto sendo igual ao máximo divisor comum de todos os coeficientes de posições visitada no trajeto.

Charles irá fazer várias operações em sequência, são elas:

• Operação 1 $X$: Considere que todos os trajetos possíveis têm a mesma probabilidade de serem feitos. Qual a probabilidade do trajeto feito ter beleza igual a $X$?
• Operação 2 $I$ $X$: Atualize o valor do coeficiente $A_i$ para ser $X$.

Você pode ajudar Charles com os seus experimentos?

A primeira linha da entrada contém o inteiro $N$ ($1 \le N \le 10^5$), a quantidade de posições do campo quântico. Seguem na segunda linha $N$ inteiros positivos $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^5$).

A terceira linha da entrada contém o inteiro $Q$ ($1 \le Q \le 10^5$), a quantidade de consultas. As próximas $Q$ linhas vão conter operações. Cada linha é uma operação que é identificada pelo inteiro $T$ ($1 \le T \le 2$). Operações com $T=1$ são seguidas de um inteiro $X$ e operações do tipo 2 são seguidas dos inteiros $I$ ($1 \le I \le N$) e $X$. Em ambas a operações, $1 \le X \le 10^5$.

Para cada experimento feito por Charles, imprima a probabilidade $\frac{P}{Q}$ do experimento ter beleza igual a $X$ na forma $P \cdot Q^{-1} \pmod{998244353}$. É garantido que $P$ é um inteiro não negativo e $Q$ é um inteiro positivo, e que $Q^{-1}$ com a propriedade $QQ^{-1}=1$ existe $\pmod{998244353}$.