Алгоритмы

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

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

Формат выходных данных
Выведите одно число — максимальное количество задач, которое Вася может решить.

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

Вдоль прямой улицы через каждый метр расположены фонарные столбы. На каждом столбе написан номер метра, на котором он расположен. Первый столб расположен в начале улицы и имеет номер 0. 

Код Рудольф гуляет вдоль улицы, от фонаря с номером a до фонаря с номером b. Полосатый кот Ихмиллион прогуливается от фонаря с номером c до фонаря с номером d. Определите, количество фонарных столбов, мимо которых проходя оба кота.



Входные данные
Вводятся четыре числа в одной строке через пробел: a, b, c, d (0 < a, b, c, d <= 100). 

Выходные данные
Выведите ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 8 6 2	2	Рудольф прогуливается от фонаря с номером 5 до  8-го фонаря и обратно, а Ихмиллион со 6-го по 2-й и обратно. Одновременно оба кота прогуливаются мимо фонарей с номерами 5 и 6. Всего фонарей два.
2	5 3 7 9	0	Нет общих фонарей, мимо которых прогуливаются оба кота.

На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

1. Компьютер называет целое число \(k > 0\).

2. Вы ровно \(k\) раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.

3. Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

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

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

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

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

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

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

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

 

В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.

Сеня выбирает себе подарки на новый год. Он знает, что Дед Мороз купит ему ровно два подарка: один якобы от мамы, а другой якобы от папы.

В магазине, где Дед Мороз будет покупать подарки, продаётся \(n\) подарков, про каждый подарок известна его цена: цена \(i\)-го подарка равна \(a_i\) рублей. Сеня знает, что Дед Мороз может потратить на покупку его подарков не больше \(x\) рублей. Разумеется, он хочет получить как можно более дорогие подарки. Таким образом, он хочет выбрать два различных подарка с максимальной суммарной ценой, но при этом она не должна превышать \(x\).

Помогите Сене выбрать себе подарки.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(x\) (\(2 \le n \le 100\,000\), \(2 \le x \le 10^9\)). Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)). Гарантируется, что существует два подарка с суммарной ценой не больше \(x\).

Формат выходных данных
Выведите одно целое число: максимальную суммарную цену двух различных подарков, не превышающую \(x\).

