Сегодня Аквамен решил заняться разминированием старого минного поля времен Второй мировой войны. Поле состоит из $$$n$$$ строк и $$$m$$$ столбцов квадратных клеток, в каждой из которых изначально закопана мина. Будем обозначать клетку на пересечении $$$x$$$-й строки и $$$y$$$-го столбца как $$$(x, y)$$$. Так как работа по извлечению мин довольно утомительна, Аквамен будет иногда задавать вам вопросы следующего вида. Артур говорит вам клетку $$$(x, y)$$$ и одно из четырех направлений (вверх, вниз, влево, вправо) и просит найти ближайшую к $$$(x, y)$$$ клетку в выбранном направлении, в которой еще есть мина, либо сказать, что такой клетки нет.

Эта задача состоит из трехподзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.