Магический диск и карты

Казак Вус давно знает Новый Сверхсекретный Секрет Леди, но ему всё равно интересно играть в игры, которые она предлагает. На этот раз Леди хочет научить Казака Вуса выполнять магические операции с диском.

Диск представляет собой круг, разделённый на ( k ) равных сегментов. На передней стороне диска по часовой стрелке последовательно записаны все числа от 1 до ( k ), по одному числу в каждом сегменте. На задней стороне против часовой стрелки последовательно записаны числа от (-1) до (-k), также по одному числу в каждом сегменте. В каждом сегменте на разных сторонах записаны два одинаковых числа, но с противоположными знаками. В верхнем секторе записано число 1.

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

Также имеется колода из ( n ) карт. На каждой карте написано число, которое по абсолютному значению не превышает ( 10^9 ). За один ход Леди просматривает все карты по очереди с начала до конца. Пусть число на текущей карте — ( a ). Если ( a > 0 ), диск вращается по часовой стрелке на ( a ) сегментов. Если ( a < 0 ), диск вращается против часовой стрелки на (-a) сегментов. Если ( a = 0 ), диск переворачивается с передней стороны на заднюю или наоборот, сохраняя сектор, который был наверху, на своём месте.

Дана начальная информация о числах на ( n ) картах и ( q ) операций, в каждой из которых нужно поменять местами две карты. После каждой операции Леди делает один ход с обновлённой колодой карт, а Казак Вус должен определить число, которое будет написано на верхнем секторе на видимой стороне после этого хода. Помогите Казаку, найдя число в верхнем секторе после каждого хода. Обратите внимание, что перед каждым новым ходом диск возвращается в начальное положение, то есть такое, в котором на верхнем секторе написано число 1.

Формат входных данных

Первая строка содержит три целых числа ( k ), ( n ) и ( q ) (( 1 \leq k \leq 10^9 ), ( 2 \leq n \leq 10^5 ), ( 1 \leq q \leq 10^5 )) — количество секторов, карт в колоде и операций соответственно.

Вторая строка содержит ( n ) целых чисел ( a[1] ), ( a[2] ), ..., ( a[n] ) ((-10^9 \leq a[i] \leq 10^9)) — номинал ( i )-й карты сверху колоды.

Следующие ( q ) строк содержат по два целых числа ( x ) и ( y ) (( 1 \leq x < y \leq n )) — позиции карт, которые нужно поменять во время выполнения соответствующей операции.

Формат выходных данных

Для каждой операции в отдельной строке выведите одно число — ответ на задачу после выполнения очередной операции.

Примеры

Примечание

Объяснение к первому примеру.

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