Pentru că Phineas şi Ferb s-au hotărât să instaureze "viarna":https://www.youtube.com/watch?v=BWETBoOPHS8 în orasul Danville, "veveriţele":https://www.youtube.com/watch?v=iYoKCLY965A s-au decis în sfârşit să o lase în pace pe Candace şi vor să îşi facă provizii de ghinde.

Iniţial veveriţele au un număr $X$ de ghinde. În fiecare din următoarele $N$ zile, copacul din curtea familiei Flynn-Fletcher are un anumit număr de ghinde (În ziua $1$ are $v[1$] ghinde, în ziua $2$ $v[2$], ... în ziua $N$ $v[N$]).

Iniţial veveriţele au un număr $X$ de ghinde. Veveriţele vor colecta ghinde pe parcursul a $N$ zile, in ziua $i$ copacul din curtea familiei Flynn-Fletcher va avea $A{~i~}$ ghinde.
 

Veveriţele au un mod interesant de a-şi aduna ghinde. Acestea sunt fericite dacă în fiecare zi numărul lor de ghinde este *mai mare sau egal* ca numărul de ghinde care se află în ziua respectivă în copac.
La finalul fiecărei zile, acestea pot să-şi adune la colecţie toate ghindele care au fost în copac în ziua aceea. (Mai întâi trebuie să se respecte condiţia, apoi pot să adune ghindele)

h2. Restricţii
* $1 ≤ $N, Q$ ≤ 10^5^$

* $1 ≤ $v[i$] ≤ 10^9^$
* $v[i$] ≤ $v[i + 1]$ pentru $1 ≤ i ≤ N - 1$

* $1 ≤ $A{~i~}$ ≤ 10^9^$
* $A{~i~}$ ≤ $A{~i+1~}$ pentru $1 ≤ i ≤ N - 1$

h2. Subtaskuri

* **Subtaskul 1 (20 de puncte):** $N,Q ≤ 2000$
* **Subtaskul 2 (20 de puncte):** $v[i] ≤ 100$, pentru $1 ≤ i ≤ N, N,Q ≤ 10^5^$
* **Subtaskul 3 (60 de puncte):** restricţiile iniţiale

* *$Subtaskul 1 (20 de puncte):$* $N,Q ≤ 2000$
* *$Subtaskul 2 (20 de puncte):$* $A{~i~}$ ≤ $100$, pentru $1 ≤ i ≤ N, N,Q ≤ 10^5^$
* *$Subtaskul 3 (60 de puncte):$* restricţiile iniţiale

h2. Exemplu