Хитрый ниндзя
Хитрый ниндзя
В большом дворце есть зал, пол которого представляет собой (2n-1) х (2n-1) сетку из квадратов, расположенных в 2n-1 рядах (пронумерованных от 1 до 2n-1) и 2n-1 колонках (пронумерованных от 1 до 2n-1) - как приведено на рисунке ниже при n = 4. Каждый квадрат на пересечении четной строки и четной колонки покрыт квадратной деревянной опорной колонной. Остальные клетки пустые. Таким образом между стенами и деревянными опорами в зале имеется n коридоров идущих слева направо и n коридоров от задней к передней части. В концах коридоров, идущих от задней к передней части, имеются дверные проемы, завешенные занавесками. В остальных случаях стены проемов не имеют.
Зал охраняют k охранников. Каждый из этих охранников дислоцируется на пересечении вертикальных и горизонтальных коридоров. Каждый охранник смотрит 4 секунды налево, 4 секунды назад, 4 секунды направо и 4 секунды вперед, далее бесконечно повторяя описанный процесс. Направление наблюдения охранников не обязательно синхронизовано: в то время как некоторые смотрят влево, некоторые могут смотреть вперед.
Ниндзя должен пересечь зал с передней части в заднюю, будучи не замеченным охранниками. Перед входом в зал ниндзя ожидает в ряду 0, то есть за одной из занавесок в дверном проеме передней стены. Он может выбрать за какой из занавесок находиться и сколько времени ждать перед входом в зал. В качестве выхода ниндзя может выбрать любую дверь в задней стене. Ровно 2 секунды требуется ниндзя для перемещения между двумя соседними клетками - во время движения ниндзю могут видеть охранники, которые смотрят прямо на него. Может ли ниндзя успешно пересечь зал? Охранники могут видеть друг сквозь друга, но не через занавески.
На рисунке 1 показано как ниндзя находит выход. Сначала ниндзя ожидает. Через 8 секунд охранник в строке 5 колонке 1 поворачивается налево и ниндзя выходит из-за занавески. Через 10 секунд ниндзя прибывает в строку 1 колонку 1. Через 12 секунд ниндзя прибывает в строку 2 колонку 1. Ниндзя ждет пока охранник в строке 3 колонке 5 повернется назад в зале; тогда ниндзя начинает движение и исчезает за занавеской в колонке 3 как раз перед тем как охранник в строке 1 повернется лицом в его направлении.
Входные данные
Первая строка содержит количество тестов. Каждый тест имеет следующий формат:
первая строка содержит два числа: n (количество коридоров в каждом направлении, 1 ≤ n ≤ 250) и k (количество охранников, 0 ≤ k ≤ 500).
k строк, по одной для каждого охранника: каждая строка содержит нечетное число r (1 ≤ r ≤ 2n-1) и нечетное число c (1 ≤ c ≤ 2n-1), а также одну из букв L, B, R или F. Первое число - номер строки, куда поставлен охранник; второе число - номер колонки охранника, буква указывает на направление в котором смотрит охранник в момент времени ноль (налево, назад, направо или вперед).
В каждой позиции зала может находиться не более одного охранника.
Выходные данные
Для каждого теста вывести в отдельной строке слово succeeds, или слово fails.
Пример
1 4 5 1 3 B 3 5 B 5 1 R 5 5 F 7 7 F
succeeds