Magiya diski və kartlar

Kazak Vus artıq çoxdan Yeni Ən Gizli Xanımın Sirrini bilir, amma o, yenə də onun təklif etdiyi oyunları oynamaqdan zövq alır. Bu dəfə Xanım Kazak Vusa disklə sehrli əməliyyatlar etməyi öyrətmək istəyir.

Disk dairə şəklindədir və k bərabər seqmentə bölünmüşdür. Diskin ön tərəfində saat əqrəbi istiqamətində ardıcıl olaraq 1-dən k-yə qədər bütün rəqəmlər yazılmışdır, hər seqmentdə bir rəqəm. Arxa tərəfində isə saat əqrəbinin əksinə ardıcıl olaraq −1-dən −k-ya qədər bütün rəqəmlər yazılmışdır, hər seqmentdə bir rəqəm. Bundan əlavə, hər seqmentdə müxtəlif tərəflərdə eyni rəqəmlər yazılmışdır, lakin fərqli işarələrlə. Üst seqmentdə 1 rəqəmi yazılmışdır.

Şəkil 1-də diskin ön tərəfi və şəkil 2-də arxa tərəfi göstərilmişdir. Üst seqment boz rənglə vurğulanmışdır.

Həmçinin, n kartdan ibarət bir dəst var. Hər kartda yazılmış rəqəm, mütləq dəyəri 10^9-dan çox olmayan bir rəqəmdir. Bir gedişdə Xanım kartların hamısını başdan sona qədər bir-bir nəzərdən keçirir. Tutaq ki, növbəti kartda yazılmış rəqəm a-dır. Əgər a > 0-dırsa, disk saat əqrəbi istiqamətində a seqment dönür. Əgər a < 0-dırsa, disk saat əqrəbinin əksinə −a seqment dönür. Əgər a = 0-dırsa, disk ön tərəfdən arxa tərəfə və ya arxa tərəfdən ön tərəfə çevrilir, üst seqment yerində qalır.

Kartların üzərindəki rəqəmlər haqqında ilkin məlumat və q əməliyyat verilir, hər birində iki kartın yerləri dəyişdirilməlidir. Hər əməliyyatdan sonra Xanım kart dəstəsi ilə bir gediş edir və Kazak Vus bu gedişdən sonra görünən tərəfdə üst seqmentdə yazılmış rəqəmi deməlidir. Kazaka kömək edin, hər gedişdən sonra üst seqmentdəki rəqəmi tapın. Diqqət yetirin ki, hər yeni gedişdən əvvəl disk başlanğıc vəziyyətinə qayıdır, yəni üst seqmentdə 1 rəqəmi yazılmış vəziyyətə.

Giriş formatı

Birinci sətir üç tam ədəd k, n və q (1 ≤ k ≤ 10^9 , 2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5) — seqmentlərin, kartların və əməliyyatların sayını ehtiva edir.

İkinci sətir n tam ədəd a[1], a[2], . . . , a[n] (−10^9 ≤ a[i] ≤ 10^9) — dəstənin üstündən i-ci kartın nominalını ehtiva edir.

Növbəti q sətir hər biri iki tam ədəd x və y (1 ≤ x < y ≤ n) ehtiva edir — müvafiq əməliyyat zamanı dəyişdirilməli olan kartların mövqeləri.

Çıxış formatı

Hər əməliyyat üçün ayrı sətirdə bir rəqəm çıxarın — növbəti əməliyyatdan sonra məsələnin cavabı.

Qeyd

Birinci nümunəyə izah.

Əməliyyat yerinə yetirildikdən sonra kart dəstəsi belə görünür: 0, −7, 0, 2. Əvvəlcə üst seqmentdə 1 rəqəmi var. Sonra Xanım 0 kartını götürür və indi üstdə −1 rəqəmi var. −7 kartından sonra üstdə −6 var, növbəti sıfırdan sonra üstdə 6 var və son kart 2-dən sonra üstdə 4 var. Aşağıdakı şəkildə bu proses təsvir edilmişdir.