Задача C. Виртуальный лабиринт ≡

Условие

Лабиринт в компьютерной игре представлен полем из H строк по W символов каждая, где каждый символ равен либо '.' (ASCII 46), что означает свободную клетку, либо '#' (ASCII 35), что означает стену.

Игроки появляются в случайной свободной клетке лабиринта и могут за один ход перемещаться на любую из соседних по горизонтали или вертикали свободных клеток. Обозначим перемещения игрока буквами N, S, W, E для направлений на север, юг, запад и восток соответственно. Направление взгляда игрока совпадает с направлением последнего сделанного им хода. Перед первым ходом игрок смотрит на север.

Игра построена на основе трёхмерного графического движка с видом от первого лица. Поэтому в каждый момент времени игрок видит только содержимое клетки непосредственно перед ним в направлении его взгляда, а также двух клеток непосредственно слева и справа от него. Один из игроков опубликовал видео своих перемещений по игровому миру. В результате анализа видео было получено количество шагов N и символы L_i F_i R_i для для каждого хода, обозначающие содержимое клеток слева, впереди и справа перед i-м ходом игрока.

Вокруг лабиринта находится неограниченное поле из пустых клеток, но известно, что игрок никогда не покидал пределы лабиринта.

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

Формат входного файла

Первая строка входного файла содержит целые числа H W. Следующие H строк содержат по W символов . и # каждая — описание лабиринта. Строка номер H + 2 содержит целое число N. Следующие N строк состоят из трёх символов L_i F_i R_i каждая.

Формат выходного файла

Первая строка выходного файла должна содержать два целых числа x y — столбец и строку начальной позиции игрока (нумерация начинается с 1). Вторая строка должна состоять из N символов N, S, W, E — последовательность ходов игрока. Если существует несколько решений, выведите любое из них. Если решения не существует, выведите единственное число −1.

Ограничения

1 ≤ W, H ≤ 100, 1 ≤ N ≤ 1000, 1 ≤ x ≤ W, 1 ≤ y ≤ H

Примеры тестов

4 5
.....
.#.#.
.#.#.
.###.
6
#..
...
#..
...
#.#
###

5 2
N
W
W
S
S

1 1
#
1
##.

-1