2319. 地球往事

【题目描述】

地球三体组织的头领叶文洁需要跟三体组织进行交流，三体组织为了保密信息，使用了一种神奇的加密方式:

刚开始给定一个初始的数列$a_1,a_2.....a_n$

每次的新信息是通过修改原有的信息传输的.

修改操作:

$xor$ l r x

$or$ l r x

$and$ l r x

表示$a_l,a_{l+1}.....a_{r-1}$,$a_r$分别xor x,or x,and x

查询操作：

$query$ l r

表示$a_l,a_{l+1}.....a_{r-1},a_r$的区间和

区间和就是这次要传输的新信息，至于区间和表达了什么意思，这就和你没有关系了（需要进行解密）.

你的任务是又快又准的求出每次的区间和

【输入格式】

第一行一个整数$n$

第二行$n$个整数$a_1,a_2...a_n$

接下来一个整数$q$,表示修改和查询的总次数

接下来$q$行，表示$q$个操作

【输出格式】

对于每个"query"输出一行，表示区间和

【样例输入】

10
82 75 64 119 24 37 65 1118 2223 4445
10
xor 7 9 4105
query 3 8
or 2 5 1113
query 4 9
and 4 8 410105
query 2 6
xor 1 9 110
and 2 4 8
or 2 7 1555
query 3 7

【样例输出】

9619
17986
2471
7923

【数据范围】

对于20%的数据$N<=2000$

对于100%的数据$N<=100000,x<=10000000$

对于100%的数据$q=N$