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