Tomb Raider

Lara Croft, the main character of Tomb Raider who travels around the world searching for lost artifacts and infiltrating dangerous tombs and ruins. On every adventure, she has to take various challenges. On this problem, your task is to take Lara to her destination in a way that is the shortest in distance.

Consider a 2D R by C grid as the map of the tomb where # represents blockage, means Lara cannot move to that cell and . (dot) represent cells where Lara can enter. S represents the starting cell and E means where you'll have to take her. By the design of the game, you can take Lara to an adjacent cell that is only to the left, right, up or down directions on a single move.

After moving N step(s) an earthquake occurs and the map of the game changes. Some blockages can be removed by the earthquake and/or some accessible cells can turn into blockages due to the wreckage. The coordinate of S and E remains unchanged. Consider Lara knows how the map will look after the earthquake at the beginning of the game. If Lara steps on a cell on her $N^{th}$ step and that cell becomes a # after earthquake, she dies.

Your job is to calculate how many minimum steps does Lara have to take in order to reach her destination safely.

Input

On the first line of input, there will be two numbers R & C that denotes the number of Rows and Columns of the map.

Then R x C grid follows that denotes the map of the tomb where # represents the inaccessible cells and . means accessible cells. S denotes the starting position of Lara and E denotes the destination of Lara's position.

On the next line, there will be a number N which denotes that the number of steps required before the earthquake arrives.

Then R x C grid follows that denotes the map of the tomb after the earthquake where #, ., S, E denotes the same meaning as described above.

$2 ≤ R, C ≤ 10^{3}$
$1 ≤ N ≤ 10^{6}$

Output

If it is possible to reach the destination, print the minimum number of steps required. Otherwise, print ”Not Possible!” without the double quote.

Samples

Input	Output
7 7 ####### #S....# #####.# #####.# #####.# #E....# ####### 3 ####### #S....# ###.#.# ###.#.# ###.#.# #E....# #######	10

Input	Output
7 7 ####### #S....# #####.# #####.# #####.# #E....# ####### 3 ####### #S....# #####.# #####.# #####.# #E...## #######	Not Possible!