题目描述

大黄蜂决定完成采集苔藓浆果的任务。为了不让自己感到无聊，她决定给每颗浆果评定美丽值。浆果的美丽值取决于它的种类，种类用一个非负整数表示。

大黄蜂有一个包含 $n$ 个数 $a_i$ 的数组。数组下标从 $0$ 开始。当她找到一颗种类为 $x$ 的浆果时，其美丽值按以下方式计算：

1. 将 $x$ 的二进制表示写成 $n$ 位：$\overline{b_{n-1}b_{n-2}\ldots b_0}$，其中 $b_0$ 是最低位。
2. 将所有满足 $b_i=1$ 的 $a_i$ 相乘。若没有满足条件的下标，则乘积为 $1$。
3. 将所得值记为 $f(x)=\prod_{i=0}^{n-1}a_i^{b_i}$，称为这颗浆果的美丽值。

一共有 $q$ 个可以找到苔藓浆果的地点。在第 $i$ 个地点，种类从 $l_i$ 到 $r_i$（包含端点）的每种浆果各有一颗。

请帮助大黄蜂求出每个地点中浆果美丽值的总和，也就是对每个 $i$ 计算 $\sum_{j=l_i}^{r_i}f(j)$。答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含一个整数 $n$，表示用于评定浆果美丽值的数组 $a$ 的长度，$1\le n\le60$。

第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$，表示计算美丽值时使用的乘数，$1\le a_i<998\,244\,353$。

第三行包含一个整数 $q$，表示生长苔藓浆果的地点数量，$1\le q\le2\cdot10^5$。

接下来 $q$ 行，每行包含两个整数 $l_i,r_i$，表示第 $i$ 个地点中浆果种类的区间，$1\le l_i\le r_i<2^n$。

输出格式

输出 $q$ 行，每行一个整数。第 $i$ 行应为第 $i$ 个地点所有浆果美丽值的总和对 $998\,244\,353$ 取模后的结果。

4
2 3 5 7
4
1 1
2 5
1 15
5 9

2
24
575
76