cartita

Time limit: 0.2s Memory limit: 64MB Input: cartita.in Output: cartita.out

În grădina lui Macarie există un șir de NN morcovi, numerotați de la 11 la NN. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul ii are în dreptul său o grămăjoară de pământ cu înălțimea de hih_i centimetri. O cârtiță neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie către un morcov, tot pământul rezultat îl scoate afară modificând astfel înălțimea grămăjoarei corespunzătoare acelui morcov, dar și ale celorlalți morcovi din grădină. Dacă, în urma săpării unei galerii către morcovul de pe poziția pospos, înălțimea grămăjoarei lui a crescut cu xx centimetri atunci înălțimile grămăjoarelor tuturor morcovilor se modifică după următoarea regulă ce depinde de un număr KK:

  • înălțimea grămăjoarei morcovului pos1pos - 1 se modifică cu xKx - K centimetri iar a morcovului pos+1pos + 1 cu x+Kx + K centimetri;
  • înălțimile gramăjoarelor morcovilor pos2pos - 2 și pos+2pos + 2 se modifică cu x2Kx - 2 \cdot K respectiv x+2Kx + 2 \cdot K centimetri.

În caz general, înălțimea se modifică după următoarele reguli pentru fiecare morcov din grădină:

  • Înălțimea hposih_{pos - i} devine hposi+xiKh_{pos - i} + x - i \cdot K, pentru fiecare ii, 1ipos11 \leq i \leq pos - 1;
  • Înălțimea hpos+ih_{pos + i} devine hpos+i+x+iKh_{pos + i} + x + i \cdot K, pentru fiecare ii, 1iNpos1 \leq i \leq N - pos.

Cerință

Se cunosc înălțimile inițiale ale tuturor celor NN grămăjoare și cele UU modificări făcute de cârtiță asupra înălțimilor grămăjoarelor de pământ ale morcovilor.

Știm că în cadrul unei secvențe continue de morcovi cel mai tentant pentru cârtiță este morcovul cu cea mai mică înălțime a grămăjoarei de pământ.

Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.

Date de intrare

Fișierul de intrare cartita.in conține pe prima linie un număr natural NN având semnificația din enunț.

Pe următoarea linie se află NN numere naturale despărțite prin câte un spațiu reprezentând, în ordine, înălțimile grămăjoarelor de pământ, al ii-lea număr reprezentând înălțimea inițială hih_i a grămăjoarei din dreptul morcovului ii.

Pe a treia linie se află un număr natural UU reprezentând numărul de morcovi către care cârtița a săpat galerii.

Pe următoarele UU linii se află câte un triplet de numere naturale pospos, xx, KK, separate între ele prin câte un spațiu, cu semnificația că, în urma săpării unei galerii către morcovul pospos, înălțimea grămăjoarei lui a crescut cu xx centimetri iar celelalte înălțimi se modifică după regula descrisă în enunț.

Pe următoarea linie se găsește numărul QQ reprezentând numărul de intervale unde se dorește identificarea înălțimii minime a unei grămăjoare corespunzătoare celui mai tentant morcov.

Pe următoarele QQ linii sunt câte două numere naturale LL, RR, separate între ele printr-un spațiu, reprezentând capetele intervalului de morcovi investigat.

Date de ieșire

Fișierul de ieșire cartita.out va conține QQ linii pe fiecare găsindu-se, în ordine, răspunsul la intervalele investigate.

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000
  • 1U300 0001 \leq U \leq 300 \ 000
  • 1Q200 0001 \leq Q \leq 200 \ 000
  • 1LRN1 \leq L \leq R \leq N
  • Inițial 1hiN1 \leq h_i \leq N, pentru fiecare ii, 1iN1 \leq i \leq N.
  • 1posN1 \leq pos \leq N, 1x4001 \leq x \leq 400 și 21K21−21 \leq K \leq 21, K0K \neq 0.
# Punctaj Restricții
1 12 N,U,Q2 000N, U, Q \le 2 \ 000
2 9 N,U2 000N, U \le 2 \ 000 și Q200 000Q \le 200 \ 000
3 25 N,U75 000N, U \le 75 \ 000 și Q15Q \le 15
4 17 N,U,Q75 000N, U, Q \le 75 \ 000
5 16 N100 000N \le 100 \ 000, U300 000U \le 300 \ 000 și Q15Q \le 15
6 7 N100 000N \le 100 \ 000, U300 000U \le 300 \ 000 și Q10 000Q \le 10 \ 000
7 14 Fără restricții suplimentare

Exemplu

cartita.in

6
1 6 2 4 3 4
3
4 5 2
2 4 1
4 2 8
3
1 6
2 4
4 4

cartita.out

-19
-3
17

Explicație

După prima galerie săpată către morcovul 44, șirul înălțimilor celor N=6N = 6 grămăjoare a devenit (0,7,5,9,10,13)(0, 7, 5, 9, 10, 13).
După a doua galerie săpată către morcovul 22, șirul înălțimilor celor N=6N = 6 grămăjoare a devenit (3,11,10,15,17,21)(3, 11, 10, 15, 17, 21).
După a treia galerie săpată către morcovul 44, șirul înălțimilor celor N=6N = 6 grămăjoare a devenit (19,3,4,17,27,39)(−19, −3, 4, 17, 27, 39).
Pe intervalul [1,6][1, 6], înălțimea minimă este 19−19, pe intervalul [2,4][2, 4], înălțimea minimă este 3−3, iar pentru ultimul interval investigat [4,4][4, 4] înălțimea minimă este 1717.

Log in or sign up to be able to send submissions!