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 Format ------ 

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 Format ------ 

For each query of type Qb or Qr, print the required answer.

------ Constraints ------ 
 
1≤Q≤10^{5}
1≤x,y≤10^{9}

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$

----- Sample Input 1 ------ 
5
Qb 4 5
Qr 4 5
Qi
Qb 4 5
Qr 4 5

----- Sample Output 1 ------ 
2
1
1
2
----- explanation 1 ------ 
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.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Implementation


Solutions:
q = int(input())
from math import log, floor

def ancestor(x):
	ans = {1}
	while x != 1:
		ans.add(x)
		if x % 2:
			x = (x - 1) // 2
		else:
			x //= 2
	return ans

def path(x, y):
	x = ancestor(x)
	y = ancestor(y)
	common = x & y
	return {max(common)} | y - common | x - common
black = 0
red = 1
while q:
	q -= 1
	(f, *r) = input().split()
	if f == 'Qi':
		black ^= 1
		red ^= 1
	else:
		ans = 0
		if f == 'Qb':
			v = black
		else:
			v = red
		(x, y) = map(int, r)
		for y in path(x, y):
			level = floor(log(y, 2))
			if level % 2 == v:
				ans += 1
		print(ans)


reverse = 0
for _ in range(int(input())):
	s = input().split()
	if s[0] == 'Qb' or s[0] == 'Qr':
		x = int(s[1])
		y = int(s[2])
		binx = bin(x)[2:]
		biny = bin(y)[2:]
		m = len(binx)
		n = len(biny)
		a = 0
		if m < n:
			while a < m and binx[a] == biny[a]:
				a += 1
		else:
			while a < n and binx[a] == biny[a]:
				a += 1
		pathx = [x]
		start = m
		while start != a:
			x //= 2
			pathx.append(x)
			start -= 1
		start = n
		pathy = [y]
		while start != a:
			y //= 2
			pathy.append(y)
			start -= 1
		r = 0
		b = 0
		for i in range(len(pathx)):
			if pathx[i].bit_length() % 2 == 0:
				r += 1
			else:
				b += 1
		for i in range(len(pathy) - 1):
			if pathy[i].bit_length() % 2 == 0:
				r += 1
			else:
				b += 1
		if not reverse:
			if s[0] == 'Qb':
				print(b)
			else:
				print(r)
		elif s[0] == 'Qb':
			print(r)
		else:
			print(b)
	else:
		reverse ^= 1


from math import *

def color(x):
	c = floor(log(x, 2))
	return c % 2

def main():
	qb_means_black = True
	T = eval(input())
	for t in range(T):
		line = input()
		if len(line.split()) == 1:
			qb_means_black = not qb_means_black
			continue
		(q, x, y) = line.split()
		(x, y) = (int(x), int(y))
		(u, v) = (x, y)
		(u_path, v_path) = (0, 0)
		while u != v:
			if u > v:
				u //= 2
				u_path += 1
			else:
				v //= 2
				v_path += 1
		c = color(u)
		if c == 0:
			blacks = 1
			blacks += u_path // 2
			blacks += v_path // 2
			reds = 1 + u_path + v_path - blacks
		else:
			reds = 1
			reds += u_path // 2
			reds += v_path // 2
			blacks = 1 + u_path + v_path - reds
		if qb_means_black:
			if q == 'Qb':
				print(blacks)
			else:
				print(reds)
		elif q == 'Qb':
			print(reds)
		else:
			print(blacks)
main()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def help(levelX):
	if flag:
		Xblack = (levelX + 1) // 2
		Xred = levelX - Xblack
	else:
		Xred = (levelX + 1) // 2
		Xblack = levelX - Xred
	return (Xblack, Xred)
