Кирилл Евгеньевич, как обычно, опаздывает на первый урок... Кабинет, конечно, открыл Данила Сергеевич, но обида на своего учителя, который продолжает повторять свои ошибки, только накапливается. Нужно проучить Кирилла Евгеньевича!

Внезапно кому-то пришла идея покопаться в шкафу. Там оказалось $$$n$$$ брусков от разломанного креста, подаренного на Новый Год. Чтобы испугать и наказать виновника, нужно составить что-то страшное — невырожденный треугольник$$$^{\text{∗}}$$$ с огромным периметром!

Так как делать вручную это сложно, помоги нам понять, какого максимального периметра можно получить треугольник, или $$$-1$$$, если не получится составить ни один треугольник. Два бруска не могут образовывать одну сторону. То есть, например, при наличии брусков $$$1,1,2,2$$$ нельзя сделать треугольник со сторонами $$$2$$$, $$$2$$$ и $$$1+1$$$.

Вам дан набор из $$$n$$$ гирек, где $$$a_i$$$ — вес $$$i$$$-й гирьки. В магазине есть бесконечное количество товаров каждого натурального веса.

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

Это интерактивная задача

Представьте, что вы оказались в одной небезызвестной игре следователем. Вам предстоит разоблачить $$$n$$$ девиантов, которые совершили вопиющие преступления. У каждого андроида $$$i$$$ есть мера наказания $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i$$$ — целое) и параметр стресса $$$c_i$$$, изначально равный нулю. Так как времени у нас мало, вам предстоит провести параллельный допрос. Одним вопросом вы можете выкрикнуть во всеуслышанье (все не сознавшиеся девианты услышат ваше заявление) «$$$X$$$ ударов ножом! Ты действовал наверняка!». Каждый девиант воспринимает это высказывание на свой счет и начинает думать:

• Если $$$X \gt a_i$$$, девиант будет уверен, что вы не знаете, что он совершил преступление, а просто гадаете, поэтому после этого он перестанет реагировать на любые вопросы.
• Если $$$X \le a_i$$$, девиант получает $$$X$$$ единиц стресса, потому что уверен, что вы вот вот раскроете его грехи. То есть $$$c_i := c_i + X$$$ (значение $$$c_i$$$ увеличивается на $$$X$$$).

Когда девиант сознался, он выходит из комнаты допроса и не слышит никакие дальнейшие вопросы.

Ваша задача заключается в том, чтобы все девианты сознались, а также узнать их меры наказания. Если хотя бы один девиант не сознался, вы получите вердикт Wrong Answer даже если выведите правильные меры наказания. Также в некоторых подгруппах от вас не будет требоваться узнать меры наказаний, достаточно лишь добиться того, что все сознались.

В этой задаче вы можете делать вопросы двух типов:

• «$$$?$$$ $$$X$$$» ($$$1 \le X \le 10^9$$$). Вы совершаете обвинение с $$$X$$$ ударами.

  После очередного запроса интерактор возвращает следующие данные:

  В первой строке вводится число $$$m$$$ ($$$0 \le m \le n$$$), количество девиантов, которые хотят признаться.

  В следующих $$$m$$$ строках вводится по $$$n + 1$$$ числу: $$$j$$$ и $$$n$$$ чисел $$$b_i$$$, где $$$b_i = a_j + a_i$$$ для всех $$$j \neq i$$$. Для $$$i = j$$$, $$$b_i = 0$$$. Номер признающегося девианта и информация про подельников соответственно.

  Гарантируется, что каждый девиант, если признается, будет признаваться только один раз.

