巴尼住在纽约。纽约市有无数个从 1 开始编号的正整数交叉路口。对于每个正整数 i,在交叉路口 i 和 2i 之间存在一条双向道路,在 i 和 2i + 1 之间存在另一条道路。您可以清楚地看到,任意两个交叉点之间都存在唯一的最短路径。
最初任何人都可以免费通过任何道路。但由于 SlapsGiving 就在我们前面,很快就会有 q 个连续的事件发生。有两种类型的事件:
1. 政府制定新规则。规则可以用整数v、u和w表示。这一行动的结果是,从 u 到 v 的最短路径上所有道路的通行费增加了 w 美元。
2. 巴尼开始从某个十字路口 v 出发,前往十字路口 u,那里有一个他想拥抱的女孩(使用他的假名 Lorenzo Von Matterhorn)。他总是使用两个交叉路口之间的最短路径(访问最少数量的交叉路口或道路)。
政府需要你的计算。巴尼每次去抱女孩,你都需要告诉政府他应该付多少钱(他经过的所有道路的通行费之和)。
输入
输入的第一行包含单个整数 q (1 ≤ q ≤ 1 000)。
接下来的 q 行包含按时间顺序排列的事件信息。如果每个事件是政府制定新规则,将从 u 到 v 的最短路径上所有道路的通行费增加 w 美元,则用表格 1 v u w 描述;如果是 Barnie 从交叉路口 v 拥抱到交叉路口 u 的事件,则用表格 2 v u 描述。
每个描述行有 1 ≤ v、u ≤ 1018、v ≠ u、1 ≤ w ≤ 109 个状态。
输出
对于第二类型的每个事件,在一行中打印 Barney 在该事件中经过的所有道路的通行费总和。按相应事件的时间顺序打印答案。
示例
输入 #1
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
输出 #1
94 0 32
注意
在示例测试用例中:
以下是使用的交叉点:
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)。