Главна тема о којој се ових дана прича у Бајтовији је најновија видео игрица. Циљ ове игре је борба против YY чудовишта. Ово створење је добило своје име по томе што не живи у XY координатном систему као сва остала чудовишта, већ у YY координатном систему.

Ова игрица има \(N\) нивоа, и познато је да за \(i\)-ти ниво, играч може да нанесе штету од \(A_i\) поена YY чудовишту, користећи једну јединицу енергије. Јунакиња наше приче, Јована, планира да наредних \(Q\) дана игра ову игрицу. За сваки дан позната је вредност \(T_i\).

Ако је \(T_i = 1\), Јована \(i\)-тог дана прелази нивое \(L_i\), \(L_{i+1}\), \(\dots\), \(R_i\) тим редом и сваки ниво започиње са \(S_i\) енергије. Како сви воле ову игрицу, сваки пут када Јована започне неки ниво још један становник Бајтовије се укључи као њен саиграч, тако да на нивоу \(L_i\) она има једног саиграча, на нивоу \(L_{i+1}\) два саиграча, и тако даље, па на крају на нивоу \(R_i\) има \(R_i - L_i + 1\) саиграча. На сваком нивоу она потроши највећи број јединица енергије на помагање саиграчима, тако да на сваког од њих потроши исти цео број енергије, а остатак енергије потроши да нанесе штету YY чудовишту.

Формално, укупна штета је \(\Sigma_{m=1}^{R_i - L_i + 1} A_{L_i + m - 1} \cdot (S_i\) \(mod\) \(m)\), где \(x\) \(mod\) \(y\) представља остатак броја \(x\) при дељењу бројем \(y\).

Ако је \(T_i = 2\), \(i\)-тог дана се игрица ажурира тако да се \(A_{L_i}\) промени на \(R_i\). Ажурирање траје цео дан и тако да није могуће играти игрицу.

За сваки дан када Јована игра игрицу, одредите укупну штету коју ће да нанесе YY чудовишту.

Пример

Нека су \(N = 5\) и \(Q = 5\), и нека су низови \(A = \{7, 2, 3, 9, 4\}\), \(T = \{1, 1, 2, 1, 1\}\), \(L = \{3, 1, 3, 1, 1\}\), \(R = \{5, 5, 5, 5, 3\}\) и \(S = \{7, 100, \varnothing, 100, 1\}\).

• Одговор за први дан је \(3 \cdot (7\) \(mod\) \(1)\) \(+\) \(9 \cdot (7\) \(mod\) \(2)\) \(+\) \(4 \cdot (7\) \(mod\) \(3)\) \(=\) \(0 + 9 + 4\) \(=\) \(13\).
• Одговор за други дан је \(7 \cdot (100\) \(mod\) \(1)\) \(+\) \(2 \cdot (100\) \(mod\) \(2)\) \(+\) \(3 \cdot (100\) \(mod\) \(3)\) \(+\) \(9 \cdot (100\) \(mod\) \(4)\) \(+\) \(4 \cdot (100\) \(mod\) \(5)\) \(=\) \(0 + 0 + 3 + 0 + 0\) \(=\) \(3\).
• Трећег дана вредност \(A_3\) постаје \(5\).
• Одговор за четврти дан је \(7 \cdot (100\) \(mod\) \(1)\) \(+\) \(2 \cdot (100\) \(mod\) \(2)\) \(+\) \(5 \cdot (100\) \(mod\) \(3)\) \(+\) \(9 \cdot (100\) \(mod\) \(4)\) \(+\) \(4 \cdot (100\) \(mod\) \(5)\) \(=\) \(0 + 0 + 5 + 0 + 0\) \(=\) \(5\).
• Одговор за пети дан је \(7 \cdot (1\) \(mod\) \(1)\) \(+\) \(2 \cdot (1\) \(mod\) \(2)\) \(+\) \(5 \cdot(1\) \(mod\) \(3)\) \(=\) \(0 + 2 + 5\) \(=\) \(7\).

Након позива ваше функције низ \(O\) треба да буде једнак \(\{13, 3, \varnothing, 5, 7\}\).

Опис функције

Потребно је да имплементирате функцију

• \(Resi(N, A[\ldots], Q, T[\ldots], L[\ldots], R[\ldots], S[\ldots], O[\ldots])\)

где је \(N\) број нивоа видео игрице, а \(Q\) број дана. Низови \(T\), \(L\), \(R\) и \(S\) описују догађаје у наредних \(Q\) дана. У низ \(O\) потебно је уписати одговоре на питања за све дане када је \(T_i = 1\). Није потребно ништа уписивати као вредности за остале чланове низа \(O\) (када је \(T_i = 2\)).

Сви низови су индексирани од 1.

Ограничења

• \(1 \leq N, Q, A_i \leq 10^5\)
• За \(T_i = 1\) важи \(1 \leq L_i \leq R_i \leq N\), \(1 \leq S_i \leq 10^5\)
• За \(Т_i = 2\) важи \(1 \leq L_i \leq N\), \(1 \leq R_i \leq 10^5\)

Подзадаци

• [8 поена]: \(N, Q \leq 1000\)
• [12 поена]: За \(T_i = 1\) важи \(S_i \leq 10\)
• [24 поена]: \(A_i = 1\) за све \(1 \leq i \leq N\) и \(T_i = 1\) за све дане
• [20 поена]: \(T_i = 1\) за све дане
• [36 поена]: Без додатних ограничења

Детаљи имплементације

Потребно је да пошаљете тачно један фајл који имплементира поменуту функцију. Осим тражене функције, ваш фајл може да садржи и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Resi(int N, int* A, int Q, int* T, int* L, int* R, int* S, long long* O);

Вашим програмима је дозвољено да мењају садржај низова, али не смеју да приступају ван њихових граница.

Уз задатак, обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Обај програм учитава са стандардног улаза следеће податке:

• У првом реду број \(N\).
• У другом реду низ \(A\) од \(N\) бројева.
• У трећем реду број \(Q\).
• У наредних \(Q\) редова по 3 или 4 броја који представљају упите.

Затим овај програм позива вашу функцију и штампа, у засебним редовима, одговоре на упите првог типа које је ваша функција уписала у низ \(O\).