甲城是一座新兴城市，城里开设了 $n$ 座工厂，分属 $k$ 家单位，每家单位至少有一座工厂。其中，第 $i$ 座工厂属于第 $c_i$ 家单位，有 $w_i$ 名工人。

目前，甲城的路网还比较不发达。城内有 $m$ 条道路，每条道路的两端是不同的工厂。如果将工厂视作图的点，道路视作图的边，那么这张图是仙人掌。

• 仙人掌，就是一张无向连通图，其中每一条边都属于至多一条简单回路。

现在甲城准备开通该城第一条公交线路。目前已经决定了：

• 这条公交线路将连接两座不同的工厂，且两座工厂属于同一单位。
• 这条公交线路在现有道路上行驶，且往返的路线是一致的。
• 这条公交线路不会重复经过同一座工厂。

一条公交线路的负荷，是该线路起点、终点和途经的所有工厂里工人的总数。

我们认为：仅仅将一条公交线路的上行、下行方向互换，得到的是本质相同的线路；但是，如果两家工厂之间有两条不同道路直接相连，那么经过不同道路的两条公交线路本质不同。

随着生产规模的扩大，该城进行了 $q$ 次招工活动。每次活动都形如：第 $i$ 座工厂新招聘了 $\Delta w$ 名工人。除此之外，各厂的工人数量不会变化，各次招工活动不独立。

现在，甲城学生算法竞赛协会悬赏 $100$ 分，请你对于初始的情况和每次招工后的情况，分别计算：在上述条件限制下，所有可能的本质不同线路的负荷之和是多少？由于答案可能会太大，请你对 $10^9+7$ 取模。

输入格式

第一行三个正整数 $n, m, k$, 分别表示工厂、道路、单位的数量。

接下来一行 $n$ 个整数 $c_1, c_2, \ldots, c_n$, 表示各工厂所属的单位。

接下来一行 $n$ 个整数 $w_1, w_2, \ldots, w_n$, 表示各工厂的工人数。

接下来 $m$ 行每行两个整数 $u, v$, 表示有一条连接第 $u, v$ 座工厂的道路。

接下来一行一个非负整数 $q$, 表示招工的次数。

接下来 $q$ 行每行两个正整数 $i, \Delta w$, 表示这次招工时，第 $i$ 座工厂新招聘了 $\Delta w$ 名工人。

输出格式

$q+1$ 行，每行一个整数，分别表示最初和每次招工后，所有满足限制的本质不同线路的负荷之和，对 $10^9+7$ 取模后的值。

样例一

input

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

output

47
52

explanation

总共有 $6$ 条线路：

1. $1\to_12\to3$, 修改前负荷 $6$, 修改后负荷 $7$;
2. $1\to_22\to3$, 修改前负荷 $6$, 修改后负荷 $7$;
3. $1\to_12\to4\to3$, 修改前负荷 $10$, 修改后负荷 $11$;
4. $1\to_22\to4\to3$, 修改前负荷 $10$, 修改后负荷 $11$;
5. $2\to4$, 修改前、后负荷均为 $6$;
6. $2\to3\to4$, 修改前负荷 $9$, 修改后负荷 $10$.

所以修改前总负荷 $47$, 修改后总负荷 $52$.

样例二

input

4 4 1
1 1 1 1
1 2 3 4
1 2
2 3
3 4
4 1
0

output

90

限制与约定

对于全部数据，$2\le n\le5\times10^5$, $n-1\le m\le 2n-2$, $1\le k\le n$, $0\le q\le n$, $1\le c_i\le k$, $1\le w_i, \Delta w\le 100$.

子任务一（$10$ 分）：$n\le100$.

子任务二（$20$ 分）：$n\le10^5, k\le5$.

子任务三（$20$ 分）：$m=n-1$.

子任务四（$15$ 分）：$w_1=w_2=\cdots=w_n=1$, $q=0$.

子任务五（$20$ 分）：$n\le10^5$.

子任务六（$15$ 分）：无特殊限制。