Магiчний диск i карти
Козак Вус вже давно знає Новий Надсекретний Секрет Ледi, але йому все одно цiкаво грати в iгри, якi вона пропонує. Цього разу Ледi хоче навчити Козака Вуса робити магiчнi операцiї на дисковi.
Диск являє собою круг, роздiлений на k рiвних сегментiв. На переднiй сторонi диска за годинниковою стрiлкою послiдовно виписано всi числа вiд 1 до k, у кожному сегментi по одному числi. На заднiй сторонi проти годинникової стрiлки послiдовно виписано всi числа вiд −1 до −k, у кожному сегментi по одному числi. Крiм того, у кожному сегментi на рiзних сторонах виписанi два однакових числа, але з рiзними знаками. У верхньому секторi записано число 1.
На рисунку 1 зображено передню сторону диска i на рисунку 2 — задню.Сiрим видiлено верхнiй сектор.
Також є колода з n карт. На кожнiй картi написано число, яке по абсолютному значенню не перевищує 10^9. За один хiд Ледi переглядає всi карти з початку до кiнця по черзi. Нехай число, що написано на черговiй картцi — a. Якщо a > 0, то диск обертається за годинниковою стрiлкою на a сегментiв. Якщо a < 0, то диск обертається проти годинникової стрiлки на −a сегментiв. Якщо a = 0, то диск перевертається з передньої сторони на задню або з задньої на передню, зберiгаючи сектор, що був вгорi, на своєму мiсцi.
Дано початкову iнформацiю про числа на n картах i q операцiй, у кожнiй з яких потрiбно помiняти двi карти мiсцями. Пiсля кожної операцiї Ледi робить один хiд з отриманою колодою карт, а Козак Вус повинен сказати число, що буде написане на верхньому секторi на сторонi, яка буде видима пiсля цього ходу. Допоможiть Козаковi, знайшовши число у верхньому секторi пiсля кожного ходу. Звернiть увагу, що перед кожним новим ходом диск повертається у початкове положення, тобто таке, у якому на верхньому секторi написано число 1.
Вхідні дані
Перший рядок мiстить три цiлi числа k, n та q (1 ≤ k ≤ 10^9 , 2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5) — кiлькiсть секторiв, карт у колодi та операцiй вiдповiдно.
Другий рядок мiстить n цiлих чисел a[1], a[2], . . . , a[n] (−10^9 ≤ a[i] ≤ 10^9) — номiнал i-ої карти з верху колоди.
Наступнi q рядкiв мiстять по два цiлi числа x та y (1 ≤ x < y ≤ n) — позицiї карт, якi треба змiнити пiд час виконання вiдповiдної операцiї.
Вихідні дані
Для кожної операцiї в окремому рядку виведiть одне число — вiдповiдь на задачу пiсля виконання чергової операцiї.
####Примiтка
Пояснення до першого прикладу.
Пiсля виконання операцiї замiни колода карт виглядає так: 0, −7, 0, 2. Спочатку у верхньому секторi знаходиться число 1. Далi Ледi бере карту 0 i тепер зверху знаходиться число −1. Пiсля карти −7 зверху знаходиться −6, пiсля наступного нуля зверху знаходиться число 6 й пiсля останньої карти 2 зверху знаходиться число 4. На зображеннi нижче проiлюстровано цей процес.
