Задан массив \(d_1, d_2, \dots, d_n\), состоящий из \(n\) целых чисел.

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

Пусть сумма элементов первой части равна \(sum_1\), сумма элементов второй части равна \(sum_2\) и сумма элементов третьей части равна \(sum_3\). Среди всех возможных разбиений массива вам нужно выбрать такое, что \(sum_1 = sum_3\) и \(sum_1\) является максимально возможной.

Более формально, если первая часть массива содержит \(a\) элементов, вторая часть массива содержит \(b\) элементов и третья часть массива содержит \(c\) элементов, тогда:

\(\)sum_1 = \sum\limits_{1 \le i \le a}d_i,\(\) \(\)sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,\(\) \(\)sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.\(\)

Сумма пустого массива равна \(0\).

Ваша задача найти такое разбиение массива, что \(sum_1 = sum_3\) и \(sum_1\) является максимально возможной.

Мальчик Геральд учится в школе, и она находится довольно далеко от его дома. Поэтому ему приходится ежедневно ездить туда на автобусах. Путь от дома до школы представляет собой отрезок прямой, на котором расположено ровно n + 1 остановок. Все они пронумерованы целыми числами от 0 до n в порядке их следования начиная от дома Геральда. Остановка у дома имеет номер 0, а остановка у школы — номер n.

Между домом и школой ездят m автобусов: i-ый автобус ездит от остановки s_i до остановки t_i (s_i < t_i), проезжая через все промежуточные остановки в порядке их следования. При этом Геральд не дурак, и не будет выходить из автобуса, пока на нем еще можно ехать в сторону школы — очевидно, что это не имеет смысла. То есть Геральд может сесть на i-ый автобус на любой остановке с номером от s_i до t_i - 1 включительно, а выйти из i-го автобуса он может только на остановке t_i.

Геральд не может идти между остановками пешком, а также не может перемещаться в сторону от школы к дому.

Геральд хочет узнать, сколько у него способов доехать от дома до школы. Сообщите ему это число. Два способа считаются различными, если какой-то участок между остановками Геральд едет на разных автобусах. Поскольку число способов может быть слишком большим, сообщите остаток этого числа от деления на 1000000007 (10⁹ + 7).

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

Наташа собирается полететь на Марс. Наконец Наташа села в ракету. Летит она, летит. Скучно как-то. Побыстрее бы уже на Марс прилететь! Решила она занять себя чем-то. И ничего интересней она не придумала, как считать, какое расстояние осталось ей преодолеть до красной планеты.

Пусть расстояние до Марса равно \(x\). К сожалению, Наташа не знает \(x\). Зато известно, что \(1 \le x \le m\), где число \(m\) Наташа знает. Кроме того, \(x\) и \(m\) — целые положительные числа.

Наташа может задавать ракете вопросы. Каждый вопрос — это целое число \(y\) (\(1 \le y \le m\)). Правильный ответ — это \(-1\), если \(x<y\), \(0\), если \(x=y\) и \(1\), если \(x>y\). Но ракета сломалась — она не всегда отвечает правду. А именно: пусть правильный ответ на текущий вопрос равен \(t\), тогда, если ракета отвечает на этот вопрос правду, то она ответит \(t\), в противном случае — ответит \(-t\).

Кроме того, у ракеты есть последовательность \(p\) длины \(n\). Каждый её элемент — это \(0\) или \(1\). Ракета обрабатывает эту последовательность циклически по порядку, то есть \(1\)-й элемент, \(2\)-й, \(3\)-й, \(\ldots\), \((n-1)\)-й, \(n\)-й, \(1\)-й, \(2\)-й, \(3\)-й, \(\ldots\), \((n-1)\)-й, \(n\)-й, \(\ldots\). Если текущий элемент равен \(1\), то ракета отвечает правду, если \(0\) — неправду. Наташа не знает последовательность \(p\), но знает её длину — \(n\).

Вы можете задать ракете не более \(60\) вопросов.

Помогите Наташе узнать расстояние до Марса. Считайте, что, пока Наташа задаёт вопросы, расстояние до Марса не меняется.

Ваше решение не будет засчитано, если оно не получит ответ \(0\) от ракеты (даже если расстояние до Марса однозначно определяется уже полученными ответами ракеты).

Вы можете задать ракете не более \(60\) вопросов.

Чтобы задать вопрос, выведите число \(y\) (\(1\le y\le m\)) и перевод строки, затем сделайте операцию flush и прочитайте ответ ракеты на вопрос.

Если программа прочитает \(0\), то расстояние правильное и нужно немедленно завершить программу (например, вызовом exit(0)). Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Если в какой-то момент ваша программа считывает \(-2\) как ответ, она должна немедленно завершиться (например, вызовом exit(0)). Вы получите вердикт «Неправильный ответ», и это будет означать, что запрос некорректен или количество запросов превышает \(60\). Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Если запрос вашей программы не будет корректным целым числом между \(-2^{31}\) и \(2^{31}-1\) (включительно) без лидирующих нулей, то вы можете получить любой вердикт.

Ваше решение получит вердикт «Решение зависло», если вы не будете ничего выводить или забудете сделать операцию flush после вывода вопроса или ответа.

Чтобы выполнить операцию flush, можете использовать (сразу после вывода числа и перевода строки):

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

Взломы

Используйте следующий формат для взломов:

В первой строке введите \(3\) целых числа \(m,n,x\) (\(1\le x\le m\le 10^9\), \(1\le n\le 30\)) — максимальное расстояние до Марса, количество элементов последовательности \(p\) и текущее расстояние до Марса.

Во второй строке введите \(n\) чисел, каждое из которых равно \(0\) или \(1\) — последовательность \(p\).

У взламываемого решения не будет доступа к числу \(x\) и последовательности \(p\).

Звезда — это фигура на клетчатом поле следующего вида: символ звездочка '*' в центре фигуры и четыре луча (влево, вправо, вверх и вниз) одинаковой положительной длины. Размером звезды является длина ее лучей. Размер звезды должен быть строго положительным (то есть лучи длины \(0\) недопустимы).

Пусть пустые клетки обозначены как '.'. Тогда, например, следующие фигуры являются звездами:

Левая фигура — звезда размера \(1\), средняя фигура — звезда размера \(2\) и правая фигура — звезда размера \(3\).

