트리 위의 게임

친구 $m$명이 $0$부터 $m-1$까지 번호가 붙은 채로 게임을 한다. 색이 $c$가지인 카드가 있으며, 색은 $0$부터 $c-1$까지 번호가 붙어 있다. 색 $i$ 카드마다 고정된 값 $p_i$가 있다.

게임을 시작할 때 각 플레이어는 카드를 원하는 만큼 고르되, 같은 색 카드는 한 장만 고른다. 서로 다른 친구가 같은 색 카드를 골라도 된다. 덱의 점수는 덱에 있는 카드 값들의 최대공약수(GCD)다. 빈 덱의 점수는 $0$이다.

게임은 $0$부터 $n-1$까지 번호가 붙은 노드 $n$개로 이루어진 트리 위에서 진행된다. 노드 $v$에는 색 $c_v$의 카드가 한 장 있다. 서로 다른 노드가 같은 색 카드를 가질 수 있다.

게임은 $m$라운드로 진행된다. $i$라운드에서는 $i$번째 친구가 플레이한다. 먼저 친구는 서로 다른 두 정점 $v$와 $u$를 고른다. 그다음 $v$에서 $u$까지 가는 경로 위의 모든 노드 $v_i$(양 끝 $v$와 $u$ 포함)에 대해, 본인을 포함한 모든 플레이어가 색 $c_{v_i}$의 카드를 한 장씩 뽑는다. 이미 그 색 카드를 가지고 있던 플레이어는 두 장을 모두 버린다. 이후 친구는 모든 플레이어 덱 점수의 합(본인 덱 포함)을 얻는다. 마지막으로 친구는 노드 $w$를 고르고, 더미에서 색 $y$의 새 카드를 뽑아 $w$의 카드와 바꾼다. 기존 카드는 버려지며 라운드가 끝난다.

첫 줄에는 정수 $m$, $c$, $n$이 주어진다 ($2 \le n, m \le 10^5$, $1 \le c \le 20$). 각각 친구 수(라운드 수), 카드 색의 수, 노드 수다.

둘째 줄에는 정수 $p_0, p_1, \dots, p_{c-1}$ ($0 \le p_i \le 10^9$)이 주어진다.

이어지는 $m$개의 줄마다 정수 $x$ ($0 \le x \le c$)로 시작하며, 이는 그 친구가 처음 가진 카드 수다. 뒤이어 $x$개의 정수 $y_0, y_1, \dots, y_{x-1}$ ($0 \le y_j < c$)이 주어지며, 이는 그 카드들의 색이다.

다음 줄에는 정수 $c_0, c_1, \dots, c_{n-1}$ ($0 \le c_v < c$)이 주어진다. $c_v$는 노드 $v$ 카드의 색이다.

이후 $n-1$개의 줄에 간선 $u$, $v$ ($0 \le u, v < n$)가 주어진다. 이 간선들은 트리를 이룬다.

마지막 $m$개의 줄에는 라운드 정보 $u$, $v$, $w$, $y$ ($0 \le u, v, w < n$; $u \ne v$; $0 \le y < c$)가 주어진다. $u$와 $v$는 그 라운드에서 고른 두 노드이고, $w$는 카드를 바꿀 노드, $y$는 새 카드의 색이다.

한 줄에 $m$개의 정수 $points_0, points_1, \dots, points_{m-1}$을 출력한다. $points_i$는 게임이 끝났을 때 $i$번째 친구가 얻은 점수를 $10^9 + 7$로 나눈 나머지다.