有一些朋友，编号从 $0$ 到 $m-1$，正在玩一个游戏。游戏中有 $c$ 种不同颜色的卡牌，颜色编号从 $0$ 到 $c-1$。每种颜色 $i$ 的卡牌都有一个固定的价值 $p_i$。游戏开始时，每个玩家选择一定数量的卡牌，且不能持有超过一张同种颜色的卡牌（尽管不同的朋友可以选择相同颜色的卡牌）。我们定义一副牌组的得分为其所有卡牌价值的 GCD（最大公约数）。注意，空牌组的得分为 $0$。游戏将在一个无向图上进行，该图是一棵包含 $n$ 个节点的树，节点编号从 $0$ 到 $n-1$。每个节点 $v$ 上都有一张颜色为 $c_v$ 的卡牌，不同节点可能拥有相同颜色的卡牌。

游戏共有 $m$ 轮。在第 $i$ 轮中，第 $i$ 个朋友进行操作。首先，他选择两个不同的顶点 $u$ 和 $v$。然后，对于从 $u$ 到 $v$ 路径上的每个节点（包括 $u$ 和 $v$），每个玩家（包括他自己）都会抽取一张颜色为该节点卡牌颜色的卡牌。如果他们已经拥有了该颜色的卡牌，他们将丢弃这两张卡牌。在此之后，玩家 $i$ 获得的得分为所有玩家（包括他自己）牌组得分的总和。最后，他选择图中的一个节点，并从牌堆中抽取一张新卡牌。然后他将该节点的卡牌替换为刚抽到的卡牌（并丢弃旧卡牌），结束他的回合。

给定每一轮的信息，请输出每位朋友在游戏结束时拥有的总得分，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含三个整数 $m, c, n$ ($2 \le m, n \le 10^5$; $1 \le c \le 20$)：朋友的数量（即轮数）、不同颜色的数量以及树的节点数。

第二行包含 $c$ 个整数 $p_0, p_1, \dots, p_{c-1}$ ($0 \le p_i \le 10^9$)，其中 $p_i$ 是颜色为 $i$ 的卡牌的价值。

接下来的 $m$ 行，每行以一个整数 $x$ ($0 \le x \le c$) 开头，表示第 $i$ 个玩家初始持有的卡牌数量。随后是 $x$ 个整数 $y_0, y_1, \dots, y_{x-1}$ ($0 \le y_i < c$)：该玩家持有的所有卡牌的颜色。

下一行包含 $n$ 个整数 $c_0, c_1, \dots, c_{n-1}$ ($0 \le c_i < c$)，表示图中每个节点的卡牌颜色。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($0 \le u, v < n$)，表示节点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。

最后，$m$ 行中的每一行包含四个整数 $u, v, w, y$ ($0 \le u, v, w < n; u \neq v; 0 \le y < c$)，这些整数编码了每一轮的信息：选择的两个节点（$u$ 和 $v$）以及将要被替换卡牌的节点 $w$，替换后的卡牌颜色为 $y$。

输出格式

输出一行，包含 $m$ 个整数：$points_0, points_1, \dots, points_{m-1}$，其中 $points_i$ 是第 $i$ 位朋友最终拥有的得分，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

6 4 9

样例输入 2

7 4 8
28 49 88 49
1 1
3 2 0 3
0
1 3
0
0
1 0
2 2 2 2 3 0 1 2
0 2
0 3
2 6
0 4
3 7
7 1
2 5
1 4 4 1
3 6 4 2
7 6 4 2
6 2 2 2
4 2 7 0
2 3 5 3
5 1 4 1

样例输出 2

207 13 121 253 13 253 106