Background

Description

定义数列 $F$ :

给定一棵 $N$ 个节点的树，每个点 $i$ 有一个权值为 $A_i$。

接下来有 $M$ 个操作：

1 u v: 设树上 $u$ 点到 $v$ 点路径上节点为 $b_1, b_2, \cdots ,b_k$ ，询问 $\sum\limits_{i=1}^k\sum\limits_{j=i}^kF(\sum\limits_{t=i}^jA_{b_t})$ 的值。（答案对$10^9+7$取模）

2 x y z: 删除连接 $y$ 与 $x$ 的无向边（保证存在此边），然后加入一条连接 $y$ 与 $z$ 的无向边，保证操作后仍然为一棵树。

3 u v K: 将 $u$ 到 $v$ 路径上所有节点的权值修改为 $K$。

Format

Input

第 $1$ 行，$4$ 个正整数 $N, M, a, b$。

第 $2$ 行，$N$ 个正整数 $A_i$ 表示各点的点权。

接下来 $N-1$ 行，每行两个数 $x_i,y_i$，表示初始树上存在连接 $x_i$ 与 $y_i$ 的无向边。

最后 $M$ 行，每行一个操作。

Output

对于每一个操作 $1$ ，输出一行表示答案。

Samples

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

17
7
36

Limitation

对于 $30\%$ 的数据，满足 $1\leq N, M \leq 500, 1\leq A_i, K, a, b\leq 10$。

对于 $100\%$ 的数据，满足 $1\leq N,M \leq 10^5, 1\leq A_i, K, a, b\leq 10^9$。