У Поликарпа есть три отрезка с целочисленными длинами $$$a$$$, $$$b$$$ и $$$c$$$.

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

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

• выбрать один из отрезков и увеличить или уменьшить длину выбранного отрезка ровно на $$$1$$$.

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

Перед вами стоит задача определить минимальное количество операций, которые необходимы, чтобы из измененных после операций отрезков $$$a$$$, $$$b$$$ и $$$c$$$ можно было сделать треугольник с положительной площадью, а концы отрезков были вершинами треугольника.

Поликарп очень любит играть в баскетбол. На последней тренировке он сделал $$$n$$$ точных бросков. Поликарп запомнил для каждого броска расстояние до кольца, с которого бросок был сделан.

Теперь Поликарп хочет посчитать количество очков, которые он набрал на тренировке. Для этого ему нужно выбрать какое-то целое неотрицательное число $$$d$$$. Тогда за каждый точный бросок с расстояния строго меньшего, чем $$$d$$$, Поликарп запишет себе $$$2$$$ очка, а за каждый бросок с расстояния большего либо равного $$$d$$$, Поликарп запишет себе $$$3$$$ очка.

Перед вами стоит задача определить минимально возможное значение $$$d$$$, при котором количество очков Поликарпа на тренировке будет в точности равно числу $$$k$$$.

У Поликарпа есть две последовательности целых чисел $$$a$$$ и $$$b$$$. В каждой из этих последовательностей по $$$n$$$ элементов.

Поликарпу стало интересно, сколько существует различных целых чисел $$$x$$$ таких, что для всех $$$i$$$ от $$$1$$$ до $$$n$$$ верно, что $$$x$$$ находится между $$$a_i$$$ и $$$b_i$$$, то есть для всех $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется хотя бы одно из двух условий:

• $$$a_i \le x \le b_i$$$;
• $$$b_i \le x \le a_i$$$.

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

Перестановкой длины $$$n$$$ называется массив из $$$n$$$ целых чисел, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

Инверсией в перестановке $$$p$$$ назовем такую пару элементов $$$p_i$$$ и $$$p_j$$$, что $$$i \lt j$$$ и $$$p_i \gt p_j$$$. В таком случае эти два элемента участвуют в инверсии.

Вам даны два целых числа $$$n$$$ и $$$k$$$. Постройте такую перестановку длины $$$n$$$, в которой ровно $$$k$$$ элементов, участвующих в инверсиях, или сообщите, что такой перестановки не существует.

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

Чтобы произошло волшебство, Поликарп должен выбрать страницу $$$x$$$ и прочитать все страницы книги, начиная со страницы $$$x$$$ и заканчивая последней страницей с номером $$$n$$$.

Также Поликарп знает, что цифры $$$a$$$ и $$$b$$$ являются волшебными. Если окажется так, что среди прочитанных Поликарпом страниц ровно $$$k$$$ номеров страниц заканчиваются на цифры $$$a$$$ или $$$b$$$, то произойдет чудо, и Поликарп получит пятерку в четверти по информатике.

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

Перед вами стоит задача определить наибольший номер страницы $$$x$$$, с которой Поликарп должен начать читать книгу, чтобы ровно $$$k$$$ номеров страниц, начиная со страницы $$$x$$$ и заканчивая страницей $$$n$$$, заканчивались на цифры $$$a$$$ или $$$b$$$.

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

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

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

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

Перед вами стоит задача определить, возможно ли перераспределить ящики таким образом, чтобы в каждой из $$$2\cdot n - 1$$$ стопок было одинаковое количество ящиков. Ящики запрещено выкидывать или добавлять, то есть Поликарп должен перераспределить именно те ящики, которые были в $$$n$$$ изначальных стопках.

У Поликарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Поликарп решил, что удалит из своей строки ровно $$$k$$$ букв. После удаления $$$k$$$ букв строка Поликарпа разделится на некоторое количество частей. Поликарп будет рассматривать только те части строки, в которых есть хотя бы одна буква, то есть пустые части рассматриваться не будут. Например, если $$$s = $$$ «abcdefghij» и Поликарп удалит первую, четвертую и шестую буквы, его строка разделится на три части «bc», «e» и «ghij».

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

Поликарп хочет, чтобы все получившиеся части его строки были одинаковыми. Перед вами стоит задача определить, возможно ли удалить ровно $$$k$$$ букв из строки $$$s$$$, учитывая все описанные условия, так, чтобы желание Поликарпа исполнилось.

У Поликарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Поликарп может выполнять со своей строкой следующую операцию:

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

