题目描述

现在，嘤嘤有一棵含有 $n$ 个结点且根为 $1$ 号结点的树，嘤嘤将其命名为珂朵莉树，每个结点具有一个权值，每个结点与根的距离就是该结点的深度。

然后，嘤嘤会在这棵树上增加 $m$ 条辅边，任意一条辅边不会和原来的树边或其他辅边重合（增加的辅边不会影响结点的深度）。

之后，嘤嘤会进行进行 $q$ 次操作。

• 操作一：让结点 $u$ 的权值增加 $k$ ，并对与结点 $u$ 相邻的结点中，深度比结点 $u$ 小的结点重复操作一。

• 操作二：让结点 $u$ 的权值增加 $k$ ，并对与结点 $u$ 相邻的结点中，深度比结点 $u$ 大的结点重复操作二。

嘤嘤想知道，经过 $q$ 次操作后，所有结点的权值分别是多少。

输入描述

第一行三个整数 $n,m,q$ ，分别表示树的结点个数，辅边条数，操作次数。

第二行 $n$ 个整数 $a_i$ ，表示每个结点的初始权值。

接下来 n-1行，每行两个整数 $u,v(1 \le u,v \le n,u \neq v)$ 表示树的结构。

接下来 $m$ 行，每行两个整数 $u,v(1 \le u,v \le n,u \neq v)$ 表示辅边连接的两个结点。

接下来 $q$ 行，每行三个整数 $t(1 \le t \le 2),u(1 \le u \le n),k$，分别表示操作类型，操作的结点。

输出描述

一行 $n$ 个整数，表示树上每个结点的权值，由于权值可能很大，请将权值对 $10^9 + 7$ 进行取模。

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

6 3 4 4 3 2 4

【样例 1 说明】

图中蓝色的边即为辅边。

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

1 1 4 5 1 4

【数据范围】

对于 $20\%$ 的数据 $n \le 1000, m = 0 , q \le 1000，k\le1000$。

对于另外 $20\%$ 的数据$n \le 10^5, m = 0$,保证没有操作一。

对于 $100\%$的数据 $n \le 10^5, m \le 2 \times 10^5, q \le 2 \times 10^5,k \le 10^9$