U319390 【230727 B2】star

小 B 喜欢观星。

今夜，她又关注到了天空中的一排，共 n 颗星星。初始时它们的亮度依次为a1, a2, · · · , an 小 B 发现这些星星的亮度会发生特定的变化，有如下两种可能： 1. [l, r] 内的所有星星 i 的亮度 ai 减少 lowbit(ai) ($lowbit(x) = \min{2^k: k ∈ N, 2^k|x}$) 2. [l, r] 内的所有亮度不为 0 的星星亮度增加 $2^{f(ai)}$，其中 f(ai) 为唯一的整数 k 满足$2^k ≤ ai < 2^{k+1}$ 小 B 想请你帮忙计算星星亮度的和，她将 q 个时刻的事件告诉了你，每个时刻可能是一次星星亮度的变化，或是小 B 向你询问一个区间 [l, r] 内所有星星亮度的和。 由于结果可能很大，此时你需要回答答案 mod 998244353 的值。

第一行一个整数 n 接下来一行 n 个整数，依次为 a1, a2, · · · , an，描述星星亮度 接下来一行一个整数 q 表示小 B 给出的事件总数 接下来 q 行，每行三个整数 op, l, r，按照时间顺序给出事件，如果 op = 1，该事件为询问；如果op = 2，表示一次 a 事件；如果 op = 3，表示一次 b 事件。

对于每次询问，即 op = 1，输出一个整数表示答案。

#### 样例 1 解释 第一个事件后星星的亮度分别为 4, 0, 0, 8, 6 第三个事件后星星的亮度分别为 8, 0, 0, 8, 6 #### 数据范围 - 对于 30% 的数据，$n, q ≤ 1000$ - 对于 50% 的数据，$n ≤ 50000$ - 对于另外 20% 的数据，$op \in \{1, 3\}$ - 对于 100% 的数据，$1 ≤ n ≤ 100000, 1 ≤ q ≤ 50000, op \in \{1, 2, 3\}, 1 ≤ l ≤ r ≤ n, 1 ≤ ai ≤ 10^9$