Problem Statement

You are given a non-negative sequence $A = (A_{1}, A_{2}, \dots , A_{N})$ of length $N$.

Process $Q$ queries. In the $i$-th query, you are given integers $L_{i}, R_{i}$ between $1$ and $N$, inclusive. Find $\mathrm{LCM}(A_{L_{i}}, A_{L_{i} + 1}, \dots, A_{R_{i}})$ modulo $998244353$.

However, the queries must be processed online.

For this reason, instead of $L_{i}, R_{i}$, you are given integers $a_{i}, b_{i}$ that are at least $0$ and less than $998244353$. Restore $L_{i}, R_{i}$ using the following procedure.

• Let $ans_{i}$ be the answer to the $i$-th query, where $ans_{0} = 1$.
• Let $x_{i}$ be the remainder when the product of $a_{i}$ and $ans_{i - 1}$ is divided by $998244353$.
• Let $y_{i}$ be the remainder when $x_{i}$ is divided by $N$, plus $1$.
• Let $z_{i}$ be the remainder when the product of $b_{i}$ and $ans_{i - 1}$ is divided by $998244353$.
• Let $w_{i}$ be the remainder when $z_{i}$ is divided by $N$, plus $1$.
• Then, $L_{i} = \min(y_{i}, w_{i})$ and $R_{i} = \max(y_{i}, w_{i})$ hold.

Constraints

• $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$
• All input values are integers.

Input

The input is given from standard input in the following format.

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

Output

Print $Q$ lines. On the $i$-th line, print the answer to the $i$-th query.

Sample

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