F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Counting Stars

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3196    Accepted Submission(s): 996


Problem Description
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$
 

Input
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$.
 

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

Sample Input
1 5 5 2 2 9 7 4 2 1 5 1 1 1 3 1 3 1 2 5
 

Sample Output
4 14
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 17:33:22, Gzip enabled