在发现泰拉的“伪天空”后，Kristen 建造了一座空间站。

该空间站可以表示为一棵包含 $n$ 个节点的树，节点编号从 $1$ 到 $n$。随着空间站发射过程的启动，空间站的能量正在增加。最初，节点 $i$ 有 $b_i$ 单位的能量。每天开始时，节点 $i$ 的能量会增加 $a_i$。

纯净水对生命至关重要。作为一名水精灵，Muelsyse 需要将纯净水运输到空间站的每个节点。

你需要处理 $k$ 次操作，操作分为两类：

1. 在第 $x$ 天结束时，空间站的模式发生改变。此时会选择两个直接相连的节点 $u$ 和 $v$。节点 $u$ 的 $a_u$（即节点 $u$ 的每日能量增量）将减少 $w$，而节点 $v$ 的 $a_v$（即节点 $v$ 的每日能量增量）将增加 $w$。保证存在连接 $u$ 和 $v$ 的边，且在操作执行前 $a_u \ge w$。
2. 在第 $x$ 天，Muelsyse 需要将纯净水运输到每个节点。具体来说，Muelsyse 将选择一个节点作为水源，记为 $r$。将纯净水从水源 $r$ 运输到节点 $u$ 的代价为 $dis_u \times c_u$ 个“流动形态”，其中 $dis_u$ 表示从节点 $u$ 到 $r$ 的路径上的边数，$c_u$ 表示节点 $u$ 当前的能量值。请帮她选择一个合适的水源节点，使得她消耗的“流动形态”总数最少。

保证在这些操作中 $x$ 是递增的。形式化地说，设第 $i$ 次操作中的 $x$ 值为 $x_i$，则对于所有 $1 \le i \le k - 1$，满足 $x_i < x_{i+1}$。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n, k \le 10^5$)，分别表示空间站的节点数和操作数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1000$)，其中 $a_i$ 表示节点 $i$ 的每日能量增量。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 1000$)，其中 $b_i$ 表示节点 $i$ 的初始能量。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示树中的一条边。

接下来的 $k$ 行包含操作描述。第 $i$ 次操作属于以下两种类型之一：

• “1 $x_i$ $u_i$ $v_i$ $w_i$” ($1 \le x_i \le 10^9, 1 \le u_i, v_i \le n$)，含义如上所述。保证存在连接 $u_i$ 和 $v_i$ 的边，且在操作执行前 $a_{u_i} \ge w_i$。
• “2 $x_i$” ($1 \le x_i \le 10^9$)，含义如上所述。

保证在这些操作中 $x$ 是递增的。

输出格式

对于每个类型 2 的操作，输出一个整数，表示 Muelsyse 消耗的最小“流动形态”总数。

样例

输入 1

5 10
1 1 4 5 1
4 1 9 1 9
1 2
2 3
2 4
1 5
2 1
1 2 3 2 3
1 3 4 2 4
1 4 2 1 8
2 5
1 6 1 5 7
2 7
2 8
2 9
2 10

输出 1

44
83
116
134
146
158