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

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

«Ну вот, — подумал Вася, — опять главному герою подарили что-то, чего в реальной жизни никто не дарит. Сейчас, видимо, ещё какое-нибудь свойство припишут этой строке, которое нужно будет вычислить.»

Красотой строки из скобок называется количество её циклических сдвигов, которые являются правильной скобочной последовательностью.

«Вау, как оригинально, — скептически пробурчал себе под нос Вася, — ни разу не видел, чтобы в задачах по программированию требовалось вычислять красоту целого объекта. Ну всё, сейчас мне зачем-то будет надо будет вычислять эту величину на подотрезках и обрабатывать какие-то запросы изменения строки.»

И в самом деле. Для запросов вида $$$(l, r)$$$ требовалось определить красоту подотрезка строки $$$s$$$ с $$$l$$$ по $$$r$$$ (включительно). Помимо этого, поступали запросы изменения определённых символов строки $$$s$$$.

«Замечательно, — разочарованно вздохнул Вася, — очередная скучная задача на структуры данных, не хочу её решать. О, а ведь можно дать эту задачу на какую-нибудь олимпиаду!»

Так Вася и поступил. Докажите Васе, что задача совсем не скучная и решите её.

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

Чтобы не быть голословным, Иванушка пообещал продемонстрировать окружающим свои навыки при помощи случайного рисунка. Рисунок представляет собой клетчатое поле с $$$n$$$ строками и $$$m$$$ столбцами, каждая клетка которого покрашена в белый или чёрный цвет. Иванушка считает, что рисунок случайный, если для любой клетки верно, что среди ее соседей по стороне не более одной клетки такого же цвета, что и она.

Его братья быстро выяснили, что задумал Иванушка. Они долго пытались объяснить ему, что он, дурачок, все ещё плохо понимает, что такое случайность. Но Иванушка так и не поверил им, поэтому они попросили помощи у вас. Они хотят найти количество различных случайных по мнению Иванушки рисунков. Два рисунка называются различными если существует клетка, которая покрашена в разные цвета на этих рисунках. Так как это число может быть слишком большим, найдите остаток от деления его на $$$10^9 + 7$$$.

В некоторой стране есть $$$n$$$ городов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Столица этой страны расположена в городе с номером $$$1$$$. Некоторые пары городов в этой стране соединены дорогами с односторонним движением, при этом для каждой пары городов $$$u$$$ и $$$v$$$ есть не более одной дороги, ведущей из города $$$u$$$ в город $$$v$$$, однако наличие дороги из города $$$u$$$ в город $$$v$$$ не запрещает существование дороги из города $$$v$$$ в город $$$u$$$. Для каждой дороги известно, груз какого максимального веса можно по ней перевозить. Требуется для каждого города определить максимальный вес груза, который можно доставить из него в столицу.

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

Бак с кипятком находится левее $$$1$$$-го места за дверью. Поскольку баком одновременно может пользоваться не более одного человека, люди стоящие у бака образуют очередь в порядке, в котором они подошли к баку. Как только человек заканчивает наливать кипяток, следующий за ним в очереди человек (если такой есть) начинает наливать кипяток себе. Каждый человек наливает себе кипяток ровно $$$p$$$ минут.

Люди не любят просто так стоять в очереди. После того, как человек на месте с номером $$$i$$$ захочет сходить за кипятком, в начале каждой минуты (включая $$$t_i$$$-ю минуту) он будет оценивать размер очереди, в которую он попадёт, если отправится за кипятком прямо сейчас, а именно он посмотрит на все места с номерами от $$$1$$$ до $$$i - 1$$$. Если хотя бы одно из этих мест пусто, то есть в очереди возле бака есть люди с номерами, меньшими $$$i$$$, человек с номером $$$i$$$ решит, что очередь слишком большая и останется на своём месте до начала следующей минуты. В противном случае человек с номером $$$i$$$ тут же встанет со своего места и приготовится идти за кипятком. Однако если человек с номером $$$j$$$ ($$$j \lt i$$$) также решит отправиться за кипятком в этот же момент, человек с номером $$$i$$$ это увидит, сядет обратно на своё место и снова будет ждать начала следующей минуты. Таким образом, в начале каждой минуты не более одного человека отправится за кипятком. Обратите внимание, что конструкция вагона такова, что люди видят только места перед собой, но не видят бак и очередь перед ним, поэтому могут принимать решения только исходя из наличия людей на местах перед ними.

Временем перемещения людей по вагону можно принебречь. Например, если человек проголодался в начале $$$t$$$-й минуты, и в этот момент очередь к баку была пуста, то он окажется у бака в начале $$$t$$$-й минуты, закончит наливать воду в конце минуты с номером $$$t + p - 1$$$, и в начале минуты с номером $$$t + p$$$ уже будет сидеть на своём месте.

Для каждого человека определите, на какой минуте он вернётся на своё место с кипятком для лапши.

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

