Rik, the Space Traveler

Mr. Rik is a famous space traveler. He lives in a galaxy named Victa. There are many planets in this galaxy. Rik doesn’t travel all the planets. He only travels the planets which are numbered from 1 to n. The planets are connected by bidirectional space tunnels. The fare of these space tunnels is so cheap. If planet u and planet v are connected by a space tunnel, only 1 gk needs to be paid to travel from u to v or from v to u. Here, "gk" is the name of the currency of the galaxy Victa. Rik starts traveling from a planet x with k gk in his moneybag. He can visit a planet for more than one time. Whenever he uses a space tunnel, 1 gk decreases from his moneybag. If the amount of money in his moneybag becomes 0 gk on a planet y, he stops traveling. Rik knows that there can be more than one planet y for a starting planet x and there can be many ways to travel. Two ways are different if the traversed planets are different or the traversal orders of the planets are different. Planets numbered from 1 to n also have a special characteristic. For any two of these planets u and v, it is always possible to travel from u to v or from v to u if Rik has enough gk.

Now, Mr. Rik is trying to calculate an important thing. How many ways he can travel If he starts traveling from a planet x with k gk in his moneybag?

For example, let, n = 3. So, Rik can travel the planets numbered from 1 to 3. Let, planet 1 and planet 2 are connected by a space tunnel, planet 1 and planet 3 are connected by another space tunnel. In this case, if Rik starts traveling from planet 1 with 3 gk, there are 4 ways to travel. The ways are:

                                   1 -> 2 -> 1 -> 3
                                   1 -> 3 -> 1 -> 2
                                   1 -> 2 -> 1 -> 2
                                   1 -> 3 -> 1 -> 3

Input

The first line contains two integers n and m (2<=n<=100; 1<=m<=(n(n-1))/2*). **m** is the number of space tunnels.

Then, m lines describing the space tunnels follow. The i-th line contains two space-separated integers ui, vi (1 <= ui, vi <= n; ui ≠ vi) - the planets, connected by the i-th space tunnel. It is guaranteed that, there's at most 1 space tunnel between two planets u and v.

The next line contains an integer q (1 <= q <= 103) - denoting the number of queries. Then q lines follow, each line containing the query. Each query contains an integer k (1 <= k <= 107), the amount of money (gk) in Rik's moneybag before starting traveling.

For 10 points: 2 <= n <= 5
For 40 points: 2 <= n <= 20
For 100 points: 2 <= n <= 100

Output

For each query, print the query number on a single line, in the format “Query x:” where x is the query number. Then n lines follow. In the i-th line, print the number of ways Rik can travel if he starts traveling from planet i with k gk in his moneybag. Since the number of ways can be very big, print the number of ways modulo 1000000007.

Sample

Input	Output
3 2 1 2 1 3 2 3 2	Query 1: 4 2 2 Query 2: 2 2 2
Notes: For the first query: Ways for starting from planet 1 are explained in problem statement. If planet 2 is the starting planet, the ways are: 2 -> 1 -> 2 -> 1 2 -> 1 -> 3 -> 1 If planet 3 is the starting planet, the ways are: 3 -> 1 -> 3 -> 1 3 -> 1 -> 2 -> 1