special

Time limit: 0.05s Memory limit: 64MB Input: special.in Output: special.out

Didel a învățat astăzi la matematică ce este un dreptunghi. El a definit numărul special al unei perechi (x,y)(x, y) astfel: A desenat un dreptunghi de lungime xx și lățime yy. Numărul special va fi numărul de pătrate (de latură naturală, mai mare ca 11) incluse în dreptunghiul desenat.

Pa˘tratul desenat de Didel pentru x=3, y=3\text{Pătratul desenat de Didel pentru} \ x = 3, \ y = 3

În figura de mai sus, sunt 44 pătrate de latură 22 și 11 pătrat de latură 33. Deci numărul special al perechii (3,3)(3, 3) va fi 55.

Cerință

Se dă un șir de nn numere întregi, a1,a2,,ana_1, a_2, \dots, a_n. Se dau qq actualizări de forma l r x yl \ r \ x \ y: Adaugă la al,al+1,,ara_l, a_{l + 1}, \dots, a_r numărul special al perechii (x,y)(x, y). După toate actualizările, să se afle maximul din șirul aa.

Date de intrare

Pe prima linie a fișierului de intrare special.in se găsesc două numere întregi, nn și qq, reprezentând numărul de elemente din șir și numărul de actualizări. Pe a doua linie se vor găsi nn numere întregi, separate prin câte un spațiu, a1,a2,,ana_1, a_2, \dots, a_n. Pe următoarele qq linii se vor găsi cele qq actualizări (pe a (i+2)(i + 2)-a linie se vor găsi numerele li,ri,xi,yil_i, r_i, x_i, y_i (separate prin câte un spațiu), reprezentând forma celei de a ii-a actualizare).

Date de ieșire

Pe prima linie a fișierului de ieșire special.out se va găsi un singur întreg, maximul din șirul aa.

Restricții și precizări

  • 1n,q100 0001 \leq n, q \leq 100 \ 000
  • 1ai1091 \leq a_i \leq 10 ^ 9 (pentru 1in1 \leq i \leq n)
  • La finalul tuturor actualizărilor, 1ai10181 \leq a_i \leq 10 ^ {18}.
  • 1lirin1 \leq l_i \leq r_i \leq n (pentru 1iq1 \leq i \leq q)
  • 1xi,yi1091 \leq x_i, y_i \leq 10 ^ 9 (pentru 1iq1 \leq i \leq q)

Exemplu

special.in

5 4
1 2 3 4 5
1 4 6 7
1 2 3 4
4 5 2 1
2 4 5 1

special.out

80

Explicație

Șirul aa devine: 79 80 73 74 579 \ 80 \ 73 \ 74 \ 5. Maximul este 8080.

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