Little boy Tom recently learnt about BIT operation. And he is interested in it. So he himself plays the game with BITs. Seeing this, great programmer Jerry give him a task. Initially, Jerry gives an array with N numbers and Q queries.
There are two types of quires:
1 i X: Change i-th element to X i;e make A[i] = X.
2 l r k: Find the number of elements in the range l to r, whose k-th bit is set i;e 1. This means, find the number of such elements A[i] where l <= i <= r and k-th bit of A[i] is 1.
Here, A[i] is the i-th element of the array Jerry gave.
As Tom is not master at BIT operation, he wants your help. Can you help him?
Input
Input starts with N denoting the size of the array.
Then N integers.
In the next line Q denoting the number of queries.
Next, Q lines define queries stated above.
1 i x
2 l r k
Constraints
1 ≤ N, Q ≤ 100000
0 ≤ Array element ≤ 2^60.
1 ≤ l ≤ r ≤ N, 0 ≤ k ≤ 60.
Output
For each query of second type, print an integer denoting the number of elements in the range l to r whose k-th bit is set.
Sample
| Input | Output |
|---|---|
5 1 2 3 4 5 5 1 2 4 2 4 4 3 2 2 4 2 1 1 7 1 1 5 | 0 2 |
