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 ≤ 1018, v ≠ u, 1 ≤ w ≤ 109 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>

  1. Intersections on the path are 3, 1, 2 and 4. 
  2. Intersections on the path are 4, 2 and 1. 
  3. Intersections on the path are only 3 and 6. 
  4. 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. 
  5. Intersections on the path are 6, 3 and 1. 
  6. Intersections on the path are 3 and 7. Passing fee of the road between them is 0. 
  7. 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).

Source: codeforces | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Implementation

Complete search


Solutions:
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')


q = int(input())
price = {}

def get_price(u):
	if u in price:
		return price[u]
	else:
		return 0
for i in range(0, q):
	temp = str(input()).split(' ')
	u = int(temp[1])
	v = int(temp[2])
	if temp[0] == '2':
		res = 0
		while u != v:
			if u > v:
				res = res + get_price(u)
				u //= 2
			else:
				res = res + get_price(v)
				v //= 2
		print(res)
	else:
		w = int(temp[3])
		while u != v:
			if u > v:
				price[u] = get_price(u) + w
				u //= 2
			else:
				price[v] = get_price(v) + w
				v //= 2


q = int(input())
d = {}
for sfsdfdsg in range(q):
	L = [int(x) for x in input().split()]
	if L[0] == 1:
		(a, b, w) = L[1:]
		while a != b:
			if a < b:
				(a, b) = (b, a)
			c = a >> 1
			if (c, a) not in d:
				d[c, a] = 0
			d[c, a] += w
			a = c
	else:
		(a, b) = L[1:]
		cost = 0
		while a != b:
			if a < b:
				(a, b) = (b, a)
			c = a >> 1
			if (c, a) not in d:
				d[c, a] = 0
			cost += d[c, a]
			a = c
		print(cost)


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]))


tree = []
n = int(input())
dic = {}
for i in range(n):
	line = list(input().split())
	if line[0] == '1':
		a = int(line[1])
		b = int(line[2])
		line[3] = float(line[3])
		old_a = a
		old_b = b
		while a != b:
			if a > b:
				a = a // 2
				key = '%d:%d' % (old_a, a)
				old_a = a
				if key not in dic:
					dic[key] = line[3]
				else:
					dic[key] += line[3]
			else:
				b = b // 2
				key = '%d:%d' % (old_b, b)
				old_b = b
				if key not in dic:
					dic[key] = line[3]
				else:
					dic[key] += line[3]
	if line[0] == '2':
		a = int(line[1])
		b = int(line[2])
		old_a = a
		old_b = b
		value = 0
		while a != b:
			if a > b:
				a = a // 2
				key = '%d:%d' % (old_a, a)
				old_a = a
				if key not in dic:
					value += 0
				else:
					value += dic[key]
			else:
				b = b // 2
				key = '%d:%d' % (old_b, b)
				old_b = b
				if key not in dic:
					value += 0
				else:
					value += dic[key]
		print('%d' % value)


def lca(u, v):
	x = list(bin(u)[2:])
	y = list(bin(v)[2:])
	res = []
	pos = 0
	k = min(len(x), len(y))
	while pos < k and x[pos] == y[pos]:
		res.append(x[pos])
		pos += 1
	res = int(''.join(res), 2)
	return res
read = lambda : map(int, input().split())
q = int(input())
from collections import Counter
d = Counter()
for i in range(q):
	s = input().split()
	t = int(s[0])
	if t == 1:
		(u, v, w) = map(int, s[1:])
		p = lca(u, v)
		cur = u
		while cur != p:
			d[cur] += w
			cur //= 2
		cur = v
		while cur != p:
			d[cur] += w
			cur //= 2
	if t == 2:
		(u, v) = map(int, s[1:])
		p = lca(u, v)
		res = 0
		cur = u
		while cur != p:
			res += d[cur]
			cur //= 2
		cur = v
		while cur != p:
			res += d[cur]
			cur //= 2
		print(res)


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

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


from collections import defaultdict

def path(u, v):
	if u > v:
		(u, v) = (v, u)
	bu = bin(u)[2:]
	bv = bin(v)[2:]
	i = 0
	j = 0
	while i < len(bu) and j < len(bv) and (bu[i] == bv[j]):
		i += 1
		j += 1
	res = []
	t = u
	res.append(t)
	while i < len(bu):
		t >>= 1
		res.append(t)
		i += 1
	while j < len(bv):
		t <<= 1
		if bv[j] == '1':
			t |= 1
		res.append(t)
		j += 1
	return res

def main():
	q = int(input())
	cost = defaultdict(int)
	for i in range(0, q):
		query = [int(x) for x in input().split()]
		v = int(query[1])
		u = int(query[2])
		p = path(v, u)
		if len(query) == 4:
			w = int(query[3])
			for j in range(0, len(p) - 1):
				cost[p[j], p[j + 1]] += w
				cost[p[j + 1], p[j]] += w
		else:
			res = 0
			for j in range(0, len(p) - 1):
				res += cost[p[j], p[j + 1]]
			print(res)
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]))


q = int(input())
fee = {}
for _ in range(q):
	s = input().split()
	if len(s) == 4:
		(event_type, u, v, w) = map(int, s)
		su = set()
		sv = set()
		while u > 1:
			su.add(u)
			u >>= 1
		while v > 1:
			sv.add(v)
			v >>= 1
		for i in su ^ sv:
			if i in fee:
				fee[i] += w
			else:
				fee[i] = w
	else:
		(event_type, u, v) = map(int, s)
		su = set()
		sv = set()
		while u > 1:
			su.add(u)
			u >>= 1
		while v > 1:
			sv.add(v)
			v >>= 1
		ret = 0
		for i in su ^ sv:
			if i in fee:
				ret += fee[i]
		print(ret)


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


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)


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)


import math
cache = {}
max_n = 10 ** 18

def get_depth(x):
	return int(math.log2(x))

def LCA(u, v):
	ans = []
	while u != v:
		d1 = get_depth(u)
		d2 = get_depth(v)
		if d1 > d2:
			(u, v) = (v, u)
		ans.append(v)
		v //= 2
	return ans
q = int(input())
ans = []
for i in range(q):
	curr = list(map(int, input().split()))
	if curr[0] == 1:
		(n1, n2, w) = (curr[1], curr[2], curr[3])
		nodes = LCA(n1, n2)
		for e in nodes:
			if e not in cache:
				cache[e] = 0
			cache[e] += w
	else:
		temp = 0
		(n1, n2) = (curr[1], curr[2])
		nodes = LCA(n1, n2)
		for e in nodes:
			if e in cache:
				temp += cache[e]
		ans.append(temp)
for e in ans:
	print(e)


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) = 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) = map(int, a[1:])
		res = 0
		for x in get_way(u, v):
			if x in d:
				res += d[x]
		print(res)


we = {}
q = int(input())
for i in range(q):
	l = list(map(int, input().split()))
	t = l[0]
	u = l[1]
	v = l[2]
	if len(l) == 4:
		w = l[3]
	p1 = [u]
	p2 = [v]
	while u != 1:
		u = u // 2
		p1 += [u]
	while v != 1:
		v = v // 2
		p2 += [v]
	p1 = p1[::-1]
	p2 = p2[::-1]
	curr = 0
	ans = 0
	while curr != min(len(p1), len(p2)) and p1[curr] == p2[curr]:
		curr += 1
	lca = p1[curr - 1]
	c1 = len(p1) - 1
	c2 = len(p2) - 1
	while p1[c1] != lca:
		we[p1[c1]] = we.get(p1[c1], 0)
		if t == 1:
			we[p1[c1]] = we.get(p1[c1], 0) + w
		else:
			ans += we[p1[c1]]
		c1 -= 1
	while p2[c2] != lca:
		we[p2[c2]] = we.get(p2[c2], 0)
		if t == 1:
			we[p2[c2]] = we.get(p2[c2], 0) + w
		else:
			ans += we[p2[c2]]
		c2 -= 1
	if t == 2:
		print(ans)


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)