• «$$$!$$$ $$$a_1\ a_2\ \dots\ a_n$$$». Этот вопрос означает, что вы готовы сказать все меры наказаний и допрос на этом заканчивается и ваша программа должна немедленно завершиться. Если не все девианты сознались, вы получите вердикт Wrong answer. Все выведенные вами числа $$$a_i$$$ должны быть целыми, а также должно быть верно $$$0 \le a_i \le 10^9$$$ ($$$0$$$ обозначает, что вы не знаете меру наказания). Если хотя бы одно число нецелое или вне этого диапазона — вы получите вердикт Wrong answer. Также, если $$$t = 1$$$ и вы вывели хотя бы одну неверную меру наказания, вы получите вердикт Wrong answer.

  После совершения данного запроса, ваша программа должна завершиться.

Интерактор в данной задаче является неадаптивным

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для этого используйте:

• fflush(stdout) или cout.flush() в C++;
• sys.stdout.flush() в Python;
• смотрите документацию для других языков.

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

Известно, что Марк ходит со скоростью $$$a$$$ м/с, а самокат едет со скоростью $$$b$$$ м/с ($$$b \gt a$$$). Марк выбирает самокат следующим образом — приложение ему подсказывает круг с центром в локации Марка минимального радиуса, содержащий хотя бы один самокат, а также отмечает на этом круге все самокаты (в некоторых точках могут стоять сразу несколько самокатов). Марк выбирает из них такой, что суммарное время хождения до него и поездки на самокате до школы минимальное. Если идти пешком окажется не хуже, Марк пойдет пешком, иначе поедет на этом самокате.

Марку понравился его метод путешествий до школы, поэтому он решил использовать его не только для школы, но и для других точек города. А именно, в $$$q$$$ дней ему надо добраться до точки ($$$x_i, y_i$$$). Он живёт в точке ($$$0, 0$$$). В каждый из дней окружность и самокаты будут одни и те же (так как компании возвращают самокаты на место). Всегда будет $$$n$$$ самокатов на одинаковом расстоянии от ($$$0, 0$$$). Для каждого из дней выведите время в пути от дома Марка до очередной точки.

Обозначим за rad$$$(n)$$$ произведение всех различных простых делителей числа $$$n$$$. Например, rad$$$(504)$$$ = rad$$$(2^3 \cdot 3^2 \cdot 7)$$$ $$$= 2 \cdot 3 \cdot 7$$$ $$$=42$$$. Положим rad$$$(1) = 1$$$.

Условие этой задачи просто: у вас есть массив $$$a$$$ размера $$$n$$$. Вам дано $$$q$$$ запросов $$$[\ell;r]$$$, посчитать rad произведения чисел $$$a_\ell, a_{\ell + 1}, \dots, a_r$$$, то есть: $$$$$$\displaystyle\texttt{rad}\left(\prod_{i=\ell}^{r} a_i\right) = \texttt{rad}\left(a_\ell \times a_{\ell + 1} \times \dots \times a_r \right)$$$$$$ Так как это число может быть довольно большим, выведите его по модулю $$$10^9 + 7$$$.

Обратите внимание на низкое ограничение по времени. Решения на языке Python стоит засылать под PyPy 3-64.

Приветствуем начинающих воров! Сегодня вам предстоит ограбить кабинет номер $$$25$$$. В снаряжении мы вам дадим лишь небольшой рюкзак, потому что ценного в месте назначения не сильно много. Однако даже такие вещи могут пригодиться Штабу! Да, рюкзак, конечно, староват, но может вместить много полезного и нужного Штабу! Периодически вам будут поступать запросы от базы. Запросы могут быть таковыми:

1. + x. Вам велено подобрать и положить в рюкзак чокопай ценностью $$$x$$$ бурлей.
2. - x. Срочно нужно выкинуть из рюкзака любой чокопай ценностью $$$x$$$ бурлей, чтобы не попасться Кириллу Евгеньевичу. Штаб тщательно следит за наполнением вашего рюкзака, поэтому всегда нужно выкинуть чокопай, который присутствует в рюкзаке.
3. ? W. Владимир Евгеньевич близко, и он будет считать рюкзак подозрительным, если суммарно чокопаи в нём стоят больше $$$W$$$. База хочет узнать, какую максимальную стоимость чокопаев гипотетически можно оставить в рюкзаке, выкинув некоторые чокопаи. Чокопаи после запроса не выкидываются.

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

