Harry, Ron and Hermione decide to take part in this year's ACM ICPC and show the world that they are excellent in coding as well. So they start preparing for the contest at full throttle.

They encounter an interesting problem. Since you also seem to be interested in ACM ICPC, let's see if you can solve this problem quicker than them. The problem is about an array, a, and some operations which are to be performed on the array. The array contains unsigned integers of size 4 bytes. The operations performed on the array are :

1. Blip: Given two indices l and r, and a number k, you need to perform a clockwise cyclic rotation of the binary representation of the elements of the array in the range [l,r], k times.
   In a single clockwise cyclic rotation operation for an element x, the right-most bit of x becomes the left-most bit and each of the remaining bit is shifted one time to the right. For example, Blip(1010₂) = 0101₂.
   In a single Blip operation, you need to perform such a rotation k times for each element a_i where l ≤ i ≤ r.
2. Flip: Given two indices l anr r, you need to flip the bits of each element of the array in the range [l,r].
   Flip operation on an element x simply flips the bits in the binary representation of x. For example, Flip(0110₂) = 1001₂.
You need to perform this operation for each element of the array in the range [l,r].
3. Tell: Given two indices l and r, you need to tell the sum of the elements of the array in the range [l,r].

Your time begins now! Let's see if you can defeat Harry, Ron and Hermione or not!

Input:

First line of the input contains an integer n, the size of the array.
The next line contains n space separated integers, a_i, the elements of the array.
The next line contains an integer q, the number of operations to be performed on the array.
The next q lines describe the q operations to be performed.
For each operation, the first input is an integer type, the type of the operation to be performed.
- If type=1, three integers follow, l, r and k, which are the same as those defined for the Blip operation. You need to perform the Blip operation for the given values of l, r and k in this operation.
- If type=2, two integers follow, l and r, which are the same as described for Flip operation. You need to perform the Flip operation for the given values of l and r in this operation.
- If type=3, two integers follow, l and r, which are the same as described for Tell operation. You need to perform the Tell operation for the given values of l and r in this operation.

Output:

For each Tell operation, print the result of the operation, i.e. the sum of the array elements in the range [l,r] in a separate line.

Constraints:

1 ≤ n ≤ 10⁵
0 ≤ a_i < 2³²
1 ≤ q ≤ 10⁵
type ∈ {1,2,3}
0 ≤ l ≤ r < n
0 ≤ k ≤ 10⁹

Additional constraints for 20 points:
1 ≤ n ≤ 1000
1 ≤ q ≤ 1000

Note: The elements of the array are of the type unsigned Integer of size 4 bytes.

Setter - Sahil Prakash