26376번 - Krimošten 서브태스크다국어

문제

U malom mjestu na obali stoji n kuća označenih brojevima od 1 do n te poredanih u niz upravo tim redoslijedom slijeva nadesno. U svakoj kući se nalazi keramička kasica prasica sa sitnim novcima za namirnice — kasica prasica u kući j sadrži točno x_j kuna.

U mjestu se pojavio kriminalac koji provaljuje u kuće i krade bogatima, a daje siromašnima. Točnije, kriminalac odabere neku početnu kuću l te se kreće niz ulicu nadesno sve do kuće r i pritom provali u sve kuće između kuće l i kuće r (obje uključivo). Na početku svog kriminalnog pohoda, on u džepu ima y kuna, a u svakoj kući on razbija kasicu prasicu te uspoređuje pronađeni iznos s onim što on trenutno ima u džepu:

• Ako trenutno u džepu ima manje novaca, onda uzima jednu pronađenu kunu i stavlja je u svoj džep.
• Ako trenutno u džepu ima više novaca, onda vadi jednu kunu iz džepa i ostavlja je u kući.
• Ako ima jednako novaca, onda ne radi ništa.

Pred vama je m mogućih scenarija pljačke. Za j-ti scenarij je poznata je početna kuća l_j, završna kuća r_j i svota y_j koju je lokalni „obijač” imao u džepu na početku pohoda. Za svaki scenarij odredite koliko novaca bi lopov imao na kraju pohoda.

입력

U prvom redu nalaze se prirodni brojevi n i m — broj kuća te broj scenarija pljačke. U drugom redu nalazi se n cijelih brojeva x₁, x₂, . . . , x_n — iznos novaca u svakoj kasici prasici. U j-tom od sljedećih m redova nalaze se tri cijela broja — l_j, r_j i y_j koji opisuju j-ti scenarij pljačke.

출력

Ispišite m redova. U j-ti red ispišite traženu količina novaca na kraju pohoda u j-tom scenariju.

제한

서브태스크

힌트