# Playing With BITs

Limits 1s, 512 MB

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 ≤ rN, 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

InputOutput
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


Login to submit.

### Statistics

79% Solution Ratio
CLown1331Earliest, Mar '18
nusuBotFastest, 0.1s
iammarajulLightest, 1.0 MB
iammarajulShortest, 726B
Toph uses cookies. By continuing you agree to our Cookie Policy.