Mizuyokan er japanskt sælgæti gert úr azuki-baunamauki. Það er búið til með því að sjóða azuki-baunamauk með agar og láta það storkna í rétthyrndu formi.

Nú á JOI-kun mizuyokan-vél. Með henni getur JOI-kun búið til lárétt ílangan rétthyrndan mizuyokan með $N-1$ lóðréttum skurðlínum. Lengd mizuyokan-bitans og staðsetningar skurðlínanna ákvarðast af $N$ stikum $d_1,d_2,\ldots,d_N$ sem stilltir eru á vélinni. Lengd mizuyokan-bitans er $d_1+d_2+\cdots+d_N$. Fjarlægðin milli $(i-1)$-tu skurðlínunnar ($1\le i\le N$) frá vinstri og $i$-tu skurðlínunnar frá vinstri er $d_i$. Hér lítum við á ystu vinstri brún mizuyokan-bitans sem $0$-tu skurðlínuna og ystu hægri brún hans sem $N$-tu skurðlínuna. Í upphafi uppfylla stikar mizuyokan-vélarinnar $d_i=L_i$ ($1\le i\le N$).

JOI-kun ætlar að halda $Q$ teboð. $j$-ta teboðið ($1\le j\le Q$) lýsist með heiltölunum $X_j,Y_j,A_j,B_j$ og fer fram á eftirfarandi hátt.

1. Stikinn $d_{X_j}$ á mizuyokan-vélinni er uppfærður og settur sem $Y_j$.
2. JOI-kun býr til nýjan mizuyokan með mizuyokan-vélinni. Hann tekur hlutann af mizuyokan-bitanum milli $A_j$-tu skurðlínunnar og $B_j$-tu skurðlínunnar og notar hann í teboðið. Hann borðar afganginn.
3. JOI-kun sker hlutann af mizuyokan-bitanum fyrir teboðið eftir einhverjum af skurðlínunum. Hann sker hlutann í eitt eða fleiri stykki. Í þessu ferli þarf eftirfarandi skilyrði að vera uppfyllt: ef stykkjunum er raðað frá vinstri eins og í upphaflegum stöðum þeirra, þá er runan af lengdum stykkjanna sikksakk (zigzag).

Hér kallast runa sikksakk ef stök rununnar hækka og lækka til skiptis. Til dæmis eru runurnar $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ sikksakk, en runurnar $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ eru ekki sikksakk. Nákvæmlega er runa $(x_1,x_2,\ldots,x_m)$ kölluð sikksakk ef annað hvort (eða bæði) af eftirfarandi skilyrðum er uppfyllt:

• Fyrir $k=1,2,\ldots,m-1$ gildir ójafnan $x_k<x_{k+1}$ ef $k$ er oddatala, og ójafnan $x_k>x_{k+1}$ ef $k$ er slétt tala.
• Fyrir $k=1,2,\ldots,m-1$ gildir ójafnan $x_k>x_{k+1}$ ef $k$ er oddatala, og ójafnan $x_k<x_{k+1}$ ef $k$ er slétt tala.

Þar sem JOI-kun vill gefa sem flestum vinum sínum mizuyokan, vill hann hámarka fjölda stykkja sem fást í lið 3. í teboðinu.

Skrifið forrit sem, gefnum upplýsingum um upphafsstika mizuyokan-vélarinnar og áætlun teboðanna, reiknar fyrir hvert teboð mesta mögulega fjölda stykkja sem hægt er að fá með því að skera hlutann af mizuyokan-bitanum þannig að skilyrðið sé uppfyllt. Athugið að miðað við skorður þessa verkefnis er alltaf hægt að skera hlutann af mizuyokan-bitanum þannig að skilyrðið sé uppfyllt.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

$$ \begin{gathered} N\\ L_1\quad L_2\quad\cdots\quad L_N\\ Q\\ X_1\quad Y_1\quad A_1\quad B_1\\ X_2\quad Y_2\quad A_2\quad B_2\\ \vdots\\ X_Q\quad Y_Q\quad A_Q\quad B_Q \end{gathered} $$

Úttak