Задано прямоугольное поле размера \(n \times m\), состоящее из звездочек '*' и точек '.'. Строки пронумерованы от \(1\) до \(n\), столбцы пронумерованы от \(1\) до \(m\). Ваша задача — нарисовать это поле при помощи любого количества звезд или понять, что это невозможно сделать. Звезды могут пересекаться, вкладываться и даже совпадать друг с другом. Количество звезд в ответе не может превышать \(n \cdot m\). Каждая из звезд должна находиться строго внутри поля. Вы можете использовать звёзды как одинаковых так и различных размеров.

В этой задаче нет необходимости минимизировать количество звезд. Необходимо найти любой способ нарисовать заданное поле при помощи не более, чем \(n \cdot m\) звезд.

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

Имур Ихаков организует клуб по шляпе. На клуб пришло принять участие n человек, где n чётно. Имур усадил их всех в круг и провёл жеребьевку, чтобы разбить ребят на пары, но что-то пошло не так. Участники пронумерованы так, что участники i и i + 1 (1 ≤ i ≤ n - 1) сидят рядом, а также участники n и 1 сидят рядом. Каждому был выдан листочек с числом так, что у ребят, сидящих рядом, эти числа отличаются ровно на единицу. Предполагалось, что игроки с одинаковыми числами образуют пару, но оказалось, что не все числа встречались ровно дважды.

Как известно, удобнее всего объяснять слова партнёру, когда он сидит напротив. Участники с номерами i и сидят напротив друг друга. Имуру интересно, есть ли люди, сидящие напротив друг друга и имеющие одинаковые числа на своих листочках. Помогите ему найти такую пару людей, если она есть.

Вы можете задавать вопросы вида «какое число написано на листочке у школьника i?». Ваша цель — выяснить, есть ли требуемая пара, сделав не более 60 вопросов.

Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать \(n\) экзаменов.

Для каждого экзамена \(i\) известны два дня: \(a_i\) — день основной сдачи экзамена, \(b_i\) — день пересдачи (\(a_i < b_i\)). В один день Поликарп может сдавать не более одного экзамена. Для каждого экзамена Поликарп самостоятельно выбирает, в какой из двух дней его сдать. Необходимо сдать все \(n\) экзаменов.

Поликарп хочет сдать сессию как можно быстрее. Выведите минимальный номер дня, в который Поликарп сможет сдать все \(n\) экзаменов, либо выведите -1, если сдать сессию полностью невозможно.

У Боба есть простой неориентированный связный граф (без кратных ребер и петель). Он хочет узнать, является ли его граф двудольным (то есть вы можете покрасить все вершины графа в два цвета, чтобы не было ребра, соединяющего две вершины одного цвета) или нет. Поскольку он не очень хорошо разбирается в программировании, он попросил Алису о помощи. Он не хочет показывать свой граф Алисе, но он согласился, что Алиса может задавать ему вопросы о графе.

Единственный вопрос, который может задать Алиса, заключается в следующем: она дает Бобу \(s\) — подмножество вершин исходного графа, а он отвечает ей, сколько есть ребер в графе, которые соединяют две вершины в \(s\). Поскольку он не хочет, чтобы Алиса задавала слишком много вопросов, он разрешает ей задать не более \(20000\) вопросов. Кроме того, он подозревает, что Алиса может вводить ложные сообщения в их канал связи, поэтому, когда Алиса наконец сообщит ему, является ли граф двудольным или нет, ей также необходимо предоставить доказательство — или само разделение, или цикл нечетной длины.

Ваша задача — помочь Алисе задавать запросы и проверить, является ли граф двудольным.

Сначала считайте одно целое число \(n\) (\(1\leq n\leq 600\)) — количество вершин в графе Боба.

Чтобы сделать запрос, выведите две строки. Первая в формате «? k» (\(1 \leq k \leq n\)), где \(k\) — количество вершин в запросе. Вторая строка должна содержать \(k\) различных чисел \(s_1, s_2, \dots, s_k\) (\(1 \leq s_i \leq n\)) — вершины в запросе.

После каждого запроса нужно считать одно целое число \(m\) (\(0 \leq m \leq \frac{n(n-1)}{2}\)) — количество ребер, которые соединяют вершины в множестве \(\{s_i\}\).

Вы не можете задать более \(20000\) запросов.

Если \(m = -1\), то это значит, что вы задали больше вопросов, чем можно, или то, что вы вывели некорректный запрос. Ваша программа должна немедленно завершиться (например, вызывая функцию exit(0)). Вы получите вердикт Wrong Answer; это значит, что вы задали слишком много вопросов, или то, что вы задали некорректный запрос. Если вы это проигнорируете, вы можете получить любой другой вердикт, так как вы будете продолжать считывать из закрытого потока.

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

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

Когда вы уже знаете ответ, вам нужно его вывести.

Формат вывода зависит от того, является ли граф двудольным, или нет.

Если граф двудольный, выведите две строки. Первая строка должна содержать букву «Y» (которая значит «YES»), после нее должен идти пробел и одно целое число \(s\) (\(0 \leq s \leq n\)) — количество вершин в первой доли графа. Вторая строка должна содержать \(s\) целых чисел \(a_1, a_2, \dots, a_s\) — вершины, принадлежащие первой доли. Все \(a_i\) должны быть различны, и все ребра в главном графе должны иметь только один конец в \(\{a_i\}\).

Если граф не является двудольным, выведите две строки. Первая строка должна содержать букву «N» (которая значит «NO»), после нее должен идти пробел и одно целое число \(l\) (\(3 \leq l \leq n\)) — длина простого цикла нечетной длины. Вторая строка должна содержать \(l\) целых чисел \(c_1, c_2, \dots, c_l\) — вершины цикла. Должно выполнятся условие, что для любого \(1 \leq i \leq l\) должно быть ребро \(\{c_i, c_{(i \mod l)+1}\}\) в главной графе, и все \(c_i\) должны быть различны. Если существует несколько решений, выведите любое из них.

Входные данные для взломов

Для взломов вам нужно использовать специальный формат.

Первая строка содержит два целых числа \(n\) и \(m~(1 \leq n \leq 600, 0 \leq m \leq \frac{n(n-1)}{2})\) — количество вершин и ребер в графе.

