34600번 - Tagi 다국어

문제

Markov veliki pomoćnik u organizaciji nastupa je robot Tagi. Kad god uhvate slobodan trenutak, Marko i Tagi vole igrati sljedeću igru: prvo Tagi odredi niz od $N$ prirodnih brojeva. Zatim Tagi mora čim brže odgovoriti na $M$ Markovih pitanja. U svakom pitanju Marka zanima koliki je zbroj brojeva u nizu od pozicije $L$ do pozicije $R$.

Naravno, Tagiju je to prelako pa su igru učinili još zanimljivijom. Marko će Tagiju u svakom pitanju zadati i broj za transformiranje $X$. Tagi će zatim brojeve od pozicije $L$ do pozicije $R$ transformirati na sljedeći način:

• Ako je broj paran, tada će njega transformirati u upola manji broj (tj., podijeliti će broj s 2ドル$)
• Ako je broj neparan, tada će taj broj transformirati u broj $X$.

Nakon što Tagi transformira brojeve, zbrojit će ih i odgovoriti Marku na pitanje. A prije nego Marko postavi novo pitanje, Tagi će sve transformacije poništiti.

Iako je Tagi besprijekoran u svim ostalim zadacima, transformiranje brojeva mu ne ide tako lako. Pomozite mu odgovoriti na Markova pitanja!

입력

U prvom retku su prirodni brojevi $N$ i $M$ (1ドル ≤ N ≤ 100,円 000,ドル 1ドル ≤ M ≤ 1,円 000,円 000$), broj brojeva u nizu i broj Markovih pitanja.

U sljedećem retku je $N$ prirodnih brojeva $A_i$ (1ドル ≤ A_i ≤ 1,円 000,円 000,円 000$), brojevi u nizu.

Slijedi $M$ redaka po tri broja $L_i,ドル $R_i$ i $X_i$ (1ドル ≤ L_i≤ R_i ≤ N,ドル 1ドル ≤ X_i ≤ 1,円 000,円 000,円 000$) koji označavaju da Marko u $i$-tom pitanju traži zbroj brojeva od pozicije $L_i$ do pozicije $R_i$ uz zadani broj za transformiranje $X_i$.

출력

U $M$ redova ispiši po jedan prirodan broj, redom odgovor na svako Markovo pitanje.

제한

노트

Opis prvog probnog primjera:

1. upit: 7ドル + 2 + 1 + 7$
2. upit: 5ドル + 5$
3. upit: 9ドル + 9 + 2$
4. upit: 4ドル$
5. upit: 1ドル + 1 + 16 + 6$