Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: segment_tree_2.in

Rezultatų failas: segment_tree_2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Masyvo užklausos 2

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 dviejų tipų:

  1. Elemento užklausa: rasti elemento a_x reikšmę
  2. Pridėjimo užklausa: prie sekos elementų a_l,a_{l+1},...a_r pridėti skaičių d.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai n ir q (1\\leqn,q\\leq200000), 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\\leq200000.

Kitose q eilučių pateikti užklausų duomenys: Simbolis c - užklausos tipas (? arba +). Jei c yra ?, tai toje eilutėje taip pat yra skaičius x - elemento užklausos pozicija (1\\leqx\\leqn). Jei c yra +, tai toje eilutėje toliau yra trys skaičiai: l,r,d - pridėjimo užklausos intervalo pradžia, pabaiga, ir prie elementų pridedama reikšmė (1\\leql\\leqr\\leqn,0\\leqd\\leq200000).

Rezultatai

Kiekvienai ? tipo užklausai išveskite prašomo elemento reikšmę.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 6
5 5 3 4 0
+ 1 4 5
+ 3 5 5
? 3
+ 1 2 0
+ 3 5 1
? 5
 
13
6
 
2 5
3 2
? 1
? 2
+ 1 2 4
? 1
? 2
 
3
2
7
6