Fişierul intrare/ieşire:	vaporeon.in, vaporeon.out	Sursă	Lot Seniori Alexandria, 2017, baraj 6
Autor	Adrian Budau	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.75 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Vaporeon

Blanche, liderul echipei Mystic, a fost capturată de echipa Lacheta! Ea a fost adusă într-o bază a echipei care conţine N obstacole numerotate de la 1 la N, fiecare obstacol i având rezistenţa R[i]. Iniţial, Blanche este plasată în dreptul celui de-al x-lea obstacol. Încercând să scape, ea îl eliberează pe Vaporeon care distruge al x-lea obstacol şi capătă puterea de atac A egală cu R[x].
Pentru a evada, Vaporeon trebuie să distrugă toate obstacolele rămase. La un moment de timp la care Vaporeon a distrus toate obstacolele din intervalul [x, y], el poate executa exact una din mişcările:

• Hydro Pump pe obstacolul x-1, dacă x-1 ≥ 1 şi R[x-1] ≤ A.
• Hydro Pump pe obstacolul y+1, dacă y+1 ≤ N şi R[y+1] ≤ A.
• Work Up, care creşte puterea de atac A la valoarea minimă dintre R[x-1] şi R[y+1]. Dacă doar unul din obstacole există, puterea de atac creşte la valoarea rezistenţei acestuia.

O mişcare Hydro Pump necesită efort 1, în timp ce o mişcare Work Up necesită efort K. Notăm cu E[x] efortul necesar evadării pornind din al x-lea obstacol. E[x] este egal cu suma minimă a eforturilor necesare pentru a distruge cele N obstacole, dacă Vaporeon a început din al x-lea obstacol.
Echipa Lacheta a anticipat această strategie, aşa că studiază diferite aranjamente ale obstacolelor, cât şi diferite poziţii în care să o plaseze iniţial pe Blanche. Ei vă vor da numărul de obstacole N, efortul K necesar unei mişcări şi rezistenţele celor N obstacole. Apoi, ei vă vor cere să efectuaţi următoarele operaţii:

• Să schimbaţi două obstacole adiacente x şi x+1.
• Să spuneţi, pentru doi indici x şi y, care este suma E[x] + E[x+1] + … + E[y] pentru aranjamentul actual al obstacolelor.

Date de intrare

Primul rând al fişierului de intrare vaporeon.in va conţine pe N şi K.
Următorul rând va conţine valorile lui R, separate prin câte un spaţiu.
Vor urma descrierile operaţiilor, una pe câte un rând. Daca P este răspunsul celei mai recente operaţii de al doilea tip (sau 0 dacă nu au fost încă astfel de operaţii), atunci operaţiile se vor codifica astfel:

• 1 X reprezintă interschimbarea lui X xor P şi (X xor P) + 1
• 2 X Y reprezintă o operaţie de găsire a sumei E[X xor P] + … + E[Y xor P]

Date de ieşire

Fişierul de ieşire vaporeon.out va conţine răspunsurile pentru toate operaţiile de al doilea tip, câte una pe un rând.

Restricţii şi precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ K ≤ 1.000.000
• 1 ≤ R[i] ≤ 1.000.000.000
• Numărul total de operaţii este mai mic sau egal cu 200.000
• Pentru 20% din teste, N ≤ 1.000 şi numărul total de apeluri la funcţiile exchange şi query nu depăşeşte 2.000.

Exemplu

Explicaţie

Operaţiile efectuate sunt:

• Una de al doilea tip pentru a calcula E[2]
• Una de al doilea tip pentru a calcula E[1] + E[2] + E[3] + E[4] + E[5]
• Una de primul tip asupra lui 2
• Una de al doilea tip pentru a calcula E[2]
• Una de al doilea tip pentru a calcula E[1] + E[2] + E[3] + E[4] + E[5]

Cum se trimit solutii?