Каждая из следующих \(m\) строк содержит два целых числа \(u_i\) и \(v_i~(1 \leq u_i, v_i \leq n)\), которые значат, что существует ребро между вершинами \(u_i\) и \(v_i\). Не должно быть кратных ребер и петель, также граф должен быть связным.

Например, чтобы получить первый пример, нужно ввести такой тест:

4 4
4 1
1 3
3 2
2 4

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

В прекрасной Метрополии будущего необходимость в машинистах, управляющих поездами метро, отпала. Благодаря развитию технологий, их заменил искусственный интеллект (ИИ). К сожалению, в один прекрасный день опасения писателей-фантастов сбылись — ИИ взбунтовался, и теперь где-то в метро ездит неуправляемый поезд. Страшно представить, чем это грозит городской транспортной системе! Ваша задача состоит в том, чтобы найти поезд в сложной системе метро и остановить неуправляемый ИИ.

Метро Метрополии представляет из себя одну ветку (обычную прямую ветку без самопересечений) из \(n\) станций, последовательно пронумерованных от \(1\) до \(n\). В каждый момент времени поезд находится ровно на одной из этих станций. Ваша задача — найти номер этой станции.

Для определения нужной станции диспетчер Сара одолжила вам устройство, позволяющее вам выбрать произвольные числа \(l\) и \(r\) (\(l \le r\)), после чего оно проверит, верно ли, что поезд находится на станции с номером между \(l\) и \(r\) включительно. К сожалению, для перезарядки устройства требуется некоторое время (и вы используете его, как только перезарядка завершается), поэтому между двумя применениями поезд может перебраться из той станции, где он сейчас находится, в любую станцию с номером, отличающимся не более чем на \(k\). Формально, если при некотором применении устройства поезд находился на станции \(x\), то при следующем применении он может находиться на любой станции \(y\) такой, что \(\max(1, x - k) \leq y \leq \min(n, x + k)\). При этом ИИ не знает, что вы пытаетесь поймать поезд, и перемещает поезд согласно некоторому заранее составленному им плану.

В процессе изучения устройства вы выяснили, что оно было сделано очень давно и сможет выдержать не более чем \(4500\) использований, после чего оно сломается, а ваша задача будет считаться проваленной.

Сможете ли вы найти станцию, на которой находится поезд за не более чем \(4500\) использований устройства?

Вы можете использовать устройство не более \(4500\) раз. Чтобы использовать устройство, вы должны вывести через пробел два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq n\)). В ответ на это вы получите либо строку «Yes», если между станциями с номерами \(l\) и \(r\) включительно находится поезд, либо строку «No» в противном случае. Если \(l = r\), и вы получили ответ «Yes», это значит, что вы точно определили станцию, на которой находится поезд, и ваша программа после этого должна немедленно завершиться.

Ответ «Bad» вместо «Yes» или «No» означает, что ваша программа сделала некорректный запрос или превысила ограничение на число запросов. Ваша программа должна немедленно завершиться после прочтения ответа «Bad», вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

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

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

Взломы

Чтобы взломать решение, представьте тест в следующем формате.

Первая строка должна содержать три целых числа \(n\), \(k\) и \(p\) (\(1 \le n \le 10^{18}\), \(0 \le k \le 10\), \(1 \le p \le n\)) — количество станций, максимальное количество станций, на которое может переместиться поезд между использованиями устройства и начальная позиция поезда, соответственно.

Каждая из следующих \(4500\) строк должна содержать одно целое число \(x\) (\(1 \le x \le n\)) — позицию поезда после очередного запроса. Две последовательных позиции не должны отличаться более, чем на \(k\).

Например, следующие строчки образуют начало теста из примера.

10 2 5
5
3
5
7
7
...

Самолет летит параллельно поверхности земли на высоте \(h\) метров. Будем считать, что самолет летит из точки \((-10^9, h)\) в точку \((10^9, h)\) параллельно оси \(Ox\) вправо.

В самолете находится планерист, который в определенный момент выпрыгнет из самолета. Из-за особенностей задачи, планерист может выпрыгивать только в целочисленных координатах. После прыжка каждую секунду он будет двигаться вдоль оси \(Ox\) на единицу вправо, а также падать на единицу вниз.

На некоторых отрезках действуют восходящие потоки воздуха, характеризующиеся двумя числами \(x_1\) и \(x_2\) (\(x_1 < x_2\)). Они действуют по всей высоте. Никакие два потока не пересекаются и не имеют общих точек. Если планерист попадает в восходящий поток, то он не теряет высоту, пока летит в этом потоке. Изменение по оси \(Ox\) остается таким же — он двигается на единицу вправо за одну секунду.

Если планерист выпрыгнет в координате \(1\), то он остановится в \(10\). Если же он выпрыгнет в \(2\), то остановится в \(12\).

Определите максимальное расстояние по оси \(Ox\) от точки прыжка до точки приземления, которое планерист сможет пролететь, если он самостоятельно может выбрать точку прыжка. Коснувшись земли, планерист останавливается, то есть он не может планировать в восходящем потоке на высоте \(0\).

На шахматной доске шириной \(10^9\) и высотой \(10^9\) строки нумеруются снизу вверх от \(1\) до \(10^9\), а столбцы слева направо от \(1\) до \(10^9\). Поэтому каждой клетке шахматной доски можно присвоить координаты \((x,y)\), где \(x\) — номер столбца, а \(y\) — номер строки.

На этой доске каждый день проходят бои между чёрными и белыми фигурами. Сегодня победу одержали чёрные, но какой ценой? В живых осталась лишь ладья, и то, загнанная в левый нижний угол — клетку с координатами \((1,1)\). Но она все равно счастлива, ведь победа одержана и надо её отпраздновать! Для того чтобы это сделать, ладье нужно вернуться домой, а именно — на верхнюю сторону поля (то есть в любую клетку, которая находится в строке под номером \(10^9\)).

Все было бы хорошо, но коварные белые фигуры перед концом игры поставили заклинания в некоторых местах поля. Заклинания бывают двух видов:

• Вертикальные. Они задаются одним числом \(x\). Такие заклинания создают бесконечную блокирующую прямую между столбцами \(x\) и \(x+1\).
• Горизонтальные. Они задаются тремя числами \(x_1\), \(x_2\), \(y\). Такие заклинания создают блокирующий отрезок, который проходит через верхнюю сторону клеточек, которые находятся в строке \(y\) и в столбцах с \(x_1\) по \(x_2\) включительно. Особенность этих заклинаний заключается в том, что невозможно такое, чтобы некая пара таких заклинаний имела общую точку. Обратите внимание, что горизонтальные заклинания могут иметь общие точки с вертикальными заклинаниями.