def ter(a, b):
	if a > b:
		(a, b) = (b, a)
	c = ''
	for i in range(a.bit_length() + 2):
		if bin(a)[i] != bin(b)[i]:
			break
		c += bin(a)[i]
	c = int(c, 2)
	o = []
	while a != c:
		o.append(a)
		a //= 2
	while b != c:
		o.append(b)
		b //= 2
	return o
n = int(input())
a = {}
y = []
for i in range(n):
	s = [int(i) for i in input().split()]
	if s[0] == 1:
		o = ter(s[1], s[2])
		for i in o:
			if i in a:
				a[i] += s[3]
			else:
				a[i] = s[3]
	else:
		ans = 0
		o = ter(s[1], s[2])
		for i in o:
			if i in a:
				ans += a[i]
		y.append(ans)
for i in y:
	print(i)


n = int(input())
t1 = {}
t2 = {}
for i in range(n):
	q = list(map(int, input().split()))
	if q[0] == 1:
		(_, u, v, w) = q
		while u != v:
			(v, u) = (max(u, v), min(u, v))
			if v & 1 == 1:
				t2[v] = t2.get(v, 0) + w
				v = (v - 1) // 2
			else:
				t1[v] = t1.get(v, 0) + w
				v = v // 2
	else:
		(_, u, v) = q
		c = 0
		while u != v:
			(v, u) = (max(u, v), min(u, v))
			if v & 1 == 1:
				c += t2.get(v, 0)
				v = (v - 1) // 2
			else:
				c += t1.get(v, 0)
				v = v // 2
		print(c)


from sys import stdin
import collections
import math

def get_common_parent(path_v, path_u):
	i = -1
	j = -1
	while path_v[i] != path_u[j]:
		if path_v[i] > path_u[j]:
			i -= 1
		elif path_v[i] < path_u[j]:
			j -= 1
		else:
			break
	return path_v[i]

