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

Паруса закреплены $$$n$$$ узлами, каждый из которых может находиться в одном из трех состояний:

• wet — в воде, без крепления к мачте;
• ready — привязан к мачте, готов к использованию;
• и bound — плотно привязан и закреплен, чтобы не оторваться от сильного ветра.

Сейчас все узлы находятся в состоянии 'w'. За одно действие Моана может выбрать отрезок поряд идущих номеров узлов и

• перевести их все в состояние 'r';
• перевести их все в состояние 'b', если ни один из них не находится в состоянии 'w'.

Вам дана последовательность из $$$q$$$ действий, которые Моане надо выполнить, но для каждого действия известно только в какое состояние надо перевести какой-то отрезок узлов (то есть вся последовательность задается строкой из букв 'r' и 'b').

Определите количество возможных конфигураций узлов после выполнения всей последовательности действий. Две конфигурации называются различными, если найдется хотя бы один узел, который в них находится в различных состояниях. Поскольку ответ может быть слишком большой, выведите остаток от его деления на $$$10^9 + 7$$$.

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

За рифом находятся $$$n$$$ островов, между которыми можно перемещаться, используя двусторонние паромы местных туземцев с развитой инфраструктурой. Есть ровно $$$m$$$ маршрутов, $$$i$$$-й используется для поездки c острова $$$v_i$$$ на остров $$$u_i$$$ (и из $$$u_i$$$ в $$$v_i$$$) и стоит $$$w_i$$$ тугриков.

Моана знает, что Мауи собирается посетить все острова и расширить свой кругозор. Также Моана знает, что вождь каждого острова берет налог на его посещение (развитая инфраструктура требует тугриков). Налог посещения $$$i$$$-го острова составит $$$a_i$$$ тугриков.

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

Формально, для каждого $$$u \in [1, n]$$$ требуется посчитать $$$\min\limits_{v=1}^n 2 \mathtt{dist}(u, v) + a_v$$$, где $$$\mathtt{dist}(u, v)$$$ — минимальное количество тугриков, нужных для поездки с острова $$$u$$$ на остров $$$v$$$.

На острове Мотунуи выросла популяция петухов, и теперь петух Хей-Хей с сородичами ищут себе пропитание.

Как известно, петухи острова не отличаются умом и сообразительностью, а потому питаются камнями, причем каждый из камней характеризуется своей вкусностью $$$k_i$$$.

Сейчас $$$n$$$ петухов стоят на прямой, на которой находятся $$$m$$$ камней. Они собираются действовать по следующему алгоритму: определяют камень с максимальной вкусностью и идут к нему по прямой. Тот петух, который дойдет первым, мгновенно съедает самый вкусный камень, и все петухи начинают идти к следующему по вкусности. Если петухи подходят к одному и тому же камню одновременно, то камень съедает петух с меньшим номером.

Для каждого камня определите, какой петух его съест.

На острове Мотунуи много примитивных игр.

Сейчас Моана, Симеа и петух Хей-Хей собрались поиграть в островные Крестики-Нолики-Квадратики. Первой ходит Моана «крестиком», вторым ходит Хей-Хей «ноликом», третьей ходит Симеа «квадратиком».

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

Процесс взаимодействия с интерактором заключается в выполнении трех раундов по три хода. В каждом раунде

1. Первый ход делает интерактор, выводя строку в формате «X $$$r_i$$$ $$$c_i$$$», где $$$r_i$$$, $$$c_i$$$ — позиция хода «крестика».
2. Второй ход делает игрок, вводя строку в формате «0 $$$r_i$$$ $$$c_i$$$», где $$$r_i$$$, $$$c_i$$$ — позиция хода «нолика». Если ход корректен, интерактор выведет на отдельной строке «OK». Обратите внимание, что символ, который вашей программе надо вывести — это ноль, а не заглавная буква 'O'.
3. Третий ход делает интерактор, вводя строку в формате «# $$$r_i$$$ $$$c_i$$$», где $$$r_i$$$, $$$c_i$$$ — позиция хода «квадратика».

Если какой-то из сделанных вашей программой ходов будет некорректен, интерактор выведет «FAIL» и завершится с вердиктом WA (Wrong Answer). Если кто-то из противников победит, то интерактор сразу же завершится с вердиктом WA.

