408469: GYM103145 D Lowbit

Lucida has a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. He asks you to perform two types of operations for him, which are described as follows:

1. 1 L R, add $$$lowbit(a_i)$$$ to each $$$a_i$$$ in the interval $$$[L, R]$$$.

2. 2 L R, query the sum of the numbers in the interval $$$[L, R]$$$.

$$$lowbit(x)$$$ is defined as the largest power of 2 that divides $$$x$$$. For example, lowbit(4)=4, lowbit(5)=1. Specially, lowbit(0)=0.

Lucida wants you to give the answer modulo $$$998244353$$$ for each of his queries.

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1\leq T \leq 20$$$) indicating the number of test cases.

For each case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the length of the sequence.

The next line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i < 998244353$$$) separated by spaces, representing the sequence.

The next line contains an integer $$$m$$$ ($$$1 \leq m \leq 10^5$$$), the number of operations.

The next $$$m$$$ lines, each line contains 3 integers $$$op, L, R$$$ ($$$1 \leq op \leq 2$$$, $$$1 \leq L \leq R \leq n$$$), represents one operation. The specific meaning is described above.

For each query, output a line contains the answer modulo $$$998244353$$$.

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

9
12
14