011 - 円盤

問題文

古代遺跡から不思議な装置が発見された。発見された装置は、両面に整数が書かれた円盤、整数が書かれたカードの束、カードの束を入れる台からなる。台にカードの束を入れると、円盤が回転する。円盤は、常に片面だけが見えている。

円盤は中心から角度が均等になるようにK個の区画に分割されていて、表側に 1 から K までの整数が順番に時計回りに刻まれている。また、円盤は裏表で区画の境界を共有しており、ある区画の表側に数　Xが刻まれているとき、その裏側には数-X が刻まれている。されに、円盤の外側には針が存在し、ある一つの区画の弧の中心を指し示している。以降、見えている面の針が指し示している値が X であるとき、円盤は X にセットされていると呼ぶ。

調査の結果、装置の挙動について以下のことが判明した。

装置の台にカードの束を入れると、装置は円盤を 1 にセットする。
その後、装置はカードを上から順に読み込んでいき、書かれている数Aに応じて以下のように動作する。

• Aが正の数の時　円盤を図の時計回りに|A|区画を回転させる
• Aが0の時 　　　針と円盤の中心を通る直線を軸として、円盤を裏返す
• Aが負の数の時　円盤を図の反時計回りに|A|区画を回転させる

ただし、|A|はAの絶対値を表す。台に入れる直前のカードの並び方によって、すべての動作終了後に円盤にセットされている値は様々である。そこで、装置の特性を調べるために、2枚のカードを交換するごとにカードの束を台にセットし、すべての動作終了後の円盤にセットされている値を求めることを繰り返した。

課題

装置の情報とカードを交換する命令がいくつか与えられたとき、各命令に対して、すべての動作終了後に円盤にセットされている値を計算するプログラムを作成せよ。ただし、各命令では、それまでの命令で得られたカードの束に対して交換を行う。

入力・出力

入力

入力は以下の形式で与えられる。

K N Q
A1 A2 ... AN
L1 R1
L2 R2
:
LQ RQ

1行目に、区画の個数K(2≦K≦10⁹)、カードの枚数N(2≦N≦100,000)、命令の個数Q(1≦Q≦100,000)が与えられる。2行目に、カードに書かれているN個の整数が与えられる。A_i(-10⁹≦A_i≦10⁹)は上からi番目のカードに書かれている数を表す。続くQ行にi番目の命令を表すL_i, R_i(1≦L_i<R_i≦N)が与えられる。命令は上からL_i番目のカードとR_iのカードの位置を交換し、カードの束を台に入れる操作を表す。

出力

各命令に対して、すべての動作終了後に装置にセットされている値を1行に出力し。

入出力例

入力例 1

5 3 1
1 -2 0
2 3

出力例 1

-3

一つめの命令後のカードの束は上から順に以下のようになる。

1 0 -2

一つめの命令に対し、装置は以下のように動作する。

したがって、すべての動作終了後に円盤にセットされている値は-3となり、これを出力する。

---

入力例 2

5 7 5
0 0 3 3 3 3 3
1 2
2 3
3 4
4 5
5 6

出力例 2

1
2
3
4
5