Задача C. Суперагент

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Женя Борин учится в школе юных суперагентов. На занятии по избавлению от слежки Борин получил такое теоретическое задание:

Зал аэропорта на плане имеет вид прямоугольника шириной W и высотой H метров. Пол разделён на клетки размером 1 × 1 метр. Клетка в северо-западном углу имеет координаты (1, 1).

На западной и северной стене через каждые два метра укреплены видеокамеры, обозревающие горизонтальную или вертикальную полосу шириной в одну клетку до противоположной стены. Таким образом, клетки, хотя бы одна координата которых чётна, просматриваются видеокамерами. Если агент попадёт в поле зрения камеры, поднимется тревога.

В зале находится N пассажиров. Пассажиры двигаются по залу, перемещаясь за 1 секунду на одну клетку по горизонтали или вертикали. Если между камерой и агентом есть хотя бы один пассажир, то агент остаётся незамеченным этой камерой.

Агент находится в точке с координатами (1, ya) и желает попасть в точку с координатами (W, ya), не подняв тревоги и затратив не более T секунд. Требуется написать программу, которая определит необходимую последовательность перемещений агента по известным координатам и перемещениям пассажиров.

Произвольное количество пассажиров может находиться одновременно в одной клетке, однако агент не может находиться в одной клетке с пассажиром.

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

Первая строка входного файла содержит числа W H T ya N. Следующие N строк содержат значения xi yi pi, где xi, yi — координаты i-го пассажира в начальный момент времени, pi — строка из T символов, описывающая перемещения пассажиров в течении T секунд. Каждый символ равен "n", если пассажир перемещается на север, "s" — на юг, "w" — на запад, "e" — на восток, "z" — стоит на месте.

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

Выходной файл должен содержать строку длиной не более T символов, описывающую движение агента в том же формате, что и движения пассажиров, либо строку IMPOSSIBLE, если решения не существует. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ W, H, T, N ≤ 100, ya и W — нечётные, 1 ≤ xi ≤ W, 1 ≤ yi, ya ≤ H

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 6 20 3 2
2 1 eeeeewwwwwweeeeeewww
3 2 ssssnnnnnsssssnnnnns
zzzzzzzzzzzeeeeee
2
3 4 5 3 1
1 1 zzzzz
IMPOSSIBLE

0.063s 0.009s 13