Tree Visits

There is a perfect binary tree of height $N$. It has $2^{N+1}-1$ nodes in total, and $2^N$ of them are leaves at depth $N$.

You walk down the tree using an $N$-bit binary number $X$. Read the bits of $X$ starting from the leftmost one: a 0 takes you to the left child, a 1 takes you to the right child. For example, when $N = 2$, $X = 0 = 00_2$ takes you to the leftmost leaf, and $X = 3 = 11_2$ takes you to the rightmost leaf. With $X = 2 = 10_2$ you move from the root to its right child, then to that child's left child.

At the very beginning $X = 0$ and only the root has been visited. Write a program that processes the following two queries.

• 1 C: change $X$ to $(X + 2^C) \bmod 2^N$. Then walk down from the root using the new $X$ and visit every node you pass. The root and the leaf you land on both count as visited nodes.
• 2: print how many distinct nodes have been visited so far. A node visited several times is counted once.

The first line contains the height $N$ of the tree and the number of queries $Q$. ($1 \le N, Q \le 10^5$)

Each of the next $Q$ lines contains one query. A query of the first kind has the form 1 C with $0 \le C < N$. A query of the second kind is the single character 2, and at least one such query is given.

For each query of the second kind, print the number of distinct visited nodes on its own line.