“严峻挑战考古探索部”（SCArED）专门负责调查那些对人类而言过于困难、危险或极其恐怖，无法进行实地考察的考古遗址。他们派遣一个或多个移动机器人进行调查，每个机器人配备了一套复杂的传感器、记录仪和操纵器。每个机器人都是无线电遥控的，并配有一个小型核反应堆，以维持有时在遗址中进行的长时间停留。

最近，人们发现了一个复杂的“Desreverezam文明”地下迷宫。SCArED派遣了两个机器人进行调查，在几个月的时间里，它们绘制了整个迷宫的地图。但随后灾难降临了——由于某种不可预见的异常，研究人员与这两个机器人失去了无线电联系（研究人员在猜测原因：要么是墙壁中的磁铁蛋白晶体，要么是愤怒的骚灵）。在尝试重新与这两个机器人取得联系几周后，他们终于成功地与它们建立了一个共享通道。

由于连接带宽有限，他们只能向机器人发送三个基本指令：（移动）前进（Forward）、（转向）左转（Left）和（转向）右转（Right）。由于这是一个共享通道，他们无法向每个机器人发送不同的指令，因此如果发送“前进”指令，两个机器人将同时尝试向前移动。如果它们前方有空位，那没问题；但如果其中一个机器人前方有墙，它会撞上墙壁并停在原地。任何“转向”指令同样会导致两个机器人同步转向。

图 1：样例输入 1。

研究人员希望找到使两个机器人都走出迷宫所需的最少“前进”指令数（“转向”指令所需的时间和能量极少，可以忽略不计）。一旦其中一个机器人走出迷宫，它就可以返回地面，后续指令对它不再产生影响。考虑图 1 中的情况，两个机器人目前都面向南方。一种让机器人走出迷宫的方法是先让机器人 B 尽快走出，将其移动到位置 $(6, 2), (6, 1), (5, 1), (4, 1)$，然后走出迷宫。这需要 5 次“前进”移动，在此过程中机器人 A 移动到 $(3, 1)$ 并停在那里，撞墙 4 次。机器人 B 走出后，机器人 A 再用 6 次“前进”移动即可走出迷宫，总共需要 11 次移动。然而，如果先让机器人 A 尽快走出，然后再让机器人 B 走出，则只需要 8 次“前进”移动。对于其他迷宫，最少“前进”移动次数可能并不涉及让其中任何一个机器人尽快走出（参见样例输入 2）。

给定一个迷宫以及机器人的初始位置和朝向，请通过确定使两个机器人都走出迷宫所需的最少“前进”指令数来帮助研究人员。如果存在多组最少“前进”指令，则优先选择撞墙次数最少的那一组。哦，还有一件事：机器人绝不能在迷宫内重叠在一起——这可能会导致它们的核反应堆发生连锁反应，引发可能摧毁地球的爆炸。必须避免这种情况。

输入格式

输入的第一行包含 3 个正整数 $c, r, e$（$c, r \le 50, e \le c$），表示迷宫有 $c$ 列和 $r$ 行（均从 1 开始编号），且迷宫出口位于方格 $(e, 1)$ 的南侧。接下来的一行格式为 $c_1\ r_1\ d_1\ c_2\ r_2\ d_2$（$1 \le c_i \le c, 1 \le r_i \le r, d_i \in \{N, E, S, W\}$），表示两个机器人分别位于位置 $(c_1, r_1)$ 和 $(c_2, r_2)$，朝向分别为 $d_1$ 和 $d_2$。位置 $(c_1, r_1)$ 和 $(c_2, r_2)$ 永远不会相同，$d_1$ 和 $d_2$ 可能不同。

随后是两行描述迷宫的行。第一行格式为 $n\ c_1\ r_1\ c_2\ r_2 \dots c_n\ r_n$（$n \le r \times c, 1 \le c_i \le c, 1 \le r_i < r$），其中每对 $c_i\ r_i$ 表示方格 $(c_i, r_i)$ 和 $(c_i, r_i + 1)$ 之间有一道水平墙。下一行类似，其中每对 $c_i\ r_i$（$n \le r \times c, 1 \le c_i < c, 1 \le r_i \le r$）表示方格 $(c_i, r_i)$ 和 $(c_i + 1, r_i)$ 之间有一道垂直墙。除出口外，所有外墙均假设存在，且不会在上述两行中列出。

输出格式

输出两个值：使两个机器人走出迷宫所需的最少“前进”指令数，以及使用这些指令时发生的撞墙次数。如果存在多种使机器人走出迷宫且“前进”指令数相同的方法，请使用撞墙次数最少的那一种。对于每个输入实例，两个机器人都能够走出迷宫。

样例

样例输入 1

7 4 4
3 2 S 6 3 S
6 1 1 1 2 1 3 2 3 5 1 5 3
11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4

样例输出 1

8 1

样例输入 2

3 4 2
1 3 S 3 2 S
1 3 3
5 1 1 2 1 1 2 1 3 2 3

样例输出 2

7 2