Description

T博士最近在研究一种神奇的风。
这种风有一个源头，称之为“风口”。风口的风要么是顺时针的，要么是逆时针的。
这种风是有能量的。
这种风是能传播的，如果风口周围都能传播风，风会像这样产生下一级的风：

（箭头表示风的转向，最中间的是风口，图中风口的风是顺时针的，对于风口的风是逆时针的情形可通过物理模型想象一下或由这个图推理。）
产生的下一级风的能量依据新产生的风所在的地形决定，有两种可以传递这种风的地形：
一、平地，下一级风的能量与风口的风能量相等，这种地形用“.”表示。
二、少量障碍物，下一级风的能量是风口的风能量的一半，这种地形用“*”表示。
每个新产生的风都能作为新的风口继续产生下一级风。
此外，还有一种地形是不能传递风的：大量障碍物，用“#”表示。
如果在风口的某一方向是“#”地形，则该方向不会产生下一级风，
其他方向视该位置的地形而定，就是说，如果是“.”或“*”地形则该方向照样传播。
T博士还发现了这种神奇的风的叠加规则：两股风叠加时，无论它们的转向是否相同，都只保留能量较大的那股风，即风叠加后的能量和转向都与叠加前能量较大的那股风相同。而如果叠加的两股风的能量相同且转向相同，则保留其中任意一股。两股风能量相同且转向不同时叠加的情况未知，因为T博士至今还没碰到这样的情况。
T博士画了几张地图，他想知道地图上的某点风的转向和能量。

Format

Input

输入文件wind.in的第一行是两个整数m和n，表示地图大小为m行n列。
接下来的m行，每行是n个字符，只会是以下的几种：
“S”表示风口，保证图中有且仅有一个“S”。
“E”表示目的地，即T博士想知道的那个点。
“.”“*”“#”见描述。
第m+2行是一个整数“0”或“1”，分别表示风口的风是顺时针方向或逆时针方向。
约定“S”处的风能量为16384，“S”和“E”处的地形均为平地。

Output

输出文件为wind.out。
若目的地会有风传到，则输出两行：第一行为一个整数，为目的地的风的能量；第二行为一个整数“0”或“1”，表示意义同输入格式。此种情形下保证目的地的风的能量大于0。
若目的地没有风传到，则输出一行：“There’s no wind!”（双引号内的字符，全英文标点）。

Sample 1

Input

3 4
####
S**E
####
0

Output

4096
1

Sample 2

Input

2 4
....
S**E
0

Output

16384
1

Sample 3

Input

6 8
********
********
***S****
###*....
...#....
E..#....
1

Output

There’s no wind!

Limitation

1s, 64MiB for each test case.

Hint

不要问我单引号怎么输出。

数据范围

对于20%的数据，m,n均不超过10。
对于50%的数据，m,n均不超过100。
对于100%的数据，m,n均不超过200。

样例解释

Output 1:
4096 （传递过程中经过两个“*”地形，能量变为原来的1/4，即变为4096）
1 （E处的风是逆时针的）

Output 2:
16384（传到目的地的风能量最大的为16384）
1（E处的风是逆时针的）

Source

NOIP2019高一综合测试题（1）