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: competition

Starter code:

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

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 add_edges(s1, s2, w):
    nonlocal 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):
    nonlocal 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]))        
                


def main():
    d = {}
    for _ in range(int(input())):
        c, *l = input().split()
        if c == "1":
            v, u, w = list(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 = list(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)


def __starting_point():
    main()

__starting_point()

def main():
    from collections import Counter
    d = Counter()
    for _ in range(int(input())):
        c, *l = input().split()
        if c == "1":
            v, u, w = list(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 = list(map(int, l))
            while u != v:
                if u < v:
                    w += d[v]
                    v //= 2
                else:
                    w += d[u]
                    u //= 2
            print(w)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
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


def __starting_point():
    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))


__starting_point()

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


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

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):
    #retourne la liste des ARETES empruntées
    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)


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:  # To add
    lca(l[1],l[2],l[3])
  else: print(lca(l[1],l[2],0))

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:  # To add

    lca(l[1],l[2],l[3])

  else: print(lca(l[1],l[2],0))



# Made By Mostafa_Khaled


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 functools import lru_cache
from collections import defaultdict
from itertools import tee


price = defaultdict(dict)


def add(start, end, w):
    nonlocal 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:
                #print(l_way)
                #print(r_way)
                r_way = r_way[:r_way.index(max(union))]
                l_way = l_way[:l_way.index(max(union))]
                #print(l_way)
                #print(r_way)
                #print(r_way)
                #del r_way[-1]
                r_way.reverse()
                return l_way + [union.pop()] + r_way

    #print(_get_raw_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]))

#print(get_way(568636620057521218, 935366325112217858))


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


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 list(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 list(fees.keys()):
            fees[fee] += w
        else:
            fees[fee] = w
        if fee2 in list(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]))
                #print(fees)

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask696ASolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()

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:
        #action == 2
        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)


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 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]
	# print (p1,p2)
	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])
	# print (b)
	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)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Jul 15 23:50:55 2020

@author: shailesh
"""


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]
#        print(node_1,cost)
        node_1 //= 2
    
    while node_2!=0:
        if new_dict[node_2]:
            cost -= intersect_dict[node_2]
#            print(node_2)
            break
        else:
            new_dict[node_2] = 1
            cost += intersect_dict[node_2]
            node_2 //= 2
#            print(node_2,cost)
    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())

#arr = [0 for i in range(n+1)]

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)
    


# from debug import debug
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)