在一个神秘的迷宫世界里,有一个n行m列的网格。你从坐标(sx,sy)的位置出发,进行t次移动。每次移动可以选择
往上(U)、往下(D)、往左(L)、往右(R)四个方向之一移动一格。
若在某一次移动中,你要前往的位置是迷宫边界之外,则你将会从另一侧出现在迷宫中,即上边界的某一列的最下面,
或下边界的某一列的最上面,或左边界的某一行的最右边,或右边界的某一行的最左边。
迷宫中的“#”表示障碍物,如果下一个要走到的位置是障碍物,则此步移动为原地踏步。请你计算经过t次移动后,最终走到的格子位置。
第一行包括三个正整数n,m,t,分别表示迷宫的行数、列数和移动的次数。
接下来n行,每行包含一个长度为m的字符串,表示迷宫的布局。其中‘#’表示障碍物,‘.’表示空位置。
接下来一行包含两个整数sx和sy,表示出发位置的坐标,其中 0<=sx<n, 0<=sy<m 。
接下来t行,每行一个字符(U、D、L、R四个字符中的一个),依次表示每次移动的方向。
输出一行包含以空格隔开的两个整数,依次表示最终移动到的格子位置。
3 4 5 .... .#.. .... 1 2 D D L D R
0 2
样例解释
从(1,2)出发,进行5i移动:
1.向下移动,最终位置(2,2);
2.向下移动,到达边界之外,最终位置(0,2);
3.向左移动,最终位置(0,1);
4.向下移动,有障碍物,最终位置(0,1);
5.向右移动,最终位置(0,2);
最终走到的格子位置为(0,2)。
对于20%的测试数据,保证图中没有障碍物;
对于另外20%的测试数据,保证 1<=n,m<=10,t=1 ;
对于另外40%的测试数据,保证 1<=n,m<=1000,保证只会朝一个方向移动 保 证 只 会 朝 一 个 方 向 移 动 ;
对于100%的测试数据,保证 1<=n,m<=1000,1<=t<=10^3, 0<=sx<n, 0<=sy<m ;