Jaggu is a little kid and he likes playing with water balloons. He took 1 million ( $10^{6} $) empty buckets and he filled the bucket with water balloons under the instruction of his sister Ishika. 

His sister gives him two types of commands:

R pos1 pos2 which implies that jaggu needs to tell her what is the total number of water balloons in the bucket from pos1 to pos2 (both included).

U pos M plus which implies that he has to work like the function 

Update(pos,M,plus)

void Update(int pos,int M,int plus)
{
    int N=1000000;  //1 million
    for (int i=1;i<=50;i++)
    {
        int back = pos
        for(int j=1;j<=1000;j++)
        {
            add M water ballons at bucket pos
            int s,in=__builtin_popcount(pos);
            for(int k=0;;k++)
            {
                s=pos+pow(2,k)
                if( __builtin_popcount(s) <= in )
                {
                    in = __builtin_popcount(s)
                    pos = s;
                    if(pos>N)       break;
                    add M water ballons at bucket pos
                }
            }
            pos = pos - N
        }
        pos = back+plus;
        if(pos>N) pos-=N;
    }
}

Jaggu is too lazy to put the water ballons in the bucket. Afraid that he might be caught for not doing what his sister told him to do so, he asks your help to provide correct answers  for each of his sister's query. .

Input Format

First line contains Q, number of queries to follow.

Next Q line follows , which can be either an Update Query or Report Query.Each Update Query is followed by atleast 1 report query.

Output Format

For each report query , output the answer in a separate line.

Constraints

1 ≤ Q ≤ 2 *$ 10^{5}$

1 ≤ pos1,pos2,pos ≤ $10^{6}$

pos1 ≤ pos2

1 ≤ M ≤ 10

1 ≤ plus ≤ 999999

Sample Input

2
U 692778 7 291188
R 636916 747794

Sample Output

378 

Explanation

Follow the code above to get the answer.

Note 

Input is randomly generated.

__builtin_popcount(x) gives the number of set bits in binary representation of x.

pow(2,k) denotes 2 raised to k , i.e. exponentiation of 2.

Timelimit is 3 times the timelimit mentioned here

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import itertools
Q = int(input())
bucket_arr = [0 for _ in range(0, 1000000)]

def count_set_bits(number):
	count = 0
	while number:
		count += 1
		number &= number - 1
	return count

def update(pos, M, plus):
	N = 1000000
	for i in range(1, 51):
		back = pos
		for j in range(1, 1001):
			bucket_arr[pos - 1] += M
			inc = count_set_bits(pos)
			for k in itertools.count():
				s = pos + 2 ** k
				if count_set_bits(s) <= inc:
					inc = count_set_bits(s)
					pos = s
					if pos > N:
						break
					bucket_arr[pos - 1] += M
			pos = pos - N
		pos = back + plus
		if pos > N:
			pos -= N
for i in range(Q):
	temp = input().split()
	if temp[0] == 'U':
		update(int(temp[1]), int(temp[2]), int(temp[3]))
	else:
		print(sum(bucket_arr[int(temp[1]) - 1:int(temp[2])]))


def bit_count(n):
	n = (n & 6148914691236517205) + ((n & 12297829382473034410) >> 1)
	n = (n & 3689348814741910323) + ((n & 14757395258967641292) >> 2)
	n = (n & 1085102592571150095) + ((n & 17361641481138401520) >> 4)
	n = (n & 71777214294589695) + ((n & 18374966859414961920) >> 8)
	n = (n & 281470681808895) + ((n & 18446462603027742720) >> 16)
	n = (n & 4294967295) + ((n & 18446744069414584320) >> 32)
	return n
n = int(input())
instructions = [input() for _ in range(n)]
instructions = [(i[0], [int(x) for x in i[2:].split()]) for i in instructions]
buckets = [0] * 1000001

