После свих својих догодовштина на такмичењима из програмирања, мали Перица је схватио да је најзанимљивији део сваког такмичења кликтање “Refresh” дугмета док чека резултате. Зато је Перица одлучио да постане професионални кликтач дугмића.

У припремама за МОКД (Међународну Олимпијаду из Кликтања Дугмића), Перица је дизајнирао специјални тренинг. Поређао је, на екрану рачунара, \(N\) дугмића у низ, при чему дугме \(i\) има тајмер који одбројава \(T_i\) стотинки. Када Перица стартује тренинг, он помера курсор по екрану и кликће.

Да би курсор померио између два суседна дугмета, Перици треба једна стотинка. Перичин циљ је да кликне свако дугме пре него што тајмер тог дугмета истекне. Такође, када год Перица кликне дугме \(i\), тајмер тог дугмета се ресетује и креће да одбројава \(T_i\) стотинки од почетка. Перица жели да пронађе стратегију којом може да помера курсор и кликће дугмиће произвољно дуго, а да тајмер ниједног дугмета не истекне до краја (то јест да између два узастопна клика дугмета \(i\) не протекне стриктно више од \(T_i\) стотинки).

При томе, претпостављамо да Перица може да изабере произвољну стартну позицију курсора на екрану, као и да сви тајмери крећу да одбројавају тек када се тренинг стартује. Такође, претпостављамо да сам клик траје занемарљиво кратко, па је померање курсора једина ствар за коју је потребно време.

Пошто је Перици кликтање дугмића досадило јако брзо, смислио је задатак за Вас. Дата су Вам почетна времена за тајмер сваког дугмета \(T_i\), као и \(Q\) упита, који могу доћи у два типа. За упите првог типа дат је индекс дугмета \(i\) и ново трајање тајмера за то дугме, \(T_i\). За упите другог типа, дати су индекси \(L\) и \(R\), и треба да одредите да ли Перица може да кликће дугмиће са индексима у интервалу \([L, R]\) произвољно дуго (то јест, да ли Перица може да успешно обави тренинг уколико су тајмери активни само на дугмићима у интервалу \([L, R]\)).

Уколико успешно обавите овај задатак, помоћићете Перици да се спреми за МОКД, а он ће са Вама поделити део награде које победа на овом престижном такмичењу доноси.

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

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

• \(Trening(N, T[\ldots], Q, X[\ldots], Y[\ldots], Z[\ldots], Ans[\ldots])\),

где је \(N\) број дугмића у низу, а \(Q\) број упита. Низ \(T[\ldots]\) садржи почетна времена за сваки од тајмера - тајмер дугмета \(i\) на почетку тренинга одбројава \(T[i]\) стотинки. Низ \(X[i]\) представља тип упита \(i\): уколико је \(X[i]=1\), упит \(i\) је првог типа, а уколико је \(X[i]=2\), онда је упит \(i\) другог типа.

Уколико је упит \(i\) првог типа, \(Y[i]\) представља индекс дугмета чији тајмер треба променити, док \(Z[i]\) представља нову вредност тајмера. Уколико је упит \(i\) другог типа, \(Y[i]\) представља леву, а \(Z[i]\) десну границу интервала на коме треба одредити да ли Перица може произвољно дуго да кликће дугмиће без да иједан тајмер истекне. Коначно, ако је упит \(i\) другог типа, у низ \(Ans\) треба уписати \(Ans[i]=1\) ако Перица може да тренира на интервалу \([Y[i], Z[i]]\) произвољно дуго. У супротном, треба уписати \(Ans[i]=0\). За упите првог типа, вредност \(Ans[i]\) неопходно је оставити непромењену.

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

Пример

Нека је \(N=5\) и \(Q=5\). Нека су почетна времена тајмера \(T=[4, 5, 6, 2, 3]\) и нека су низови \(X=[2, 2, 2, 1, 2], Y=[1, 1, 4, 3, 1]\), \(Z=[5, 3, 5, 2, 3]\) и \(Ans=[-1, -1, -1, -1, -1]\). Први упит је другог типа, и одговор на њега је НЕ, јер не постоји начин да Перица произвољно дуго кликће све дугмиће без да иједан тајмер истекне. На други упит је одговор ДА, јер Перица може да кликће дугмиће по у распореду 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1… На трећи упит је одговор ДА такође, јер Перица може кликтати по распореду 4, 5, 4, 5, 4… У четвром упиту се тајмер трећег дугмета поставља на 2 стотинке, па је одговор на пети упит НЕ.

Дакле, низ \(Ans\) треба поставити на \(Ans=[0, 1, 1, -1, 0]\).

Ограничења

• \(1\leq N, Q\leq 2\cdot 10^5\),
• \(1\leq T[i] \leq 10^9\), за све \(i\in [1, N]\),
• \(1\leq X[i] \leq 2\), за све \(i\in [1, Q]\),
• Ако је \(X[i]=1\), тада \(1\leq Y[i] \leq N\) и \(1\leq Z[i] \leq 10^9\),
• Ако је \(X[i]=2\), тада \(1\leq Y[i] \leq Z[i] \leq N\),
• \(Ans[i]=-1\) за све \(i\in [1, Q]\).

Подзадаци

Тест примери су подељени у \(4\) подзадатка:

• [6 поена]: \(T[i]\leq 6\) и \(Z[i]\leq 6\) кадгод је \(X[i]=1\).
• [15 поена]: \(N, Q\leq 2\cdot 10^3\).
• [23 поена]: Сви су упити другог типа, то јест важи \(X[i]=2\) за све \(i \in [1, Q]\).
• [56 поена]: Нема додатних ограничења.

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

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

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

void Trening(int N, int* T, int Q, int* X, int* Y, int* Z, int* Ans);

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

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

• У првом реду бројеве \(N\) и \(Q\).
• У другом реду \(N\) бројева који представљају почетне вредности тајмера.
• У наредних \(Q\) редова по три броја, \(X[i], Y[i], Z[i]\) који описују упит.

Затим овај програм позива вашу функцију уз низ \(Ans=[-1, \ldots, -1]\) и штампа низ \(Ans\) који је вратила ваша функција.