一方通行与最后之作

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

学园都市仅有的七名超能力者(Level 5)排名第一位,能力为“矢量操作”,代号「一方通行(Accelerator)」。

 

       某天,「最后之作」自己去商场玩耍,很晚还没有回来。「一方通行」很担心于是决定去找最后之作。

       商场可以大体看作一个 N*M 的矩形,墙壁和遮挡物用 '*' 表示,空白位置用 '.' 表示,一方通行和最后之作的起始位置分别用 'A' 和 'L' 表示。(显然,他们两个人的起始位置是不可能有遮挡物的)

        两人总共最多进行 K 次移动,每次移动可以用两个字符串 name 和 direction 来表示。

        如果 name 为"Accelerator",表示本次是「一方通行」移动。

        如果 name 为"LastOrder",表示本次是「最后之作」移动。

        direction 可能为"up"或"down"或"left"或"right",分别表示向上、向下、向左、向右移动一个单位长度。 

        如果本次要移动的位置在商场外或者存在遮挡物,那么将不移动。如果两人中途已经相遇(坐标重合),那么之后的所有移动全部取消。

        数据保证「一方通行」和「最后之作」会相遇,如果最后是「一方通行」走向「最后之作」请输出"Accelerator",如果是「最后之作」走向「一方通行」请输出"MisakaMisaka"。然后输出两人实际总共移动了多少步。

Input

首先输入两个正整数 N, M表示商场的大小。(2 <= N, M <= 100)

然后输入一个 N 行 M 列的字符矩阵。

下一行输入一个正整数 K,表示两人总共最多进行 K 次移动。 ( 1 <= K <= 100)

接下来 K 行,每行包括两个字符串,分别表示移动的角色和移动的方向。

Output

第一行输出一个字符串。

第二行输出一个正整数,表示两人实际总共移动了多少步相遇。

Sample Input

4 5
A.*..
..*..
..*..
....L
11
Accelerator down
LastOrder left
LastOrder right
LastOrder left
LastOrder left
Accelerator down
Accelerator down
Accelerator down
LastOrder up
LastOrder left
LastOrder left

Sample Output

MisakaMisaka
9

Hint

样例中,两人最终在第四行第一列相遇,最后一次移动是「最后之作」走向「一方通行」。

「一方通行」移动了3步,「最后之作」移动了6步,两人总共移动了9步。

Source

lxw