题目描述

奶牛贝蒂正在一个特殊的巨大的棋盘上做游戏。这个棋盘有的格子是红色，有的格子是蓝色，一开始奶牛贝蒂站在其中一个格子里，贝蒂面向某个方向（上下左右分别用 \(U,D,L,R\) 表示）。接下来贝蒂看向自己脚下的格子颜色，如果是蓝色，右转 \(90\) 度，将该格涂为红色，并向前移一格；如果是红色，她就左转 \(90\) 度，将该格涂为蓝色，并向前移一格；

那么在经过 \(k\) 步之后，贝蒂会在哪一个格子里？（尽管放心，数据保证一定走不到棋盘外面）

格式

输入格式

输入第 \(1\) 行是 \(m,n\) 两个整数\(（3 <m,n< 1000）\)，表示棋盘行数和列数。

接下来是 \(m\) 行数据，每行 \(n\) 个整数。\(0\) 表示红色格子，\(1\) 表示蓝色格子。

接下来一行 \(4\) 个整数：\(x,y,s,k\), 其中 \(x,y\) 为表示贝蒂一开始所在格子的行号和列号（行号从上到下增长，列号从左到右增长，都是从 \(0\) 开始编号）。\(s\) 是一个大写字母，表示贝蒂的朝向。\(k\) 表示贝蒂需要走的步数 \((0<=k<=100)\)。

输出格式

输出两个空格分开的整数 \(a,b\), 表示贝蒂在 \(k\) 步后，所处格子的行号和列号。

样例1

样例输入1

5 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 3 L 5

样例输出1

1 3

样例2

样例输入2

3 3
0 0 0
1 1 1
1 1 1
1 1 U 6

样例输出2

0 0

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T1\)