Q = inp()
flag = 1
for _ in range(Q):
	S = input().split()
	if len(S) == 1:
		flag ^= 1
	else:
		(color, x, y) = S
		if color == 'Qb':
			color = 0
		else:
			color = 1
		(x, y) = (int(x), int(y))
		levelX = 0
		sumX = 0
		while sumX + (1 << levelX) < x:
			sumX += 1 << levelX
			levelX += 1
		sumY = 0
		levelY = 0
		while sumY + (1 << levelY) < y:
			sumY += 1 << levelY
			levelY += 1
		levelY += 1
		levelX += 1
		(Xblack, Xred) = help(levelX)
		(Yblack, Yred) = help(levelY)
		while levelX > levelY:
			x >>= 1
			levelX -= 1
		while levelX < levelY:
			y >>= 1
			levelY -= 1
		while x != y:
			x >>= 1
			y >>= 1
			levelY -= 1
		(LCAblack, LCAred) = help(levelY)
		if color:
			ans = Xred + Yred - 2 * LCAred
		else:
			ans = Xblack + Yblack - 2 * LCAblack
		temp = levelY % 2
		if color:
			if flag:
				if temp == 0:
					ans += 1
			elif temp == 1:
				ans += 1
		elif flag:
			if temp == 1:
				ans += 1
		elif temp == 0:
			ans += 1
		pr(ans)


def dec_to_bin(z):
	return int(bin(z)[2:])
testCases = int(input())
baseBlack = 1
for i in range(testCases):
	theStr = input()
	if theStr == 'Qi':
		baseBlack = -baseBlack
	else:
		(Color, Fir, Sec) = theStr.split()
		if Color[1] == 'b':
			theColor = 1
		else:
			theColor = -1
		Fir = int(Fir)
		Sec = int(Sec)
		x = str(dec_to_bin(max(Fir, Sec)))
		ynum = dec_to_bin(min(Fir, Sec))
		ystr = str(ynum)
		lenx = len(x)
		leny = len(ystr)
		newx = int(x[0:leny])
		if newx == ynum:
			leveldown = 0
		else:
			leveldown = len(str(abs(2 * newx - 2 * ynum)))
		dist = leveldown * 2 + lenx - leny + 1
		if baseBlack * theColor * (lenx % 2 * 2 - 1) == 1:
			print(int(dist / 2 + 0.6))
		else:
			print(int(dist / 2))


t = int(input())
flag = False
while t:
	t -= 1
	inp = input()
	inp = inp.split()
	query = inp[0]
	if query == 'Qi':
		if flag == True:
			flag = False
		else:
			flag = True
	else:
		x = int(inp[1])
		y = int(inp[2])
		c = 0
		start = 'Black'
		while True:
			if x < y:
				y = int(y / 2)
				c += 1
			elif x > y:
				x = int(x / 2)
				c += 1
				if start == 'Black':
					start = 'Red'
				else:
					start = 'Black'
			else:
				c += 1
				if x != 1:
					while x != 1:
						x = int(x / 2)
						if start == 'Black':
							start = 'Red'
						else:
							start = 'Black'
				if start != 'Black':
					start = 'Red'
				break
		BLACK = int(c / 2)
		RED = int(c / 2)
		if c % 2 == 1:
			if start == 'Black':
				BLACK += 1
			else:
				RED += 1
		if query == 'Qb':
			if flag:
				print(RED)
			else:
				print(BLACK)
		elif query == 'Qr':
			if flag:
				print(BLACK)
			else:
				print(RED)


from bisect import bisect_right
factors = [1 << i for i in range(0, 31)]

def count_dist(x, y, q, flag):
	x_init = bisect_right(factors, x)
	y_init = bisect_right(factors, y)
	total = 0
	for _ in range(abs(x_init - y_init)):
		if x_init > y_init:
			x = x >> 1
		else:
			y = y >> 1
		total += 1
	while x != y:
		x = x >> 1
		y = y >> 1
		total += 2
	final = bisect_right(factors, x)
	same_y = (y_init - final) // 2
	same_x = (x_init - final) // 2
	same_total = same_x + same_y + 1
	diff_total = total - same_total + 1
	if final % 2 == 0:
		red = same_total
		black = diff_total
	else:
		red = diff_total
		black = same_total
	if q == 'r':
		if flag == 1:
			print(red)
		else:
			print(black)
	elif flag == 1:
		print(black)
	else:
		print(red)
