Лабиринт
Робот застрял в лабиринте! Лабиринт состоит из четырех типов клеток:
"." обозначает пустую клетку, через которую робот может пройти.
"#" обозначает блок, через который робот не может пройти.
"S" указывает начальное положение робота.
"T" указывает цель, к которой стремится робот.
Теперь мы отправляем роботу команды, где "L", "R", "U", "D" означают, что робот делает один шаг влево, вправо, вверх или вниз соответственно. Помогите нам определить состояние робота после выполнения команд.
Входные данные
Первая строка содержит одно целое число T, обозначающее количество тестов. Каждый тест начинается с одного целого числа N (1 ≤ N ≤ 50), которое указывает размер лабиринта. Следующие N строк представляют собой лабиринт, каждая строка имеет длину N. Затем идет целое число Q (1 ≤ Q ≤ 100), обозначающее количество запросов. Следующие Q строк содержат команды, состоящие только из символов "L", "R", "U", "D", длина каждой команды меньше 1000.
Выходные данные
Для каждого запроса выведите одну строку:
Я добрался! - если робот может достичь цели после выполнения команды. Заметьте, что достижение цели до окончания команды также считается.
Я не знаю! - если робот не смог достичь цели после выполнения команды.
Я врезался! - если робот столкнулся с блоком во время выполнения команды.
Я вышел! - если робот вышел за пределы лабиринта во время выполнения команды.