Информатика

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии (2≤P_i≤50) и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).
 

Примеры

№	Входные данные	Выходные данные
1	5 2 4 1 2 3 4 2 5 3 3 1	0
2	5 5 2 1 2 2 1 3 2 2 3 2 3 4 2 4 5 1 5	2
3	10 2 6 1 3 5 7 4 9 6 2 4 6 8 10 7 3 8	1
4	4 2 2 1 2 2 3 4 1 3	-1

На вход программы поступает строка текста, в которой могут встречаться:
— прописные и строчные (т.е. большие и маленькие) латинские буквы;
— пробелы;
— знаки препинания: точка, запятая, восклицательный и вопросительный знак;
— символ –, обозначающий в некоторых случаях тире, а в некоторых — дефис.
Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.
Напишите программу, определяющую, сколько слов в данной строке текста.

Входные данные
Вводится строка длиной не более 200 символов.

Выходные данные
Выведите одно число — количество слов, которые содержатся в исходной строке.
 
Примеры

№	Входные данные	Выходные данные
1	Hello , world!	2
2	www.olympiads.ru	3
3	Gyro-compass - this is a ...	4

X мальчиков и Y девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Напишите программу, которая выдаст, как нужно сесть мальчикам и девочкам, чтобы рядом с каждым мальчиком сидела хотя бы одна девочка, а рядом с каждой девочкой — хотя бы один мальчик.

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Входные данные
Сначала вводится число N — количество элементов исходной последовательности (1 ≤ N ≤ 100). Далее идут N чисел — элементы этой последовательности, натуральные числа от 1 до 9.

Выходные данные
Выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.

