Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Christmas Tree

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 N (1 ≤ N ≤ 105), M (0 ≤ M ≤ 2*105) and K. (1 ≤ K ≤ 20) Here, N is the number of nodes in the tree, M is the number of edges and K is the number of levels.

The next line contains N integers, B[i] (3 ≤ B[i] ≤ 107). The ith of them is the beauty of the ith vertex.

Each of the next K lines describe each level. The ith line start with an integer Si which is the number of nodes in level i and is followed by Si integers, the id (1 ≤ id ≤ N) of the vertex in that level.

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

The next line contains an integer Q (1 ≤ Q ≤ 105) which represents the number of queries. Then Q lines follows each having a single integer u.

Output

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

Samples

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] = 7

A[5] = B[5] = 17

A[6] = B[6] = 7

A[7] = B[7] = 19

A[2] = (77 + 717 + 719) % (109+7) = 618763218

A[3] = (77 + 77 + 719) % (109+7) = 107227964

A[1] = (7(77 + 717 + 719) + 7(77 + 77 + 719)) % (109+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.

Author
  • flash_7's Avatar

    flash_7

    Tarango works NSUPS. He loves to play FIFA & travel with friends. When not solving problems, he spends most of his time day dreaming. And, he most definitely is not a "manga lover".
Discussion
Submit

Login to submit