Pear Trees

Alin wants to start a new life as a farmer in the countryside of Sălaj. He has planted a row of $N$ pear trees, numbered from $1$ to $N$ in the order in which they were planted. The pear tree $i$ ($1 \leq i \leq N$) has $P_i$ flowers. Now he is thinking about pollinating the trees by releasing some bees.

Alin studies $Q$ scenarios in which pollination can take place. For each scenario $j$ ($1 \leq j \leq Q$):

• he chooses an interval [$L_j$, $R_j$];
• releases the bees at the $L_j$ pear tree;
• the bees will then visit all pear trees to the right, in order, up to the $R_j$ pear tree, including $R_j$.

The Sălaj pear trees have a special way of interacting with bees:

• if the number of flowers in the currently visited tree, call that number $X$, has the same parity as the number of flowers in the previous tree, call that number $Y$, then the number of flowers in the current tree will increase to $X \cdot Y$;
• otherwise, the current tree will bloom $Y$ new flowers, increasing its total to $X+Y$.

For each scenario $j$ ($1 \leq j \leq Q$), Alin wants to know the number of flowers in the $R_j$-th pear tree at the end of the pollination for this scenario. Since this number may be very large, output it modulo $998 \ 244 \ 353$.

Task

Given the number of flowers for each pear tree, compute the result for each scenario modulo $998 \ 244 \ 353$.

Input data

The first line of the input contains the integer $N$ - the number of pear trees.

The second line of the input contains $N$ integers separated by spaces - the number of flowers in each pear tree.

The third line of the input contains the integer $Q$ - the number of scenarios.

Each of the next $Q$ lines contain $2$ space-separated integers - $L_j$ and $R_j$ - the left and right ends for the interval of trees that will be pollinated in the $j$-th scenario.

Output data

The output will contain $Q$ lines. On line $j$ ($1 \leq j \leq Q$), the result for scenario $j$ will be printed.

Constraints and clarifications

• $1 \leq N, Q \leq 200 ' 000$
• $0 \leq P_i \leq 998 \ 244 \ 352$ for $1 \leq i \leq N$.
• $1 \leq L_j \leq R_j \leq N$ for $1 \leq j \leq Q$.
• All scenarios are independent

Example 1

stdin

5
4 2 5 7 8
3
1 3
4 5
1 5

stdout

13
15
99

Explanation

For the first example, each scenario goes as follows:

$\underline{\textbf{4}}\ \textbf{2}\ \underline{5}\ 7\ 8 \rightarrow \underline{4}\ \textbf{8}\ \underline{\textbf{5}}\ 7\ 8 \rightarrow \underline{4}\ 8\ \underline{\textbf{13}}\ 7\ 8$

$4\ 2\ 5\ \underline{\textbf{7}}\ \underline{\textbf{8}} \rightarrow 4\ 2\ 5\ \underline{7}\ \underline{\textbf{15}}$

$\underline{\textbf{4}}\ \textbf{2}\ 5\ 7\ \underline{8} \rightarrow \underline{4}\ \textbf{8}\ \textbf{5}\ 7\ \underline{8} \rightarrow \underline{4}\ 8\ \textbf{13}\ \textbf{7}\ \underline{8} \rightarrow \underline{4}\ 8\ 13\ \textbf{91}\ \underline{\textbf{8}} \rightarrow \underline{4}\ 8\ 13\ 91\ \underline{\textbf{99}}$

Example 2

stdin

3
100000 100000 100000
1
1 3

stdout

733427426

Explanation

For the second example, the answer is $1000000000000000$, which modulo $998 \ 244 \ 353$ is equal to $733427426$.