Козак Вус вже давно знає Новий Надсекретний Секрет Лед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 написано число, яке по абсолютному значенню не перевищує 109. За один х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лi числа k, n та q (**1 ≤ k ≤ 109 , 2 ≤ n ≤ 105 , 1 ≤ q ≤ 105**) — кiлькiсть секторiв, карт у колодi та операцiй вiдповiдно.

Другий рядок мiстить n цiлих чисел a[1], a[2], . . . , a[n] (**−109 ≤ ai ≤ 109**) — ном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ї замiни колода карт виглядає так: 0, −7, 0, 2. Спочатку у верхньому секторi знаходиться число 1. Далi Ледi бере карту 0 i тепер зверху знаходиться число −1. Пiсля карти −7 зверху знаходиться −6, пiсля наступного нуля зверху знаходиться число 6 й пiсля останньої карти 2 зверху знаходиться число 4. На зображеннi нижче проiлюстровано цей процес.