Марку стало интересно, сколько различных строк длины от $$$\ell$$$ до $$$r$$$ можно получить, если автомат при нажатии на вторую кнопку показывает $$$k$$$ единиц. Но так как автомат старый, а интерес у Марка большой, вам предстоит ответить на $$$q$$$ запросов вместо автомата.

Так как ответ на любой запрос Марка может быть очень большим, посчитайте его по модулю $$$998244353$$$

С незапамятных времен в прекрасный город $$$\mathbb{S}$$$ ездит делегация из нашего лицея для участия в одной небезызвестной олимпиаде. Давайте погрузимся в тот год, когда команда нашей школы впервые приехала в этот город. Тогда инфраструктура была не так развита, на улицах лежала интеллигенция, между частями города переправлялись на лодках. Однако путешествовать на лодках удовольствие не из дешевых, поэтому местным правительством было принято учредить постройку мостов между островами-частями города.

Так как построить мост так, чтобы он стоял навека, довольно сложно, мосты в городе $$$\mathbb{S}$$$ строят каждый год. В год номер $$$i$$$ с первого прибытия учеников лицея в данный город строится новый мост между островами $$$u_i$$$ и $$$v_i$$$. Некоторые мосты настолько производят впечатление, что они называются важными. Важным считается такой мост $$$v_i\leftrightarrow u_i$$$, что острова $$$u_i$$$ и $$$v_i$$$ станут несвязными при его удалении; иными словами, невозможно по любым мостам добраться от острова номер $$$u_i$$$ до $$$v_i$$$, не используя прямой мост между ними.

Так как со временем строятся все более величественные и красивые мосты, а старые неизбежно перестают становиться важными, правительству города $$$\mathbb{S}$$$ стало интересно, сколько лет тот или иной мост был важным. Так как правительство города $$$\mathbb{S}$$$ занимается в большинстве своем бюрократическими вопросами, выполнить эту задачу предстоит вам. Для каждого моста выведите количество лет, которое он будет важным, или $$$-1$$$, если он все равно останется таковым.

Правильная скобочная последовательность это строка, которая состоит только из символов «(» и «)», из которой возможно получить корректное арифметическое выражение, вставляя символы «+» и «1». Например, «», «(())» и «()()» являются правильными, а «)(» и «(()» не являются правильными скобочными последовательностями. Просто же скобочной последовательностью называется строка из символов «(» и «)».

Назовём правильностью скобочной последовательности максимальную длину её правильной скобочной подпоследовательности. Например, возьмем строку «()())((())()». Для неё правильными подпоследовательностями будут, к примеру, следующие: «$$$\color{red}{\underline{\color{red}{\text{()}}}}$$$())((())()», «$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$))((($$$\color{red}{\underline{\color{red}{\text{))}}}}$$$()», «$$$\color{red}{\underline{\color{red}{\text{()()}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{((())}}}}$$$($$$\color{red}{\underline{\color{red}{\text{)}}}}$$$», а также другие (но поля условия слишком малы, чтобы их всех перечислить). Как видно, подпоследовательностью является наша последовательность, из которой удалили ноль или больше элементов, а порядок оставшихся не поменялся. Для данной последовательности правильность будет равна $$$10$$$ (последняя из приведённых подпоследовательностей имеет такую длину).

Дано $$$n$$$ изначально пустых скобочных последовательностей. Приходят $$$q$$$ запросов двух видов:

• «$$$1 \ \ell \ r \ x$$$» — дописать к последовательностям на отрезке $$$[\ell, r]$$$ $$$|x|$$$ скобок. Если $$$x \gt 0$$$, то скобки открывающие, если $$$x \lt 0$$$ — закрывающие.
• «$$$2 \ \ell \ r$$$» — вывести сумму правильностей последовательностей на отрезке $$$[\ell, r]$$$.