Limits 1s, 512 MB

Professor Rio has an amazing Christmas tree. Unlike other trees, this Christmas tree has some special properties.

  1. All the vertices are categorized in different levels (Level 1, Level 2, ..., Level K).
  2. There may exist an edge between vertex u and v only if their levels are adjacent to each other. The vertex with the higher level number will be the parent of another vertex.
  3. There are at most 20 levels in the Christmas tree.
  4. Each of the vertices of the tree has two types of special values, beauty and attractiveness.
  5. All the beauty values are prime numbers.
  6. Professor Rio doesn't like some of the prime numbers and so he has restricted them. The restricted list is [2, 3, 5, 11, 13, 41, 148721]. The beauty values also will not be from this restricted list.

Initially, you are given the beauty of all of the vertices. But you will have to find out the attractiveness of some of them. There is a formula to calculate this attractiveness value.

If a vertex u has X children v1, v2, v3, ..., vX, then the attractiveness of u is B[u]^A[v1] + B[u]^A[v2] + B[u]^A[v3] + ... + B[u]^A[vX]. But if a vertex u has no child then the attractiveness of u is B[u]. Here, A[i] = attractiveness of vertex i and B[i] = beauty of vertex i.

Input

The first line contains three integers NN (1N1051 ≤ N ≤ 10^{5}), MM (0M2×1050 ≤ M ≤ 2 \times 10^{5}) and KK (1K201 ≤ K ≤ 20). Here, NN is the number of nodes in the tree, MM is the number of edges and KK is the number of levels.

The next line contains NN integers, B[i]B[i] (3B[i]1073 ≤ B[i] ≤ 10^{7}). The ii-th of them is the beauty of the ii-th vertex.

Each of the next KK lines describe each level. The ii-th line start with an integer SiS_i which is the number of nodes in level ii and is followed by SiS_i integers, the ID\text{ID} (1IDN1 ≤ \text{ID} ≤ N) of the vertex in that level.

Then M lines follows. Each containing two integers uu and vv (1u,vN1 ≤ u, v ≤ N). Which means there is an edge between vertex uu and vv.

The next line contains an integer QQ (1Q1051 ≤ Q ≤ 10^{5}) which represents the number of queries. Then QQ lines follows each having a single integer uu.

Output

For each of the query, you have to print the attractiveness of vertex uu. As this value might become huge, print it with modulo 10000000071000000007.

Sample

InputOutput
7 8 3 
7 7 7 7 17 7 19
1 1
2 2 3
4 4 5 6 7
1 2
1 3
2 4
2 5
2 7
3 4
3 6
3 7
7
1
2
3
4
5
6
7
632804163
618763218
107227964
7
17
7
19

Explanation of the sample test case:

A[4]=B[4]=7A[4] = B[4] = 7

A[5]=B[5]=17A[5] = B[5] = 17

A[6]=B[6]=7A[6] = B[6] = 7

A[7]=B[7]=19A[7] = B[7] = 19

A[2]=(77+717+719)A[2] = (7^{7} + 7^{17} + 7^{19}) % (10^{9}+7) = 618763218

A[3]=(77+77+719)A[3] = (7^{7} + 7^{7} + 7^{19}) % (10^{9}+7) = 107227964

A[1]=(7(77+717+719)+7(77+77+719))A[1] = (7^{(7^{7} + 7^{17} + 7^{19})} + 7^{(7^{7} + 7^{7} + 7^{19})}) % (10^{9}+7) = 632804163

Note: Christmas tree of professor Rio is not a normal tree. So the total number of edges doesn't depend on the total number of vertex.


Submit

Login to submit.

Statistics

72% Solution Ratio
imranziadEarliest, Jan '17
mahabub.tweetFastest, 0.2s
SilentGLightest, 8.4 MB
mpnri2Shortest, 1457B
Toph uses cookies. By continuing you agree to our Cookie Policy.