Кирилл — знатный садовод. Он очень любит свой сад и заботливо ухаживает за растениями в нём. Но главная его гордость — огромный зелёный лабиринт, стены которого простираются на сотни метров и состоят из переплетённых веток диких кустарников. Однажды вечером, как обычно подстригая заросли винограда, Кирилл с ужасом вспомнил, что, увлёкшись садом, он забыл о других обязанностях по дому: в частности, в раковине до сих пор стоит гора грязной посуды, а картошка всё ещё не почищена. А ведь совсем скоро домой приедут родители Кирилла, и он должен будет держать ответ за своё безответственное поведение. Необходимо задержать их, чтобы успеть сделать все дела! К счастью для Кирилла, единственный путь в дом проходит через лабиринт. Однако, так как родители Кирилла каждый вечер проходят через этот лабиринт, они хорошо знают кратчайший путь. Поэтому единственное, что остаётся бедному мальчику, это быстро изменить лабиринт так, чтобы самый короткий путь в получившемся лабиринте стал бы как можно длиннее. Времени осталось мало, поэтому Кирилл успеет посадить только один новый куст, чтобы перекрыть некоторый проход. Но куда же его посадить?

Лабиринт можно представить в виде клетчатой сетки из n строк и m столбцов. Каждый куст занимает целый квадрат 1×1. Изначально некоторые клетки заняты кустами, а некоторые свободны. Из любой клетки можно переходить только в смежные по стороне клетки, если они свободны. Также в лабиринте отмечены две клетки: парковка, где изначально окажутся родители Кирилла, и дом, куда они захотят попасть. Необходимо закрыть ровно одну свободную клетку (разумеется, в этой клетке не должна находиться парковка или дом) кустом таким образом, чтобы длина самого короткого пути от парковки до дома стала бы максимально возможной.

В первой строке даны целые числа n и m — количество строк и столбцов в лабиринте соответственно (2 ≤ n, m ≤ 1000; n · m ≤ 10⁵). Во второй строке даны координаты парковки (сначала строка, потом столбец). Нумерация строк начинается сверху с 1, нумерация столбцов начинается слева с 1. В третьей строке даны координаты дома в аналогичном формате. В следующих n строках по m символов каждая дано описание лабиринта. Каждая строка состоит только из символов «.» (обозначает свободную клетку) и «#» (обозначает куст). Гарантируется, что координаты парковки и дома не совпадают, обе эти клетки свободны и существует путь от парковки до дома. Также гарантируется, что, кроме этих двух клеток, в лабиринте есть ещё хотя бы одна свободная клетка.

Выведите координаты свободной клетки (сначала строку, потом столбец), в которую нужно посадить куст, чтобы максимизировать длину кратчайшего пути от парковки до дома. Если существует возможность так поставить куст, что не будет существовать пути между начальной и конечной точками, предпочтительнее использовать эту возможность (в этом случае родителям придётся копать подкоп, и Кирилл точно успеет всё сделать). Если существует несколько оптимальных ответов, выведите любой.