There is a grid of n rows and m columns each cell containing a robot. Rows are numbered 0 to n-1 and columns 0 to m-1.
Every robot has some initial energy associated with it which is equal to the number of distinct palindromes in its name. Some robots are connected with special connectors. Every morning these connectors generate some amount of energy and distribute it among the robots which are connected via this connector.
This is how it actually works-
Let two robots R1 with energy e1 and R2 with energy e2 are connected to each other, then the connector will generate energy e2 for robot R1 and energy e1 for robot R2 i.e final energy of robots R1 and R2 is e1+e2 both. On second day they both have energy 2*(e1+e2), as on 2nd day connector will use energies from the previous day not the initial energies.
Your task is to calculate the final energy (modulo 1000000007) of each robot after D days.
Two Robots can be connected to each other with multiple connectors.

INPUT -

First line contains two integers (n,m) ,size of grid.
Next n lines containing m space separated words(names of each robots).
Then one integer C(number of connectors)
Next C lines contains four integers(x1,y1,x2,y2) each i.e. robot at (x1,y1) is connected with robot at(x2,y2)
0 ≤ x1,x2 < n
0 ≤ y1,y2 < m
Last line contains one integer D.

OUTPUT-

n lines each containing m space separated integers i.e. final energy of each robot after D days modulo (10^9+7).

Constraints-

1 ≤ n,m ≤ 10

0 ≤ C ≤ 100

0 < D ≤ 1000000000

Robot names contains only lowercase (a-z) characters.

1 ≤ length of each robot name ≤ 10

SAMPLE INPUT
2 2
ab ba
cc da
3
0 0 1 1
0 0 1 1
1 0 1 1
4

SAMPLE OUTPUT
230 2
116 256

Explanation

Initial Energies
2 2
2 2

After day 1-
6 2
4 8

After Day 2-
22 2
12 24

After Day 3-
70 2
36 80

After Day 4-
230 2
116 256

见题面

见题面