Question
Binary Operations and Count Query
You are given a list B of size N (1-indexed), where all elements are initially set to 0. You need to perform Q operations on this list. Each operation is one of the following types:
- 1 X: Update BX to 2 * BX + 1.
- 2 X: Update BX to BX / 2 (integer division).
- 3 X Y: Convert all integers from BX to BY (inclusive) to their binary forms, concatenate them, and count the total number of 1s. Print this count.
Input
The first line of the input contains two space-separated integers N, the size of array and Q, the number of queries.
The next Q lines each contain a single query.
The next Q lines each contain a single query.
Output
Perform each query sequentially and print the answer to each query of third type in a 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.