Примеры

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

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй — с (K+1)-й по (2*K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Входные данные
Вводятся два числа: K - количество строк, которое печатается на странице, и N - номер строки (1<=K<=200, 1<=N<=20000).

Выходные данные
Выведите два числа - номер страницы, на которой будет напечатана эта строка, и номер строки на странице.
 
Примеры

№	Входные данные	Выходные данные
1	50 1	1 1
2	20 25	2 5
3	15 43	3 13

Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара не заканчивается на подстроку «fixed», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На товары, название которых заканчивается на подстроку «fixed», скидка не распространяется. 

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

Выходные данные
Выведите одно число - итоговую стоимость покупки.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 bananassale 10 x2 breadfixed 5 x5 colafixed 20 x2 gumsale 9 x10 tea 2 x15	166	В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 1 соответственно. Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+1⋅15=166$.

 

Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара заканчивается на подстроку «sale», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На остальные товары скидка не распространяется.

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

Выходные данные
Выведите одно число - итоговую стоимость покупки.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 bananassale 10 x2 breadfixed 5 x5 colafixed 20 x2 gumsale 9 x10 tea 2 x15	181	В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 2 соответственно. Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+2⋅15=181.

 

Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.

• Сначала Маша выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
• Затем Даша выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
• Затем Маша выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
• В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает тот, кто не может сделать ход.

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

Входные данные
Первая строка содержит N.
Вторая строка содержит N разделённых одиночными пробелами целых чисел a1,…,aN.


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

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 7	4	Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
2	6 3 2 3 2 3 1	8	Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход.

Наскучившись стандартными двумерными произведениями искусства (а также разочаровавшись тем, что другие копируют ее работы), великая художница Пикоусо решила перейти к более минималистичному, одномерному стилю. Ее последняя картина может быть описана одномерным массивом цветов длины N (\(1<=N<=300\)), где каждый цвет указывается целым числом в интервале \(1…N\).
К великому разочарованию Пикоусо, ее конкурент Муне, похоже, придумал, как копировать даже эти одномерные картины! Муне закрашивает один интервал одним цветом, ждет, пока он высохнет, затем красит другой интервал и так далее. Муне может использовать каждый из N цветов столько раз, сколько пожелает (возможно ни одного).

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


Входные данные
Первая строка содержит число N. Следующая строка содержит N целых чисел в интервале \(1…N\), указывающих цвет каждой ячейки в картине Пикоусо.

 

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

Примеры

№	Входные данные	Выходные данные
1	10 1 2 3 4 1 4 3 2 1 6	6

 

Пояснение

В этом примере Муне может скопироват картину так: (незакрашенные ячейки обозначены цветом 0).

Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
Муне закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
Муне закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
Муне закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
Муне закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
Муне закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
Муне закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.

Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).  Размещение коров весьма занимательно. Для каждой ячейки (x,y) с \(x>=0\) и \(y>=0\), существует корова в ячейке (x,y), если для всех целых чисел \(k>=0\), остатки \(\lfloor {\frac {x}{3^k} }\rfloor\) и \(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для \(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже.

 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт Q вопросов, кажый содержит три целых числа xi,yi,di. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (xi, yi) до (xi+di, yi+di) (включая конечные точки).


Входные данные
Первая строка содержит Q (\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих Q строк содержит 3 целых числа di, xi, и yi (\(0<=x_i,y_i,d_i<=10^{18}\)).


Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.
 
 

Примеры

№	Входные данные	Выходные данные
1	8 10 0 0 10 0 1 9 0 2 8 0 2 0 1 7 1 1 7 2 1 7 1000000000000000000 1000000000000000000 1000000000000000000	11 0 4 3 1 2 2 1000000000000000001

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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

Входные данные
Первая строка ввода содержит N и K. Следующие N строк содержат N различных целых чисел в интервале \(1…10^9\), указывающих сколько лет назад жил каждый из предшественников Беси.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 3 101 85 100 46 95	36	Один из способов для Беси посетить всех своих предшественников за 36 лет таков: Войти в портал в текущем году и вернуться на 48 лет в прошлое. Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое. Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек (огромная шахматная доска). Изначально пастбище пустое.
Фермер Джон добавит N (1≤N≤10⁵) коров на пастбище одну за одной. i-ая корова занимает ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (0≤x_i,y_i≤1000).

Говорят, что корове "комфортабельно", если по горизонтали и вертикали она имеет ровно три других коровы. Фермер Джон хочет посчитать, скольким коровам комфортабельно на его пастбище. Для каждого i в интервале 1…N, выведите общее количество коров, которым комфортабельно после того, как i-ая корова добавлена на пастбище.

Входные данные: 
Первая строка содержит одно целое число N. Каждая из последующих N строк содержит два разделённых пробелом целых числа, указывающих (x,y) - координаты ячейки коровы. Гарантируется, что все ячейки различны.
Выходные данные: 
i-ая строка вывода должна содержать общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2	0 0 0 1 0 0 1 2	После того, как добавлены первые 4 коровы, корове в ячейке (1,1) стало комфортабельно. После того, как добавлены первые 7 коров, корове в ячейке (2,1) стало комфортабельно. После того, как добавлены первые 8 коров, корове в ячейках (2,1) и (2,2) стало комфортабельно.

Пастбище Фермера Джона может рассматриваться как NхN решётка (\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка (i,j) описывается целым числом - уровнем зелёности G(i,j), в интервале \(1…200\).

Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).

Входные данные
Первая строка содержит N. Каждая из следующих N строк содержит N целых чисел и все вместе они описывают величины G(i,j) для пастбища NхN .

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

Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.

 
 

Примеры

№	Входные данные	Выходные данные
1	3 57 120 87 200 100 150 2 141 135	8

Фермер Джон решил заменить изгородь вокруг своего пастбища.
Эта новая изгородь описывается строкой символов, каждый из которых "N" (north), "E" (east), "S" (south), или "W" (west). Каждый символ описывает 1 метр изгороди. Например, если строка NESW, это означает, что изгородь начинатся одним метром на север, затем 1 метр на восток, затем 1 метр на юг, и затем 1 метр на запад, возвращаясь в стратовую точку.

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

Фермер Джон хочет узнать, указанный путь обходится по часовой стреле или против часовой стрелки? По часовой стрелке - огороженный регион находится по правую сторону от изгороди, если идти по пути, определённому строкой. Против часовой стрелки - огороженный регион находится по левую сторону от изгороди, если идти по пути, определённому строкой.

Входные данные: 
Первая строка содержит целое число N (1≤N≤20). Каждая из последующих N строк содержит строку длиной не менее 4 символов и не более 100, описывающую путь изгороди.
Выходные данные: 
Для каждого из N путей, описанных по вводе, выведите строку содержащую "CW" (clockwise - по часовой стрелке) или "CCW" (counterclockwise - против часовой стрелки).
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 NESW WSSSEENWNEESSENNNNWWWS	CW CCW	Оба пути   (? символ "пробел") обозначает стартовую точку: *>* ^ v <*   *<*<*<*   v     ^ *<      * v       ^ * *>*>* * v ^   v ^ * *<* * * v   ^ v ^ *>*>* *>*

Из N коров выбирается делегация (1≤N≤2⋅10⁵). Они стоят в ряд, корова i имеет породу b_i.

Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).

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

Входные данные: 
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].
Выходные данные: 
Количество возможных делегаций на одной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	9	Каждая делегация соответствует одному из следующих триплетов лидеров: (1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N  коров участвуют в выборе делегации (1≤N≤2⋅10⁵). Они стоят в ряд, и корова i имеет породу b_i.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l…r для целых l и r удовлетворяющих 1≤l<r≤N. две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.


Входные данные: 
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].

Выходные данные: 
Количество возможных делегаций, на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	13	Каждая делегация соответствует одной из следующих пар лидеров: (1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).

 

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами x_i и y_i (0≤x_i,y_i≤10⁴).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p₁,p₂,…,p_N из N точек
Она рисует отрезки между p₁ и p₂, p₂ и p₃, p₃ и p₁.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от p_i до p_j для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10⁹+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x_i и y_i.

Выходные данные: 
Количество перестановок по модулю 10⁹+7.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 4 1 1 1 2	0	Никакая перестановка не сработает.
2	4 0 0 0 4 4 0 1 1	24	Все перестановки работают.
3	5 0 0 0 4 4 0 1 1 1 2	96	Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1). Для этой перстановки Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0). Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2). Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1). Рисунок: Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤10⁵) и её i-ую статью цитировали c_i раз (0≤c_i≤10⁵).

Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.

Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤10⁵), т конечно она может процитировать каждую из своих статей не более одного раза.

