Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Let’s play a game.We add numbers 1,2...n in increasing order from 1 and put them into some sets.

When we add i,we must create a new set, and put iinto it.And meanwhile we have to bring [i-lowbit(i)+1,i-1] from their original sets, and put them into the new set,too.When we put one integer into a set,it costs us one unit physical strength. But bringing integer from old set does not cost any physical strength.

After we add 1,2...n,we have q queries now.There are two different kinds of query:

1 L R:query the cost of strength after we add all of [L,R](1≤L≤R≤n)

2 x:query the units of strength we cost for putting x(1≤x≤n) into some sets.

When we add i,we must create a new set, and put iinto it.And meanwhile we have to bring [i-lowbit(i)+1,i-1] from their original sets, and put them into the new set,too.When we put one integer into a set,it costs us one unit physical strength. But bringing integer from old set does not cost any physical strength.

After we add 1,2...n,we have q queries now.There are two different kinds of query:

1 L R:query the cost of strength after we add all of [L,R](1≤L≤R≤n)

2 x:query the units of strength we cost for putting x(1≤x≤n) into some sets.

There are several cases,process till end of the input.

For each case,the first line contains two integers n and q.Then q lines follow.Each line contains one query.The form of query has been shown above.

n≤10^18,q≤10^5

For each case,the first line contains two integers n and q.Then q lines follow.Each line contains one query.The form of query has been shown above.

n≤10^18,q≤10^5

9 2lowbit(i) =i&(-i).It means the size of the lowest nonzero bits in binary of i. For example, 610=1102, lowbit(6) =102= 210 When we add 8,we should bring [1,7] and 8 into new set. When we add 9,we should bring [9,8] (empty) and 9 into new set. So the first answer is 8+1=9. When we add 6 and 8,we should put 6 into new sets. So the second answer is 2.Hint

提交代码