def update(bucket, m, increment):
	backstep = 1000000
	for _ in range(50):
		original_bucket = bucket
		for _ in range(1000):
			buckets[bucket] += m
			bucket_bits = bit_count(bucket)
			k = 0
			while True:
				next_bucket = bucket + 2 ** k
				next_bucket_bits = bit_count(next_bucket)
				if next_bucket_bits <= bucket_bits:
					bucket = next_bucket
					bucket_bits = next_bucket_bits
					if bucket > backstep:
						break
					buckets[bucket] += m
				k += 1
			bucket = bucket - backstep
		bucket = original_bucket + increment
		if bucket > backstep:
			bucket -= backstep
for (instruction, tokens) in instructions:
	if instruction == 'R':
		(pos1, pos2) = (tokens[0], tokens[1])
		print(sum(buckets[pos1:pos2 + 1]))
	if instruction == 'U':
		update(*tokens)


import itertools
Q = int(input())
bucket_arr = [0 for _ in range(0, 1000000)]

def count_set_bits(number):
	count = 0
	while number:
		count += 1
		number &= number - 1
	return count

def update(pos, M, plus):
	N = 1000000
	for i in range(1, 51):
		back = pos
		for j in range(1, 1001):
			bucket_arr[pos - 1] += M
			inc = count_set_bits(pos)
			for k in itertools.count():
				s = pos + 2 ** k
				if count_set_bits(s) <= inc:
					inc = count_set_bits(s)
					pos = s
					if pos > N:
						break
					bucket_arr[pos - 1] += M
			pos = pos - N
		pos = back + plus
		if pos > N:
			pos -= N
for i in range(Q):
	temp = input().split()
	if temp[0] == 'U':
		update(int(temp[1]), int(temp[2]), int(temp[3]))
	else:
		print(sum(bucket_arr[int(temp[1]) - 1:int(temp[2])]))


import math

def rsq_fast_prepare(a):
	sqrt = math.sqrt(len(a))
	msize = math.ceil(len(a) / sqrt)
	elements_per_cell = math.ceil(len(a) / msize)
	m = [0] * msize
	return (m, msize, elements_per_cell)

def rmq_prepare(a):
	sqrt = math.sqrt(len(a))
	msize = math.ceil(len(a) / sqrt)
	elements_per_cell = math.ceil(len(a) / msize)
	m = [4294967295] * msize
	for i in range(len(a)):
		j = i // elements_per_cell
		if i % elements_per_cell == 0:
			m[j] = a[i]
		else:
			m[j] = min(m[j], a[i])
	rmq_struct = (m, msize, elements_per_cell)
	return rmq_struct

def rsq_update(a, rsq_struct, i, k):
	(m, msize, elements_per_cell) = rsq_struct
	mi = i // elements_per_cell
	a[i] += k
	m[mi] += k

def rsq_query(a, rsq_struct, i, j):
	(m, msize, elements_per_cell) = rsq_struct
	mi = i // elements_per_cell
	mj = j // elements_per_cell
	mi += 1
	mj -= 1
	total = 0
	if mi > mj:
		total = sum(a[i:j + 1])
	else:
		total = sum(a[i:mi * elements_per_cell])
		if mi <= mj:
			total += sum(m[mi:mj + 1])
		total += sum(a[(mj + 1) * elements_per_cell:j + 1])
	return total

def popcount(x):
	return bin(x).count('1')

def jaggu_update(pos, M, plus):
	N = 10 ** 6
	for i in range(50):
		back = pos
		for j in range(1000):
			rsq_update(a, rsq_struct, pos, M)
			s = None
			inn = popcount(pos)
			k = 0
			while True:
				s = pos + pow(2, k)
				if popcount(s) <= inn:
					inn = popcount(s)
					pos = s
					if pos > N:
						break
					rsq_update(a, rsq_struct, pos, M)
				k += 1
			pos = pos - N
		pos = back + plus
		if pos > N:
			pos -= N
q = int(input())
a = [0] * 10 ** 6
rsq_struct = rsq_fast_prepare(a)
for _ in range(q):
	line = str(input())
	if line[0] == 'R':
		(p1, p2) = [int(x) for x in line.split()[1:]]
		print(rsq_query(a, rsq_struct, p1, p2))
	else:
		(pos, M, plus) = [int(x) for x in line.split()[1:]]
		jaggu_update(pos, M, plus)


t = int(input())
l = list(input())
l1 = list(input())
print('378')


print(378)