Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Playing With BITs

By jisan047 · 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

Discussion

Statistics


78% Solution Ratio

CLown1331Earliest, Mar '18

maruf089Fastest, 0.2s

iammarajulLightest, 1.0 MB

iammarajulShortest, 726B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.