Хомячки на торе
После спасения двух своих друзей из вентиляции хомячки устроили весёлый праздник. Они пригласили всех смешариков, стали пить чай и грызть всё подряд. А потом хомячки притащили огромную баранку и предложили смешарикам сыграть с ними в игру. Смешарики по очереди говорят хомячкам команды, а хомячки бегают по баранке, выполняя их.
Баранка представляет собой клетчатый тор размером 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-ой строке вывести его координаты после исполнения команд.