Magical Disk and Cards

Cossack Vus has long known the New Top Secret of the Lady, but he still enjoys playing the games she offers. This time, the Lady wants to teach Cossack Vus how to perform magical operations on a disk.

The disk is a circle divided into ( k ) equal segments. On the front side of the disk, numbers from 1 to ( k ) are written sequentially in a clockwise direction, with one number in each segment. On the back side, numbers from (-1) to (-k) are written sequentially in a counterclockwise direction, with one number in each segment. In each segment, the numbers on opposite sides are the same but with opposite signs. The number 1 is positioned in the top sector.

Figure 1 shows the front side of the disk, and Figure 2 shows the back side. The top sector is highlighted in gray.

There is also a deck of ( n ) cards. Each card has a number written on it, which does not exceed ( 10^9 ) in absolute value. In one move, the Lady reviews all the cards from start to finish in sequence. Let the number on the current card be ( a ). If ( a > 0 ), the disk rotates clockwise by ( a ) segments. If ( a < 0 ), the disk rotates counterclockwise by (-a) segments. If ( a = 0 ), the disk flips from the front side to the back or from the back to the front, keeping the sector that was on top in its place.

Given the initial information about the numbers on ( n ) cards and ( q ) operations, in each of which two cards need to be swapped, the Lady makes one move with the resulting deck of cards. Cossack Vus must determine the number that will be on the top sector on the visible side after this move. Help Cossack Vus find the number in the top sector after each move. Note that before each new move, the disk returns to its initial position, where the number 1 is in the top sector.

Input Format

The first line contains three integers ( k ), ( n ), and ( q ) (( 1 \leq k \leq 10^9 ), ( 2 \leq n \leq 10^5 ), ( 1 \leq q \leq 10^5 )) — the number of sectors, cards in the deck, and operations, respectively.

The second line contains ( n ) integers ( a[1] ), ( a[2] ), ..., ( a[n] ) ((-10^9 \leq a[i] \leq 10^9)) — the value of the ( i )-th card from the top of the deck.

The next ( q ) lines contain two integers ( x ) and ( y ) (( 1 \leq x < y \leq n )) — the positions of the cards that need to be swapped during the corresponding operation.

Output Format

For each operation, output one number on a separate line — the answer to the problem after performing the current operation.

Examples

Note

Explanation for the first example:

After performing the swap operation, the deck of cards looks like this: 0, (-7), 0, 2. Initially, the number 1 is in the top sector. Then the Lady takes the card 0, and now the number (-1) is on top. After the card (-7), the number (-6) is on top, after the next zero, the number 6 is on top, and after the last card 2, the number 4 is on top. The image below illustrates this process.