Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: height.in

Rezultatų failas: height.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kalno aukštis

Yra N eilėje stovinčių kalnų, sunumeruotų 1,2,...,N, jų aukščiai virš jūros lygio iš pradžių yra h_1,h_2,h_3,...h_N. Kartais, dėl tektoninių plokščių judėjimo, kalnų aukščiai keičiasi. Ir keičiasi net ne po vieną, o ištisais intervalais! Vienu kartu, pasikeičia keleto kalnų, esančių iš eilės, aukščiai. Jums reikės atsakyti, koks yra tam tikro kalno aukštis tam tikru momentu. Konkrečiai, jums bus duodamos dviejų tipų užklausos:

  1. Nurodoma, kad kalnų l,l+1,...,r-1,r aukščiai padidėjo per d metrų; jei d - neigiamas, reiškia, tie kalnai nusileido žemyn.
  2. Užduodamas klausimas: koks dabar yra kalno a aukštis virš jūros lygio.

Pradiniai duomenys

Pirmojoje eilutėje pateikti skaičiai N,Q(1\\leqN\\leq100000, 1\\leqQ\\leq200000) - kalnų skaičius ir užklausų skaičius.

Antroje eilutėje yra N skaičių - pradiniai kalnų skaičiai. -100000\\leqh_i\\leq100000.

Tolesnėse Q eilučių yra užklausos, po vieną kiekvienoje eilutėje.

Kiekvienos užklausos pradžioje nurodomas skaičius t - užklausos tipas.

Jei t=1, toliau nurodomi skaičiai l,r,d - intervalo galai ir aukštis, per kurį pakilo kalnai (1\\leql\\leqr\\leqN,-100000\\leqd\\leq100000).
Jei t=2, nurodomas skaičius a - numeris kalno, kurio aukštį reikia išvesti (1\\leqa\\leqN).

Rezultatai

Kiekvienai antro tipo užklausai išveskitę po skaičių - nurodyto kalno aukštį.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6 6
1 2 3 4 5 6
2 4
1 2 5 3
2 2
1 3 6 -2
2 4
2 6
 
4
5
5
4