Question
Array Snap
Zara holds an array B of size M (1-indexed), initialized with all zeros. She needs to perform P queries on this array. Each query is one of the following types:
-
Type 1 Y
Perform:B[Y] = 2 × B[Y] + 1
(Appends a1to the binary representation ofB[Y].) -
Type 2 Y
Perform:B[Y] = floor(B[Y] / 2)
(Removes the least significant bit from the binary representation ofB[Y].) -
Type 3 Y Z
For alliin the rangeY ≤ i ≤ Z, concatenate the binary representations ofB[i], count the total number of'1'bits in this concatenated string, and print the result.
You must process all queries in the order given. For each Type 3 query, output the answer on a new line.
Input
The first line of the input contains two integers M, the size of array and P, the number of queries.
The next P lines each contain a single query.
Constraints
1 ≤ P, M ≤ 5 x 105
1 ≤ Y ≤ Z ≤ M
The next P lines each contain a single query.
Constraints
1 ≤ P, M ≤ 5 x 105
1 ≤ Y ≤ Z ≤ M
Output
Perform each query sequentially and print the answer to each query of third type in new line.
Example
Sample Input
5 6
1 1
1 2
1 3
3 1 3
3 2 4
3 1 5
Sample Output
3
2
3
Explanation
Initially, B=[0, 0, 0, 0, 0]
After 1st query, B=[1, 0, 0, 0, 0]
After 2nd query, B=[1, 1, 0, 0, 0]
After 3rd query, B=[1, 1, 1, 0, 0]
For 4th query, number of ones in binary representation of B[1] = B[2] = B[3] = 1. So, answer is 3.
For 5th query, answer is 2.
For 6th query, answer is 3.
5 6
1 1
1 2
1 3
3 1 3
3 2 4
3 1 5
Sample Output
3
2
3
Explanation
Initially, B=[0, 0, 0, 0, 0]
After 1st query, B=[1, 0, 0, 0, 0]
After 2nd query, B=[1, 1, 0, 0, 0]
After 3rd query, B=[1, 1, 1, 0, 0]
For 4th query, number of ones in binary representation of B[1] = B[2] = B[3] = 1. So, answer is 3.
For 5th query, answer is 2.
For 6th query, answer is 3.