tests = int(input())
flag = 1
for _ in range(tests):
	q = input().split()
	if 'Qi' in q:
		flag = 1 - flag
	else:
		(x, y) = map(int, q[1:])
		if 'Qr' in q:
			count_dist(x, y, 'r', flag)
		else:
			count_dist(x, y, 'b', flag)


root = 0
for _ in range(int(input())):
	q = list(map(str, input().split()))
	if q[0] == 'Qi':
		root = (root + 1) % 2
	else:
		x = int(q[1])
		y = int(q[2])
		xca = []
		yca = []
		lxca = 0
		lyca = 0
		while x > 0:
			lxca += 1
			xca.append(x)
			if x & 1:
				x -= 1
				x //= 2
			else:
				x //= 2
		while y > 0:
			lyca += 1
			yca.append(y)
			if y & 1:
				y -= 1
				y //= 2
			else:
				y //= 2
		lx = lxca - 1
		ly = lyca - 1
		lca_dist = 0
		while lx >= 0 and ly >= 0:
			if xca[lx] == yca[ly]:
				lca_dist += 1
			else:
				break
			lx -= 1
			ly -= 1
		lca_color = 0
		if lca_dist & 1:
			lca_color = root
		else:
			lca_color = (root + 1) % 2
		ans = 0
		accept1 = 0
		accept2 = 0
		if q[0] == 'Qb':
			if lca_color == 0:
				accept1 = 0
				accept2 = 1
			else:
				accept1 = 1
				accept2 = 0
		elif lca_color == 1:
			accept1 = 0
			accept2 = 1
		else:
			accept1 = 1
			accept2 = 0
		for i in range(lca_dist, lxca + 1):
			if accept1 == 0:
				ans += 1
			accept1 = (accept1 + 1) % 2
		for i in range(lca_dist + 1, lyca + 1):
			if accept2 == 0:
				ans += 1
			accept2 = (accept2 + 1) % 2
		print(ans)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

def print_var(*args):
	for var_name in args:
		calling_frame = sys._getframe().f_back
		var_val = calling_frame.f_locals.get(var_name, calling_frame.f_globals.get(var_name, None))
		print(var_name + ':', str(var_val))

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)
	return r1 if r1 == r2 else None

def bintree_lca(a, b):
	(bina, binb) = (bin(a)[2:], bin(b)[2:])
	res = 0
	lena = len(bina)
	lenb = len(binb)
	minl = min(lena, lenb)
	for i in range(minl):
		if bina[i] != binb[i]:
			break
		res += 1
	if res == 0:
		return 1
	return int(bina[:res], 2)

def main():
	data = sys.stdin
	Q = int(data.readline())
	BLACK = 0
	RED = 1
	impair = BLACK
	pair = RED
	for iq in range(Q):
		s = data.readline().strip()
		if s[1] == 'i':
			(impair, pair) = (pair, impair)
		else:
			(l, r) = s.split()[1:]
			(l, r) = (int(l), int(r))
			lca = bintree_lca(l, r)

			def node_height(i):
				return len(bin(i)) - 2
			lca_height = node_height(lca)
			l_height = node_height(l)
			r_height = node_height(r)
			lca_col = impair if lca_height % 2 == 1 else pair
			countl = l_height - lca_height + 1
			countr = r_height - lca_height + 1
			same_as_lca_l = (countl + 1) // 2
			same_as_lca_r = (countr + 1) // 2
			same_as_lca = same_as_lca_l + same_as_lca_r - 1
			not_same_as_lca_l = countl - same_as_lca_l
			not_same_as_lca_r = countr - same_as_lca_r
			not_same_as_lca = not_same_as_lca_l + not_same_as_lca_r
			nb_black = same_as_lca if lca_col == BLACK else not_same_as_lca
			nb_red = same_as_lca if lca_col == RED else not_same_as_lca
			if s[1] == 'b':
				print(nb_black)
			else:
				print(nb_red)
main()


