题目描述

有一棵由无数个编号从 $1$ 开始的节点组成的树，$i$ 与 $2×i$ 和 $2×i+1$ 之间有一条无向边，任意两点间有唯一最短路。

最初，所有的边权为 $0$。有 $q$ 次操作如下：

1. 1 v u w 表示将 $u$ 到 $v$ 最短路径中的所有边边权加上 $w$。
2. 2 v u 表示询问从 $u$ 到 $v$ 最短路径上的边权之和。

对于每个操作 $2$，输出答案。

p.s：这里的最短路径指到达最少数量的点或边的路径。

输入格式

第一行一个整数 $q$，$1\le q\le 1000$。

接下来 $q$ 行，每行一个操作，$1\le v, u\le 10^{18}$，$1\le w\le 10^9$。

输出格式

对于每个操作 $2$，在一行中输出一个整数表示答案。

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

94
0
32