Если же ваша программа сможет помешать кому-либо из противников выиграть, интерактор завершится с вердиктом OK. Во избежание получения вердиктов TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded) ваша программа также должна завершаться с кодом возврата $$$0$$$ после успешного ответа интерактора на последний запрос.

Также обратите внимание, что вывод каждого запроса должен завершаться переводом строки (символ '{\}n') и сбросом буфера вывода (sys.stdout.flush() в Python, cout.flush() в C++, System.out.flush() в Java и аналогичными методами в других языках).

Крюк Мауи опять сломался. В этот раз он далековато от Те Фити, чтобы та помогла ему его починить. Однако он знает одно заклинание, которое может ему помочь (не зря же он полубог).

Это заклинание он всегда носит с собой — оно написано на небольшом клочке его одежды. Но теперь он жалеет, что у него нет тату с этим заклинанием — за время плаваний надпись размыло, и некоторые буквы стали менее узнаваемы. Мауи попытался разобрать их, и в итоге получил строку $$$s$$$, но что-то не сходится.

Он точно помнит, что в верном заклинании нет подстрок, являющихся палиндромами, то есть читающихся одинаково слева направо и справа налево. Также он уверен, что получившаяся у него строка $$$s$$$ не сильно отличается от изначального заклинания.

Помогите ему определить минимальное число букв, которое необходимо заменить в $$$s$$$, чтобы в ней не осталось подстрок-палиндромов. Напомним, что подстрока — это (в данном случае, непустая) последовательность подряд идущих символов строки.

Богиня Те Фити благосклонна к людям, но периодически проверяет использование ее ресурсов и просит у вождя Туи отчет.

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

Испокон веков этот показатель рассчитывается так: у вождя есть количество кокосов $$$a_i$$$, собранное соплеменниками за каждый из $$$n$$$ дней промежутка времени, тогда успешность использования ресурсов равна $$$$$$P = \sum\limits_{i = 1}^{n} (a_i \bmod t)$$$$$$ для некоторого $$$t \le \min(a)$$$.

Очевидно, что вождю выгодно максимизировать $$$P$$$ для увеличения благосклонности богини, при этом $$$t$$$ он может выбрать сам. Помогите ему определить оптимальное значение $$$t$$$ для отчета и соответствующий ему показатель $$$P$$$.

Как известно, океан опасен не только возможными штормами, но и множеством быстрых течений, которые могут унести лодку очень далеко от ожидаемого конца маршрута. Моана и Мауи прекрасно об этом знают, более того, они знают, что всего в океане $$$m$$$ таких течений между $$$n$$$ различными точками.

Течение номер $$$i$$$ соединяет точки $$$u_i$$$ и $$$v_i$$$, и обладает мощностью $$$w_i$$$. В отличие от нашего мира, течения периодически меняют свое направление на противоположное, так что будем считать их двунаправленными.

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

И все было бы просто, если бы на этом все закончилось, но поскольку надо торопиться, герои могут попросить богов океана изменить мощность любого течения на произвольное целое число от $$$1$$$ до $$$10^9$$$.

Определите для каждого течения $$$f$$$ максимальную мощность $$$p_f$$$ такую, что если сделать мощность $$$f$$$ равной $$$p_f$$$, а остальные течения оставить без изменений, будет существовать искомый набор течений, включающий в себя $$$f$$$.

На острове Мотунуи верят в богиню Те Фити, которая обожает медианы и целые числа.

В честь нее придумали игру:

• Выбирается $$$n$$$ попарно различных целых чисел, $$$i$$$-е число равно $$$a_i$$$.
• Создается пустое множество чисел $$$m$$$.
• Числа по одному в произвольном порядке добавляются в $$$m$$$ так, чтобы на любом шаге после добавления очередного числа медиана элементов $$$m$$$ оставалась целым числом.

В данной задаче медиана определяется следующим образом. Упорядочим элементы $$$m$$$ по возрастанию. Тогда если размер множества нечетный, то медиана равна центральному элементу полученной последовательности, иначе — полусумме двух центральных чисел.

Отправляясь в приключение, Моана оставила Симее $$$n$$$ попарно различных чисел. Помогите Симее заполнить множество $$$m$$$ целиком до возвращения Моаны.

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

