题目描述

有一排 $N$ 棵梨树，编号为 $1$ 到 $N$。第 $i$ 棵树初始有 $P_i$ 朵花。

每次询问给出一个区间 $[L,R]$。蜜蜂从第 $L$ 棵树开始，依次访问

$$L,L+1,\ldots,R.$$

第 $L$ 棵树的花数保持为 $P_L$。当蜜蜂从前一棵树来到当前树时，设当前树原本有 $X$ 朵花，前一棵树在本次过程中的最终花数为 $Y$：

• 若 $X$ 与 $Y$ 奇偶性相同，当前树的花数变为 $X\cdot Y$；
• 否则，当前树的花数变为 $X+Y$。

对于每个询问，求本次过程中第 $R$ 棵树最终的花数，答案对 $998244353$ 取模。

各次询问彼此独立，不会修改原数组。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

第三行包含整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $L,R$。

输出格式

对每次询问输出一行答案。

数据范围

• $1\le N,Q\le200000$；
• $0\le P_i\le998244352$；
• $1\le L\le R\le N$。

子任务

子任务	分值	限制
1	0	样例
2	13	$N,Q\le1000$
3	14	$P_i\le1$
4	8	$N\le1000$
5	9	所有 $P_i$ 奇偶性相同
6	56	无额外限制

样例一

输入

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

输出

13
15
99

例如区间 $[1,5]$ 中，花数依次变为：

$$[4,2,5,7,8] \to[4,8,5,7,8] \to[4,8,13,7,8] \to[4,8,13,91,8] \to[4,8,13,91,99].$$

样例二

输入

3
100000 100000 100000
1
1 3

输出

733427426

实际结果为 $10^{15}$，取模后为 $733427426$。