Помогите Беси определить максимальный h-индекс, который она может достичь написанием своей обзорной статьи.

Заметим, что научный руководитель должен был предупредить Беси, что написание статьи исключительно с целью увеличения своего h-индекса сомнительно с этической точки зрения.

ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.

Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.

ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.

№	Входные данные	Выходные данные	Пояснение
1	4 0 1 100 2 3	2	Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2.
2	4 1 1 100 2 3	3	Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.

Беси поступает на работу в компьютерную лабораторию. Она хочет определить степерь важности каждого из N работников лаборатории (1≤N≤100). Все степени важности различны. То есть, нет двух работников с одинаковой степенью важности. Для определения степени важности сотрудников Беси использует список публикаций лаборатории.

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

Например, если лаборатория состоит (в порядке возрастания важности) из студентки Elsie, проф. Mildred и проф. Dean, они могут быть авторами статьи (Elsie-Mildred-Dean), если они все внесли различное количество усилий. А именно, Elsie внесла больше усилий чем Mildred, а Mildred больше чем Dean. Однако у них также может быть статья в порядке Elsie-Dean-Mildred если Mildred и Dean внесли одинаковое количество усилий, а Elsie больше их обоих.

По заданным K публикациям этой лаборатории (1≤K≤100), помогите Беси определить для всех пар сотрудников этой лаборатории кто более важен, если это возможно определить.

ФОРМАТ ВВОДА 
Первая строка содержит два целых числа K и N.
Вторая строка содержит N разделённых одиночными пробелами строк, содержащих имена членов лаборатории. Каждое имя состоит не более чем из 10 маленьких латинских букв.

Каждая из следующих K строк содержит N разделённых одиночными пробелами строк, указывающих список авторов в одной публикации.

ФОРМАТ ВЫВОДА 
Вывод должен состоять из N строк, по N символов в строке. На строке i, для любого j≠i, j-ый символ должен быть 1, если i-ый член более важный чем j-ый, 0, если i-ый член менее важный чем j-ый, и ? если невозможно определить при заданном списке публикаций.
i-ый символ в строке i должен быть B потому что это любимый символ Беси.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 3 dean elsie mildred elsie mildred dean	B11 0B? 0?B	В первом примере одна статья (elsie-mildred-dean) не даёт достаточно информации, чтобы определить кто важнее elsie или mildred. Однако точно Dean более важен чем оба. Поэтому возможны оба порядка Elsie<Mildred<Dean и Mildred<Elsie<Dean
2	2 3 elsie mildred dean elsie mildred dean elsie dean mildred	B00 1B0 11B	В этом втором примере единственный возможный порядок удовлетворяющий обоим статьям: Elsie<Mildred<Dean поскольку вторая публикация помогает определить, что Mildred важнее, чем Elsie.

 

Малькольма Рейнольдса попросили доставить пустые контейнеры на самую отдаленную планету звездной системы. На корабле осталась только одна свободная ячейка объемом Х, в которую можно положить контейнеры. Капитан решил сложить несколько контейнеров друг в друга. Все контейнеры имеют подобные размеры. Контейнер с меньшим объемом свободно помещается в контейнер с объемом на 3 условных единицы больше. Определите, какое наибольшее количество контейнеров может доставить капитан Рейнольдс?

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

Выходные данные
Выведите одно число — максимальное количество контейнеров, которое сможет доставить Малькольм Рейнольдс.
 

Примеры

№	Входные данные	Выходные данные
1	60 2 60 63	1
2	26  5 26 24 22 21 18	3