  InterviewBit Academy is now Scaler Academy! # Bob and Queries

Bob has an array W of A integers. Initially, all the elements of the array are zero. Bob asks you to perform Q operations on this array.

There are three types of operations that can be performed

1 X -1: Update the value of A[X] to 2 * A[X] + 1.

2 X -1: Update the value A[X] to ⌊A[x]/2⌋ , where ⌊⌋ is Greatest Integer Function.

3 X Y: Take all the A[i] such that X <= i <= Y and convert them into their corresponding binary strings.
Now concatenate all the binary strings and find the total no. of ‘1’ in the resulting string.

Input Format

``````The first argument has the integer A.
The second argument is a 2d matrix B, of size Q x 3, representing the queries.
``````

Output Format

``````Return an array of integers where ith index represents the answer of the ith type 3 query.
``````

Constraints

``````1 <= A, Q <= 500000
1 <= X, Y <= N
``````

For Example

``````Input 1:
A = 5
B = [   [1, 1, -1]
[1, 2, -1]
[1, 3, -1]
[3, 1, 3]
[3, 2, 4]   ]
Output 1:
[3, 2]
Explanation 1:
=> [0, 0, 0, 0, 0]
=> [1, 0, 0, 0, 0]
=> [1, 1, 0, 0, 0]
=> [1, 1, 1, 0, 0]
=> Concatenation of Binary String between index 1 and 3 : 111
Output : 3
=> Concatenation of Binary String between index 2 and 4 : 110
Output : 2

Input 2:
A = 5
B = [   [1, 1, -1]
[1, 2, -1]
[3, 1, 3]
[2, 1, -1]
[3, 1, 3]   ]
Output 2:
[2, 1]
Explanation 2:
=> [0, 0, 0, 0, 0]
=> [1, 0, 0, 0, 0]
=> [1, 1, 0, 0, 0]
=> Concatenation of Binary String between index 1 and 3 : 110
Output : 2
=> [0, 1, 0, 0, 0]
=> Concatenation of Binary String between index 2 and 4 : 010
Output : 1
``````
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details. 