Hamsters on a torus (RU)

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

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

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

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

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

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

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

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

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