Problem E. Emulate a robot

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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 × N array of characters, where '#' represents 1 × 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.

Constraints

1 ≤ N ≤ 1000,  − 105 ≤ x, y ≤ 105, 1 ≤ S ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 5 10
###
#..
#..
2 9

0.085s 0.016s 13