Mizuyokan on japanilainen makeinen, joka valmistetaan azukipaputahnasta. Se tehdään keittämällä azukipaputahnaa agarin kanssa ja hyydyttämällä seos suorakulmion muotoiseen vuokaan.

Nyt JOI-kunilla on mizuyokan-kone. Sen avulla JOI-kun voi valmistaa vaakasuunnassa pitkän suorakulmion muotoisen mizuyokanin, jossa on $N-1$ pystysuoraa leikkausviivaa. Mizuyokanin pituus ja leikkausviivojen paikat määräytyvät koneeseen asetetuista $N$ parametrista $d_1,d_2,\ldots,d_N$. Mizuyokanin pituus on $d_1+d_2+\cdots+d_N$. Vasemmalta lukien $(i-1)$. leikkausviivan ($1\le i\le N$) ja vasemmalta lukien $i$. leikkausviivan välinen etäisyys on $d_i$. Tässä mizuyokanin vasenta reunaa pidetään $0$. leikkausviivana ja oikeaa reunaa $N$. leikkausviivana. Aluksi mizuyokan-koneen parametrit toteuttavat ehdon $d_i=L_i$ ($1\le i\le N$).

JOI-kun suunnittelee järjestävänsä $Q$ teekutsut. $j$. teekutsut ($1\le j\le Q$) kuvataan kokonaisluvuilla $X_j,Y_j,A_j,B_j$, ja ne etenevät seuraavasti.

1. Mizuyokan-koneen parametri $d_{X_j}$ päivitetään ja sen arvoksi asetetaan $Y_j$.
2. JOI-kun valmistaa uuden mizuyokanin mizuyokan-koneella. Hän ottaa mizuyokanista osan, joka jää $A_j$. leikkausviivan ja $B_j$. leikkausviivan väliin, ja käyttää sen teekutsuilla. Loput hän syö itse.
3. JOI-kun leikkaa teekutsuille varatun mizuyokanin osan joitakin leikkausviivoja pitkin. Hän leikkaa mizuyokanin osan yhdeksi tai useammaksi palaksi. Tässä prosessissa seuraavan ehdon on täytyttävä: jos palat järjestetään vasemmalta oikealle alkuperäisten paikkojensa mukaisesti, palojen pituuksien muodostama lukujono on siksak-jono (zigzag).

Lukujonoa kutsutaan siksak-jonoksi, jos sen alkiot vuorotellen kasvavat ja pienenevät. Esimerkiksi jonot $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ ovat siksak-jonoja, mutta jonot $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ eivät ole siksak-jonoja. Täsmällisesti sanottuna jono $(x_1,x_2,\ldots,x_m)$ on siksak-jono, jos jompikumpi (tai molemmat) seuraavista ehdoista pätee:

• Kaikilla $k=1,2,\ldots,m-1$ epäyhtälö $x_k<x_{k+1}$ pätee, jos $k$ on pariton, ja epäyhtälö $x_k>x_{k+1}$ pätee, jos $k$ on parillinen.
• Kaikilla $k=1,2,\ldots,m-1$ epäyhtälö $x_k>x_{k+1}$ pätee, jos $k$ on pariton, ja epäyhtälö $x_k<x_{k+1}$ pätee, jos $k$ on parillinen.

Koska JOI-kun haluaa tarjota mizuyokania mahdollisimman monelle ystävälleen, hän haluaa maksimoida teekutsujen vaiheessa 3. saatavien palojen määrän.

Kirjoita ohjelma, joka mizuyokan-koneen alkuparametrien ja teekutsujen suunnitelman perusteella laskee jokaisille teekutsuille suurimman mahdollisen palojen määrän, joka voidaan saada leikkaamalla mizuyokanin osa niin, että ehto täyttyy. Huomaa, että tämän tehtävän rajoitusten puitteissa mizuyokanin osa on aina mahdollista leikata niin, että ehto täyttyy.

Syöte

Lue seuraavat tiedot standardisyötteestä.

$$ \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} $$

Tuloste

Kirjoita $Q$ riviä standarditulosteeseen. Tulosteen $j$. rivi ($1\le j\le Q$) vastaa $j$. teekutsuja. Sen tulee sisältää suurin mahdollinen palojen määrä, joka voidaan saada leikkaamalla mizuyokanin osa $j$. teekutsuilla niin, että ehto täyttyy.

Rajoitukset

• $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$).
• Kaikki annetut arvot ovat kokonaislukuja.

Osatehtävät

1. (6 pistettä) $N\le 200,Q\le 10$.
2. (9 pistettä) $N\le 2\,000,Q\le 10$.
3. (13 pistettä) $Q\le 10$.
4. (32 pistettä) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 pistettä) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

3

Huomautus

Ensimmäisillä teekutsuilla mizuyokan-koneen parametreiksi asetetaan $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun käyttää mizuyokanin osaa $0$. leikkausviivan ja $5$. leikkausviivan väliltä kuvan 1 mukaisesti.

Kuva 1. Teekutsuille varattu mizuyokan

JOI-kun voi leikata mizuyokanin osan esimerkiksi seuraavasti.

Kuva 2. Kolme tapaa leikata mizuyokan. Ylhäältä alas: Tapa 1, Tapa 2, Tapa 3.

Tavassa 1 palojen pituudet ovat $5,14,7,4$. Koska tämä jono ei ole siksak-jono, se ei täytä ehtoa. Toisaalta tavassa 2 palojen pituudet ovat $11,8,11$. Koska tämä jono on siksak-jono, se täyttää ehdon. Tavassa 3 palan pituus on $30$. Koska tämä jono on siksak-jono, myös se täyttää ehdon.

Jos JOI-kun leikkaa mizuyokanin osan tavalla 2, hän saa 3 palaa. Koska hänen ei ole mahdollista leikata mizuyokanin osaa niin, että ehto täyttyy ja hän saa vähintään 4 palaa, tulosta ensimmäiselle riville 3.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Syöte 2

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

Tuloste 2

1
2
3

Huomautus

Ensimmäisillä teekutsuilla teekutsuille varatun mizuyokanin osan pituus on $4$. Siinä on yksi leikkausviiva etäisyydellä $2$ vasemmasta reunasta. Jos JOI-kun käyttää mizuyokanin leikkaamatta sitä, hän saa yhden palan. Palojen pituuksien jono on $(4)$, joka on siksak-jono. Koska hän ei voi saada enempää kuin yhden palan, tulosta 1.

Toisilla teekutsuilla teekutsuille varatun mizuyokanin osan pituus on $9$. Siinä on kaksi leikkausviivaa etäisyyksillä $2,4$ vasemmasta reunasta. Jos JOI-kun leikkaa mizuyokanin kohdasta, jonka etäisyys vasemmasta reunasta on $4$, hän saa kaksi palaa. Palojen pituuksien jono on $(4,5)$, joka on siksak-jono. Koska hän ei voi saada enempää kuin kaksi palaa, tulosta 2.

Kolmansilla teekutsuilla teekutsuille varatun mizuyokanin osan pituus on $10$. Siinä on kolme leikkausviivaa etäisyyksillä $1,3,5$ vasemmasta reunasta. Jos JOI-kun leikkaa mizuyokanin leikkausviivoista, joiden etäisyydet vasemmasta reunasta ovat $3,5$, hän saa kolme palaa. Palojen pituuksien jono on $(3,2,5)$, joka on siksak-jono. Koska hän ei voi saada enempää kuin kolme palaa, tulosta 3.

Tämä esimerkkisyöte täyttää osatehtävien $1,2,3,5,6$ rajoitukset.