問題文

長さ $N$ の非負数列 $A = (A_{1}, A_{2}, \dots , A_{N})$ が与えられます。

$Q$ 個のクエリを処理してください。$i$ 番目のクエリでは、$1$ 以上 $N$ 以下の整数 $L_{i}, R_{i}$ が与えられるので、$\mathrm{LCM}(A_{L_{i}}, A_{L_{i} + 1}, \dots, A_{R_{i}})$ を $998244353$ で割ったあまりを答えてください。

ただし、クエリはオンラインで処理してください。

このため、$L_{i}, R_{i}$ の代わりに $0$ 以上 $998244353$ 未満の整数 $a_{i}, b_{i}$ が与えられるので、以下の手順で $L_{i}, R_{i}$ を復元してください。

• $ans_{i}$ を $i$ 番目のクエリの答えとします。ただし、$ans_{0} = 1$ とします。
• $x_{i}$ を $a_{i}$ と $ans_{i - 1}$ の積を $998244353$ で割ったあまりとします。
• $y_{i}$ を $x_{i}$ を $N$ で割ったあまりに $1$ を足した値とします。
• $z_{i}$ を $b_{i}$ と $ans_{i - 1}$ の積を $998244353$ で割ったあまりとします。
• $w_{i}$ を $z_{i}$ を $N$ で割ったあまりに $1$ を足した値とします。
• このとき、$L_{i} = \min(y_{i}, w_{i})$ と $R_{i} = \max(y_{i}, w_{i})$ が成り立ちます。

制約

• $1\leq N\leq 2\times 10^{5}$
• $1\leq A_{i} \leq 2\times 10^{5}$
• $1\leq Q\leq 2\times 10^{5}$
• $0\leq a_{i} < 998244353$
• $0\leq b_{i} < 998244353$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
$Q$
$a_{1}$ $b_{1}$
$a_{2}$ $b_{2}$
$\vdots$
$a_{Q}$ $b_{Q}$

出力

$Q$ 行出力してください。$i$ 行目には $i$ 番目のクエリの答えを出力してください。

サンプル

10
6 3 4 167 2001 924 167167 167924 154308 214
7
304921541 763013770
364152278 493873646
913728501 147488912
853264047 856697087
387754750 361771040
445185209 445241330
241421656 198733890

6
12
12
2001
750239690
562468351
289452377

10
6 3 4 167 2001 924 167167 167924 154308 214
7
1 2
1 3
2 3
5 5
6 10
5 8
1 10