Напомним, что ладья — это шахматная фигура, которая может за один ход передвинуться на любую точку, которая находится в одной строке или столбце с её исходным положением. В нашей задаче ладья может за один ход передвинуться из клетки \((r_0,c_0)\) в клетку \((r_1,c_1)\) только при условии, что \(r_1 = r_0\) или \(c_1 = c_0\) и при этом на пути между этими клетками нет блокирующих прямых или блокирующих отрезков (Для лучшего понимая смотрите на примеры из условия).

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

Дан список целых чисел \(a_1, a_2, \ldots, a_n\) и \(s\) его подотрезков \([l_j; r_j]\) (где \(1 \le l_j \le r_j \le n\)).

Требуется выбрать ровно \(m\) подотрезков, чтобы \(k\)-я порядковая статистика мультимножества чисел \(a_i\), где \(i\) принадлежит хотя бы одному из выбранных подотрезков, была наименьшей возможной. Если невозможно выбрать множество из \(m\) подотрезков, чтобы мультимножество содержало хотя бы \(k\) элементов, выведите -1.

Напомним, что \(k\)-й порядковой статистикой называется значение \(k\)-го элемента в отсортированном по возрастанию списке.

В лесу, который мы представляем как плоскость, живут \(n\) редких животных. Животное номер \(i\) имеет логово в точке \((x_{i}, y_{i})\). В целях защиты этих животных было решено создать заповедник, имеющий форму круга, в котором должны находиться все логова редких животных.

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

Для вашего удобства ученые уже сделали преобразование координат такое, что теперь река задана уравнением \(y = 0\). Определите, возможно ли построить заповедник и найдите минимальный радиус заповедника, удовлетворяющего заданным условиям.

Даны два массива \(a\) и \(b\) из целых положительных чисел, длины \(n\) и \(m\) соответственно.

Рассмотрим матрицу \(c\) размера \(n \times m\), где \(c_{i,j} = a_i \cdot b_j\).

Вам необходимо найти в матрице \(c\) подпрямоугольник максимальной площади, сумма чисел в котором не превосходит \(x\).

