Задача 10. На чердаке ≡

Условие

По дому бродит привиденье.

Весь день шаги над головой.

На чердаке мелькают тени.

По дому бродит домовой.

...

Борис Пастернак, "Июль", 1956 г.

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

Привидение способно перемещаться в клетку, занятую препятствием или домовым, но тратит на это 2 секунды (на перемещение в свободную — 1 секунду).

Домовой не может перемещаться в клетку, занятую препятствием, зато способен быстро бегать и может переместиться в любую клетку на той же вертикали или горизонтали за 2 секунды (если на пути нет препятствий).

Участники не могут выходить за пределы чердака. Кто быстрее доберётся до финиша?

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m — длина и ширина чердака. В следующих n строках расположены строки длиной m, состоящие из символов "#" (клетка с препятствием, ASCII код 35) и "." (свободная клетка, ASCII код 46). Гарантируется, что домовой сможет добраться до финиша.

Формат выходных данных

Выведите через пробел победителя (Ghost (привидение) или Brownie (домовой)) и время, за которое он доберётся до финиша. Если оба существа достигнут цели одновременно, выведите одно слово Draw.

Ограничения

1 ≤ n, m ≤ 40

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере чердак представляет собой узкую полоску шириной в одну клетку без препятствий. Привидение и домовой стартуют с крайней левой клетки. Чтобы добраться до крайней правой клетки, привидению понадобится 4 секунды (по 1 секунде на преодоление каждой клетки), домовой же добежит за 2 секунды.

Во втором примере чердак представляет собой полоску шириной в три клетки с зигзагообразными препятствиями. Привидение и домовой стартуют с крайней левой верхней клетки. Чтобы добраться до крайней правой нижней клетки, привидению понадобится 18 секунд (оно сперва спустится вниз на две клетки и потом будет двигаться вправо, преодолев всего три клетки с препятствиями — это один из самых оптимальных путей), домовой же добежит по единственному доступному для себя маршруту за 28 секунд.

В третьем примере оба героя способны добраться до финиша за 18 секунд (смотри рисунок).

Примеры тестов

1 5
.....

Brownie 2

3 14
.#...#...#...#
.#.#.#.#.#.#.#
...#...#...#..

Ghost 18

4 13
.####..#...#.
.####..#...#.
.####....#...
.......####..

Draw