Із-за підозри у шахрайстві один з параноїдальних авторів задач вирішив шифрувати всі свої повідомлення перед відправкою їх іншим членам жюрі. При цьому він не скористався стандартними методами шифрування, так як вващав що всі вони є гігантською частиною змови по придавленню змагання IDI Open зсередини. Він вважав, що шахраї - найгірші програмісти. І оскільки дешифрування вимагає певних навмчок програмування, то його можна не боятися.
Разом з закодованим повідомленням він відправляв інформацію про його дешифрування. Проблема полягала лише у тому, що не всі члены жюрі могли реалізувати декодування. Ви повинні допомогти дешифрувати повідомлення, написавши для цього програму.
Дешифрування виконується моделюванням руху робота на сітці. На початку робот знаходиться у північно-західному кутку сітки, обличчям повернутий на південь. Робот є достатньо простим механізмом, і виконує лише три різні команди:
L
повертає робота на 90° ліворуч
R
повертає робота на 90° праворуч
F
пересуває робота на одну клітинку вперед. Якщо у результаті переміщення вперед робот впаде з решітки, то він замість переміщення повертається на 180° і не рухається.
Інструкції роботу подаються у рядку у вигляді набору команд, які можуть містити цикли. Цикл подається у вигляді (множество команд)число
де число
дорівнює кількості повторень множини команд у дужках, які повинні бути виконані. Рекурсивно можуть бути побудовані довгі послідовності команд. Більш формально:
Дешифрований текст отримується в результаті конкатенації символів у комірках сітки, на яких зупиняється робот після виконання кожного командного рядка.
Перший рядок містить кількість тестів T (0<T≤100). Кожен тест починається рядком, який містить числа W (0<W≤50) і H (0<H≤50), відокремлені одним пропус ком і задають розміри сітки. Далі йде H рядків, кожен з яких містить W символів, що описують сітку. Наступний рядок містить кількість командних рядків N (0<N≤20). Після нього йде N командних рядків, які повинні бути викпонані роботом.
Командні рядки містять не більше 50 символів і мають синтаксис, описаний в умові. Символи з ASCII кодом менше 32 і більше 126 не зустрічаються на сітці робота.
Для кожного тесту у окремому рядку вивести дешифрований текст.