2119: 机器人

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:3

题目描述

年轻的机器人技师小Y建成了他的第一个机器人。小Y已经对机械很在行了,但是他不善于编程,所以他为机器人写了一个非常简单的程序。
机器人以每秒一米的速度前进,直到它遇到了最近的障碍物,然后它就一直向左转90直到它的面前没有障碍物,然后继续前进。机器人旋转的速度很快,所以旋转可以被认为不需要时间。机器人不会自己停下来。 为了测试这个机器人,小Y找了一块大场地并在这上布置了一个迷宫。迷宫被表示成一个N×N的字符矩阵,在矩阵中,“#”表示1×1的障碍物,而“.”则表示同等大小的空地。所有迷宫外的空间都是空地。 迷宫的西北角被标定为(1,1),x坐标轴由正西指向正东,y坐标轴由正北指向正南。 起初,小Y把机器人放在坐标(x,y)并面向北,打开机器人的开关并等上S秒,那么,现在机器人在哪里呢? 起始位置不在任一个障碍上并且至少有一个面没有障碍物。

输入

输入文件包含N,x,y,S,紧跟着N行每行N个字符表示迷宫的情况。

输出

输出文件必须包含一组整数x,y,表示S秒后机器人的位置。
需要注意的是,起始位置与终点位置都有可能在迷宫之外。

样例输入 复制

3 2 5 10 
### 
#.. 
#.. 

样例输出 复制

2 9 

提示

1<=n<=1000  -10^5<=x,y<=10^5  1<=s<=10^9