printРабочее место участника


1458. Emulate a robot

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Young robot technician Vasya built his first robot. Vasya is already good with mechanics, but not so good with programming, so he created a very simple program for his robot.
Robot drives forward at the speed of 1 meter per second until the nearest obstacle. Then it rotates to the left by `90°` steps until there is no obstacle in front of it, and continues driving. The turning is so fast it can be considered instantaneous. The robot never stops by itself.
To test the robot, Vasya has found a big field and built a labyrinth in it. The labyrinth is represented by `N\ times\ N` array of characters, where '#' represents `1\ times\ 1` meter obstacle and '.' – empty place of the same size. All space outside the labyrinth is empty too.
North-west corner of the labyrinth has coordinates `(1,\ 1)`. Coordinate axises run from west to east and from north to south.
Vasya placed the robot at coordinates `(x,\ y)` facing north, started it and waited for `S` seconds. Where is the robot now?
Starting position is not inside of an obstacle and is not surrounded by the obstacles from all sides.
Input file format
Input file contains integers `N\ x\ y\ S` followed by `N` lines of `N` characters each – the labyrinth representation.
Output file format
Output file must contain integers `x'\ y'` – coordinates of the robot after `S` seconds.
Note that both starting and final coordinates may be outside of the labyrinth.
`1\ ≤\ N\ ≤\ 1000`, `-10^5\ ≤\ x,\ y\ ≤\ 10^5`, `1\ ≤\ S\ ≤\ 10^9`

Sample Input

3 2 5 10

Sample Output

2 9
Source: NEERC ICPC, Far Eastern subregion, 2009