D. Остров сокровищ
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Наконец отважные путешественники достигли острова, где зарыты сокровища пиратов. Однако, когда корабль уже подплывал к острову, капитан обнаружил, что какая-то крыса отгрызла кусочек от карты сокровищ.

Карту сокровищ можно представить себе как прямоугольник размера n × m, каждая ячейка которого означает квадрат острова со стороной в одну милю. Некоторые ячейки означают море и они непроходимы. Все остальные ячейки проходимы, а в некоторых из них находятся некоторые достопримечательности. Например, большой дуб на холме или пещера в скалах.

Кроме того, на карте имеется набор из k инструкций, каждая из которых имеет вид:

«Пройти x миль в направлении y»,

где возможны направления: север, юг, восток и запад. Если последовательно выполнить все эти инструкции последовательно от первой до последней, то придешь ровно в то место, где зарыты сокровища.

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

Капитан хочет узнать какие из достопримечательностей имеет смысл проверить. Он просит вас помочь в этом деле.

Входные данные

В первой строке находятся два целых числа n и m (3 ≤ n, m ≤ 1000).

Далее расположены n строк по m символов в каждой — описание карты острова. «#» означает море. Гарантируется, что все ячейки по периметру прямоугольника — море. «.» означает проходимую клетку без каких либо достопримечательностей, а достопримечательности обозначаются большими буквами латинского алфавита (от «A» до «Z»). Не все буквы алфавита могут быть использованы. Однако гарантируется, что хотя бы одна из них на карте присутствует. Все достопримечательности обозначены различными буквами.

В следующей строке находится число k (1 ≤ k ≤ 105), после чего идут k строк, в каждой из которых описывается одна инструкция. Каждая из инструкций имеет вид «dir len», где dir — направление, а len — расстояние. dir может принимать значения «N», «S», «W» и «E» для севера, юга, запада и востока соответственно. При этом север находится наверху, юг внизу, запад слева, а восток справа. len — целое число от 1 до 1000.

Выходные данные

Выведите все достопримечательности, удовлетворяющие инструкциям, в виде одной строки без каких либо разделителей в алфавитном порядке. Если ни одна из достопримечательностей не подходит, то выведите «no solution» без кавычек.

Примеры
Входные данные
6 10
##########
#K#..#####
#.#..##.##
#..L.#...#
###D###A.#
##########
4
N 2
S 1
E 1
W 2
Выходные данные
AD
Входные данные
3 4
####
#.A#
####
2
W 1
N 2
Выходные данные
no solution