Skrifið $Q$ línur í staðalúttak. $j$-ta línan ($1\le j\le Q$) í úttakinu samsvarar $j$-ta teboðinu. Hún á að innihalda mesta mögulega fjölda stykkja sem hægt er að fá með því að skera hlutann af mizuyokan-bitanum í $j$-ta teboðinu þannig að skilyrðið sé uppfyllt.

Skorður

• $1\le N\le 250\,000$.
• $1\le L_i\le 10^9$ ($1\le i\le N$).
• $1\le Q\le 50\,000$.
• $1\le X_j\le N$ ($1\le j\le Q$).
• $1\le Y_j\le 10^9$ ($1\le j\le Q$).
• $0\le A_j<B_j\le N$ ($1\le j\le Q$).
• Öll gefin gildi eru heiltölur.

Undirverkefni

1. (6 stig) $N\le 200,Q\le 10$.
2. (9 stig) $N\le 2\,000,Q\le 10$.
3. (13 stig) $Q\le 10$.
4. (32 stig) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 stig) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 stig) Engar viðbótarskorður.

Dæmi

Inntak 1

6
5 6 8 7 4 9
1
6 9 0 5

Úttak 1

3

Skýring

Í fyrsta teboðinu eru stikar mizuyokan-vélarinnar stilltir á $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun notar hlutann af mizuyokan-bitanum milli $0$-tu skurðlínunnar og $5$-tu skurðlínunnar eins og á Mynd 1.

Mynd 1. Mizuyokan-bitinn fyrir teboðið

JOI-kun getur til dæmis skorið hlutann af mizuyokan-bitanum á eftirfarandi hátt.

Mynd 2. Þrjár aðferðir til að skera mizuyokan-bitann. Aðferð 1, Aðferð 2, Aðferð 3 að ofan.

Í Aðferð 1 eru lengdir stykkjanna $5,14,7,4$. Þar sem þessi runa er ekki sikksakk uppfyllir hún ekki skilyrðið. Hins vegar eru lengdir stykkjanna í Aðferð 2 jafnar $11,8,11$. Þar sem þessi runa er sikksakk uppfyllir hún skilyrðið. Í Aðferð 3 er lengd stykkisins $30$. Þar sem þessi runa er sikksakk uppfyllir hún einnig skilyrðið.

Ef JOI-kun sker hlutann af mizuyokan-bitanum með Aðferð 2 fær hann 3 stykki. Þar sem ekki er hægt fyrir hann að skera hlutann af mizuyokan-bitanum þannig að skilyrðið sé uppfyllt og hann fái 4 eða fleiri stykki, skal skrifa út 3 í fyrstu línuna.

Þetta sýnidæmi uppfyllir skorður allra undirverkefna.

Inntak 2

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

Úttak 2

1
2
3

Skýring

Í fyrsta teboðinu er lengd hlutans af mizuyokan-bitanum fyrir teboðið $4$. Það er ein skurðlína í fjarlægð $2$ frá vinstri brún. Ef JOI-kun notar mizuyokan-bitann án þess að skera hann fær hann eitt stykki. Runan af lengdum stykkjanna er $(4)$, sem er sikksakk. Þar sem hann getur ekki fengið fleiri en eitt stykki skal skrifa út 1.

Í öðru teboðinu er lengd hlutans af mizuyokan-bitanum fyrir teboðið $9$. Það eru tvær skurðlínur í fjarlægðum $2,4$ frá vinstri brún. Ef JOI-kun sker mizuyokan-bitann við skurðlínuna í fjarlægð $4$ frá vinstri brún fær hann tvö stykki. Runan af lengdum stykkjanna er $(4,5)$, sem er sikksakk. Þar sem hann getur ekki fengið fleiri en tvö stykki skal skrifa út 2.

Í þriðja teboðinu er lengd hlutans af mizuyokan-bitanum fyrir teboðið $10$. Það eru þrjár skurðlínur í fjarlægðum $1,3,5$ frá vinstri brún. Ef JOI-kun sker mizuyokan-bitann við skurðlínurnar í fjarlægðum $3,5$ frá vinstri brún fær hann þrjú stykki. Runan af lengdum stykkjanna er $(3,2,5)$, sem er sikksakk. Þar sem hann getur ekki fengið fleiri en þrjú stykki skal skrifa út 3.

Þetta sýnidæmi uppfyllir skorður undirverkefna $1,2,3,5,6$.