Таємничий лабіринт#3598
Робот знову опинився в двовимірному лабіринті. Цього разу лабіринт має вхід і вихід.
Як і в попередній задачі, лабіринт складається з × ґраток, його верхня сторона звернена на північ, і кожна клітинка є або порожньою, або стіною. На відміну від попереднього, одна з порожніх клітинок з'єднана з входом, а інша з виходом.
Робот досить складний: є певний контроль, але не повний. Він пов'язаний з контролером, який має дві кнопки: вперед і поворот. Кнопка "вперед" переміщує робота до наступної клітинки, якщо це можливо. Робот не може рухатися в стіну або за межі лабіринту. Кнопка "поворот" повертає робота, як запрограмовано. Програма - це кінцева послідовність з команд, кожна з яких є або 'L' (поворот ліворуч), або 'R' (поворот праворуч). Перший поворот слідує за першою командою; другий поворот слідує за другою командою; аналогічно для наступних поворотів. Кнопка "поворот" перестає працювати, коли команди вичерпані; кнопка "вперед" все ще працює в такому випадку. Робот завжди повертається на градусів за раз.
Спочатку робот розміщується на клітинці входу, спрямований на північ. Ваше завдання - визначити, чи може він досягти виходу, якщо керувати ним правильно.
Вхід - це послідовність наборів даних. Кожен набір даних форматований наступним чином.
s_1 ... s_N c_{1,1}c_{1,2} ... c_{1,W} ... c_{H,1}c_{H,2} ... c_{H,W}
Перший рядок набору даних містить три цілі числа , і (1 ≤ H, W ≤ 1000, 1 ≤ N ≤ 1000000).
Другий рядок містить програму з команд.
Кожен з наступних рядків містить рівно символів. Кожен з цих символів представляє клітинку лабіринту. "." позначає порожню, "#" позначає стіну, "S" позначає вхід, а "G" позначає вихід. Є рівно одна клітинка входу і одна клітинка виходу.
Кінець введення позначається рядком з трьома нулями.
Для кожного набору даних виведіть, чи може робот дістатися виходу в рядку: "Yes", якщо може, або "No" в іншому випадку (без лапок).
Приклад 1