Barney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a bidirectional road between intersections i and 2i and another road between i and 2i + 1 for every positive integer i. You can clearly see that there exists a unique shortest path between any two intersections. [Image] 

Initially anyone can pass any road for free. But since SlapsGiving is ahead of us, there will q consecutive events happen soon. There are two types of events:

1. Government makes a new rule. A rule can be denoted by integers v, u and w. As the result of this action, the passing fee of all roads on the shortest path from u to v increases by w dollars. 

2. Barney starts moving from some intersection v and goes to intersection u where there's a girl he wants to cuddle (using his fake name Lorenzo Von Matterhorn). He always uses the shortest path (visiting minimum number of intersections or roads) between two intersections.

Government needs your calculations. For each time Barney goes to cuddle a girl, you need to tell the government how much money he should pay (sum of passing fee of all roads he passes).


-----Input-----

The first line of input contains a single integer q (1 ≤ q ≤ 1 000).

The next q lines contain the information about the events in chronological order. Each event is described in form 1 v u w if it's an event when government makes a new rule about increasing the passing fee of all roads on the shortest path from u to v by w dollars, or in form 2 v u if it's an event when Barnie goes to cuddle from the intersection v to the intersection u.

1 ≤ v, u ≤ 10^18, v ≠ u, 1 ≤ w ≤ 10^9 states for every description line.


-----Output-----

For each event of second type print the sum of passing fee of all roads Barney passes in this event, in one line. Print the answers in chronological order of corresponding events.


-----Example-----
Input
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4

Output
94
0
32



-----Note-----

In the example testcase:

Here are the intersections used: [Image]   Intersections on the path are 3, 1, 2 and 4.  Intersections on the path are 4, 2 and 1.  Intersections on the path are only 3 and 6.  Intersections on the path are 4, 2, 1 and 3. Passing fee of roads on the path are 32, 32 and 30 in order. So answer equals to 32 + 32 + 30 = 94.  Intersections on the path are 6, 3 and 1.  Intersections on the path are 3 and 7. Passing fee of the road between them is 0.  Intersections on the path are 2 and 4. Passing fee of the road between them is 32 (increased by 30 in the first event and by 2 in the second).

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
def main():
	from collections import Counter
	d = Counter()
	for _ in range(int(input())):
		(c, *l) = input().split()
		if c == '1':
			(v, u, w) = map(int, l)
			while u != v:
				if u < v:
					d[v] += w
					v //= 2
				else:
					d[u] += w
					u //= 2
		else:
			w = 0
			(v, u) = map(int, l)
			while u != v:
				if u < v:
					w += d[v]
					v //= 2
				else:
					w += d[u]
					u //= 2
			print(w)
main()


def add_edges(s1, s2, w):
	global edges
	i = 0
	while i < len(s1) and i < len(s2) and (s1[i] == s2[i]):
		i += 1
	j = len(s1)
	while j > i:
		if s1[:j] in edges:
			edges[s1[:j]] += w
		else:
			edges[s1[:j]] = w
		j -= 1
	j = len(s2)
	while j > i:
		if s2[:j] in edges:
			edges[s2[:j]] += w
		else:
			edges[s2[:j]] = w
		j -= 1

def way(s1, s2):
	global edges
	i = 0
	while i < len(s1) and i < len(s2) and (s1[i] == s2[i]):
		i += 1
	w = 0
	j = len(s1)
	while j > i:
		if s1[:j] in edges:
			w += edges[s1[:j]]
		j -= 1
	j = len(s2)
	while j > i:
		if s2[:j] in edges:
			w += edges[s2[:j]]
		j -= 1
	return w
q = int(input())
edges = dict()
for i in range(q):
	l = list(map(int, input().split()))
	if l[0] == 1:
		l[1] = bin(l[1])
		l[1] = l[1][2:]
		l[2] = bin(l[2])
		l[2] = l[2][2:]
		add_edges(l[1], l[2], l[3])
	if l[0] == 2:
		l[1] = bin(l[1])
		l[1] = l[1][2:]
		l[2] = bin(l[2])
		l[2] = l[2][2:]
		print(way(l[1], l[2]))


d = {}

def lca(x, y, w):
	res = 0
	while x != y:
		if x < y:
			(x, y) = (y, x)
		d[x] = d.get(x, 0) + w
		res += d[x]
		x //= 2
	return res
