Robot

Chủ đề của cuộc thi ROBCON năm nay là "Tìm đường thoát mê cung". Tuấn vừa chế tạo được một robot để tham dự cuộc thi này. Tuấn rất thành thạo trong kỹ thuật chế tạo máy nhưng trong lập trình lại không được tốt như vậy. Do đó, Tuấn mới chỉ lập được một chương trình còn khá đơn giản để điều khiển robot của mình.

Robot di chuyển về phía trước với tốc độ $1$ mét/giây cho đến khi gặp vật cản. Khi gặp vật cản robot sẽ liên tiếp thực hiện quay trái $90$ độ cho đến khi trước mặt nó không có vật cản và lại tiếp tục di chuyển về phía trước. Thời gian để robot thực hiện đổi hướng chuyển động là cực nhanh, vì thế được coi là bằng $0$. Robot không bao giờ tự dừng chuyển động.

Để thử nghiệm robot, Tuấn đã xây dựng một mê cung trên một mặt sàn thi đấu rất rộng lớn. Mặt sàn có dạng một lưới ô vuông kích thước $1\times 1$ mét. Các cột của lưới được đánh số bởi các số nguyên từ $-{10}^{10}$ đến ${10}^{10}$, từ trái qua phải. Các dòng của lưới được đánh số bởi các số nguyên từ $-{10}^{10}$ đến ${10}^{10}$, từ trên xuống dưới. Ô nằm trên giao của cột $x$ và dòng $y$ được gán với toạ độ $(x,y)$. Mê cung mà Tuấn xây dựng là một lưới con kích thước $N\times N$ với ô ở góc trái trên có toạ độ $(1,1)$. Trong một số ô của mê cung có đặt vật cản, các ô còn lại là ô rỗng (ô không có vật cản).

Tuấn đặt robot của mình vào ô có toạ độ $(x,y)$, mặt robot quay về phía trên của lưới và cho robot chuyển động. Biết rằng vị trí mà Tuấn đặt robot không có vật cản và có ít nhất một ô chung cạnh với ô đặt robot là ô rỗng. Tuấn muốn xác định vị trí của robot sau $S$ giây.

Yêu cầu: Hãy giúp Tuấn giải quyết vấn đề đặt ra.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên $N$, $x$, $y$, $S$ được ghi cách nhau bởi dấu cách ($1\le N\le 1000$, $-{10}^5\le x,y\le {10}^5$);
• $N$ dòng tiếp theo mô tả mê cung, mỗi dòng gồm $N$ ký hiệu được ghi liên tiếp nhau, mỗi ký hiệu được lấy từ tập {#, .}, trong đó ký hiệu # cho biết ô tương ứng trong mê cung có vật cản, còn ký hiệu . cho biết ô tương ứng trong mê cung là ô rỗng. Dòng thứ $i$ trong $N$ dòng này là dòng $y=i$ của mê cung, ký hiệu thứ $j$ của dòng là ô ở cột $x=j$.

Dữ liệu ra

In ra hai số nguyên cách nhau bởi một dấu cách là toạ độ của ô mà robot đạt đến sau $S$ giây.

Ô xuất phát và ô mà robot đạt đến sau $S$ giây không nhất thiết phải nằm trong mê cung.

Ràng buộc

• $1\le N\le 1000$;
• $-{10}^5\le x,y\le {10}^5$;
• $1\le S\le {10}^9$.

Subtasks

• Subtask 1 ($50\%$ số test, $50\%$ số điểm): $1\le S\le {10}^5$;
• Subtask 2 ($50\%$ số test, $50\%$ số điểm): $1\le S\le {10}^9$.

Ví dụ