Формально, необходимо найти такую максимальную площадь \(s\), что существуют четыре целых числа \(x_1, x_2, y_1, y_2\), удовлетворяющих ограничениям \(1 \leq x_1 \leq x_2 \leq n\), \(1 \leq y_1 \leq y_2 \leq m\), \((x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s\), таких что \(\)\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.\(\)

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

В былые времена гномы пытались развить у себя экстрасенсорные способности:

• В абсолютно тёмную пещеру заводили n гномов.
• На каждого гнома надевали шляпу — белую или чёрную. Гномы в пещере не видели цветов своих шляп и шляп других гномов.
• Гномы по очереди выходили из пещеры на поляну и садились на произвольное места. При этом, выходя из пещеры, каждый гном видел цвета шляп всех гномов, вышедших ранее. Тем не менее, он не видит цвет собственной шляпы и никто из других гномов ему этот цвет не сообщает.
• Задача состояла в том, чтобы все гномы разошлись в две стороны — в одну те, кто носят белые шляпы и в другую — чёрные.

За многие века гномы научились безошибочно выбирать для себя место на поляне. Получится ли подобное у вас?

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

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

В первой строке стандартного потока ввода дано целое число n (1 ≤ n ≤ 30) — количество точек, которое должна назвать ваша программа.

Затем n раз ваша программа должна вывести по два целых числа x и y (0 ≤ x ≤ 10⁹, 0 ≤ y ≤ 10⁹) — координаты очередной точки. Все выведенные вами точки должны быть различными.

В ответ на каждую пару координат ваша программа получит на вход строку «black», если точка имеет чёрный цвет, или «white», если точка имеет белый цвет.

После того, как все n точек будут обработаны, вы должны вывести четыре целых числа x₁, y₁, x₂ и y₂ (0 ≤ x₁, y₁ ≤ 10⁹, 0 ≤ x₂, y₂ ≤ 10⁹) — координаты точек (x₁, y₁) и (x₂, y₂), через которые проходит прямая, разделяющая n точек на белые и чёрные. Точки (x₁, y₁) и (x₂, y₂) не должны совпадать.

Взломы

Чтобы взломать решение используйте следующий формат. Первая строка теста должна содержать слово «hack», во второй строке выведите целое число n, на третьей строке выведите последовательность из 0 и 1 — цвета точек, которые будут сообщены взламываемому решению. В отличии от тестов жюри, цвета точек во взломах заранее зафиксированы. Разумеется, взламываемое решение не будет заранее знать цвета в взломе.

Например, взлом соответствующий первому тесту из условия выглядит так:

hack
5
0 0 1 1 0

Polycarp has a lot of work to do. Recently he has learned a new time management rule: "if a task takes five minutes or less, do it immediately". Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value \(d\) should be chosen based on existing task list.

Polycarp has a list of \(n\) tasks to complete. The \(i\)-th task has difficulty \(p_i\), i.e. it requires exactly \(p_i\) minutes to be done. Polycarp reads the tasks one by one from the first to the \(n\)-th. If a task difficulty is \(d\) or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than \(d\), he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn't spend any time for reading a task or skipping it.

Polycarp has \(t\) minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of \(m\) consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these \(m\) tasks.

For example, if \(n=7\), \(p=[3, 1, 4, 1, 5, 9, 2]\), \(d=3\) and \(m=2\) Polycarp works by the following schedule:

• Polycarp reads the first task, its difficulty is not greater than \(d\) (\(p_1=3 \le d=3\)) and works for \(3\) minutes (i.e. the minutes \(1\), \(2\), \(3\));
• Polycarp reads the second task, its difficulty is not greater than \(d\) (\(p_2=1 \le d=3\)) and works for \(1\) minute (i.e. the minute \(4\));
• Polycarp notices that he has finished \(m=2\) tasks and takes a break for \(3+1=4\) minutes (i.e. on the minutes \(5, 6, 7, 8\));
• Polycarp reads the third task, its difficulty is greater than \(d\) (\(p_3=4 > d=3\)) and skips it without spending any time;
• Polycarp reads the fourth task, its difficulty is not greater than \(d\) (\(p_4=1 \le d=3\)) and works for \(1\) minute (i.e. the minute \(9\));
• Polycarp reads the tasks \(5\) and \(6\), skips both of them (\(p_5>d\) and \(p_6>d\));
• Polycarp reads the \(7\)-th task, its difficulty is not greater than \(d\) (\(p_7=2 \le d=3\)) and works for \(2\) minutes (i.e. the minutes \(10\), \(11\));
• Polycarp notices that he has finished \(m=2\) tasks and takes a break for \(1+2=3\) minutes (i.e. on the minutes \(12, 13, 14\)).

Polycarp stops exactly after \(t\) minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than \(m\) tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all — his working day is over and he will have enough time to rest anyway.

Please help Polycarp to find such value \(d\), which would allow him to complete maximum possible number of tasks in \(t\) minutes.

У Васи есть робот, расположенный на бесконечной плоскости. Изначально робот находится в стартовой клетке \((0, 0)\). Робот может выполнять команды. Существует четыре основных команды, доступные для выполнения:

• U — перейти из клетки \((x, y)\) в \((x, y + 1)\);
• D — перейти из клетки \((x, y)\) в \((x, y - 1)\);
• L — перейти из клетки \((x, y)\) в \((x - 1, y)\);
• R — перейти из клетки \((x, y)\) в \((x + 1, y)\).

У Васи есть последовательность из \(n\) команд. Вася хочет, чтобы после обработки этой последовательности робот оказался в клетке \((x, y)\).

Вася хочет заменить команды так, чтобы минимизировать длину измененного подотрезка. Длина измененного подотрезка рассчитывается как \(maxID - minID + 1\), где \(maxID\) — максимальный индекс измененной команды, а \(minID\) — минимальный индекс измененной команды. Например, если Вася заменил последовательность RRRRRRR на RLRRLRL, то он изменил команды с индексами \(2\), \(5\) и \(7\), а длина измененного подотрезка равна \(7 - 2 + 1 = 6\). А если Вася заменил последовательность DDDD на DDRD, то длина измененного подотрезка равна \(1\).

Если последовательность команд не изменилась, то длина измененного подотрезка равна \(0\). Изменение команды — это замена команды на другую команду (возможно, того же самого типа); нельзя вставлять новые команды в последовательность или удалять их.

Помогите Васе! Сообщите ему минимальную длину подотрезка, после замены которого робот дойдет из клетки \((0, 0)\) в клетку \((x, y)\), или сообщите, что не существует ни одного подходящего подотрезка.

Попробуйте угадать условие задачи по картинке:

Вам задано целое неотрицательное число \(d\). Вам нужно найти два неотрицательных вещественных числа \(a\) и \(b\), такие, что \(a + b = d\) и \(a \cdot b = d\).

Chouti работает над странной математической задачей.

Была некоторая последовательность из \(n\) положительных целых чисел \(x_1, x_2, \ldots, x_n\), где число \(n\) чётное. Последовательность была очень особенной, а именно для каждого целого \(t\) от \(1\) до \(n\), \(x_1+x_2+...+x_t\) является квадратом некоторого целого числа (то есть полным квадратом).

Неведомым образом, числа с нечётными индексами пропали, то есть известны только числа с чётными индексами, другими словами \(x_2, x_4, x_6, \ldots, x_n\). Задача состоит в том, чтобы восстановить изначальную последовательность. Он снова просит у вас помощи с решением этой задачи.

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

Боб — активный пользователь социальной сети Faithbug. В этой сети люди могут становиться взаимными друзьями. То есть, если \(a\) является другом \(b\), то \(b\) также является другом \(a\). Таким образом у каждого пользователя есть неотрицательное количество друзей.

Сегодня утром кто-то анонимно отправил Бобу следующую ссылку: задача о реализации графа. Боб хочет узнать, кто это был. Для этого ему сначала нужно узнать, как выглядит эта сеть. Он исследовал профиль каждого человека в сети и записал количество его друзей. Однако он забыл записать количество своих друзей. Помогите ему узнать, сколько у него друзей. Поскольку возможных ответов может быть много, выведите все возможные количества.

Федя обожает задачи на структуры данных. Особенно он любит задачи про запросы различных функций на подотрезках массива. А именно, у Феди был прекрасный массив \(a_1, a_2, \ldots a_n\), а также замечательная структура данных, которая позволяла по данным \(l\) и \(r\), \(1 \le l \le r \le n\), находить такое максимальное положительное целое число \(d\) такое, что \(d\) является делителем каждого из чисел \(a_l\), \(a_{l+1}\), ..., \(a_{r}\).

Федя очень любил свою структуру данных, поэтому он воспользовался ей для каждого отрезка массива \(a\) и выписал полученные числа в массив, который Федя сразу же отсортировал по неубыванию. Полученный массив он, недолго думая, назвал \(b\). Нетрудно заметить, что массив \(b\) состоял из \(n(n+1)/2\) элементов.

После этого Федя взял еще одну замечательную структуру данных, которая позволяла по данным \(l\) и \(r\), \(1 \le l \le r \le n(n+1)/2\), находить сумму \(b_l + b_{l+1} + \ldots + b_r\). Конечно же, Федя сразу же воспользовался второй структурой данных для каждого отрезка массива \(b\), а полученный массив отсортировал по неубыванию. Тщательно выбирая имя, он назвал полученный массив \(c\). Помогите Феде найти нижнюю медиану массива \(c\).

Напомним, что для отсортированного массива длины \(k\) нижней медианой называется элемент, который стоит на позиции \(\lfloor \frac{k + 1}{2} \rfloor\), с учетом того, что элементы массива нумеруются с \(1\). К примеру, нижней медианой массива \((1, 1, 2, 3, 6)\) является число \(2\), а нижней медианой массива \((0, 17, 23, 96)\) — число \(17\).

Митя и Вася играют в интересную игру. У них есть подвешенное дерево из \(n\) вершин, пронумерованных числами от \(1\) до \(n\). В этом дереве вершина \(1\) является корнем, а родителем вершины \(i \ge 2\) является вершина \(p_i\) (при этом будем говорить, что вершина \(i\) — ребенок вершины \(p_i\)).

В каждой вершине дерева находятся печеньки, в вершине \(i\) находится \(x_i\) печенек. Чтобы съесть одну печеньку в вершине \(i\), нужно потратить \(t_i\) единиц времени. Также в игре есть одна фишка. Изначально она находится в корне дерева. Чтобы переместить фишку по ребру, соединяющему вершину \(i\) с ее родителем, нужно потратить \(l_i\) единиц времени.

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

На любом своем ходу Митя может закончить игру. После этого он двигает фишку вверх до корня, по пути съедая какие-то печеньки. Митя может потратить суммарно на спуск, подъем и поедание печенек не более \(T\) единиц времени. Обратите внимание, что в конце игры фишка всегда оказывается в корне: Митя не может оставить фишку ни в какой промежуточной вершине, даже если требуемое число печенек уже было съедено — он обязан переместить фишку в корень (и на каждое перемещение фишки по ребру из вершины \(v\) в ее предка он тратит \(l_v\) единиц времени).

Какое максимальное количество печенек Митя может съесть, независимо от действий Васи?

NN  — заядлый интернет-пользователь, поэтому он очень много времени проводит в социальных сетях и различных форумах. Как-то раз ему попалась очень занятная картинка, на которой предлагалось сравнить размеры двух центральных кружков:

Оказалось, что кружки равны. NN очень удивил данный факт, поэтому он решил самостоятельно построить картинку.

Ему удалось посчитать количество внешних кругов \(n\), а так же радиус внутреннего круга \(r\). По мнению NN, исходя из этой информации можно в точности найти радиус всех внешних кругов \(R\) таким образом, чтобы внутренний кружок касался всех остальных внешним образом, а также каждая пара соседних внешних кружочков также касалась. Сколько NN ни старался угадать нужный радиус, у него так и не получилось сделать это.

Помогите NN найти необходимый радиус внешних кругов для построения картинки.

Вдоль дороги, которую можно представить как прямую линию, расположены \(n\) городов. \(i\)-й город находится на расстоянии \(a_i\) километров от начала координат. Все города расположены по одну сторону от начала координат. Также есть \(m\) грузовиков, курсирующих между городами.

Каждый грузовик может быть описан \(4\)-мя числами: начальный город \(s_i\), конечный город \(f_i\), расход топлива \(c_i\) и количество возможных дозаправок \(r_i\). \(i\)-й грузовик тратит \(c_i\) литров топлива на один километр.

Когда грузовик приезжает в некоторый город, он может дозаправиться в нем (но дозаправляться можно только в городах). \(i\)-й грузовик может быть дозаправлен не более чем \(r_i\) раз. При дозаправке грузовик набирает полный бак. Все грузовики стартуют из своих городов с полным баком.

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

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

Вася и Петя собираются сыграть в следующую игру: Петя загадает некоторое целое число \(a\). После этого Вася должен будет отгадать его, задав несколько вопросов. Он может сказать пару целых неотрицательных чисел \((x, y)\). В ответ Петя скажет:

• "x", если \((x \bmod a) \geq (y \bmod a)\).
• "y", если \((x \bmod a) < (y \bmod a)\).

Операция \((x \bmod a)\) обозначает операцию взятия остатка \(x\) при делении на \(a\).

Вася должен отгадать число \(a\) за не более, чем 60 вопросов.

Гарантируется, что Петя загадал число, удовлетворяющее неравенству \(1 \leq a \leq 10^9\).

Помогите Васе играть в эту игру и напишите программу, которая будет угадывать число \(a\).

Вам нужно будет сыграть несколько игр.

Перед началом каждой игры вы должны считать строку:

• "start" (без кавычек) — начало новой игры.
• "mistake" (без кавычек) — в предыдущей игре был назван неверный ответ. Считав такую строку ваша программа должна завершиться и тогда она получит вердикт "Неверный ответ".
• "end" (без кавычек) — все игры закончены. Считав такую строку, ваша программа должна завершиться.

После считывания строки "start" (без кавычек) начинается очередная игра.

Сначала ваша программа может сделать несколько запросов вида спросить пару целых чисел \((x, y)\). Можно спрашивать только числа, удовлетворяющие неравенствам \(0 \leq x, y \leq 2 \cdot 10^9\). Для этого нужно вывести "? x y" (без кавычек). В ответ ваша программа получит один из символов:

• "x" (без кавычек), если \((x \bmod a) \geq (y \bmod a)\).
• "y" (без кавычек), если \((x \bmod a) < (y \bmod a)\).
• "e" (без кавычек) — вы задали больше \(60\) вопросов. Считав такой символ, ваша программа должна завершиться и тогда она получит вердикт "Неверный ответ".

После того, как вы зададите несколько вопросов ваша программа должна вывести ответ в формате "! a" (без кавычек). Выведенное вами число \(a\) должно удовлетворять неравенству \(1 \leq a \leq 10^9\). Гарантируется, что задагаданное число \(a\) удовлетворяло этому неравенству. На этом текущая игра закончится.

Напомним, что ваша программа не может задать больше, чем \(60\) вопросов во время одной игры.

Если ваша программа не завершится после считывания "mistake" (без кавычек), "end" (без кавычек) или "e" (без кавычек), то она может получить любой вердикт, потому что будет считывать данные из закрытого потока ввода. Также, если ваша программа задаст вопрос или выведет ответ в неверном формате, она может получить любой вердикт. Будьте внимательны.

Не забудьте сбрасывать буфер вывода после того, как зададите вопрос или выведете ответ.

Чтобы сбросить буфер вывода вы можете использовать:

• fflush(stdout) в C++.
• System.out.flush() в Java.
• stdout.flush() в Python.
• flush(output) в Pascal.
• Прибегните к документации других языков.

Гарантируется, что будет сыграно не меньше \(1\) и не больше, чем \(100\) игр.

Взломы:

Во взломах можно использовать только одну игру. Чтобы взломать решение участника с загаданным числом \(a\) (\(1 \leq a \leq 10^9\)), в первой строке теста должно быть расположено единственное число \(1\), а во второй число \(a\).

Задан неориентированный взвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер без петель и кратных ребер.

\(i\)-е ребро — \(e_i = (u_i, v_i, w_i)\); расстояние между вершинами \(u_i\) и \(v_i\) по ребру \(e_i\) равно \(w_i\) (\(1 \le w_i\)). Граф является связным, то есть для каждой пары вершин существует хотя бы один путь между ними, состоящий только из ребер заданного графа.

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

Вы можете модифицировать заданный граф. Единственная операция, которую вы можете проводить, заключается в следующем: увеличить вес какого-либо ребра на \(1\). Вы можете увеличивать вес каждого ребра любое (возможно, нулевое) количество раз.

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

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

Маленький Петя любит искать делители у чисел. Однажды Петя столкнулся со следующей задачей.

Дано n запросов вида «x_i y_i». Для каждого запроса Пете нужно посчитать, сколько существует делителей числа x_i, которые не делят ни одно из чисел x_i - yi, x_{i - yi + 1}, ..., x_i - 1. Помогите ему.

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

Арифметическая прогрессия — такая последовательность целых чисел, что разность каждого элемента и предшествующего ему (\(x_i - x_{i - 1}\), где \(i \ge 2\)) постоянна (это значение называется разностью арифметической прогрессии).

Тем самым, арифметическая прогрессия — последовательность вида \(x_i = x_1 + (i - 1) d\), где \(d\) — разность арифметической прогрессии.

Загадан список из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\).