Например, если строка Поликарпа равна «cccrrrttt», то после применения одной операции строка станет равна «ccrrrttt», а если строка Поликарпа равна «aabbbcc», то после применения одной операции строка станет равна «aabbcc».

Перед вами стоит задача определить, как будет выглядеть строка Поликарпа, если к ней последовательно применить ровно $$$k$$$ описанных операций.

Поликарп является тренером футбольного клуба в Берляндии.

За прошедший сезон его команда сыграла $$$n$$$ матчей, за которые набрала $$$p$$$ очков. Известно, что за один матч команда может получить следующее количество очков:

• в случае победы команда получает $$$k$$$ очков ($$$k \gt 1$$$);
• в случае ничьи команда получает $$$1$$$ очко;
• в случае поражения команда получает $$$0$$$ очков.

Поликарп не помнит точные результаты каждого из $$$n$$$ матчей его команды. Ему стало интересно, какое максимальное количество ничьих могло быть у его команды за прошедший сезон, если она набрала $$$p$$$ очков за $$$n$$$ матчей. Перед вами стоит задача помочь Поликарпу и определить максимальное количество ничьих.

Поликарп вышел в финал телепередачи «Твоя игра».

В финале для Поликарпа подготовлены $$$n$$$ вопросов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, причем каждый вопрос имеет свою стоимость. Если Поликарп ответит на вопрос, то к его счету прибавится стоимость вопроса, а если Поликарп не ответит на вопрос, то из его счета вычтется стоимость вопроса. Изначально счет Поликарпа равен нулю.

По правилам финала сначала Поликарп должен удалить ровно $$$k$$$ вопросов, которые ему точно не будут заданы. Относительный порядок остальных вопросов останется без изменений.

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

Поликарп перед началом финала узнал темы всех $$$n$$$ вопросов. Теперь он точно знает на какие вопросы он сможет ответить верно, а на какие не сможет.

Перед вами стоит задача определить максимальный счет, который может набрать Поликарп в конце финала, если вы можете помочь ему и подсказать, какие $$$k$$$ вопросов нужно удалить в начале финала и какие вопросы в ходе финала ему нужно пропустить.

Поликарп отметил на координатной прямой $$$n$$$ точек с целочисленными координатами.

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

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

Дан неориентированный граф, состоящий из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$.

Ваша задача — выбрать подмножество из ровно $$$k$$$ различных вершин данного графа. Пусть выбранные вершины — это $$$v_1, v_2, \cdots, v_k$$$. Тогда все эти вершины удаляются из графа, а вместо них добавляется новая вершина $$$V$$$, соединённая со всеми вершинами, с которыми была соединена каждая из вершин $$$v_1, v_2, \cdots, v_k$$$ (то есть если хотя бы одна вершина $$$v_i$$$ не соединена с какой-то вершиной $$$x$$$, то и $$$V$$$ не будет соединена с $$$x$$$).

Можно ли сделать так, чтобы вершина $$$V$$$ была соединена со всеми оставшимися вершинами графа? Если можно, то выведите выбранные вершины $$$v_1, v_2, \cdots, v_k$$$ в произвольном порядке.

Если существует несколько ответов, то выведите любой из них.

Бинарная строка — это строка, состоящая из символов 0 и/или 1. Назовем бинарную строку чередующейся, если в ней нет двух одинаковых соседних символов. Например, строки 0, 1, 101, 0101 — чередующиеся.

Для бинарной строки определим чередующуюся $$$k$$$-раскраску следующим образом:

• для каждого символа строки выбирается цвет от $$$1$$$ до $$$k$$$;
• для каждого цвета, если выписать все символы строки, покрашенные в этот цвет, в том порядке, в котором они идут в строке, мы получим чередующуюся строку.

Например, для строки 100111 существует чередующаяся $$$3$$$-раскраска: покрасим символы $$$2$$$ и $$$6$$$ в цвет $$$1$$$, символы $$$1$$$, $$$3$$$, и $$$4$$$ в цвет $$$2$$$, а символ $$$5$$$ — в цвет $$$3$$$. Тогда для каждого из трех цветов строка, состоящая только из символов этого цвета, будет чередующаяся (для цвета $$$1$$$ это 01, для цвета $$$2$$$ — 101, для цвета $$$3$$$ — 1).

Вам дана бинарная строка $$$s$$$. Вам нужно обрабатывать запросы двух типов:

• $$$1$$$ $$$i$$$ — заменить символ $$$s_i$$$ на противоположный (0 на 1, 1 на 0);
• $$$2$$$ $$$l$$$ $$$r$$$ — посчитать минимальное $$$k$$$ такое, что для строки $$$s_l s_{l+1} s_{l+2} \dots s_r$$$ существует чередующаяся $$$k$$$-раскраска.