题目描述

本题使用文件输入输出：输入文件名为 robot.in，输出文件名为 robot.out。

一个房间是 $n$ 行 $m$ 列的网格，行从上到下编号 $1 \sim n$，列从左到右编号 $1 \sim m$。每个格子要么是空地 .，要么是障碍 #。

一台扫地机器人开始时停在第 $x$ 行第 $y$ 列的空地上，面朝四个方向（上、下、左、右）之一。机器人工作 $k$ 个单位时间，每个单位时间它做且只做下面一件事：

• 看一眼正前方的那个格子。如果它在房间内且是空地，机器人就前进一格到那里；
• 否则（正前方出了房间，或者是障碍），机器人原地向右转 $90^\circ$（上 → 右 → 下 → 左 → 上），这个单位时间内不移动。

机器人到过的每个格子（包括出发的格子）都会被打扫干净。请你求出 $k$ 个单位时间结束后，一共有多少个不同的格子被打扫过。

输入格式

输入文件名为 robot.in。

第一行三个整数 $n, m, k$，表示房间的行数、列数和工作的单位时间数。

第二行两个整数和一个大写字母 $x, y, c$，表示机器人的起始行、起始列和起始朝向。$c$ 是 U、D、L、R 之一，分别表示朝上（行号减小的方向）、朝下、朝左（列号减小的方向）、朝右。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只含 . 和 #，描述房间。保证第 $x$ 行第 $y$ 列是空地。

输出格式

输出文件名为 robot.out。

一行一个整数，表示被打扫过的不同格子的数量。

样例 #1

样例输入 #1

3 4 12
1 1 R
..#.
....
....

样例输出 #1

6

样例解释

机器人从 $(1,1)$ 朝右出发，$12$ 个单位时间依次是：

到过的格子有 $(1,1),(1,2),(2,2),(3,2),(3,1),(2,1)$ 共 $6$ 个。第 $9$、$11$ 个单位时间回到了已经打扫过的格子，不重复计数。

样例 #2

样例输入 #2

2 2 5
1 1 U
.#
#.

样例输出 #2

1

样例解释

机器人四面都走不通，$5$ 个单位时间全在原地转圈，只有出发的格子被打扫过。

样例 #3

样例输入 #3

见附件中的 robot/robot3.in。

样例输出 #3

见附件中的 robot/robot3.ans。

提示

数据范围

• 对于 $30\%$ 的数据：$n, m \le 10$，$k \le 100$；
• 对于 $60\%$ 的数据：$n, m \le 100$，$k \le 10^4$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 1000$，$1 \le k \le 10^6$，$1 \le x \le n$，$1 \le y \le m$。

附件

• robot3.in
• robot3.ans