q = int(input())
while q > 0:
	q -= 1
	a = list(map(int, input().split()))
	if a[0] == 1:
		lca(a[1], a[2], a[3])
	else:
		print(lca(a[1], a[2], 0))


import collections

def lca(u, v):
	ub = bin(u)[2:]
	vb = bin(v)[2:]
	r = 0
	for (i, (a, b)) in enumerate(zip(ub, vb)):
		if a != b:
			break
		r = r * 2 + int(a)
	return r

def add(cost, n, root, w):
	while n > root:
		cost[n] += w
		n //= 2

def get(cost, n, root):
	r = 0
	while n > root:
		r += cost[n]
		n //= 2
	return r
q = int(input())
cost = collections.Counter()
for _ in range(q):
	cmd = list(map(int, input().split()))
	if cmd[0] == 1:
		(v, u, w) = cmd[1:]
		root = lca(v, u)
		add(cost, v, root, w)
		add(cost, u, root, w)
	else:
		(v, u) = cmd[1:]
		root = lca(v, u)
		print(get(cost, v, root) + get(cost, u, root))


I = input
n = int(I())
d = {}

def lca(u, v, w):
	res = 0
	while u != v:
		if u < v:
			(u, v) = (v, u)
		d[u] = d.get(u, 0) + w
		res += d[u]
		u = u // 2
	return res
for i in range(n):
	l = list(map(int, I().split()))
	if l[0] == 1:
		lca(l[1], l[2], l[3])
	else:
		print(lca(l[1], l[2], 0))