import math
rootColor = int(0)
nodeColor = int()
test = int(input())
while test:
	count = int(0)
	ans = int(0)
	inp = str(input())
	if inp[1] == 'i':
		if rootColor == 0:
			rootColor = 1
		else:
			rootColor = 0
	else:
		(c, start, end) = map(str, inp.split())
		c = c[1]
		start = int(start)
		end = int(end)
		l1 = int(math.log(start, 2) + 1)
		l2 = int(math.log(end, 2) + 1)
		if l1 % 2 == 0:
			if rootColor == 0:
				nodeColor = 1
			else:
				nodeColor = 0
		else:
			nodeColor = rootColor
		if l1 > l2:
			d = int(l1 - l2)
			start = start >> d
			count += d
		elif l2 > l1:
			d = int(l2 - l1)
			end = end >> d
			count += d
		xorr = int(start ^ end)
		flag = int(0)
		if xorr == 0:
			flag = 1
		if flag == 0:
			l1 = int(math.log(xorr, 2) + 1)
			start = start >> l1
			count = count + 2 * l1
		count += 1
		ans = int(count / 2)
		if count % 2 == 1:
			if c == 'b' and nodeColor == 0:
				print(int(ans + 1))
			elif c == 'r' and nodeColor == 1:
				print(int(ans + 1))
			else:
				print(int(ans))
		else:
			print(int(ans))
	test -= 1