Всего в языке есть n букв, а звуки, соответствующие каждой из них, мы обозначим числами a₁, ..., a_n. Разным буквам может соответствовать один и тот же звук. Слов в языке ровно 2ⁿ - 1, и каждое из них является произвольной подпоследовательностью этих n букв (порядок букв в слове совпадает с порядком в алфавите).

Обозначим за s_i i-е в лексикографическом порядке звучание слова. То есть возьмем все слова языка, выпишем последовательность звуков для каждого из них, и упорядочим эти последовательности по возрастанию. Здесь мы считаем, что слово x меньше слова y, если либо последовательность звуков x — префикс последовательности звуков y, либо первый отличающийся звук в x меньше, чем соответствующий звук в y.

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

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

Однако однажды случилась катастрофа: богиня Те Фити потеряла свое сердце, все магические пути исчезли, а острова остались изолированными друг от друга. Вождь Туи, отчаянно желая восстановить порядок, собрал лучших шаманов. Маги предложили древний ритуал восстановления, согласно которому можно было создавать новые островки — магические узлы. Всего было создано $$$k$$$ новых островков.

Из каждого нового острова $$$n+1, n+2, \ldots, n+k$$$ можно создать какие-то пути на исходные $$$n$$$ островов. Более точно, для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ известны параметры $$$l_i$$$, $$$r_i$$$ и $$$c_i$$$, означающие, что, потратив $$$c_i$$$ энергии, можно создать путь с острова $$$n + i$$$ на остров $$$j$$$, если $$$l_i \le j \le r_i$$$. Разумеется, с каждого нового острова можно провести несколько путей, но за каждый придется отдать $$$c_i$$$ энергии.

Определите, удастся ли с помощью этих путей соединить все $$$n + k$$$ островов в единую сеть, чтобы от каждого острова можно было добраться до любого другого. И, если можно, определите минимальное количество энергии, необходимое для этого.

Если вы справитесь, древняя Полинезия будет спасена, а былая магия вернет островам процветание. Но если вы потерпите неудачу — острова останутся изолированными, и мир навсегда погрузится в хаос. Все зависит от вас!

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

Оба выбрали себе по одной фигуре, а также они нарисовали поле размером $$$n \times m$$$ на песке. Так как они играли в импровизированные первые шахматы, они выбирали ровно одну из двух фигур: ладью или слона (причем не обязательно, чтобы Мауи и Моана выбрали разные фигуры), которые ходят по стандартным шахматным правилам (ладья ходит по горизонтали или вертикали на произвольное расстояние, а слон — так же по диагонали).

Победителем считается тот, кто сможет побить фигуру противника. Если спустя $$$10^{100}$$$ ходов никто не сможет сделать этого, игра признается ничейной.

В какой-то момент на доске сложилась следующая ситуация: фигура Мауи находится на клетке с координатами $$$(x_1, y_1)$$$, а фигура Моаны — на клетке $$$(x_2, y_2)$$$ (нумерация строк и столбцов начинается с $$$1$$$). Сейчас ходит Мауи. Понимая, что Моана действует хитро и стратегически, Мауи просит вас помочь оценить шансы на победу: кто выиграет, если оба будут играть оптимально?

Моана отправилась в путешествие на своем каноэ, чтобы спасти свой остров. Для этого ей нужно собрать специальные магические ракушки, расположенные на $$$2^n$$$ островах. Количество магических ракушек на $$$i$$$-м острове равно $$$a_i$$$, причем острова нумеруются с нуля и до $$$2^n - 1$$$.

Моана хочет собрать как можно больше ракушек как можно быстрее, поэтому хочет посетить два острова и собрать все ракушки на них. Но может случиться такое, что богиня огня Те Ка будет препятствовать ей в ее приключении, и Моана сможет посетить два острова с номерами $$$i$$$ и $$$j$$$ только если $$$i\ |\ j \leq k$$$, где $$$|$$$ означает операцию побитового «или».

Величина $$$k$$$ заранее неизвестна, поэтому помогите Моане для каждого $$$k$$$ от $$$1$$$ до $$$2^n - 1$$$ найти $$$\max\limits_{i\,|\,j \le k} a_i + a_j$$$. Еще раз обратим внимание, что номера островов начинаются с нуля, иными словами, их двоичные записи идут от $$$n$$$ нулей до $$$n$$$ единиц.