В одном королевстве есть \(n\) городов, расположенных вдоль длинной прямой дороги, \(i\)-й город расположен на расстоянии \(x_i\) километров от начала дороги (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

В ближайшее время король планирует провести реформу управления королевством и разделить его на \(k\) провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от \(a\) до \(b\) городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами \(i\) и \(l\), для которых \(1 \le i\), \(i + l - 1 \le n\), \(a \le l \le b\) и в провинцию входят города с номерами \(i, i + 1, \ldots, i + l - 1\).

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

Формат входных данных
Первая строка ввода содержит четыре целых числа: \(n\), \(k\), \(a\) и \(b\) (\(1 \le n \le 200\), \(1 \le k \le n\), \(1 \le a \le b \le n\), \(ak \le n \le bk\)). Вторая строка ввода содержит \(n\) целых чисел: \(x_1, x_2, \ldots, x_n\) (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

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

Примечание
В примере оптимально первые 4 города объединить в первую провинцию, а пятый и шестой — во вторую. Максимальное расстояние между двумя городами в одной провинции: \(13 - 6 = 7\).

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — <<PriceFixed>>. У этого магазина есть несколько особенностей:

• В магазине есть бесконечный запас каждого товара.

• Все товары в нем стоят одинаково — ровно 2 рубля.

• Для каждого из \(i\) товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели \(b_i\) товаров (любого типа, не обязательно типа \(i\)), то на все последующие покупки \(i\)-го товара будет действовать скидка \(50\%\) (то есть, \(i\)-й товар можно будет покупать за 1 рубль!).

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

Формат входных данных
В первой строке вводится число \(n\) \((1 \leq n \leq 100\,000)\) — количество различных товаров в списке.

В следующих \(n\) строках вводятся описания товаров. Каждое описание состоит из двух чисел \(a_i\) и \(b_i\), (\(1 \leq a_i \leq 10^{14}\), \(1 \leq b_i \leq 10^{14}\)) — требуемое число товаров типа \(i\) и сколько товаров нужно купить, чтобы получить скидку на товар \(i\).

Сумма всех \(a_i\) в тесте не превосходит \(10^{14}\).

Формат выходных данных
Выведите искомую минимальную сумму, которая требуется Лене для совершения всех покупок.

В первом примере из условия Лена может купить товары в таком порядке:

1. единицу товара 3 за 2 рубля,

2. единицу товара 1 за 2 рубля

3. единицу товара 1 за 2 рубля,

4. единицу товара 2 за 1 рубль (она может купить его со скидкой, так как уже куплено 3 товара),

5. единицу товара 1 за 1 рубль (она может купить его со скидкой, так как уже куплено 4 товара).

Суммарно она потратит 8 рублей. Можно показать, что меньше потратить невозможно.

Во втором примере из условия Лена может купить товары в таком порядке:

1. единицу товара 1 за 2 рубля,

2. две единицы товара 2 по 2 рубля за каждую,

3. единицу товара 5 за 2 рубля,

4. единицу товара 3 за 1 рубль,

5. две единицы товара 4 по 1 рублю за каждую,

6. единицу товара 1 за 1 рубль.

Суммарно при таком порядке приобретения товаров Лена потратит 12 рублей.

Найдите и выведите в возрастающем порядке все несократимые обыкновенные дроби \(f\) со знаменателем не превышающим \(n\), которые удовлетворяют неравенству \(1/p < f < 1/q\).

Формат входных данных
На ввод подается три числа: \(n\), \(p\) и \(q\) (\(1 \le n \le 100\), \(1 \le q < p \le 100\)).

Формат выходных данных
Выведите все искомые дроби, по одной на строке.

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

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Натуральное число \(p\) называется простым, если оно имеет ровно два различных делителя: \(1\) и \(p\). Например, числа \(2\), \(3\), \(5\) являются простыми. Число \(1\) простым не считается.

Целое число \(p\) будем называть квазипростым, если \(p\) или \(-p\) является простым. Например, числа \(-2\), \(2\), \(-3\), \(3\), \(-5\), \(5\) являются квазипростыми.

Хотя любое натуральное число можно единственным образом представить в виде произведения простых, для целых чисел и квазипростых это уже неверно. Например, число \(12\) можно тремя способами представить в виде произведения квазипростых: \(12=2\cdot 2\cdot 3\), \(12=(-2)\cdot 2\cdot (-3)\), \(12=(-2)\cdot (-2)\cdot 3\).

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

Формат входных данных
На первой строке ввода находится число \(n\) (\(-10^9 \le n \le 10^9\), \(n \ne 0\), \(n \ne \pm 1\)).

Формат выходных данных
На первой строке выведите \(k\) — количество способов представить \(n\) в виде произведения квазипростых. В следующих \(k\) строках выведите все способы представить \(n\) в виде произведения квазипростых. Произведения можно выводить в любом порядке, множители в каждом произведении можно выводить в любом порядке.

У Максима есть n книг различных жанров. В i-й книге ai страниц. Сегодня он хочет прочитать  не менее xj страниц, при этом, чтобы не запутаться в историях, он хочет прочитать как можно меньше книг. 
Помогите Максиму  определить минимальное количество книг, которые он должен прочитать, чтобы общее число прочитанных страниц было не менее xj. Если это невозможно, выведите -1. Максим не может читать одну и ту же книгу дважды. 

Формат входных данных

Первая строка содержит натуральное число n (1 ≤ 𝑛 ≤ 10⁵) - количество книг, которые есть у Максима. Вторая строка  содержит n целых чисел a1, a2, ..., an (1≤ ai ≤10⁴) - количество страниц в i-й книге. Третья строка содержит натуральное число xj (1 ≤ xj ≤ 2⋅10⁹) - количество страниц, которое хочет прочитать Максим.

Формат выходных данных
Выведите ответ на задачу.

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

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 103). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 109).

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

Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел  делилась на 4 и при этом была максимально возможной.

Формат входных данных
В первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Формат выходных данных
Выведите значение найденной максимальной суммы. Если такой суммы нет, то выведите -1.
  
 

Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.

На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

• Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).

• Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).

• Суммарная высота всех использованных колец должна быть максимальна.

Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.