import sys
input = sys.stdin.readline
from math import log2
from collections import defaultdict
d = defaultdict(int)
for i in range(int(input().strip())):
	l = list(map(int, input().strip().split()))
	if l[0] == 1:
		(u, v, w) = l[1:]
		while u != v:
			if int(log2(u)) < int(log2(v)):
				(u, v) = (v, u)
			d[u, u // 2] += w
			u = u // 2
	else:
		(u, v) = l[1:]
		ans = 0
		while u != v:
			if int(log2(u)) < int(log2(v)):
				(u, v) = (v, u)
			ans += d[u, u // 2]
			u = u // 2
		print(ans)


from functools import lru_cache
from collections import defaultdict
from itertools import tee
price = defaultdict(dict)

def add(start, end, w):
	global price
	for (x, y) in get_way(start, end):
		if x not in price:
			price[x] = defaultdict(lambda : 0)
		if y not in price:
			price[y] = defaultdict(lambda : 0)
		price[x][y] += w
		price[y][x] += w

def get_price(start, end):
	result = 0
	for (x, y) in get_way(start, end):
		if x in price:
			result += price[x][y]
	return result

@lru_cache(maxsize=1000)
def get_way(start, end):

	def _get_raw_way():
		nonlocal start, end
		(l_way, r_way) = ([start], [end])
		while True:
			l = l_way[-1] // 2
			if l:
				l_way.append(l)
			r = r_way[-1] // 2
			if r:
				r_way.append(r)
			if r_way[-1] == start:
				return r_way
			union = set(l_way) & set(r_way)
			if union:
				r_way = r_way[:r_way.index(max(union))]
				l_way = l_way[:l_way.index(max(union))]
				r_way.reverse()
				return l_way + [union.pop()] + r_way
	(a, b) = tee(_get_raw_way())
	next(b, None)
	return list(zip(a, b))
q = int(input())
for _ in range(q):
	data = list(map(int, input().split(' ')))
	if data[0] == 1:
		add(data[1], data[2], data[3])
	else:
		print(get_price(data[1], data[2]))


q = int(input())

def full_way(u):
	res = set()
	while u >= 1:
		res.add(u)
		u //= 2
	return res

def get_way(u, v):
	res1 = full_way(u)
	res2 = full_way(v)
	m = max(res1 & res2)
	res = set()
	for x in res1 | res2:
		if x > m:
			res.add(x)
	return res
d = {}
for i in range(q):
	a = input().split()
	if a[0] == '1':
		(v, u, w) = list(map(int, a[1:]))
		for x in get_way(u, v):
			if x not in d:
				d[x] = 0
			d[x] += w
	else:
		(v, u) = list(map(int, a[1:]))
		res = 0
		for x in get_way(u, v):
			if x in d:
				res += d[x]
		print(res)


def path_to_root(n):
	path = [n]
	while n != 1:
		if n % 2:
			path.append((n - 1) // 2)
			n = (n - 1) // 2
		else:
			path.append(n // 2)
			n //= 2
	return path

def path_beetwen(a, b):
	p1 = path_to_root(a)
	p2 = path_to_root(b)
	l1 = len(p1)
	l2 = len(p2)
	x = 0
	while x < l2:
		if p2[x] in p1:
			break
		x += 1
	path = p1[:p1.index(p2[x]) + 1] + p2[:x][::-1]
	return path

def fee_on_path(fees, a, b):
	path = path_beetwen(a, b)
	total_fee = 0
	for x in range(len(path) - 1):
		fee = str(path[x]) + '_' + str(path[x + 1])
		if fee in fees.keys():
			total_fee += fees[fee]
	return total_fee

def update_fees(fees, a, b, w):
	path = path_beetwen(a, b)
	for x in range(len(path) - 1):
		fee = str(path[x]) + '_' + str(path[x + 1])
		fee2 = str(path[x + 1]) + '_' + str(path[x])
		if fee in fees.keys():
			fees[fee] += w
		else:
			fees[fee] = w
		if fee2 in fees.keys():
			fees[fee2] += w
		else:
			fees[fee2] = w

class CodeforcesTask696ASolution:

	def __init__(self):
		self.result = ''
		self.events_count = 0
		self.events = []

	def read_input(self):
		self.events_count = int(input())
		for x in range(self.events_count):
			self.events.append([int(y) for y in input().split(' ')])

	def process_task(self):
		fees = {}
		for x in range(self.events_count):
			if self.events[x][0] == 1:
				update_fees(fees, self.events[x][1], self.events[x][2], self.events[x][3])
			else:
				print(fee_on_path(fees, self.events[x][1], self.events[x][2]))

	def get_result(self):
		return self.result
Solution = CodeforcesTask696ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from collections import defaultdict

def find_cost(node_1, node_2, intersect_dict):
	new_dict = defaultdict(lambda : 0)
	cost = 0
	while node_1 != 0:
		new_dict[node_1] = 1
		cost += intersect_dict[node_1]
		node_1 //= 2
	while node_2 != 0:
		if new_dict[node_2]:
			cost -= intersect_dict[node_2]
			break
		else:
			new_dict[node_2] = 1
			cost += intersect_dict[node_2]
			node_2 //= 2
	while node_2 != 0:
		node_2 //= 2
		cost -= intersect_dict[node_2]
	return cost

def increase_cost_on_path(node_1, node_2, inc_cost, intersect_dict):
	new_dict = defaultdict(lambda : 0)
	while node_1 != 0:
		new_dict[node_1] = 1
		intersect_dict[node_1] += inc_cost
		node_1 //= 2
	while node_2 != 0:
		if new_dict[node_2]:
			break
		else:
			intersect_dict[node_2] += inc_cost
			node_2 //= 2
	while node_2 != 0:
		intersect_dict[node_2] -= inc_cost
		node_2 //= 2
	return intersect_dict
Q = int(input())
intersect_dict = defaultdict(lambda : 0)
for q in range(Q):
	query = [int(i) for i in input().split()]
	if query[0] == 1:
		(v, u, w) = query[1:]
		intersect_dict = increase_cost_on_path(v, u, w, intersect_dict)
	else:
		(v, u) = query[1:]
		cost = find_cost(u, v, intersect_dict)
		print(cost)


def find_path(x, y):
	(p1, p2) = ([], [])
	while x != 0:
		p1.append(x)
		x = x // 2
	while y != 0:
		p2.append(y)
		y = y // 2
	p1 = p1[::-1]
	p2 = p2[::-1]
	for i in range(min(len(p1), len(p2))):
		if p1[i] == p2[i]:
			ind = i
		else:
			break
	path = []
	for i in range(ind, len(p1)):
		path.append(p1[i])
	path = path[::-1]
	for i in range(ind + 1, len(p2)):
		path.append(p2[i])
	return path
q = int(input())
cost = {}
for i in range(q):
	a = list(map(int, input().split()))
	b = find_path(a[1], a[2])
	if a[0] == 1:
		w = a[-1]
		for j in range(1, len(b)):
			if (b[j], b[j - 1]) not in cost:
				cost[b[j], b[j - 1]] = w
				cost[b[j - 1], b[j]] = w
			else:
				cost[b[j], b[j - 1]] += w
				cost[b[j - 1], b[j]] += w
	else:
		ans = 0
		for j in range(1, len(b)):
			if (b[j], b[j - 1]) in cost:
				ans += cost[b[j], b[j - 1]]
		print(ans)


def main():
	d = {}
	for _ in range(int(input())):
		(c, *l) = input().split()
		if c == '1':
			(v, u, w) = map(int, l)
			while u != v:
				if u < v:
					d[v] = d.get(v, 0) + w
					(u, v) = (v // 2, u)
				else:
					d[u] = d.get(u, 0) + w
					u //= 2
		else:
			res = 0
			(v, u) = map(int, l)
			while u != v:
				if u < v:
					res += d.get(v, 0)
					(u, v) = (v // 2, u)
				else:
					res += d.get(u, 0)
					u //= 2
			print(res)
main()


import math
q = int(input())
s = {}
o = []
for i in range(q):
	r = list(map(int, input().split()))
	(a, b) = (r[1], r[2])
	if r[0] == 2:
		o.append(0)
	while a != b:
		if math.log2(a) > math.log2(b) and a != 1:
			if a not in s:
				s[a] = 0
			if r[0] == 1:
				s[a] += r[3]
			else:
				o[-1] += s[a]
			a //= 2
		elif b != 1:
			if b not in s:
				s[b] = 0
			if r[0] == 1:
				s[b] += r[3]
			else:
				o[-1] += s[b]
			b //= 2
print(*map(str, o), sep='\n')


from collections import defaultdict
arr = defaultdict(int)
for i in range(int(input())):
	t = list(map(int, input().strip().split()))
	if t[0] == 1:
		(type, a, b, w) = t
		if b > a:
			(a, b) = (b, a)
		while a != b:
			if a > b:
				arr[a] += w
				a //= 2
			else:
				arr[b] += w
				b //= 2
	if t[0] == 2:
		(type, a, b) = t
		res = 0
		st = set()
		if a < b:
			(a, b) = (b, a)
		res = 0
		while a != b:
			if a > b:
				res += arr[a]
				a //= 2
			else:
				res += arr[b]
				b //= 2
		print(res)


def UCLN(a, b):
	while a != b:
		if a > b:
			a = a // 2
		else:
			b = b // 2
	return a

def find_path(u, v):
	ucln = UCLN(u, v)
	arr1 = []
	arr2 = []
	while u >= ucln:
		arr1.append(u)
		u = u // 2
	while v > ucln:
		arr2.append(v)
		v = v // 2
	return arr1 + arr2[::-1]
p = int(input())
dic = {}
for i in range(p):
	value = list(map(int, input().split()))
	action = value[0]
	if action == 1:
		path = find_path(value[1], value[2])
		for i in range(len(path) - 1):
			if '{}{}'.format(path[i], path[i + 1]) not in dic and '{}{}'.format(path[i + 1], path[i]) not in dic:
				dic['{}{}'.format(path[i], path[i + 1])] = value[3]
				dic['{}{}'.format(path[i + 1], path[i])] = value[3]
			else:
				dic['{}{}'.format(path[i], path[i + 1])] += value[3]
				dic['{}{}'.format(path[i + 1], path[i])] += value[3]
	else:
		total = 0
		path = find_path(value[1], value[2])
		for i in range(len(path) - 1):
			if '{}{}'.format(path[i], path[i + 1]) in dic:
				total += dic['{}{}'.format(path[i], path[i + 1])]
		print(total)


import sys, os, io
from collections import defaultdict
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
cost = defaultdict(lambda : 0)
q = int(input())
for _ in range(q):
	qi = [int(i) for i in input().split()]
	(u, v) = (qi[1], qi[2])
	vis = defaultdict(lambda : 0)
	path1 = []
	while u > 0:
		path1.append(u)
		vis[u] = 1
		u //= 2
	path2 = []
	inter = -1
	while v > 0:
		if vis[v]:
			inter = v
			break
		path2.append(v)
		v //= 2
	path = []
	for i in path1:
		path.append(i)
		if i == inter:
			break
	for i in path2[::-1]:
		path.append(i)
	if qi[0] == 1:
		w = qi[3]
		for i in range(1, len(path)):
			cost[path[i], path[i - 1]] += w
			cost[path[i - 1], path[i]] += w
	else:
		ans = 0
		for i in range(1, len(path)):
			ans += cost[path[i], path[i - 1]]
		print(ans)


(cost, res) = ({}, [])
t = int(input())
for i in range(t):
	arr = list(map(int, input().split()))
	if len(arr) == 4:
		(_, u, v, w) = arr
		while u != v:
			if u > v:
				cost[u] = cost.get(u, 0) + w
				u //= 2
			else:
				cost[v] = cost.get(v, 0) + w
				v //= 2
	else:
		(_, u, v) = arr
		curr_res = 0
		while u != v:
			if u > v:
				curr_res += cost.get(u, 0)
				u //= 2
			else:
				curr_res += cost.get(v, 0)
				v //= 2
		res.append(str(curr_res))
print('\n'.join(res))


import sys, os, io
from sys import stdin
from collections import defaultdict
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
t = int(input())
costEdge = defaultdict(lambda : 0)
for _ in range(t):
	query = [int(x) for x in input().split()]
	u = query[1]
	v = query[2]
	parents = {}
	while u:
		parents[u] = 1
		u //= 2
	lca = -1
	path1 = []
	while v:
		path1.append(v)
		if v in parents:
			lca = v
			break
		v //= 2
	u = query[1]
	path2 = []
	while u != lca:
		path2.append(u)
		u //= 2
	path2.append(lca)
	if query[0] == 1:
		w = query[3]
		for i in range(len(path2) - 1):
			costEdge[path2[i], path2[i + 1]] += w
			costEdge[path2[i + 1], path2[i]] += w
		for i in range(len(path1) - 1):
			costEdge[path1[i], path1[i + 1]] += w
			costEdge[path1[i + 1], path1[i]] += w
	else:
		ans = 0
		for i in range(len(path2) - 1):
			ans += costEdge[path2[i], path2[i + 1]]
		for i in range(len(path1) - 1):
			ans += costEdge[path1[i], path1[i + 1]]
		print(ans)


from math import log
q = int(input())
prix = {}
depenses = []

def est_dessous(v, u):
	return u == v or u == 1 or (u < v and 0 <= v - 2 ** int(log(v / u) / log(2)) * u < 2 ** int(log(v / u) / log(2)))

def pqc(u, v):
	res = []
	while not est_dessous(v, u):
		res.append((u, u // 2))
		u = u // 2
	while not u == v:
		if est_dessous(v, 2 * u):
			res.append((u, 2 * u))
			u = 2 * u
		elif est_dessous(v, 2 * u + 1):
			res.append((u, 2 * u + 1))
			u = 2 * u + 1
	return res
for k in range(q):
	event = tuple(map(int, input().split()))
	if event[0] == 1:
		for (a, b) in pqc(event[1], event[2]):
			if (a, b) in prix:
				prix[a, b] += event[3]
			elif (b, a) in prix:
				prix[b, a] += event[3]
			else:
				prix[a, b] = event[3]
	else:
		s = 0
		for (a, b) in pqc(event[1], event[2]):
			if (a, b) in prix:
				s += prix[a, b]
			elif (b, a) in prix:
				s += prix[b, a]
		depenses.append(s)
for k in depenses:
	print(k)


w = {}

def up(a, b, d):
	while a != b:
		if a < b:
			(a, b) = (b, a)
		if a not in w:
			w[a] = 0
		w[a] += d
		a = a // 2

def get(a, b):
	res = 0
	while a != b:
		if a < b:
			(a, b) = (b, a)
		if a in w:
			res += w[a]
		a = a // 2
	return res
q = int(input())
for i in range(q):
	a = [int(b) for b in input().split()]
	if a[0] == 1:
		up(a[1], a[2], a[3])
	else:
		print(get(a[1], a[2]))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
I = input
n = int(I())
d = {}

def lca(u, v, w):
	res = 0
	while u != v:
		if u < v:
			(u, v) = (v, u)
		d[u] = d.get(u, 0) + w
		res += d[u]
		u = u // 2
	return res
for i in range(n):
	l = list(map(int, I().split()))
	if l[0] == 1:
		lca(l[1], l[2], l[3])
	else:
		print(lca(l[1], l[2], 0))