题目描述

$Oxy$ 得到了一段长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$。他需要支持两种操作：

• $\text{1}$ $l$ $r$：对于所有 $l \leq i \leq r$，将 $a_i$ 增加 $\mathrm{lowbit}(a_i)$；
• $\text{2}$ $l$ $r$：查询区间 $[l, r]$ 内所有元素的和。

其中，$\mathrm{lowbit}(x)$ 表示整数 $x$ 的二进制表示中最低位的 $1$ 所对应的数值，即

例如 $\mathrm{lowbit}(4)=4$，$\mathrm{lowbit}(5)=1$，以及特别地，$\mathrm{lowbit}(0)=0$。

对于每次查询操作，你需要输出区间和对模数 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）--- 序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \leq a_i \leq 998244352$) --- 初始序列。

第三行包含一个整数 $q$ ($1 \leq q \leq 10^5$)--- 操作的数量。

接下来的 $q$ 行中，每行包含三个整数 $op, l, r$ ($1 \le op \le 2$，$1 \le l \le r \le n$)，表示一次操作：

• 若 $op = 1$，对区间 $[l, r]$ 内每个元素执行 $a_i \leftarrow a_i + \mathrm{lowbit}(a_i)$；
• 若 $op = 2$，询问当前区间 $[l, r]$ 内所有元素之和。

输出格式

对于每个询问，输出区间元素之和对 $998244353$ 取模的结果。

样例

6
1 2 3 4 5 6
5
1 3 6
2 1 4
1 1 5
2 1 6
2 3 6

15
46
40

1
998244352
2
1 1 1
2 1 1

8388607