Professor Rio has an amazing Christmas tree. Unlike other trees, this Christmas tree has some special properties.
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.
The first line contains three integers (), () and (). Here, is the number of nodes in the tree, is the number of edges and is the number of levels.
The next line contains integers, (). The -th of them is the beauty of the -th vertex.
Each of the next lines describe each level. The -th line start with an integer which is the number of nodes in level and is followed by integers, the () of the vertex in that level.
Then M lines follows. Each containing two integers and (). Which means there is an edge between vertex and .
The next line contains an integer () which represents the number of queries. Then lines follows each having a single integer .
For each of the query, you have to print the attractiveness of vertex . As this value might become huge, print it with modulo .
Input | Output |
---|---|
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: 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. |