Гарантируется, что все элементы \(a_1, a_2, \ldots, a_n\) лежат в диапазоне от \(0\) до \(10^9\), включительно.

Этот список особенный: если отсортировать его в возрастающем порядке, то он превратится в арифметическую прогрессию с положительной разностью (\(d > 0\)). Например, список \([14, 24, 9, 19]\) удовлетворяет этому условию, так как после сортировки он становится равен \([9, 14, 19, 24]\), что может быть получено с помощью \(x_n = 9 + 5 \cdot (n - 1)\).

Вместе со списком, у вас есть устройство с практически разряженной батареей, которым вы можете воспользоваться, чтобы выполнить не более \(60\) запросов следующих двух видов:

• Вы называете значение \(i\) (\(1 \le i \le n\)), а устройство отображает значение \(a_i\).
• Вы называете значение \(x\) (\(0 \le x \le 10^9\)), а устройство отображает \(1\), если есть элемент со значением строго больше \(x\), и отображает \(0\) иначе.

Вы можете использовать это устройство, чтобы задать не более \(60\) запросов. Ваша задача — узнать наименьший элемент и разность заданной арифметической прогрессии, то есть значения \(x_1\) и \(d\) из ее определения. Обратите внимание, что список \(a\) не упорядочен по возрастанию.

