битмаски

В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по вопросам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь организаторам необходимо распределить секции по дням: в каждый день будут проводиться 4 секции.

Известно, что в съезде примут участие \(n\) человек. Каждый участник съезда выбрал 3 секции, которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно, каждый участник в один день может присутствовать не более чем на одной секции. Поэтому если в один день будут идти две или три секции, выбранные каким-то участником, то он всё равно сможет посетить только одну из них. Если же выбранные секции будут проходить в разные дни, участник сможет посетить их все.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 10\,000\)) — количество участников съезда.

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

Формат выходных данных
Программа должна вывести \(3\) строки, в каждой из которых должны быть \(4\) числа через пробел — номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний несколько, можно вывести любое из них.

Примечание
В примере из условия расписание составлено так, что второй и третий участник посетят все желаемые секции, а первый — две секции (\(5\) и одну из секций \(1\), \(6\)). Таким образом, суммарно будут посещены 8 секций. Можно показать, что этот результат улучшить нельзя.

Напомним, что простое число — это целое число, которое делится ровно на два целых числа: на единицу и на себя. Последовательность простых чисел начинается с \(2, 3, 5, \ldots\).

Рассмотрим первые \(n\) простых чисел. Давайте разделим их на две части \(A\) и \(B\) так, чтобы каждое простое число принадлежало ровно одной из этих двух частей. Обозначим произведение всех простых чисел в \(A\) как \(a\), а произведение всех простых чисел в \(B\) как \(b\). Произведение чисел в пустом множестве будем считать равным \(1\). Будем называть разбиение красивым, если \(a < b\) и \(b-a\) минимальное возможное.

Дано \(n\), найдите красивое разбиение множества первых \(n\) простых чисел и выведите соответствующее значение \(a\).

Формат входных данных
Входные данные содержит целое число \(n\) на отдельной строке (\(1 \le n \le 30\)).

Формат выходных данных
Выведите значение \(a\) в красивом разбиении множества первых \(n\) простых чисел.

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от \(0\) до \(9\) в виде цифр <<почтового индекса>> (см. рисунок):

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

Алексей уже выяснил, что индикатор всё ещё способен показать какие-то \(n\) цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

Формат входных данных
Первая строка входных данных содержит число \(n\) (\(1 \le n \le 10\)) — количество цифр, которые смог показать на индикаторе Алексей.

Следующие \(n\) строк содержат по одной цифре \(a_i\) (\(0 \le a_i \le 9\)) — сами цифры, которые Алексей смог показать. Гарантируется, что все \(a_i\) различны.

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

 

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

•  «Правда ли, что ровно x из твоих соседей из Зедд патруля?»
•  «Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

•  «0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
•  «1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

Мальчик Коля любит графы, но не любит циклы. У Коли есть несколько ориентированных не обязательно связных
графов. Графы могут содержать параллельные ребра, но не содержат петли. К сожалению, некоторые из них могут содержать
циклы.
Коля хочет развернуть некоторые ребра в каждом графе, чтобы избавиться от циклов. Разворотом ребра будем считать
замену ребра из вершины a в вершину b на противоположное ребро, которое будет направлено из вершины b в вершину a. При
этом Коля хочет развернуть наименьшее число ребер в каждом графе, чтобы получившиеся графы не содержали циклов.
Помогите Коле узнать, какое наименьшее число ребер ему нужно развернуть в каждом графе.

Входные данные
В первой строке входных данных содержится число t - число графов (1≤t≤8).
В первой строке описания каждого графа дано два числа n и m - число вершин и число ребер соответственно
(2≤n≤10, 1≤m≤1000).
В следующих m строках содержатся пары чисел a_i, b_i - описание ребер графа (1≤ a_i, b_i ≤ n, a_i ≠ b_i).
Для удобства, описания графов разделены пустыми строками. Пустой строки после последнего графа нет.
Гарантируется, что суммарное число вершин во всех графах не превосходит 50.

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

Примеры

№	Входные данные	Выходные данные
1	4 2 2 1 2 2 1 4 2 1 4 4 3 3 3 1 2 2 3 3 1 3 5 1 2 2 3 3 1 2 3 1 3	1 0 1 1

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

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

Про каждую задачу известно время ti, которое нужно затратить, чтобы сделать её, а также прибыль pi, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

• Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
• Суммарная прибыль от выполнения этих задач была максимальна.

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

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

Входные данные

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

Выходные данные

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

 

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31