Bob has an array A[] of N 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:
Note: It is guaranteed that there is at least 1 type-3 query in the every test case. All the array elements will fit into 64 bit integers.
Input Format:
First line consists of two space-separated integers N and Q.
Next, Q lines consist of Q operations of either of the 3 types as described above.
Output Format:
For each type-3 query print the answer that is the no. of '1' in the resulting string.
Constraints:
\(1 \le N,Q \le 500000\)
\(1 \le X \le Y \le N\)
Initially, A=[0,0,0,0,0]
After 1st query, A=[1,0,0,0,0]
After 2nd query, A=[1,1,0,0,0]
After 3rd query, A=[1,1,1,0,0]
For 4th query, no. of '1' in binary representation of A[1]=A[2]=A[3]=1. So, answer=3.
For 5th query, answer is 2.
Challenge Name
MakeMyTrip Java Developer Hiring Challenge
MakeMyTrip Java Developer Hiring Challenge