Complete Binary Tree and Queries

Time limit3sMemory limit1024 MB

Summary

Given a complete binary tree with N vertices and a movable root, answer queries for the sum of vertex numbers in the subtree of v under the current root.

Level: Medium5 of 10
Topics: Math, Tree, Implementation
Solved: No attempts yet

Problem

There is a complete binary tree with $N$ vertices. Initially, vertex $1$ is the root. For every vertex $x$ except vertex $1$ , vertex $x$ has vertex $\lfloor \frac x2 \rfloor$ as its parent.

Process the following queries on this tree.

1 v: Change the root of the tree to vertex $v$ .
2 v: Print the sum of the numbers of all vertices in the subtree rooted at vertex $v$ in the current tree.

Input

The first line contains $N$ and $Q$ separated by a space. ( $1 \le N \le 1\,000\,000\,000$ ; $1 \le Q \le 50\,000$ )

The next $Q$ lines each contain one query. At least one query of type 2 is given. ( $1 \le v \le N$ )

Output

For each query of type 2, print the answer on its own line.

Examples1

Example 1
Input
```
10 5
2 3
2 5
1 8
2 4
2 1
```
Expected output
```
16
15
47
17
```