e-olymp
Задачи

Хомячки на торе

Хомячки на торе

prb214

После спасения двух своих друзей из вентиляции хомячки устроили весёлый праздник. Они пригласили всех смешариков, стали пить чай и грызть всё подряд. А потом хомячки притащили огромную баранку и предложили смешарикам сыграть с ними в игру. Смешарики по очереди говорят хомячкам команды, а хомячки бегают по баранке, выполняя их.

Баранка представляет собой клетчатый тор размером W*H. Всего в празднике участвует N хомячков. Все хомячки разные, для простоты пронумеруем их от 0 до N-1. После спасения из системы вентиляции хомячки резко поумнели, и теперь могут выполнять набор очень сложных команд. Очередная команда подается хомячку с номером, равным сумме координат всех хомячков по модулю N. Команды бывают следующих типов:

• Влево L - если на горизонтали есть другие хомячки, то встать слева на одну клетку от ближайшего хомячка, который находится слева. Если таких нет, то сдвинуться на одну клетку влево.

• Аналогично выполняются команды R, U, D, соответственно для движения вправо, вверх и вниз.

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

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

В первой строке заданы три целых числа W, H - размеры тора по горизонтали и вертикали соответственно (H, W100000), и N - число хомячков (N1000). Во второй строке находится N пар чисел - исходные координаты хомячков. Хомячки нумеруются, начиная с нуля. Координаты ограничены размерами баранки: 0X < W, 0Y < H. В предпоследней строке задано M - количество команд, 0M1000. В последней строке находится программа. Команды перечисляются через пробел.

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

Для каждого i-ого хомячка в i-ой строке вывести его координаты после исполнения команд.

Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
3 3 2
1 1
2 2
3
R U L
Выходные данные #1
2 1
1 0