from math import *
flag = 0
for _ in range(int(input())):
	s = input().strip()
	if s == 'Qi':
		flag = not flag
		continue
	(s, x, y) = s.split()
	(x, y) = (int(x), int(y))
	l1 = []
	l2 = []
	i = j = 0
	l1.append(x)
	l2.append(y)
	while x > 0:
		l1.append(x // 2)
		x //= 2
		i += 1
	while y > 0:
		l2.append(y // 2)
		y //= 2
		j += 1
	while i >= 0 and j >= 0 and (l1[i] == l2[j]):
		(j, i) = (j - 1, i - 1)
	(j, i) = (j + 1, i + 1)
	ans = 0
	if (i + 1) % 2 == 0:
		ans += (i + 1) // 2
	else:
		ans += i // 2
		lo = int(log(l1[i], 2))
		if s == 'Qr':
			if flag + lo % 2 == 1:
				ans += 1
		if s == 'Qb':
			if (flag + lo % 2) % 2 == 0:
				ans += 1
	j -= 1
	if (j + 1) % 2 == 0:
		ans += (j + 1) // 2
	else:
		ans += j // 2
		lo = int(log(l2[j], 2))
		if s == 'Qr':
			if flag + lo % 2 == 1:
				ans += 1
		if s == 'Qb':
			if (flag + lo % 2) % 2 == 0:
				ans += 1
	print(ans)


ini = {'odd': 'black', 'even': 'red'}
for _ in range(int(input())):
	q = [i for i in input().split()]
	if q[0] == 'Qi':
		temp = ini['odd']
		ini['odd'] = ini['even']
		ini['even'] = temp
	else:
		(a, b) = (f'{int(q[1]):b}', f'{int(q[2]):b}')
		k = 0
		count = {'black': 0, 'red': 0}
		for (i, j) in zip(a, b):
			if i != j:
				break
			else:
				k += 1
		dist = len(a) + len(b) - 2 * k
		if (dist + 1) % 2 == 0:
			count['red'] = count['black'] = (dist + 1) / 2
		else:
			if len(a) % 2 == 0:
				count[ini['even']] += 1
			else:
				count[ini['odd']] += 1
			count['red'] += dist / 2
			count['black'] += dist / 2
		if q[0] == 'Qb':
			print(int(count['black']))
		else:
			print(int(count['red']))


import math
root = int(0)
node = int()
q = int(input())
while q:
	cou = int(0)
	tra = int(0)
	s = str(input())
	if s[1] == 'i':
		if root == 0:
			root = 1
		else:
			root = 0
	else:
		(c, x, y) = map(str, s.split())
		c = c[1]
		x = int(x)
		y = int(y)
		x1 = int(math.log(x, 2) + 1)
		y1 = int(math.log(y, 2) + 1)
		if x1 % 2 == 0:
			if root == 0:
				node = 1
			else:
				node = 0
		else:
			node = root
		if x1 > y1:
			d = int(x1 - y1)
			x = x >> d
			cou += d
		elif y1 > x1:
			d = int(y1 - x1)
			y = y >> d
			cou += d
		xo = int(x ^ y)
		u = int(0)
		if xo == 0:
			u = -1
		if u == 0:
			y1 = int(math.log(xo, 2) + 1)
			x = x >> y1
			cou = cou + 2 * y1
		cou += 1
		tra = int(cou / 2)
		if cou % 2 == 1:
			if c == 'b' and node == 0:
				print(int(tra + 1))
			elif c == 'r' and node == 1:
				print(int(tra + 1))
			else:
				print(int(tra))
		else:
			print(int(tra))
	q -= 1


from math import floor, ceil
black = 1
red = 0
for _ in range(int(input())):
	query = input().split()
	path = [0, 0]
	if query[0] == 'Qi':
		(black, red) = (red, black)
		continue
	x = int(query[1])
	y = int(query[2])
	if x < y:
		(x, y) = (y, x)
	while len(bin(x)) != len(bin(y)):
		path[len(bin(x)) % 2] += 1
		x = floor(x / 2)
	while x != y:
		path[len(bin(x)) % 2] += 1
		path[len(bin(y)) % 2] += 1
		(x, y) = (floor(x / 2), floor(y / 2))
	path[len(bin(x)) % 2] += 1
	if query[0] == 'Qb':
		print(path[black])
	else:
		print(path[red])


from math import *

def com_anc(x, y):
	if x < y:
		(x, y) = (y, x)
	while x != y:
		x = x // 2
		if x < y:
			y = y // 2
	return x

def count(x, y):
	k1 = floor(log(x, 2))
	k2 = floor(log(y, 2))
	d = k2 - k1
	if d % 2 == 0:
		return (d // 2, d // 2)
	else:
		return (d // 2 + 1, d // 2)

def q(switch, x):
	k = floor(log(x, 2)) + 1
	if k % 2 == 0:
		if switch % 2 == 0:
			return 'red'
		else:
			return 'black'
	elif switch % 2 == 0:
		return 'black'
	else:
		return 'red'
qu = int(input())
switch = 0
for i in range(qu):
	s = input()
	if s == 'Qi':
		switch += 1
	else:
		(red, black) = (0, 0)
		s = s.split()
		x = s[1]
		y = s[2]
		a = int(max(int(x), int(y)))
		b = int(min(int(x), int(y)))
		anc = com_anc(a, b)
		color = q(switch, anc)
		if color == 'red':
			red += count(anc, a)[1] + 1 + count(anc, b)[1]
			black += count(anc, a)[0] + count(anc, b)[0]
		else:
			black += count(anc, a)[1] + 1 + count(anc, b)[1]
			red += count(anc, a)[0] + count(anc, b)[0]
		if s[0] == 'Qb':
			print(black)
		else:
			print(red)


from math import log2

def pathLength(x, y):
	res = 1
	while x != y:
		res += 1
		if x > y:
			x //= 2
		else:
			y //= 2
	return res
inversions = 0
for _ in range(int(input())):
	inp = list(input().split(' '))
	if len(inp) == 1:
		inversions = (inversions + 1) % 2
	else:
		q = inp[0][1]
		x = int(inp[1])
		y = int(inp[2])
		lev_x = int(log2(x)) % 2
		lev_y = int(log2(y)) % 2
		path_len = pathLength(x, y)
		(red, black) = (0, 0)
		if lev_x == 1 and lev_y == 1:
			black = path_len // 2
			red = path_len - black
		elif lev_x == 0 and lev_y == 0:
			red = path_len // 2
			black = path_len - red
		else:
			red = path_len // 2
			black = path_len - red
		if inversions == 1:
			if q == 'b':
				print(red)
			else:
				print(black)
		elif q == 'b':
			print(black)
		else:
			print(red)