7. Exotické korenia

Marcel si pred vedúcovskou chatou KSP kúpil automatický robotický systém na uskladňovanie korenia od firmy Kuchárske Stroje a Potreby s.r.o., prístroj má tvar kruhovej poličky, v ktorej je jeden rad priehradok, v každej priehradke je niekoľko vrecúšok s jedným druhom korenia.

Prístroj má hlavicu, ktorá vyberá a podáva korenia. Hlavica vždy ukazuje na jedno vrecúško korenia.

Marcel si pozerá svoje recepty a rozmýľa nad tým, ako si rozmiestniť korenia tak, aby nestrávil veľa času čakaním na to, kým mu robot podá korenie. Aby vedel optimalizovať toto rozloženie, tak by od vás potreboval vykonávať \(2\) typy udalostí:

• Zmeň počet vrecúšok s korením v nejakej priehradke.

• Odpovedaj na otázku, ako dlho bude robotovi trvať vybrať konkrétny druh korenia, teda dostať sa zo začiatočnej pozície, vrchu priehradky \(x\), na koncovú pozíciu, spodok priehradky \(x'\), odkiaľ vie vybrať dané korenie.

Úloha

Máme jednu cyklickú radu priehradok, dlhú \(n\) (v každej priehradke je niekoľko vrecúšok korenia jedného typu). V priehradke \(i\) sa nachádza \(a_{i}\) vrecúšok.

Poličku obsluhuje robot, ktorý sa vie hýbať tromi spôsobmi:

• Pohyb cyklicky doprava - z vrchu priehradky \(x\) na vrch priehradky \(x+1\), alebo zo spodu priehradky \(x\) na spodok priehradky \(x+1\),resp na \(0\) ak sa \(x=n-1\), tento pohyb trvá 1 sekundu.

• Pohyb cyklicky doľava - z vrchu priehradky \(x\) na vrch priehradky \(x-1\), alebo zo spodu priehradky \(x\) na spodok priehradky \(x-1\), respektíve na \(n-1\) ak sa \(x=0\), tento pohyb trvá 1 sekundu.

• Pohyb dole - Ak sa robot nachádza na vrchu priehradky \(i\), tak sa vie za \(a_i\) sekúnd dostať na spodok priehradky \(i\).

Máme dva typy udalostí:

• Zmeň počet vrecúšok v priehradke \(x_i\) na \(a_{new}\).

• Otázka: Zisti, za koľko najmenej sekúnd sa vie robot presunúť, ak sa na začiatku nachádza na vrchu priehradky \(x\), a potrebuje sa dostať na spodok priehradky \(x'\)? Robot môže použiť ľubovoľne veľa pohybov doprava a doľava, a najviac jeden pohyb dolu.

Formát vstupu

V prvom riadku vstupu sú medzerou oddelené čísla \(n,q\), kde \(1 \leq n,q \leq 5 \cdot 10^5\), udávajúce počet priehradok a otázok.

Na nasledujúcom riadku sú medzerou oddelené hodnoty \(a_i\), počty vrecúšok na kôpkach v priehradkách, kde \(1 \leq a_i \leq 10^9\) a \(0 \leq i \leq n-1\).

Na nasledujúcich \(q\) riadkoch sa nachádzajú udalosti 2 typov:

• “! \(x\) \(a_{new}\)” - zmeň hodnotu \(a_x\) na \(a_{new}\), kde \(0 \leq x \leq n-1\) a \(1 \leq a_{new} \leq 10^9\).
• “? \(x\) \(x'\)” - vypíš minimálny potrebný čas na to, aby sa robot dostal z vrchu priehradky \(x\) na spodok priehradky \(x'\), kde \(0 \leq x,x' \leq n-1\).

Obmedzenia a hodnotenie

Táto úloha má 8 testovacích sád. V nich sú nasledovné obmedzenia:

V sadách \(3,5,6\) sa navyše nachádzajú iba udalosti typu \(?\).

V sadách \(3,4\) platí, že vo všetkých udalostiach typu \(?\) je \(|x-x'|=N/2\), a \(N\) je párne.

Vstupy a výstupy pre túto úlohu sú veľké, preto odporúčame používať FastIO a \n namiesto endl v C++. Upozorňujeme vás, že pomalšie jazyky ako Python nemusia prechádzať v časovom limite.

Formát výstupu

Pre každú udalosť typu \(?\) vypíš na samostatný riadok odpoveď.

Príklady

Input:

5 2
1 1 1 1 1
? 0 0
? 0 4

Output:

1
2

V prvej otázke sa robot vie posunúť dole, za 1 sekundu.

V druhej otázke sa robot posunie doľava a dole, všimnite si, že tento pohyb je cyklický.

Input:

5 3
9 9 9 9 9
? 0 0
! 4 1
? 0 0

Output:

9
3

V prvej otázke sa robot vie posunúť dole za 9 sekúnd.

Po zmene sa v druhej otázke oplatí prejsť doľava, dole za 1 sekundu a doprava, taktiež si všimnite cyklickosť pohybov do strán.