Наконец отважные путешественники достигли острова, где зарыты сокровища пиратов. Однако, когда корабль уже подплывал к острову, капитан обнаружил, что какая-то крыса отгрызла кусочек от карты сокровищ.
Карту сокровищ можно представить себе как прямоугольник размера n × m, каждая ячейка которого означает квадрат острова со стороной в одну милю. Некоторые ячейки означают море и они непроходимы. Все остальные ячейки проходимы, а в некоторых из них находятся некоторые достопримечательности. Например, большой дуб на холме или пещера в скалах.
Кроме того, на карте имеется набор из k инструкций, каждая из которых имеет вид:
«Пройти x миль в направлении y»,
где возможны направления: север, юг, восток и запад. Если последовательно выполнить все эти инструкции последовательно от первой до последней, то придешь ровно в то место, где зарыты сокровища.
К сожалению, капитан не знает от какого места нужно выполнять инструкции — именно этот кусочек карты был утерян. Но капитан точно помнит, что там была указана какая то из достопримечательностей. Кроме того, капитан знает, что весь путь проходит по проходимым клеткам острова.
Капитан хочет узнать какие из достопримечательностей имеет смысл проверить. Он просит вас помочь в этом деле.
Выходные данные
Выведите все достопримечательности, удовлетворяющие инструкциям, в виде одной строки без каких либо разделителей в алфавитном порядке. Если ни одна из достопримечательностей не подходит, то выведите «no solution» без кавычек.