円盤
古代遺跡から不思議な装置が発見された。発見された装置は、両面に整数が書かれた円盤、整数が書かれたカードの束、カードの束を入れる台からなる。台にカードの束を入れると、円盤が回転する。円盤は、常に片面だけが見えている。
円盤は中心から角度が均等になるように$K$個の区画に分割されていて、表側に$1$から$K$までの整数が順番に時計回りに刻まれている。また、円盤は裏表で区画の境界を共有しており、ある区画の表側に数$X$が刻まれているとき、その裏側には数$-X$が刻まれている。さらに、円盤の外側には針が存在し、ある一つの区画の弧の中心を指し示している。以降、見えている面の針が指し示している値が$X$であるとき、円盤は$X$にセットされていると呼ぶ。
図 1 $K$ = 5 の場合(図の左側では円盤は1に、右側では-1にセットされている)
調査の結果、装置の挙動について以下のことが判明した。
装置の台にカードの束を入れると、装置は円盤を1にセットする。
その後、装置はカードを上から順に読み込んでいき、書かれている数$A$に応じて以下のように動作する。
- $A$が正の数のとき: 円盤を図の時計回りに$|A|$区画回転させる
- $A$が$0$ のとき: 針と円盤の中心を通る直線を軸として、円盤を裏返す
- $A$が負の数のとき: 円盤を図の反時計回りに$|A|$区画回転させる
ただし、$|A|$は$A$の絶対値を表す。台に入れる直前のカードの並び方によって、すべての動作終了後に円盤にセットされている値は様々である。そこで、装置の特性を調べるために、2枚のカードを交換するごとにカードの束を台にセットし、すべての動作終了後の円盤にセットされている値を求めることを繰り返した。
装置の情報とカードを交換する命令がいくつか与えられたとき、各命令に対して、すべての動作終了後に円盤にセットされている値を計算するプログラムを作成せよ。ただし、各命令では、それまでの命令で得られたカードの束に対して交換を行う。
入力
入力は以下の形式で与えられる。
$K$ $N$ $Q$ $A_1$ $A_2$ ... $A_N$ $L_1$ $R_1$ $L_2$ $R_2$ $...$ $L_Q$ $R_Q$
１行目に、区画の個数$K$ ($2 \leq K \leq 10^9$)、カードの枚数$N$ ($2 \leq N \leq 100,000$)、命令の個数$Q$ ($1 \leq Q \leq 100,000$)が与えられる。２行目に、カードに書かれている$N$個の整数が与えられる。$A_i$ ($-10^9 \leq A_i \leq 10^9$)は上から$i$番目のカードに書かれている数を表す。続く$Q$行に$i$番目の命令を表す$L_i,R_i$ ($1 \leq L_ i < R_i \leq N$) が与えられる。命令は上から$L_i$番目のカードと$R_i$番目のカードの位置を交換し、カードの束を台に入れる操作を表す。
出力
各命令に対して、すべての動作終了後に装置にセットされている値を１行に出力する。
入出力例
入力例１
5 3 1 1 -2 0 2 3
出力例１
-3
一つめの命令後のカードの束は上から順に以下のようになる。
1 0 -2
一つ目の命令に対し、装置は以下のように動作する。
図2 装置の動作の様子
したがって、すべての動作終了後に円盤にセットされている値は-3となり、これを出力する。
入力例２
5 7 5 0 0 3 3 3 3 3 1 2 2 3 3 4 4 5 5 6
出力例２
1 2 3 4 5