小球滚格子

题目描述

有一个 $n$ 行 $m$ 列的网格，每个格子要么是空地 .，要么是障碍 #。一个小球放在某个空地上，初始朝向为上、右、下、左四个方向之一，分别用字符 U、R、D、L 表示。小球要依次执行 $k$ 个动作，每个动作的规则完全相同：如果沿当前朝向走一格后的位置仍在网格内且是空地，小球就移到那一格，朝向不变；否则小球留在原地，朝向顺时针旋转 $90$ 度。

请输出执行完 $k$ 个动作后小球所在格子的行号与列号。

输入格式

第一行两个整数 $n$ 与 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述网格。

最后一行依次为初始行号 $x_0$、初始列号 $y_0$、初始朝向字符与整数 $k$。行列号都从 $1$ 开始。

输出格式

一行两个整数 $x$ 与 $y$，中间用一个空格分隔。

样例

输入样例

3 4
.#..
....
..#.
1 1 R 5

输出样例

3 1

样例解释

第 $1$ 个动作：右边是障碍，转向下；第 $2$、$3$ 个动作向下走两格到 $(3,1)$；第 $4$ 个动作越界，转向左；第 $5$ 个动作越界，转向上。最终停在 $(3,1)$。

数据范围

$1 \le n, m \le 1000$，$1 \le k \le 10^6$，$1 \le x_0 \le n$，$1 \le y_0 \le m$，数据保证初始位置是空地。