ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2006. Kirill the Gardener

Time limit: 2.0 second
Memory limit: 128 MB
Kirill is a great gardener. He loves his garden and takes good care of the plants. The jewel of the garden is a huge green maze. Its walls are hundreds of meters long and consist of intertwined branches of wild bushes. One evening Kirill was trimming the grape leaves when he suddenly realized a horrible fact: he got so consumed by the gardening routine that he haven’t been doing any of his house chores! In fact, the kitchen sink is full of dirty dishes and the potato is lying unpeeled. To make things worse, Kirill’s parents will arrive soon. They will surely punish the boy for his bad behavior… He must detain them and finish the chores! Luckily for Kirill, the only way to the house is through the maze. But his parents walk through the maze every day and know the shortest path good. So there’s only one thing Kirill can do: he should alter the maze making the shortest path in it as long as possible. The boy is running out of time so he can plant only one new bush to block some way. But where should he plant it?
The maze can be represented as a grid of n rows and m columns. Each bush takes up a single 1×1 square. Some cells are initially occupied by bushes and some cells are empty. One can move from any cell to empty side-adjacent cells only. Besides, the maze has two marked cells: the parking space where Kirill’s parents will be situated and the house they will want to get to. Kirill’s task is to choose exactly one empty cell (naturally, this cell mustn’t be the parking space or the house) and to plant a bush in it so that the length of the shortest path from the parking space to the house would be maximum possible.

Input

The first line contains integers n and m that are the number of rows and columns in the maze, correspondingly (2 ≤ n, m ≤ 1000; n · m ≤ 105). The second line contains the coordinates of the parking space (row number and column number). The rows are numbered from the top starting from 1 and the columns are numbered from the left starting from 1. The third line contains the coordinates of the house in the same format. The next n lines contain m characters each and describe the maze. Each line consists of characters “.” (for an empty cell) and “#” (for a bush). It is guaranteed that the coordinates of the parking space and the house do not coincide, both these cells are empty, and a path from the parking space to the house exists. It is also guaranteed that the maze has at least one empty cell besides these two cells.

Output

Output the coordinates of the cell (row number and column number) where Kirill should plant a bush in order to maximize the length of the shortest path from the parking space to the house. If it is possible to plant a bush so that there will be no path from the parking space to the house, Kirill should do it because in this case the parents will have to dig a tunnel to get out of the maze and Kirill will surely have enough time. If there are multiple optimal choices, you may output any of them.

Sample

inputoutput
4 4
1 1
4 4
..##
#.##
#...
###.
2 2
Problem Author: Ilya Kuchumov. (Prepared by Oleg Merkurev)
Problem Source: Ural Regional School Programming Contest 2013