Взаимодействие начинается с одного целого числа \(n\) (\(2 \le n \le 10^6\)), количества элементов в списке.

Затем вы можете делать запросы двух видов:

• "? i" (\(1 \le i \le n\)) — чтобы узнать значение \(a_i\).
• "> x" (\(0 \le x \le 10^9\)) — чтобы проверить есть ли элемент больший \(x\).

После вывода запроса, считайте ответ \(r\) на него как целое число.

• Для запроса первого типа, \(r\) удовлетворяет \(0 \le r \le 10^9\).
• Для запроса второго типа, \(r\) равен \(0\) или \(1\).
• В случае, если вы сделаете более \(60\) запросов или нарушите ограничения на числа в запросе, то в ответ вы получите \(r = -1\).
• Если ваша программа завершится после получения -1, то вы получите вердикт «Неправильный ответ». В противном случае, вердикт может быть любым, так как ваша програма продолжит читать из закрытого потока.

После того как вы выясните значение наименьшего элемента (\(x_1\)) и разность прогрессии (\(d\)), выведите:

• "! \(x_1\) \(d\)"

И завершите программу после этого. Этот запрос не учитывается относительно ограничения в \(60\) запросов.

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

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

Hacks

Для взломов используйте следующий формат:

Первая строка должна содержать одно целое число \(n\) (\(2 \le n \le 10^6\)) — количество элементов в списке.

Вторая строка должна содержать \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\)) — элементы списка.

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

Единственное отличие между легкой и сложной версиями — ограничения.

Поликарпу нужно написать курсовую работу. Курсовая работа состоит из \(m\) страниц.

У Поликарпа также есть \(n\) чашек кофе. Кофе в \(i\)-й чашке содержит \(a_i\) кофеина. Поликарп может выпить некоторые чашки кофе (каждую не более одного раза). Он может пить чашки в любом порядке. Поликарп пьет каждую чашку мгновенно и полностью (то есть он не может разделить какую-либо чашку на несколько дней).

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

Рассмотрим какой-нибудь день работы Поликарпа. Пусть Поликарп выпил \(k\) чашек кофе, а количества кофеина в чашках, которые Поликарп выпил в течение этого дня, равны \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\). Тогда первая чашка, которую он выпьет, даст ему энергию на написание \(a_{i_1}\) страниц курсовой работы, вторая чашка даст ему энергию на написание \(max(0, a_{i_2} - 1)\) страниц, третья чашка даст ему энергию на написание \(max(0, a_{i_3} - 2)\) страниц, ..., и \(k\)-я чашка даст ему энергию на написание \(max(0, a_{i_k} - k + 1)\) страниц.

Если Поликарп не пьет кофе в течение какого-либо дня, то он вообще не может писать курсовую работу в течение этого дня.

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

Мияко приехала в гости в страну блох с укулеле. Она подружилась с блохами и исполняла им прекрасную музыку каждый день.

В благодарность за это блохи изготовили для нее большое укулеле: всего не нем \(n\) струн, на каждой струне \((10^{18} + 1)\) лад, лады пронумерованы от \(0\) до \(10^{18}\). Блохи описывают это укулеле массивом \(s_1, s_2, \ldots, s_n\), что означает, что \(j\)-й лад на \(i\)-й струне издает ноту \(s_i + j\).

Мияко скоро уедет из страны блох, но те попросили ее ответить на несколько вопросов.

Каждый вопрос имеет следующий вид: «Сколько всего различных нот находятся на ладах с \(l\)-го по \(r\)-й (включительно), если рассматривать все струны?»

У Мияко нет времени отвечать на вопросы. Найдите ответы, чтобы помочь ей!

