Хом'ячки на торі#214
Після того як двох своїх друзів було врятовано з вентиляційної системи, хом'ячки вирішили влаштувати святкування. Вони запросили своїх друзів, пили чай і їли все, що змогли знайти. Потім хом'ячки дістали величезний бублик і запропонували пограти в гру. Друзі по черзі дають команди хом'ячкам, які бігають навколо бублика, виконуючи ці команди.
Бублик представляється як клітинний тор розміром W \times H. Всього у святкуванні беруть участь хом'яків. Усі хом'яки унікальні, тому для зручності пронумеруємо їх від до N-1. Після порятунку хом'яки стали набагато розумнішими і тепер можуть виконувати складні послідовності команд. Наступну команду виконує хом'як, чий номер дорівнює сумі координат усіх хом'яків за модулем . Команди такі:
Вліво : Якщо на цьому ж рядку є інші хом'яки, переміститися на клітинку одразу ліворуч від найближчого хом'яка ліворуч. Якщо таких немає — переміститися на одну клітинку вліво.
Аналогічно, команди , та використовуються для пересування праворуч, вгору і вниз відповідно.
Визначте фінальні позиції всіх хом'яків після завершення гри.
Перший рядок містить три цілі числа: , (1 \leq W, H \leq 100\,000) — горизонтальні й вертикальні розміри тора, та (1 \leq N \leq 1\,000) — кількість хом'яків. Другий рядок містить пар цілих чисел — початкові координати хом'яків. Нумерація хом'яків починається з нуля. Координати задовольняють 0 \leq X < W, 0 \leq Y < H. Передостанній рядок містить (0 \leq M \leq 1\,000) — кількість команд. Останній рядок містить перелік команд, розділених пробілами.
Для кожного -го хом'яка виведіть його координати після виконання всіх команд у -му рядку.
Приклад 1