Counting Stars

As an elegant and accomplished girl, Bella loves watching stars at night (especially the Polaris). There are totally $n$ stars in the sky. We can define $a_i$ as the initial $brightness$ of $i$-th star.

At $t$-th second, the $brightness$ of some stars may change due to stars' activity. To simplify this problem, we can approximately divide activities into two kinds:

1. $\forall i \in [l,r]$ , the $brightness$ of $i$-th star decreases by $a_i \& (-a_i)$
2. $\forall i \in [l,r], a_i \neq 0$ , the $brightness$ of $i$-th star increases by $2^k$, where $k$ satisfy $2^k\leq a_i < 2^{k+1}$

Also, Bella has some queries. For each query, she wants to know the $sum$ of $brightness$ of stars in the range $[l,r]$, which means $\sum_{i=l}^r a_i$

As we all know, Bella is a big smart. Thus, she could not solve such difficult problem by herself. Please help her solve this problem and answer her queries.

Since the answer may be too large, please output the answer modulo $998244353$

The first line contains an integer $T(T \leq 5)$ , denoting the number of test cases.

For each test case:

The first line contains an integers $n(1 \leq n \leq 100000)$, denoting the number of stars .

The second line contains $n$ integers $a_1,a_2,\dots,a_n (1 \leq a_i \leq 10^9)$, denoting the initial $brightness$ of stars.

The third line contains an integer $q(1 \leq q \leq 100000)$, denoting the number of operations.

Each of the next $q$ lines contains three integers $opt_i,l_i,r_i$, denoting the kind of operations and ranges.

$opt_i=1$ means Bella's query.

$opt_i=2$ means the first kind of stars' activity.

$opt_i=3$ means the second kind of stars' activity.

It is guaranteed that for all test cases, $\sum n \leq 4 \times 10^5,\sum q \leq 4 \times 10^5$.

For each Bella's query, output the answer modulo $998244353$ in a single line.

1

5

5 2 2 9 7

4

2 1 5

1 1 1

3 1 3

1 2 5

4

14

2021“MINIEYE杯”中国大学生算法设计超级联赛（8）