E. Crumby Conundrum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As many know from the tale of Hansel and Gretel, they disperse breadcrumbs throughout the forest they're traveling in to make sure they don't get lost. After Gretel's heroics to escape from the witch and return home, the two thought they were done with these adventures. Of course, reality is not always what it seems...

The witch somehow survived the oven, and has magically teleported Hansel and Gretel into a dark room. She warns them that they are about to be teleported into an $$$n$$$ x $$$n$$$ forest. The siblings are presented the following drawing of the forest grid:

  • "." denotes an empty space (there are at least two of these)
  • "#" denotes an impassable tree
  • "E" denotes an exit (there are at least one and most $$$n$$$ of these)

Hansel and Gretel are told that in each of $$$q$$$ simulations, they will be randomly placed in an empty cell. They will be given $$$q_i$$$ breadcrumbs, and they will be required to place a breadcrumb at every cell in the shortest path to an exit (this includes both the "spawn point" and the exit). If Hansel and Gretel fail to reach an exit in any of the queries (i.e. they have too few breadcrumbs), the witch will return the favor and push the siblings into an oven!

Fortunately, Gretel has a machine she created that the witch doesn't know about! Before each simulation, she can input $$$p_i$$$: the probability that Hansel and Gretel can reach the exit from a randomly-selected empty cell if they start with $$$q_i$$$ breadcrumbs. As long as the probability is accurate, the machine will guarantee Hansel and Gretel survive the simulation without the witch knowing. If any probability is wrong... to say the least, they're cooked. Help them survive the forest (again)!

Input

The first line will contain $$$n$$$ ($$$3 \le n \le 1000$$$) and $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), the size of the forest and the number of queries.

The next $$$n$$$ lines will contain a string of length $$$n$$$, representing a row in the grid with the above key. It is guaranteed there exists at least two "." characters and at least one and at most $$$n$$$ "E" characters in the grid.

The next $$$q$$$ lines each contain one integer $$$q_i$$$ ($$$2 \le q_i \le n^2$$$), the breadcrumbs in the $$$i$$$'th simulation.

Output

Print out $$$q$$$ lines, where the $$$i$$$'th line contains the probability ($$$p_i$$$) for the $$$i$$$'th query. $$$p_i$$$ should have an absolute or relative error of at most $$$10^{-6}$$$, and can be equal to $$$0$$$ or $$$1$$$.

Examples
Input
4 3
.#..
..E.
##..
.E..
2
3
4
Output
0.54545455
0.90909091
1.00000000
Input
5 3
E#...
##.##
...#E
...##
.....
2
4
10
Output
0.00000000
0.00000000
0.00000000
Note

In the first sample, there are 6 empty cells that are 2 breadcrumbs from an exit, 4 cells that are 3 away, and 1 cell that is 4 away. Thus, the respective probabilities are $$$\frac{6}{11}$$$, $$$\frac{10}{11}$$$, and $$$1$$$.

In the second it is impossible to reach an exit, so our probability is always $$$0$$$.