Алгоритмы сортировки

Магазин производит закупку болтов (bolt) и гаек (nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

Определите, сколько всего будет куплено гаек и какая сумма останется неиспользованной.

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	6 6500 1500 bolt 500 bolt 3500 nut 3000 nut 2500 bolt 1000 nut	2 500

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

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

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

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

У всех жителей Цветочного города спросили его любимый фрукт.  Определите самый любимый фрукт среди всех жителей Цветочного города.

Входные данные
Программа получает на вход текст (количество строк может быть много). Текст заканчивается строкой END!. 

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

Пример

№	Входные данные	Выходные данные
1	apple orange banana banana orange END!	banana

Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

 Примеры

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

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

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи. В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10⁹) - возможное время приезда i-го друга.

Формат выходных данных
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.
 
 

Примеры

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

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные
Требуется вывести массив после сортировки.

Примеры

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

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число Ai. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты. 
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел Ai (\(1<=A_i<=10^5\))

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 1 2 1 3 7	3	Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду. Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2	15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1	7

 

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

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

У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую. 

Будем считать, что строка s = s1s2...sn лексикографически меньше строки t = t1t2...tm, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
-  \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).


Входные данные
В первой строке задаются числа N и L. Далее идут строки s1, s2, .., sN, каждая в отдельной строке.

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

 

Примеры

№	Входные данные	Выходные данные
1	3 3 dxx axx cxx	axxcxxdxx

 

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

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

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

Входные данные
Первая строка содержит целое число N (1  N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк -  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

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

Каждый день на планете Кирнес состоит из h часов. Каждый час состоит из m минут, причём m обязательно чётное. Известно, что на данный момент n товарных поездов отправляются с вокзала ежедневно по разу в день: i-й поезд отправляется в h_i часов и m_i минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \( {m \over 2}\)минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \({m \over 2}\) минут до неё, а следующая должна отправиться ровно через \({m \over 2}\) минут после. Кроме этого, электричку надо подать на платформу за k минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \({m \over 2}\) минут, то первая электричка отправится с вокзала в 0 часов и t минут, причем t < \({m \over 2}\) . Обратите внимание, что если t < k, то платформа вокзала будет занята и последние k − t минут предыдущего дня.

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

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

Формат входных данных
Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 100 000, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ \({m \over 2}\)) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут m четное.
В следующих n строках вводится по два целых числа hi и mi (0 ≤ h_i < h, 0 ≤ m_i < m) — время отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.

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

Примеры

№	Входные данные	Выходные данные
1	2 24 60 15 16 0 17 15	0 0
2	2 24 60 16 16 0 17 15	1 0 2

Замечание

В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в t ∈ [1, 15], то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если t ∈ {0, [16, 29]}, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать t = 0, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, t = 13.
 

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

Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

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

Если задача не имеет решения, необходимо вывести одно число 0.

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

Примеры

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

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

Выходные данные
Выведите минимальное натуральное  четырехзначное число, состоящее из тех же цифр.

Примеры

№	Входные данные	Выходные данные
1	1513	1135

У ковбоя Влада день рождения! На праздник собрались n детей. Чтобы поздравить ковбоя, дети решили водить вокруг Влада хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе рядом стоят очень высокий и очень низкий ребёнок, им трудно держаться за руки. Поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной.

Более формально, пусть n детей выстроились в хоровод. Пронумеруем их целыми числами от 1 до n так, чтобы справа от ребёнка с номером i стоял ребёнок с номером i+1, а справа от ребёнка с номером n стоял ребёнок с номером 1. Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.

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

Входные данные
В первой строке содержится одно целое число n (2 ≤ n≤ 10⁵) — количество детей, которые пришли на день рождения ковбоя Влада.

Во второй строке заданы n целых чисел a_i (1≤a_i≤10⁹) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на 10⁹, таким образом, рост ребёнка с a_i=1 чуть выше метра, а рост ребёнка с a_i=10⁹ составляет два метра.

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 1 1 3 2	1 2 3 2 1	Здесь неудобство хоровода равно 1, так как разность в росте между соседними детьми равна 1, 1, 1, 1 и 0 соответственно. Обратите внимание, что последовательности [23211] , [32112]  задают те же хороводы и отличаются только выбором ребёнка с номером 1.
2	3 30 10 20	10 30 20	Неудобство хоровода равно 20, так как разность в росте детей высотой 10 и 30 равна 20.

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.

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

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

Примеры

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

Маше на день рождения подарили набор матрёшек!

Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a_i и a_j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a_i < a_j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.

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

Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a_i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a_i ≤ 10 000 ).

Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
 

Примеры

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

В числе подсчитали количество единиц, в получившемся опять подсчитали количество единици т.д.
Например: 111211121112111 - 12 - 1 - 1 - 1 - ...

В итоге полученная последовательность стабилизировалась. На каком числе?

Например, последовательность 111211121112111 - 12 - 1 - 1 - 1 - ... стабилизировалась на числе 1.

Входные данные
Вводится одно натуральное число, состоящее из не более чем 100 цифр.

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

Примеры

№	Входные данные	Выходные данные
1	12345	1
2	2007	0

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

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

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

 Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число стаканов и бутылок напитков в i-ом наборе (1≤n_i≤10⁵).
Во второй строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
В третьей строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
Гарантируется, что сумма n_i по всем тестовым наборам не превосходит 3⋅10⁵.

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

Примеры

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

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

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

Коля хочет своеобразно оценить сколько способов есть разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы. Так как число способов может быть довольно большим, Коля хочет знать его по модулю 1 000 000 007. Помогите Коле посчитать это число.
Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число бутылок напитков и стаканов в i-ом наборе (1≤n_i≤10⁵).
Во второй строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
В третьей строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
Гарантируется, что сумма ni по всем тестовым наборам не превосходит 3⋅10⁵.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 1 1 1 2 1 5 1 2 3 4 5 1 2 3 4 5 3 2 2 2 2 1 2	6 1 0	В первом тестовом наборе любой напиток помещается в любой стакан. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе ни один напиток не поместится во второй стакан, поэтому ответ будет ноль

Беси опубликовала N статей (1 <= N <= 10⁵). i-ая статья процитирована ci раз (0 <= c_i <= 10⁵).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

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

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

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

Выходные данные
Максимальный h-индекс.
 

Примеры

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