def get_path(start, tree):
	path = []
	while start != 1:
		path.append(start)
		if start // 2 in tree[start]:
			pass
		else:
			tree[start][start // 2] = 0
			tree[start // 2][start] = 0
		start = start // 2
	path.append(1)
	path.reverse()
	return path

def increase_cost(start, tree, parent, w):
	while start != parent:
		if start // 2 in tree[start]:
			tree[start][start // 2] += w
			tree[start // 2][start] += w
		else:
			tree[start][start // 2] = w
			tree[start // 2][start] = w
		start = start // 2

def calculate_cost(start, tree, parent, total):
	while start != parent:
		total[0] += tree[start][start // 2]
		start = start // 2
q = int(stdin.readline().strip())
tree = collections.defaultdict(dict)
for _ in range(q):
	arr = list(map(int, stdin.readline().split()))
	if len(arr) == 4:
		u = arr[1]
		v = arr[2]
		w = arr[3]
		if u > v:
			(v, u) = (u, v)
		path_v = get_path(v, tree)
		path_u = get_path(u, tree)
		common_parent = get_common_parent(path_v, path_u)
		increase_cost(v, tree, common_parent, w)
		increase_cost(u, tree, common_parent, w)
	else:
		u = arr[1]
		v = arr[2]
		if u > v:
			(v, u) = (u, v)
		path_v = get_path(v, tree)
		path_u = get_path(u, tree)
		common_parent = get_common_parent(path_v, path_u)
		total = [0]
		calculate_cost(v, tree, common_parent, total)
		calculate_cost(u, tree, common_parent, total)
		print(total[0])


q = int(input())
L = [list(map(int, input().split())) for _ in range(q)]
T = {1: 0}

def binaire(n):
	if n <= 1:
		return [n]
	else:
		return binaire(n // 2) + [n % 2]

def inserer2(T, A, w, i):
	if i in T:
		T[i] += w
	else:
		T[i] = w
	if A == []:
		return T
	return inserer2(T, A[1:], w, 2 * i + A[0])

def inserer(T, A, B, w, i):
	if A == []:
		T = inserer2(T, B[1:], w, 2 * i + B[0])
		return T
	if B == []:
		T = inserer2(T, A[1:], w, 2 * i + A[0])
		return T
	if A[0] == B[0]:
		return inserer(T, A[1:], B[1:], w, 2 * i + A[0])
	else:
		T = inserer2(T, A[1:], w, 2 * i + A[0])
		T = inserer2(T, B[1:], w, 2 * i + B[0])
		return T

def compter2(T, A, i):
	if A == []:
		if i in T:
			return T[i]
		else:
			return 0
	elif i in T:
		return T[i] + compter2(T, A[1:], 2 * i + A[0])
	else:
		return compter2(T, A[1:], 2 * i + A[0])

def compter(T, A, B, i):
	if A == []:
		return compter2(T, B[1:], 2 * i + B[0])
	if B == []:
		return compter2(T, A[1:], 2 * i + A[0])
	if A[0] == B[0]:
		return compter(T, A[1:], B[1:], 2 * i + A[0])
	else:
		a = compter2(T, A[1:], 2 * i + A[0])
		b = compter2(T, B[1:], 2 * i + B[0])
		return a + b
for i in range(q):
	x = L[i]
	A = binaire(x[1])
	B = binaire(x[2])
	if x[0] == 1:
		T = inserer(T, A[1:], B[1:], x[3], 1)
	else:
		print(compter(T, A[1:], B[1:], 1))


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 way(v):
	A = []
	while v:
		A.append(v)
		v //= 2
	return A[::-1]

def edges_between(u, v):
	A = way(u)
	B = way(v)
	i = 0
	while i < min(len(A), len(B)) and A[i] == B[i]:
		i += 1
	C = A[i - 1:][::-1] + B[i:]
	D = []
	for i in range(len(C) - 1):
		D.append((C[i], C[i + 1]))
	return D

def make_good(A):
	return (min(A), max(A))

def mark(u, v, w, cost):
	A = edges_between(u, v)
	for elem in A:
		new_elem = make_good(elem)
		if new_elem in cost:
			cost[new_elem] += w
		else:
			cost[new_elem] = w

def calc(u, v, cost):
	A = edges_between(u, v)
	total = 0
	for elem in A:
		new_elem = make_good(elem)
		if new_elem in cost:
			total += cost[new_elem]
	return total

def main():
	cost = dict()
	for i in range(int(input())):
		tmp = list(map(int, input().split()))
		if tmp[0] == 1:
			mark(tmp[1], tmp[2], tmp[3], cost)
		else:
			print(calc(tmp[1], tmp[2], cost))
main()


from collections import defaultdict

def log2(i):
	c = 0
	while i > 0:
		i >>= 1
		c += 1
	return c
q = int(input())
t = defaultdict(int)

def add(u, v, w):
	lu = int(log2(u))
	lv = int(log2(v))
	if lv > lu:
		(u, lu, v, lv) = (v, lv, u, lu)
	for _ in range(lu - lv):
		t[u] += w
		u >>= 1
	while u != v:
		t[u] += w
		t[v] += w
		u >>= 1
		v >>= 1

def query(u, v):
	lu = int(log2(u))
	lv = int(log2(v))
	if lv > lu:
		(u, lu, v, lv) = (v, lv, u, lu)
	ans = 0
	for _ in range(lu - lv):
		ans += t[u]
		u >>= 1
	while u != v:
		ans += t[u] + t[v]
		u >>= 1
		v >>= 1
	return ans
for _ in range(q):
	s = input()
	if s[0] == '1':
		(_, u, v, w) = map(int, s.split(' '))
		add(u, v, w)
	else:
		(_, u, v) = map(int, s.split(' '))
		print(query(u, v))


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)


from collections import Counter

def sort(a, b):
	if a > b:
		return (b, a)
	else:
		return (a, b)

def find_path(u, v):
	path = []
	(u, v) = sort(u, v)
	while u != v:
		path.append(sort(v // 2, v))
		v = v // 2
		(u, v) = sort(u, v)
	return path
dist = Counter()
n = int(input())
for i in range(n):
	l = [int(j) for j in input().split()]
	if l[0] == 1:
		path = find_path(l[1], l[2])
		for p in path:
			dist[p] += l[3]
	if l[0] == 2:
		cost = 0
		path = find_path(l[1], l[2])
		for p in path:
			cost += dist[p]
		print(cost)


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)


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter
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))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	q = int(input())
	c = {}
	while q:
		a = list(map(int, input().split()))
		if a[0] == 1:
			u = min(a[1], a[2])
			v = max(a[1], a[2])
			while v != u:
				if v > u:
					k = v >> 1
					if (k, v) in c:
						c[k, v] += a[3]
					else:
						c[k, v] = a[3]
					v = k
				else:
					k = u >> 1
					if (k, u) in c:
						c[k, u] += a[3]
					else:
						c[k, u] = a[3]
					u = k
		else:
			ans = 0
			u = min(a[1], a[2])
			v = max(a[1], a[2])
			while v != u:
				if v > u:
					k = v >> 1
					if (k, v) in c:
						ans += c[k, v]
					v = k
				else:
					k = u >> 1
					if (k, u) in c:
						ans += c[k, u]
					u = k
			print(ans)
		q -= 1
	return
main()


from collections import defaultdict
va = defaultdict(int)
tree = [[0, 0] for i in range(202)]
cnt = 1

def prefix(a, b):
	ans = ''
	for i in range(min(len(a), len(b))):
		if a[i] == b[i]:
			ans += a[i]
		else:
			break
	return ans
q = int(input())
for i1 in range(q):
	s = input()
	if s[0] == '1':
		(_, u, v, w) = map(int, s.split())
		u = bin(u).replace('0b', '')
		v = bin(v).replace('0b', '')
		lu = len(u)
		lv = len(v)
		m = prefix(u, v)
		lm = len(m)
		while lu > lm:
			lu -= 1
			va[u] += w
			u = u[:-1]
		while lv > lm:
			lv -= 1
			va[v] += w
			v = v[:-1]
	else:
		sum = 0
		(_, u, v) = map(int, s.split())
		u = bin(u).replace('0b', '')
		v = bin(v).replace('0b', '')
		lu = len(u)
		lv = len(v)
		m = prefix(u, v)
		lm = len(m)
		while lu > lm:
			lu -= 1
			sum += va[u]
			u = u[:-1]
		while lv > lm:
			lv -= 1
			sum += va[v]
			v = v[:-1]
		print(sum)


q = int(input())

def get_path(u, v):
	u2 = u
	v2 = v
	u_visited = set()
	while u2 > 1:
		u_visited.add(u2)
		u2 = u2 // 2
	u_visited.add(1)
	v2_path = []
	while v2 not in u_visited:
		v2_path.append(v2)
		v2 = v2 // 2
	path = v2_path + sorted([x for x in u_visited if x >= v2])
	return path
prices = {}
for i in range(q):
	row = list(map(int, input().split()))
	if row[0] == 1:
		(u, v, w) = row[1:]
		path = get_path(*sorted([u, v]))
		for (a_, b_) in zip(path, path[1:]):
			(a, b) = sorted([a_, b_])
			prices.setdefault((a, b), 0)
			prices[a, b] += w
	else:
		(u, v) = row[1:]
		path = get_path(*sorted([u, v]))
		price = 0
		for (a_, b_) in zip(path, path[1:]):
			(a, b) = sorted([a_, b_])
			price += prices.get((a, b), 0)
		print(price)


from sys import stdin, stdout
n = int(stdin.readline())
prices = {}
for i in range(n):
	s = stdin.readline().strip()
	if int(s[0]) == 1:
		(ind, a, b, w) = map(int, s.split())
		while a != b:
			if a > b:
				if (a, a // 2) not in prices:
					prices[a, a // 2] = w
				else:
					prices[a, a // 2] += w
				a //= 2
			else:
				if (b, b // 2) not in prices:
					prices[b, b // 2] = w
				else:
					prices[b, b // 2] += w
				b //= 2
	else:
		(ind, a, b) = map(int, s.split())
		cnt = 0
		while a != b:
			if a > b:
				if (a, a // 2) in prices:
					cnt += prices[a, a // 2]
				a //= 2
			else:
				if (b, b // 2) in prices:
					cnt += prices[b, b // 2]
				b //= 2
		stdout.write(str(cnt) + '\n')


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())


d = {}

def pro(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
	s = list(map(int, input().split()))
	if s[0] == 1:
		pro(s[1], s[2], s[3])
	else:
		print(pro(s[1], s[2], 0))


from collections import Counter

def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def shortest_path(i, j):
	path = []
	while i != j:
		if i > j:
			path.append((i // 2, i))
			i //= 2
		else:
			path.append((j // 2, j))
			j //= 2
	return path

def solve():
	q = read_int()
	wage = Counter()
	for _ in range(q):
		l = read_ints()
		if l[0] == 1:
			(u, v, w) = l[1:]
			if u > v:
				(u, v) = (v, u)
			for pair in shortest_path(u, v):
				wage[pair] += w
		else:
			(u, v) = l[1:]
			if u > v:
				(u, v) = (v, u)
			T = 0
			for pair in shortest_path(u, v):
				T += wage[pair]
			print(T)
solve()


q = int(input())
ans = []
cost = {}

def getn(v, k=1):
	res = []
	while k <= v:
		res.append(v)
		v //= 2
	return res

def getp(arr):
	res = []
	for i in range(len(arr) - 1):
		res.append((arr[i], arr[i + 1]))
	return res

def gets(u, v):
	(resu, resv) = (getn(u), getn(v))
	for i in resv:
		if i in resu:
			return getp(getn(u, i)) + getp(getn(v, i))
for i in range(q):
	(t, *p) = map(int, input().split())
	(u, v) = (p[0], p[1])
	if v < u:
		(u, v) = (v, u)
	path = gets(u, v)
	if t == 1:
		for rd in path:
			if rd in cost:
				cost[rd] += p[2]
			else:
				cost[rd] = p[2]
	else:
		tot = 0
		for rd in path:
			if rd in cost:
				tot += cost[rd]
		ans.append(tot)
print('\n'.join(map(str, ans)))


import collections

def gen_path_to_root(x):
	while x:
		yield x
		x //= 2

def gen_path(a, b):
	ap = tuple(gen_path_to_root(a))
	bp = tuple(gen_path_to_root(b))
	x = max(set(ap) & set(bp))
	for xp in (ap, bp):
		for i in range(1, len(xp)):
			if xp[i] < x:
				break
			yield frozenset((xp[i - 1], xp[i]))
costs = collections.defaultdict(int)
q = int(input())
for _ in range(q):
	(t, *rest) = map(int, str.split(input()))
	if t == 1:
		(*rest, w) = rest
		for step in gen_path(*rest):
			costs[step] += w
	else:
		print(sum(map(lambda k: costs[k], gen_path(*rest))))


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


from sys import stdin
from collections import *

def arr_inp(n):
	return [int(x) for x in stdin.readline().split()]

def lca(u, v, w):
	res = 0
	while u != v:
		if u < v:
			(u, v) = (v, u)
		if w:
			mem[u, u >> 1] += w
			mem[u >> 1, u] += w
		else:
			res += mem[u, u >> 1]
		u >>= 1
	return res
(ans, mem) = ([], defaultdict(int))
for i in range(int(input())):
	arr = arr_inp(1)
	if arr[0] == 1:
		lca(arr[1], arr[2], arr[3])
	else:
		ans.append(str(lca(arr[1], arr[2], 0)))
print('\n'.join(ans))


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


from math import log2

class Node:

	def __init__(self, level, left, right, parent, val):
		self.val = val
		self.level = level
		self.left = left
		self.right = right
		self.parent = parent
tree = dict()

def create_path(u):
	if u == 0 or u in tree:
		return
	node = Node(log2(u), [u + u, 0], [u + u + 1, 0], [u // 2, 0], u)
	tree[u] = node
	create_path(u // 2)

def ascend(x, cost, w=0):
	x.parent[1] += w
	cost += x.parent[1]
	tree[x.val] = x
	x = tree[x.parent[0]]
	return (cost, x)

def common_ancestor(u, v, w=0):
	a = tree[u]
	b = tree[v]
	cost = 0
	while a != b:
		if a.level == b.level:
			(cost, a) = ascend(a, cost, w)
			(cost, b) = ascend(b, cost, w)
		elif a.level < b.level:
			(cost, b) = ascend(b, cost, w)
		elif b.level < a.level:
			(cost, a) = ascend(a, cost, w)
	return cost

def update_path(u, v, w):
	if u not in tree:
		create_path(u)
	if v not in tree:
		create_path(v)
	cost = common_ancestor(u, v, w)
	return cost

def main():
	q = int(input())
	for i in range(q):
		str = input()
		w = None
		if str[0] == '1':
			(z, v, u, w) = [int(x) for x in str.split()]
			if v < u:
				(u, v) = (v, u)
			update_path(u, v, w)
		else:
			(z, v, u) = [int(x) for x in str.split()]
			if v < u:
				(u, v) = (v, u)
			print(update_path(u, v, 0))
main()


import sys
q = int(input())
fees = {}
for i in range(q):
	(event_type, v, u, *w) = map(int, input().split())
	if event_type == 1:
		w = w[0]
		(u, v) = (min(u, v), max(u, v))
		while u != v:
			parent = v // 2
			if v not in fees:
				fees[v] = 0
			fees[v] += w
			v = parent
			(u, v) = (min(u, v), max(u, v))
	elif event_type == 2:
		(u, v) = (min(u, v), max(u, v))
		res = 0
		while u != v:
			parent = v // 2
			if v in fees:
				res += fees[v]
			v = parent
			(u, v) = (min(u, v), max(u, v))
		print(res)


from collections import defaultdict
R = lambda : map(int, input().split())
g = defaultdict(int)
for _ in range(int(input())):
	arr = list(R())
	if arr[0] == 1:
		(l, r, w) = arr[1:]
		while l != r:
			if l < r:
				g[r] += w
				r //= 2
			else:
				g[l] += w
				l //= 2
	else:
		(l, r) = arr[1:]
		res = 0
		while l != r:
			if l < r:
				res += g[r]
				r //= 2
			else:
				res += g[l]
				l //= 2
		print(res)


(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))


def IncreaseCost(x, y, z):
	a = min(x, y)
	b = max(x, y)
	while a != b:
		while b > a:
			if not str(b // 2) + ' ' + str(b) in d:
				d[str(b // 2) + ' ' + str(b)] = z
			else:
				d[str(b // 2) + ' ' + str(b)] = d[str(b // 2) + ' ' + str(b)] + z
			b = b // 2
		(a, b) = (b, a)

def CountCost(x, y):
	res = 0
	a = min(x, y)
	b = max(x, y)
	while a != b:
		while b > a:
			if str(b // 2) + ' ' + str(b) in d:
				res = res + d[str(b // 2) + ' ' + str(b)]
			b = b // 2
		(a, b) = (b, a)
	return res
q = int(input())
d = {}
res = []
for i in range(0, q):
	line = input().split()
	if line[0] == '1':
		IncreaseCost(int(line[1]), int(line[2]), int(line[3]))
	else:
		res = res + [CountCost(int(line[1]), int(line[2]))]
for i in res:
	print(i)