Funny Gnomish Hockey#12827

Funny Gnomish Hockey

1 секунда
512 мегабайтів
Складна

Гноми, що живуть у темних та холодних печерах, винайшли власну гру на кризі. Її назвали гномовий хокей.

Однак він досить відрізняється від відомого нам хокею. Гра відбувається багатьма шайбами на кризі H \times W з зовнішніми стінами навколо. І є тільки одна команда що намагається поцілити у ворота.

Деякі клітини пусті, у деяких є шайби. Шайба бездоганно розміщується у клітині. Гном може посунути довільну шайбу у довільному з чотирьох напрямків паралельно осям координат.

Коли шайба б'є щось (або зовнішню стіну, або іншу шайбу), вона миттєво зупиняється. Коли у шайбу потрапляє інша шайба, вона починає рухатись у тому самому напрямку. Це стосується і випадків коли шайба б'є кілька шайб що стоять одна за одною у напрямку руху: наприклад, нехай шайба б'є дві шайби та що стоять у ряд: тоді зупиняється, починає рух і миттєво зупиняється у тій самій клітині, але "передає" рух , яка починає рухатись. Зауважте, що шайба не заміняє іншу у клітині, натомість, вона зупиняється безпосередньо перед нею.

Рівно одну клітину позначено як ворота. Якщо команді вдається зупинити довільну шайбу у воротах, вона виграє раунд. Інакше, програє. Зауважте, що якщо шайба пролітає через ворота, це не рахується перемогою.

Вам задано розмір поля, початкове розташування шайб та воріт. Перевірте, чи виграють гноми якщо будуть грати оптимальним чином.

Вхідні дані

Перший рядок входу містить два цілих та (1 \le H, W \le 16). Кожен з наступних рядків містить рівно символів. Символ 'p' позначає шайбу, символ 'g' — ворота, символ '.' — інші клітині на кризі. Ви можете вважати що є тільки одні ворота та принаймні одна шайба.

Вихідні дані

Надрукуйте "yes" якщо гноми можуть зупинити шайбу у воротах, або "no" у противному випадку.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading