Walks on the binary tree

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
You have a perfect binary tree of height N. That is, it contains 2^{N+1}  1 nodes.
A path from the root to a leaf can be represented by an integer X which lies between 0 and 2^{N}  1 (both inclusive) as follows:
Consider the N length binary representation of X. Start reading from the left, and at each bit, 0 denotes going to the left child, and 1 denotes going to the right child. For eg. if N = 2, and X = 0 = (00)_{2}, it would correspond to the path which goes to the leftmost leaf. X = 3 = (11)_{2} would correspond to the path from root to the rightmost leaf.
At the beginning, X = 0, and you have visited only the root till now. Then, you get Q queries. A query can be of two types:
 Type 1: "! C": This means that X has to be changed to X = ( X + 2^{C} ) mod 2^{N}, and then you start from the root, and walk down the route represented by the new X.
 Type 2: "?": This means that you should print the number of nodes that you have visited at least once.
Input
 The first line contains a single integer T, which denotes the number of testcases. The description of each testcase follows.
 The first line of each testcase contains two integers: N and Q, which denote the height of the tree and the number of the queries respectively.
 Q lines follow, which are the descriptions of the queries. Each line will either be a "! C" or a "?" (without quotes).
Output
For each query of Type 2, you have to print one integer in a new line
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, Q ≤ 10^{5}
 0 ≤ C < N
 The sum of N over all testcases does not exceed 10^{5}, and sum of Q over all testcases does not exceed 10^{5}
Subtasks
 Subtask 1 (30 points) : The sum of N over all testcases does not exceed 2000, and sum of Q over all testcases does not exceed 2000
 Subtask 2 (70 points) : Original constraints
Example
Input: 1 2 9 ! 0 ? ! 1 ? ! 0 ? ! 0 ! 0 ? Output: 3 5 6 7
Explanation
Let us label the tree nodes as follows:
The node 0 corresponds to the root.
At the beginning, X = 0, and then after the first query, X becomes 0 + 2^{0} mod 4 = 1 = (01)_{2}. The path 0  1  4 is traveled along.
The next query asks for the number of visited nodes, which is 3.
In the third query, X becomes 1 + 2^{1} mod 4 = 3 = (11)_{2}. The path 0  2  6 is traveled along.
The fourth query asks for the number of visited nodes. The visited nodes are {0, 1, 4, 2, 6}. Hence the answer is 5.
In the fifth query, X becomes 3 + 2^{0} mod 4 = 0 = (00)_{2}. The path 0  1  3 is traveled along.
The sixth query asks for the number of visited nodes. The visited nodes are {0, 1, 4, 2, 6, 3}. Hence the answer is 6.
In the seventh query, X becomes 0 + 2^{0} mod 4 = 1 = (01)_{2}. The path 0  1  4 is traveled along.
In the eight query, X becomes 1 + 2^{0} mod 4 = 2 = (10)_{2}. The path 0  2  5 is traveled along.
The ninth query asks for the number of visited nodes. The visited nodes are {0, 1, 4, 2, 6, 3, 5}. Hence the answer is 7.
Author:  altruist_ 
Editorial  https://discuss.codechef.com/problems/WALKBT 
Tags  altruist_, aug17, datastructure, hard, lazypropagation, persistence, segmenttree 
Date Added:  21072017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions