Эта задача является интерактивной.
Таджа легко выигрывает в эту игру, но все её друзья не смогли. Теперь она предлагает вам сыграть в неё.
Игровой инвентарь состоит из поля $n \times n$ ($5 \le n \le 40$), фишки, двух монет (COIN1, COIN2), двух игральных костей с направлениями (DICE1, DICE2) и множества блоков размером в одну клетку.
| Название | Количество граней | Грани |
|---|---|---|
| COIN1. Монета перемещения | 2 | SLIDE, RAM |
| COIN2. Монета модификации | 2 | PLACE, REMOVE |
| DICE1. Первая кость с направлениями | 4 | N (Север), S (Юг), W (Запад), E (Восток) |
| DICE2. Вторая кость с направлениями | 8 | N (Север), S (Юг), W (Запад), E (Восток), NW (Северо-запад), NE (Северо-восток), SW (Юго-запад), SE (Юго-восток) |
Перед началом игры фишка и некоторые блоки расставляются на поле. Затем игрок делает ходы. Сначала игрок выбирает монету и подбрасывает её, чтобы определить действие. Затем он выбирает одну из костей и бросает её, чтобы определить направление $dir$. После этого происходит одно из четырех действий:
| Название действия | Действие |
|---|---|
| SLIDE | Переместить фишку по пустым клеткам в направлении $dir$ до столкновения с блоком или границей лабиринта |
| RAM | Переместить фишку по пустым клеткам в направлении $dir$ до столкновения с первым блоком. Затем переместить фишку и этот блок в том же направлении, пока движущийся блок не столкнется с другим блоком или границей поля |
| PLACE | Если соседняя клетка в направлении $dir$ от фишки пуста и находится внутри поля, поместить блок в эту клетку |
| REMOVE | Если соседняя клетка в направлении $dir$ от фишки содержит блок и находится внутри поля, убрать блок из этой клетки |
Цель игры — поставить фишку на финишную клетку.
Один запрос в этой задаче — это один подброс монеты и один бросок кости.
Протокол взаимодействия
Сначала интерактор сообщает размер лабиринта, сам лабиринт и координаты финишной клетки. Затем происходят следующие 4-шаговые действия:
- Программа жюри выводит координаты фишки или сообщает, что фишка достигла финишной клетки.
- Ваша программа выводит название монеты.
- Программа жюри выводит название действия, выпавшего на монете.
- Ваша программа выводит название кости.
- Программа жюри выводит название направления, выпавшего на кости, и дополнительную информацию для действия "RAM".
Выходные данные
Стандартный вывод должен состоять из пары строк: название монеты и название кости. Название монеты — это строка "COIN1" или "COIN2". Название кости — это строка "DICE1" или "DICE2".
Не забудьте сбросить буфер стандартного вывода после вывода каждой строки.
Входные данные
Первая строка стандартного ввода содержит одно целое число $n$ — размер лабиринта. Следующие $n$ строк содержат $n$ символов "." (ASCII 46) или "#" (ASCII 35), обозначающих пустую клетку и клетку с блоком соответственно.
Следующая строка содержит два целых числа $r_f$ и $c_f$ — номер строки и номер столбца финишной клетки. Верхний левый угол имеет координаты $(1, 1)$, нижний правый — $(n, n)$. Финишная и начальная клетки пусты.
Следующие группы описывают каждый ход:
- Первая строка группы содержит два целых числа $r, c$ — номер строки и номер столбца фишки, или $(-1, -1)$, если фишка достигла финишной клетки.
- Следующая строка содержит название действия, выпавшего на монете.
- Следующая строка содержит название направления, выпавшего на кости.
- Если текущее действие — "RAM", следующие две строки содержат два целых числа $r_1, c_1$ и $r_2, c_2$, означающие, что фишка столкнулась с блоком с координатами $(r_1, c_1)$ и переместила этот блок в клетку $(r_2, c_2)$.
Северное направление соответствует уменьшению номера строки. Южное — увеличению номера строки. Западное направление — уменьшению номера столбца. Восточное направление — увеличению номера столбца.
Каждая сторона любой монеты или кости выпадает с одинаковой вероятностью.
Начальное состояние лабиринта для примера
Представление пути
Примеры
Входные данные 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
Выходные данные 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1