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