Вы наконец-то осуществили свою давнюю мечту и оказались в Мэйбилэнде, но радоваться пока что рано. Теперь вам предстоит быстро адаптироваться к новому месту и действовать согласно установленным в этом волшебном городе порядкам, иначе вас быстро раскусят местные жители. Первое, с чем вам предстоит разобраться — необычная система передвижения.

Мэйбилэнд представляет собой $$$n$$$ замков, пронумерованных от $$$1$$$ до $$$n$$$ и соединенных $$$n - 1$$$ тропинкой, при этом гарантируется, что по тропинкам можно добраться от любого замка до любого другого замка. Проще говоря, Мейбилэнд является деревом.

В момент времени $$$1$$$ вы находитесь в замке с номером $$$1$$$. За одну мэйби-минуту вы можете переместиться из текущего замка в любой другой замок, с которым текущий соединен тропинкой. Обратите внимание, что перемещение обязательно должно произойти, то есть, остаться в том же замке в следующий момент времени вы не можете.

Также вы знаете, что $$$m$$$ раз случится чудо и в замке с номером $$$v_i$$$ в момент времени $$$t_i$$$ окажется вкусный леденец, соответственно, если в момент $$$t_i$$$ вы оказались в замке $$$v_i$$$, то вы можете забрать вкусный леденец с собой. Учтите, что по истечении момента времени $$$t_i$$$ вкусный леденец исчезает, и если вы не успели его забрать, то у вас больше не будет возможности взять его снова.

Так как телепортация в Мэйбилэнд случается один раз в жизни, вы хотите получить как можно больше вкусных леденцов. Скажите, какое максимальное количество вкусных леденцов вы можете собрать после прогулки по Мэйбилэнду.

В лаборантской 325 есть $$$n$$$ шкафов. На них возложена большая задача — хранить памятные фото и конфеты олимпиадников. Но есть проблема: у любого хранилища есть предел, а у шкафов ножки, поэтому как только в шкафу набирается определённое число предметов $$$lim_i$$$, ножки ломаются а шкаф падает. Всё бы ничего если бы за раз мог упасть только один шкаф, но ведь они стоят друг рядом с другом и каждый имеет свою высоту $$$h_i$$$, поэтому если падает шкаф на позиции $$$i$$$, то упадут все шкафы на отрезке $$$[i;i+h_i-1]$$$, они в свою очередь повалят какие-то свои отрезки.

Вы могли бы спасти ситуацию в лаборантской, но для этого нужна поддержка фонда Спидвагона. Поэтому остаётся лишь следить за ситуацией. По сути вам необходимо обрабатывать $$$q$$$ запросов, которые бывают двух типов:

• $$$1 \; l \; r \; x$$$ — на шкафы с номерами от $$$l$$$ до $$$r$$$ включительно положили $$$x$$$ предметов. Предметы могут поставить и на сломанные шкафы.
• $$$2 \; l \; r$$$ — узнать сколько осталось целых шкафов на отрезке от $$$l$$$ до $$$r$$$ включительно.

Пеппино — владелец маленькой пиццерии возле Пицца-башни. Его ресторан весь погряз в долгах, и чтобы выйти из затруднительного положения, он пытается придумать новый рецепт пиццы, который бы привлёк много новых посетителей и окупил затраты на ресторан.

Пицца по новому рецепту состоит из $$$n$$$ кусков. У каждого куска разный состав: изначально $$$i$$$-й кусок имеет вкус $$$a_i$$$, и он уменьшается на $$$b_i$$$ каждую минуту, при этом гарантируется, что $$$a_i \ge n \cdot b_i$$$. За одну минуту можно съесть один кусок. Пеппино интересно, какого максимального суммарного вкуса можно достичь, если есть их в оптимальном порядке.

Вы уже с другом уже третий день играете в Minecraft, возводя грандиозные здания, путешествуя между вселенными и ни разу не выходя из дома. Чтобы сделать игру еще более увлекательной, вы решили довериться схеме из интернета и построить портал в MysteryUniverse503, но что-то пошло не по плану, и вы с другом телепортируетесь в SecretWorld404.

Известно, что вторгаться на чужую территорию без спроса - плохо, поэтому либо вы, либо ваш друг понесут серьезное наказание. Чтобы определить, кто из вас останется играть, а кто с позором уйдет на новую карту, вы решили сыграть в игру, которую нашли в зачарованной книге.

Правила игры гласят, что игра ведется на слабо-связном ориентированном$$$^{*}$$$ ациклическом графе из $$$n$$$ вершин, в каждой из которых находится либо сундук, либо верстак, и $$$m$$$ рёбер. Вы с другом будете ходить по очереди, вы ходите первым.

Во время хода нужно выбрать одну из вершин, в которой лежит сундук, и число $$$k$$$, после чего поменять предмет на противоположный (сундук на верстак или верстак на сундук) во всех вершинах, до которых от выбранной можно добраться за $$$\le k$$$ ходов (включая выбранную). Если оказывается так, что во всех вершинах графа находится верстак, то игрок, который сейчас должен делать ход ход, проигрывает.

Требуется определить, кто станет победителем и останется играть в SecretWorld404, если вы с другом играете оптимально.

$$$^{*}$$$Слабо-связный ориентированный граф - ориентированный граф, который станет связным, если убрать направление ребер.