eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Хитрый ниндзя

Хитрый ниндзя

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

В большом дворце есть зал, пол которого представляет собой (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
1
4 5
1 3 B
3 5 B
5 1 R
5 5 F
7 7 F
Выходные данные #1
succeeds
Источник 2011 Benelux Algorithm Programming Contest, Preliminaries, Задача H