eolymp
bolt
Try our new interface for solving problems
Problems

Место встречи изменить нельзя

Место встречи изменить нельзя

Добрые друзья Петя и Вася решили поиграть в прятки в лабиринте. Через несколько часов игры им стало скучно и они решили найти друг друга как можно раньше. Лабиринт имеет форму прямоугольника и разбит на \textbf{N}×\textbf{M} клеток, в каждой из которых либо стена, либо проход. Петя и Вася могут переходить из одной клетки в другую, если у клеток есть общая сторона. Не разрешается посещать клетки, в которых стоит стена. Мальчики могут ходить одновременно. Необходимо найти клетку, в которой могут встретится Вася и Петя через минимально возможное число ходов. \InputFile В первой строке \textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{100} - размеры лабиринта. Далее \textbf{4} натуральных числа \textbf{P_x}, \textbf{P_y}, \textbf{V_x}, \textbf{V_y} - координаты клеток, в которых находятся Петя и Вася соответственно. Гарантируется, что в начальный момент времени мальчики не находятся в клетках, занятых стеной (\textbf{P_x}, \textbf{V_x} - номер строки, \textbf{P_y}, \textbf{V_y} - номер столбца). Далее \textbf{N} строк по \textbf{M} чисел в каждой, описывающие лабиринт, \textbf{1} - если в данной клетке стоит стена, \textbf{0} - иначе. \OutputFile В первой строке два натуральных числа \textbf{X_m}, \textbf{Y_m} - координаты клетки, в которой они встретятся. Если они не смогут встретится, то в выходной файл нужно вывести \textbf{-1}. Если решение несколько - выведите любое.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4 3
1 2
3 1
1 0 1
1 0 0
0 1 0
0 0 0
Output example #1
3 3