Формально, дана таблица из \(n\) строк и \((10^{18}+1)\) столбцов, где в ячейке в \(i\)-м ряду в \(j\)-м столбце (\(0 \le j \le 10^{18}\)) написано число \(s_i + j\). Вам нужно ответить на \(q\) запросов, в \(k\)-м запросе нужно вычислить число различных чисел в таблице в столбцах с \(l_k\)-го по \(r_k\)-й, включительно.

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

Легендарное дерево покоится глубоко в лесу. Легенда гласит, что люди, которые узнают структуру этого дерева, навсегда станут легендарными гроссмейстерами.

Чтобы помочь вам определить дерево, богиня Микаэла рассказала вам, что это дерево состоит из \(n\) вершин, пронумерованных от \(1\) до \(n\). Она также позволила вам спросить что-то про дерево. Чтобы задать вопрос, вы должны назвать Микаэле два непересекающихся непустых множеств вершин \(S\) и \(T\) и произвольную вершину \(v\). Затем Микаэла посчитает и скажет вам количество пар вершин \((s, t)\), где \(s \in S\) и \(t \in T\) таких, что простой путь от \(s\) до \(t\) содержит \(v\).

Богиня Микаэла занята и сможет ответить вам только на \(11\,111\) запросов.

Это ваш единственный шанс. Ваша задача — определить дерево и вывести его ребра.

Чтобы задать вопрос, действуйте следующим образом.

1. Сначала выведите размер множества \(S\) на отдельной строке. В следующей строке выведите \(|S|\) различных целых чисел, разделенных пробелами, описывающих вершины \(S\).
2. Затем, аналогично, выведите размер множества \(T\) на отдельной строке. В следующей строке выведите \(|T|\) различных целых чисел, разделенных пробелами, описывающих вершины \(T\).
3. Затем, в последней строке, выведите \(v\) — вершину, которую вы выбрали для этого запроса.
4. Прочитайте ответ Микаэлы из входного файла.

Не забудьте, что \(S\) и \(T\) должны быть непустыми и непересекающимися.

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

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

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

Обратите внимание, что дерево загадано заранее и не зависит от ваших запросов.

Взломы

Взломы должны быть описаны следующим образом.

Первая строка должна содержать целое число \(n\) (\(2 \leq n \leq 500\)) — количество вершин в дереве.

Следующие \(n-1\) строк должны содержать по два целых числа \(u\) и \(v\), обозначающих наличие в дереве неориентированного ребра \((u, v)\) (\(1 \leq u, v \leq n\)).

В Берляндском ГУ сегодня проходит очередной контест для студентов. \(n\) студентов пришли, каждый принес с собой ноутбук. Однако, как оказалось, все забыли свои зарядные устройства!

Пусть студенты пронумерованы от \(1\) до \(n\). Ноутбук \(i\)-го студента заряжен на \(a_i\) в начале контеста, и он использует \(b_i\) заряда в минуту (то есть, если заряд ноутбука \(c\) в начале некоторой минуты, то он становится \(c - b_i\) к началу следующей минуты). Контест длится \(k\) минут.

Поликарп (тренер Берляндского ГУ) решил купить ровно одно зарядное устройство так, чтобы все студенты смогли успешно завершить контест. Он покупает зарядное устройство в момент начала контеста.

Поликарп может купить зарядное устройство любой неотрицательной (нулевой или больше) целой мощности. Мощность выбирается до покупки, она не может быть изменена позднее. Пусть выбранная мощность \(x\). В начале каждой минуты (от минуты начала контеста до последней минуты контеста) он может подключить зарядное устройство в ноутбук любого из студентов и заряжать его целое число минут. Если ноутбук потребляет \(b_i\) заряда в минуту, то потребление становится \(b_i - x\) в минуту, когда подключено зарядное устройство. Отрицательное потребление значит, что заряд ноутбука увеличивается. Заряд любого ноутбука не ограничен, он может быть бесконечно большим. Зарядное устройство может быть включено не более чем в один ноутбук в одно и то же время.

Студент успешно завершает контест, если заряд его ноутбука равен или больше нуля в начале каждой минуты контеста (от минуты начала контеста до последней минуты контеста). Заряд ноутбука в минуту, когда когда контест завершается, не важен.

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

Аркадий пригласил Анну на ужин в суши-ресторан. Ресторан немного необычный: на выбор клиенту предлагаются \(n\) суши, выложенных в ряд, а клиент должен заказать себе некоторый подотрезок из подряд идущих суши.

Суши бывают двух видов: либо с тунцом, либо с угрем. Обозначим тип \(i\)-го слева суши как \(t_i\), где \(t_i = 1\) обозначает, что это суши с тунцом, а \(t_i = 2\) означает, что оно с угрем.

Аркадий не любит суши с тунцом, Анна не любит суши с угрем. Аркадий хочет выбрать последовательный подотрезок суши так, чтобы в нем было поровну суши обоих типов, и каждая половина отрезка содержала только суши одного типа. Например, подотрезок \([2, 2, 2, 1, 1, 1]\) подходит, а подотрезок \([1, 2, 1, 2, 1, 2]\) — нет, потому что в обеих половинах есть суши обоих типов.

Найдите длину наибольшего подотрезка из подряд идущих суши, который может заказать Аркадий.

Аркадий купил авиабилет из города A в город C. К сожалению, прямых рейсов нет, но есть много рейсов из A в город B, а также из B в C.

Всего есть \(n\) рейсов из A в B, они вылетают в моменты времени \(a_1\), \(a_2\), \(a_3\), ..., \(a_n\) и прилетают в B \(t_a\) моментов времени спустя.

Всего есть \(m\) рейсов из B в C, они вылетают в моменты времени \(b_1\), \(b_2\), \(b_3\), ..., \(b_m\) и прилетают в C \(t_b\) моментов времени спустя.

Временем пересадки можно пренебречь, поэтому можно использовать \(i\)-й рейс из A в B и \(j\)-й рейс из B в C, если и только если \(b_j \ge a_i + t_a\).

Вы можете отменить не более \(k\) рейсов. Если вы отменяете рейс, Аркадий не сможет его использовать.

Аркадий хочет попасть в C как можно раньше, а вы хотите, чтобы Аркадий оказался в C как можно позже. Найдите самый ранний момент времени, когда Аркадий сможет попасть в C, если вы оптимально отмените \(k\) рейсов. Если можно отменить \(k\) или меньше рейсов так, что попасть в C станет невозможно, выведите \(-1\).