🏡 index : github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: RBTREE
problem_name: 'Chef and Red Black Tree'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: ma5termind
problem_tester: null
date_added: 28-09-2014
tags:
    - ad
    - easy
    - graph
    - lca
    - ma5termind
    - nov14
editorial_url: 'http://discuss.codechef.com/problems/RBTREE'
time:
    view_start_date: 1416216600
    submit_start_date: 1416216600
    visible_start_date: 1416216600
    end_date: 1735669800
    current: 1493558178
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/NOV14/mandarin/RBTREE.pdf) and [Russian](http://www.codechef.com/download/translated/NOV14/russian/RBTREE.pdf).

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. 1<=Q<=105** 
**1. 1<=x,y<=109** 


**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<=103 1<=x,y<=105 : **25 pts****
- Subtask #3: **1<=Q<=105 1<=x,y<=109 : **48 pts****