В \(i\)-й из последующих \(n\) строк записаны три числа \(a_i\), \(b_i\) и \(h_i\) (\(1 \leq a_i, b_i, h_i \leq 10^9\), \(b_i > a_i\)) — внутренний радиус, внешний радиус и высота \(i\)-го кольца соответственно.

Формат выходных данных
Выведите максимальную высоту башни, которую смогут получить работники фабрики.

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).

Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.

После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру “Банковские карты”.

Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с \(n\)-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если \(n=3\) и у Шерлока номер карты \(123\), а у Мориарти \(321\), то сначала Шерлок называет число \(1\), а Мориарти называет число \(3\) и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число \(2\), и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет \(3\), а Мориарти называет \(1\) и получает щелбан.

Шерлок, конечно, будет играть честно, но Мориарти, как настоящий злодей, подсмотрел номер карты Шерлока и теперь хочет называть цифры своей банковской карты не последовательно, а в некотором другом порядке (однако количество каждой из цифр он не изменяет). Например в случае выше, Мориарти мог бы назвать цифры в последовательности \(3\), \(2\), \(1\) и не получил бы щелбанов вообще, а мог назвать \(2\), \(3\) и \(1\) и выдать Шерлоку целых два щелбана.

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

Формат входных данных
В первой строке находится одно целое число \(n\) (\(1 \leqslant n \leqslant 1000\)) — количество цифр в банковских картах Шерлока и Мориарти.

Во второй строке записана последовательность из \(n\) цифр — номер кредитной карточки Шерлока.

В третьей строке записана последовательность из \(n\) цифр — номер кредитной карточки Мориарти.

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

Во второй строке выведите так же одно число — максимальное число щелбанов, которое Мориарти может дать Шерлоку.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n \leq 3\), наберёт не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq n \leq 8\), наберет не менее \(30\) баллов.

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

• появления доступного парковочного места, когда он приезжает;

• возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i \le t^\mathrm{in}_j\) и \(t^\mathrm{out}_i \ge t^\mathrm{out}_j\).

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

Формат входных данных

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

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

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(n\) строках перечислены времена въезда и выезда для каждого сотрудника, в \(i\)-й строке через пробел \(t^\mathrm{in}_i\) и \(t^\mathrm{out}_i\) (\(1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9\)).

Формат выходных данных
Выведите ответ на задачу для каждого набора входных данных в том порядке, в котором они перечислены во вводе.

В первой строке выведите число \(k\) — минимальное необходимое количество рядов.

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

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

Рассмотрим все представления числа \(n\) в виде суммы различных целых возрастающих слагаемых: \(n = a_1 + a_2 + \ldots + a_k\), \(a_1 < a_2 < \ldots < a_k\).

Будем называть такое разбиение хаотическим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых среднее не равно среднему арифметическому крайних. Иначе говоря, для всех \(i\) от 1 до \(k - 2\) выполнено \(a_{i+1} \ne (a_i + a_{i+2}) / 2\).

Задано число \(n\). Выведите все его хаотические разбиения на слагаемые.

На ввод подается целое число \(n\) (\(1 \le n \le 80\)).

Выведите все хаотические разбиения на слагаемые числа \(n\). Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком <<+>> без пробелов.

В этой задаче 25 тестов, каждый оценивается независимо в 4 балла.

Будем называть два натуральных числа \(x\) и \(y\) непохожими, если они различны и нет двух различных отличных от \(1\) чисел \(a\) и \(b\), таких, что и \(x\) и \(y\) делятся как на \(a\), так и на \(b\). Например, 6 и 9 непохожи, так как единственное число, отличное от 1, на которое делятся оба числа "— 3. А вот числа 12 и 18 не являются непохожими, так как оба делятся на 2, 3 и 6.

Задано натуральное число \(x\), а также натуральные числа \(l\) и \(r\). Требуется найти все числа \(y\), такие что \(l \le y \le r\), и числа \(x\) и \(y\) непохожи.

Формат входных данных
На первой строке ввода задано число \(x\) (\(1 \le x \le 10^9\)).

На второй строке ввода задано число \(l\), на третьей строке ввода задано число \(r\) (\(1 \le l \le r \le 10^9\); \(r - l \le 1000\)).

Формат выходных данных
На первой строке выведите число \(k\) "— количество непохожих на \(x\) чисел на отрезке от \(l\) до \(r\), включительно.

На второй строке выведите все эти числа в возрастающем порядке.