eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Queries on anti-xor

Queries on anti-xor

Ліміт часу 2.5 секунди
Ліміт використання пам'яті 64 MiB

Recently our coach - Etibar has invented a new bitwise operation. It is like a reverse of xor operation. Then called it as anti-xor. Now he is giving you a new problem which is related to his invention on queries. The sign of anti-xor is #.

You are given N number. Perform the following operations on those integers.

1) Anti-xor X with integer from L to R. This query is represented as “1 L R X

2) Output the sum of all numbers from L to R. This query is represented as “2 L R

Assume that all numbers are 20 bits integers. So you do anti-xor operation on last 20 bits.

Вхідні дані

You are given an integer N (1N100000). In the second line you are given N integers (0A_i10^6). The next line contains the number of queries Q (1Q100000). Each of the next Q lines contains one query of one of the forms above.

Вихідні дані

For each query of the type “2 L R” print on a separate line the sum of all integers from L to R.

Приклад

Вхідні дані #1
5
4 6 10 123 456
6
1 1 5 6
1 3 4 10
2 2 5
1 2 4 7
2 1 5
2 2 3
Вихідні дані #1
2096813
4193730
1048581
Автор Mahammad Valiyev
Джерело Local Contest #2 Qafqaz University by Mahammad Valiyev