e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

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

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

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