Laiko ribojimas: 3s

Atminties ribojimas: 256MB

Duomenų failas: daugiau_uzklausu.in

Rezultatų failas: daugiau_uzklausu.out

Jei norite pateikti savo sprendimą - prisijunkite.

Sudėtingos užklausos

Jūs turite masyvą, sudarytą iš n sveikųjų skaičių a_1, a_2, a_3, ..., a_n. Jūsų uždavinys - įvykdyti q užklausų turimai skaičių sekai.

Užklausos gali būti trijų tipų:

  1. Nustatymo užklausa: sekos elementams a_l,a_{l+1},...a_r nustatyti reikšmę d.
  2. Pridėjimo užklausa: prie sekos elementų a_l,a_{l+1},...a_r pridėti skaičių d.
  3. Sumos užklausa: apskaičiuoti elementų a_l,a_{l+1},...a_r kvadratų sumą.

Pradiniai duomenys

Pirmoje eilutėje pateiktas testų skaičius t (1\\leqt\\leq20). Sekančiose eilutėse pateikiami testų duomenys.

Testo duomenys:

Pirmoje eilutėje pateikti du skaičiai n ir q (1\\leqn,q\\leq100000), atitinkamai nurodantys masyvo elementų skaičių bei užklausų kiekį.

Antroje eilutėje pateikta n skaičių a_i: pradinės elementų reikšmės. 0\\leqa_1,a_2,a_3,...,a_n\\leq1000.

Kitose q eilučių pateikti užklausų duomenys: Skaičius c - užklausos tipas ('0', '1' arba '2').

Jei c yra 0, tai toje eilutėje toliau yra trys skaičiai: l,r,d - nustatymo užklausos intervalo pradžia, pabaiga, ir elementams nustatoma reikšmė (1\\leql\\leqr\\leqn,-1000\\leqd\\leq1000).

Jei c yra 1, tai toje eilutėje toliau yra trys skaičiai: l,r,d - pridėjimo užklausos intervalo pradžia, pabaiga, ir elementams pridedama reikšmė (1\\leql\\leqr\\leqn,-1000\\leqd\\leq1000).

Jei c yra 2, tai toje eilutėje taip pat yra du skaičiai l ir r - sumuojamo intervalo pradžia ir pabaiga (1\\leql\\leqr\\leqn).

Rezultatai

Kiekvienai 2 tipo užklausai išveskite prašomų elementų kvadratų sumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1
 
Testas 1:
30
7
13
Testas 2:
1

Pastaba: Kvadratų sumos niekada neviršys 10^9