题目描述
Asif loves chocolates. He eats a lot of chocolates every day and has become very fat. So his father has decided to make him walk.
Asif's father has given him a binary tree of N nodes. Some of these nodes would contain chocolates(A node can contain maximum one chocolate). Now Asif's father asks him to start from a node numbered M. Asif is allowed to eat chocolate only while standing on this node. Also he can carry only one chocolate at a time. So Asif will start from M, collect any one chocolate and bring it back to M, and eat it. He continues this process until no chocolates are left.
Initially there will be no chocolates on any nodes
You task is to process queries of 2 types.
Type 0: For the given M, find out the distance that Asif should walk to collect all the chocolates.
Type 1: Place a chocolate on node M(if it doesn't already contain a chocolate).
Note : After processing a query of type 0, you should not remove the chocolates from the nodes.
Root of the tree will be numbered 1, and a node numbered x will have children numbered 2x and 2x+1. Distance between any two connected nodes is 1.
Input:
First line will contain N(1 ≤ N ≤ 100000), no of nodes.
Next line will contain Q(1 ≤ Q ≤ 100000), number of queries you need to process
Each of the next Q lines will contain two integers, Type(0 or 1) and M(1 ≤ M ≤ N).
Output:
For each query of Type 0, print the distance that Asif should walk.
SAMPLE INPUT
6
9
0 1
1 4
0 2
1 5
0 1
1 4
0 1
1 1
0 6
SAMPLE OUTPUT
0
2
8
8
20
Explanation
0 1: There are no chocolate initially, so output 0
1 4: Chocolate added to node 4
0 2: Path traversed is 2->4->2 so output 2
1 5: Chocolate added to node 5
0 1: Path traversed, 1->2->4->2->1->2>5>2>1 output 8
1 4: Node 4 already had a chocolate. So do nothing
0 1: Path traversed, 1->2->4->2->1->2>5>2>1 output 8
1 1: Chocolate added to node 1
0 6: Path traversed 6->3->1>2->4->2->1->3->6->3->1->2->5->2->1->3->6 ->3->1->3->6 output 20.
输入格式
见题面
输出格式
见题面