Магічний диск і карти#9093

Магічний диск і карти

1 секунда

64 мегабайти

Дуже складна

Козак Вус вже давно знає Новий Надсекретний Секрет Леді, але йому все одно цікаво грати в ігри, які вона пропонує. Цього разу Леді хоче навчити Козака Вуса робити магічні операції на диску.

Диск являє собою круг, розділений на $k$ рівних сегментів. На передній стороні диска за годинниковою стрілкою послідовно виписано всі числа від $1$ до $k$ , у кожному сегменті по одному числу. На задній стороні проти годинникової стрілки послідовно виписано всі числа від $- 1$ до $- k$ , у кожному сегменті по одному числу. Крім того, у кожному сегменті на різних сторонах виписані два однакових числа, але з різними знаками. У верхньому секторі записано число $1$ .

На рисунку 1 зображено передню сторону диска і на рисунку 2 — задню. Сірим виділено верхній сектор.

Також є колода з $n$ карт. На кожній карті написано число, яке по абсолютному значенню не перевищує $1 0^{9}$ 10^9. За один хід Леді переглядає всі карти з початку до кінця по черзі. Нехай число, що написано на черговій карті — $a$ . Якщо $a > 0$ a > 0, то диск обертається за годинниковою стрілкою на $a$ сегментів. Якщо $a < 0$ a < 0, то диск обертається проти годинникової стрілки на $- a$ сегментів. Якщо $a = 0$ a = 0, то диск перевертається з передньої сторони на задню або з задньої на передню, зберігаючи сектор, що був угорі, на своєму місці.

Дано початкову інформацію про числа на $n$ картах і $q$ операцій, у кожній з яких потрібно поміняти дві карти місцями. Після кожної операції Леді робить один хід з отриманою колодою карт, а Козак Вус повинен сказати число, що буде написане на верхньому секторі на стороні, яка буде видима після цього ходу. Допоможіть Козакові, знайшовши число у верхньому секторі після кожного ходу. Зверніть увагу, що перед кожним новим ходом диск повертається у початкове положення, тобто таке, у якому на верхньому секторі написано число $1$ .

Вхідні дані

Перший рядок містить три цілі числа $k$ , $n$ та $q$ ( $1 \leq k \leq 1 0^{9}, 2 \leq n \leq 1 0^{5}, 1 \leq q \leq 1 0^{5}$ 1 \leq k \leq 10^9,\ 2 \leq n \leq 10^5,\ 1 \leq q \leq 10^5) — кількість секторів, карт у колоді та операцій відповідно.

Другий рядок містить $n$ цілих чисел $a_{1}$ a_1, $a_{2}$ a_2, $\dots$ , $a_{n}$ a_n ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \leq a_i \leq 10^9) — номінал $i$ -ої карти з верху колоди.

Наступні $q$ рядків містять по два цілих числа $x$ та $y$ ( $1 \leq x < y \leq n$ 1 \leq x < y \leq n) — позиції карт, які треба змінити під час виконання відповідної операції.

Вихідні дані

Для кожної операції в окремому рядку виведіть одне число — відповідь на задачу після виконання чергової операції.

Приклади

Приклад 1

Приклад 2

Примітка

Пояснення до першого прикладу.

Після виконання операції заміни колода карт виглядає так: $0$ , $- 7$ , $0$ , $2$ . Спочатку у верхньому секторі знаходиться число $1$ . Далі Леді бере карту $0$ і тепер зверху знаходиться число $- 1$ . Після карти $- 7$ зверху знаходиться $- 6$ , після наступного нуля зверху знаходиться число $6$ й після останньої карти $2$ зверху знаходиться число $4$ . На зображенні нижче проілюстровано цей процес.