CF696A.Lorenzo Von Matterhorn

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 2_i_ and another road between i and 2_i_ + 1 for every positive integer i. You can clearly see that there exists a unique shortest path between any two intersections.

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

巴尼生活在纽约市（NYC）。NYC 拥有无限多个路口，编号为从 1 开始的正整数。对每个正整数 $i$，在路口 $i$ 与 $2i$ 之间存在一条双向道路，在路口 $i$ 与 $2i+1$ 之间也存在一条双向道路。显然，任意两个路口之间都存在唯一的一条最短路径。

最初，任何人都可以免费通行任意道路。但由于“掌掴感恩节”（SlapsGiving）即将到来，接下来将依次发生 $q$ 个事件。事件分为两类：

1. 政府颁布一项新规定。该规定由三个整数 $v$、$u$ 和 $w$ 表示。作为该操作的结果，从路口 $u$ 到 $v$ 的最短路径上的所有道路的通行费均增加 $w$ 美元。

2. 巴尼从某个路口 $v$ 出发，前往路口 $u$（那里有一位他想拥抱的女孩，他用假名“洛伦佐·冯·马特霍恩”（Lorenzo Von Matterhorn）接近她）。他总是沿最短路径（即经过最少数量的路口或道路）行进。

政府需要你进行如下计算：每次巴尼前往拥抱女孩时，你需要告诉政府他需支付多少钱（即他所经过的所有道路的通行费之和）。

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.

输入的第一行包含一个整数 $q$（$1 \le q \le 1\,000$）。

接下来的 $q$ 行按时间顺序描述事件。每个事件的格式如下：若为政府发布新规则的事件，则格式为 1 v u w，表示将从交叉路口 $u$ 到 $v$ 的最短路径上所有道路的通行费增加 $w$ 美元；若为 Barnie 前去拥抱的事件，则格式为 2 v u，表示 Barnie 从交叉路口 $v$ 前往交叉路口 $u$。

对每行描述，均有 $1 \le v,\,u \le 10^{18}$，$v \ne u$，且 $1 \le w \le 10^9$。

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.

对于每个第二类事件，输出巴尼在该事件中经过的所有道路的通行费总和，每行一个答案。按对应事件发生的时间顺序输出答案。

In the example testcase:

Here are the intersections used:

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

在示例测试用例中：

所使用的交叉路口如下所示：

1. 路径上的交叉路口为 3、1、2 和 4。
2. 路径上的交叉路口为 4、2 和 1。
3. 路径上的交叉路口仅有 3 和 6。
4. 路径上的交叉路口为 4、2、1 和 3。路径上各条道路的通行费用依次为 32、32 和 30。因此答案为 $32 + 32 + 30 = 94$。
5. 路径上的交叉路口为 6、3 和 1。
6. 路径上的交叉路口为 3 和 7。它们之间道路的通行费用为 0。
7. 路径上的交叉路口为 2 和 4。它们之间道路的通行费用为 32（在第一次事件中增加了 30，在第二次事件中又增加了 2）。