Канал, по которому Алиса и Боб обмениваются информацией, прослушивает Ева. Алиса может прислать Бобу некоторое множество $$$A$$$ целых неотрицательных чисел. Если для некоторого достаточно большого $$$t \geq 0$$$ все числа $$$0, 1, 2, \ldots, t$$$ лежат в множестве $$$A$$$, то это повышает подозрения Евы о том, что переданная информация была зашифрована перед отправкой. Поэтому передавая некоторое множество $$$A$$$ целых чисел, Алиса хочет минимизировать минимальное целое неотрицательное число, которое не принадлежит множеству $$$A$$$, назовем это число тревожностью Евы.

Для того, чтобы шифровать информацию, Алиса с Бобом придумали такую простую схему: пусть Алиса хочет передать Бобу множество $$$A = \{a_1, a_2, \ldots, a_n\}$$$ целых неотрицательных чисел. Алиса может выбрать некоторое целое число $$$x$$$ ($$$0 \leq x \leq k$$$) и передать Бобу множество $$$\{a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x\}$$$, где значок $$$\oplus$$$ обозначает операцию взятия побитового исключающего ИЛИ двух чисел. При этом о значении числа $$$k$$$ они договорились заранее. Таким образом, Алиса хочет сделать свой выбор так, чтобы тревожность Евы, а именно минимальное целое неотрицательное число, не принадлежащее множеству $$$\{a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x\}$$$, было как можно меньше.

Алиса еще не выбрала, какое конкретно множество $$$A$$$ она хочет передать Бобу. Изначально она хочет передать Бобу пустое множество $$$A = \varnothing$$$. После этого Алиса $$$q$$$ раз принимает решение о том, что хочет добавить или удалить из текущего множества $$$A$$$ некоторое число. И после каждой такой операции она хотела бы знать минимальную возможную тревожность Евы, которой Алиса может добиться, если она захочет передать Бобу текущее множество. Помогите ей и напишите программу, которая будет вычислять это значение.

Наверняка вы знаете много математических фокусов. В этой задаче вам предлагается продемонстрировать свои умения в одном из таких фокусов.

У вас есть массив из различных натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. Помимо этого, перед вами стоит стол, на котором лежат $$$10^{18}$$$ карточек, на которых записаны все натуральные числа от $$$1$$$ до $$$10^{18}$$$, каждое ровно на одной карточке.

Вы можете подойти к столу и взять карточку с числом $$$x$$$. После этого вы можете выбрать ровно одно любое число $$$a_i$$$ в вашем массиве и поменять его либо на $$$\frac{a_i}{x}$$$, либо на $$$a_i \cdot x$$$. При этом делить $$$a_i$$$ на $$$x$$$ разрешается только в случае, если $$$a_i$$$ делится на $$$x$$$. Таким образом все числа в вашем массиве должны оставаться натуральными. После выполнения данной операции использованная карточка выкидывается и больше никогда не возвращается на стол.

Вы хотите несколько раз взять со стола карточки и выполнить операции таким образом, чтобы в итоге все числа массива оказались равными. Определите, какое минимальное количество карточек потребуется взять со стола, чтобы совершить этот фокус. Гарантируется, что хотя бы один способ сделать все числа в массиве равными существует.

В ожидании новых приключений Башмачок захотел совершить доброе дело. Посовещавшись с Картой и Рюкзаком, он решил подарить Даше связный граф. Даша не любит, когда в графе присутствуют петли или кратные ребра, и Башмачок прекрасно об этом знает. После долгих поисков Башмачок выбрал $$$t$$$ вариантов графа, которые могли бы понравиться Даше, но, к сожалению, все его планы решил испортить лис Жулик.

Жулик узнал, что Даша недавно научилась считать до $$$3$$$, и у него родилась идея. Он хочет совершить кражу так, чтобы Даша не заметила пропажи, поэтому он решил украсть непустой набор вершин такой, что если удалить выбранные вершины и связанные с ними рёбра из графа, то для любой из оставшихся вершин будет верно, что ее степень (число смежных рёбер) будет иметь такой же остаток от деления на $$$3$$$, что и степень до удаления рёбер. Также он понял, что будет слишком подозрительно, если он украдет все вершины, поэтому он решил воздержаться от такой соблазнительной затеи.

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

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

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

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

У мальчика Коли есть черепашка и поле $$$2 \times n$$$. Строки поля пронумерованы от $$$1$$$ до $$$2$$$ сверху вниз, а столбцы от $$$1$$$ до $$$n$$$ слева направо.

Предположим, что в каждой клетке есть съедобный лист салата, энергетическая ценность которого в клетке поля в строке $$$i$$$ и столбце $$$j$$$ составляет $$$a_{i,j}$$$. Черепашка изначально находится в верхней левой клетке и хочет попасть в правую нижнюю. Черепашка умеет двигаться только вниз и вправо, а среди всех возможных путей она выберет тот, который максимизирует суммарную энергетическую ценность листьев салата, через которые она проходит (если таких путей несколько, она выберет произвольный из них).

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