Chef and Red Black Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef likes trees a lot. Today he has an infinte full binary tree (each node has exactly two childs) with special properties.
Chef's tree has the following special properties :
 Each node of the tree is either colored red or black.
 Root of the tree is black intially.
 Both childs of a red colored node are black and both childs of a black colored node are red.
The root of the tree is labelled as 1. For a node labelled v, it's left child is labelled as 2*v and it's right child is labelled as 2*v+1.
Chef wants to fulfill Q queries on this tree. Each query belongs to any of the following three types:
 Qi Change color of all red colored nodes to black and all black colored nodes to red.
 Qb x y Count the number of black colored nodes on the path from node x to node y (both inclusive).
 Qr x y Count the number of red colored nodes on the path from node x to node y (both inclusive).
Help chef accomplishing this task.
Input
First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line). Each query belongs to one of the three types mentioned above.
Output
For each query of type Qb or Qr, print the required answer.
Constraints
 1<=Q<=10^{5}
 1<=x,y<=10^{9}
Sample Input
5
Qb 4 5
Qr 4 5
Qi
Qb 4 5
Qr 4 5
Sample Output
2
1
1
2
Explanation
With the initial configuration of the tree, Path from node 4 to node 5 is 4>2>5 and color of nodes on the path is B>R>B.
 Number of black nodes are 2.
 Number of red nodes are 1.
After Query Qi, New configuration of the path from node 4 to node 5 is R>B>R.
 Number of black nodes are 1.
 Number of red nodes are 2.
Scoring
 Subtask #1: 1<=Q<=100 1<=x,y<=1000 : 27 pts
 Subtask #2: 1<=Q<=10^{3} 1<=x,y<=10^{5} : 25 pts
 Subtask #3: 1<=Q<=10^{5} 1<=x,y<=10^{9} : 48 pts
Author:  ma5termind 
Editorial  http://discuss.codechef.com/problems/RBTREE 
Tags  adhoc, easy, graph, lca, ma5termind, nov14 
Date Added:  28092014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 