我们已经见过许多关于树的问题了，所以今天我们来解决一个简单的树上问题。

给定一棵包含 $N$ 个节点的树（无环无向连通图）。树的节点编号从 $1$ 到 $N$。每个节点都有一个权值 $W_i$。我们将对这棵树进行四种操作，你需要高效地解决它们。祝你玩得开心！

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 10$)。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $N$ ($1 \le N \le 100,000$)。接下来的 $N-1$ 行，每行包含两个整数 $x, y$，表示它们之间有一条边。这同时也给出了初始的树结构。

下一行包含 $N$ 个整数，表示每个节点的初始权值 $W_i$ ($0 \le W_i \le 1,000,000,000$)。

下一行包含一个整数 $Q$ ($1 \le Q \le 10,000$)。接下来的 $Q$ 行，每行以一个整数 $1, 2, 3$ 或 $4$ 开头，表示操作的类型。

1. 给定三个整数 $u, v, w$，将路径上从 $u$ 到 $v$（包含 $u$ 和 $v$）的所有节点的权值更新为 $w$ ($1 \le u, v \le N, 0 \le w \le 1,000,000,000$)。
2. 给定三个整数 $u, v, w$，将路径上从 $u$ 到 $v$（包含 $u$ 和 $v$）的所有节点的权值增加 $w$ ($1 \le u, v \le N, 0 \le w \le 1,000,000,000$)。
3. 给定三个整数 $u, v, w$，将路径上从 $u$ 到 $v$（包含 $u$ 和 $v$）的所有节点的权值乘以 $w$ ($1 \le u, v \le N, 0 \le w \le 1,000,000,000$)。
4. 给定两个整数 $u, v$，查询路径上从 $u$ 到 $v$（包含 $u$ 和 $v$）的所有节点的权值的立方和。即输出 $\sum W_x^3$，其中 $x$ 为路径上的节点 ($1 \le u, v \le N$)。

输出格式

对于每个测试用例，输出一行 “Case #x:”，其中 $x$ 是测试用例的编号（从 $1$ 开始）。对于操作 $4$，输出一行一个整数表示结果。结果可能很大，请对 $1,000,000,007$ ($10^9 + 7$) 取模。

样例

样例输入 1

1
5
2 1
1 3
5 3
4 3
1 2 3 4 5
6
4 2 4
1 5 4 2
2 2 4 3
3 2 3 4
4 5 4
4 2 4

样例输出 1

Case #1:
100
8133
20221