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

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

Примем во внимание некоторые очевидные условия:

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

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

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• одна строка с двумя положительными целыми p и n: цена подарка в рублях (1 <= p <= 1000000) и количество скидывающихся (2 <= n <= 100), включая вас.
• одна строка с n положительными целыми a_i (1 <= a_i <= 1000000), где a_i — максимальная сумма, которую i-ый друг готов дать.

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

На каждый кейс:

• одна стркоа с n целыми - количество денег, которое каждый друг даст на подарок. Если стоимость подарка не может быть собрана из того, что могут дать друзья, выведите без кавычек "IMPOSSIBLE".

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

Это происходит следующим образом. Используются только латинские заглавные буквы. Вначале имеется строка из букв A. Их ровно столько, сколько букв в вашем имени. (Предположим, вы указали длину имени ранее.) Вначале курсор на первой букве. Когда вы двигаете джойстик вперед, буква меняется на следующую по алфавиту, если назад, то на предыдующую. Алфавит зациклен, то есть за Z идет A, а перед A идет Z.

Движение джойстика вправо и влево смещает курсор соответственно на букву вперед или назад. Движение курсора так же зациклено. То есть, движение вправо на последней букве перемешает курсор на первую и наоборот.

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

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• одна строка до 1000 символов заглавных латинских букв - имя, которое нужно ввести.

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

На каждый кейс:

• одна строка с целым неотрицательным числом - минимальнрое количество движений.

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

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

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

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• На первой строке количество команд 2 <= n <= 500.
• На следующей стркое n целых t_i (1 <= t_i <= n): отсортированный по рейтингу список команд за прошлый год, от самой сильной команды до самой слабой. Команда t_i занимает i-ю позицию в прошлогоднем списке. Все t_i различны.
• Одна строка с целым 0 <= m <= 25 000 - количество пар команд, относительное положение которых изменилось.
• m строк с двумя целыми a_i and b_i (1 <= a_i < b_i <= n) - команды, относительное положение которых в списке изменилось. Каждая пара указана ровно один раз.

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

На каждый кейс:

• Одна строка с n целыми числами - положение команд за этот год, от лучшей к худшей. Если команда на какой-то позиции не может быть определена точно, выведите знак вопроса без кавычек "?". Если пары, предоставленные жюри, некорректные, для данного кейса выведите без кавычек "IMPOSSIBLE".

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

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

Первое число — количество тест-кейсов. В каждом тесте до 200 кейсов. На первой строке надо количество кейсов. Далее на каждый кейс:

• Положительное целое число длиный не более 7 цифр.

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

На каждый кейс:

• Одна строка с одним числом - количество простых чисел, которые можно "собрать" из цифр данного числа.

Все знают Эдсгера. А он знает все самые быстрые маршруты в городе. И он совсем не таксист.

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

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

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• число вершин 1 <= n <= 50000 и число ребер 0 <= m <= 50000 через пробел,
• m строк с описанием ребер: номер вершины 1 <= u <= n в начале ребра, номер вершины 1 <= v <= n в конце ребра и вес 1 <= w <= 10⁹ - за какое время можно преодолеть этот участок дороги, в минутах, все через пробел,
• f и t - начальная и конечная точки маршрута.

Суммарное число как ребер, так и вершин во всех кейсах одного теста не превосходит 50000.

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

На каждый кейс:

• единственное число - продолжительность езды по самому быстрому маршруту, в минутах, если маршрута не существует, выведите без кавычек "NO".

Гарантируется, что в каждом кейсе ответ не превосходит 10⁹.

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

Точно так же цифры представляются на цифровых циферблатах.

Какие минимальное и максимальное числа можно составить из данного количества спичек?

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• Одна строка с количеством спичек (от 2 до 100 штук влючительно).

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

На каждый кейс:

• Одна строка с минимальным и максимальным числом. Эти числа не должны содержать нулей в начале и должны быть положительными.

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

Вам дана последовательность целых положительных чисел. Посчитайте количество отрезков этой последовательности, сумма чисел в которых делится на данное число. Отрезки могут пересекаться. Наример, последовательность 2;1;2;1;1;2;1;2 содержит шесть отрезков, сумма которых делится на четыре: [1, 8], [2, 4], [2, 7], [3, 5], [4, 6], [5, 7].

Например, отрезок последовательности от второго элемента до седьмого имеет сумму 8, которая делится на 4. Обратите внимание, что индексация последовательности начинается с единицы.

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Далее на каждый кейс:

• Каждый кейс начинается со строки с двумя целыми числами 1 <= d <= 1 000 000 и 1 <= n <= 50 000, делитель сумм и длины данной последовательности соответственно.
• Вторая строка содержит саму последовательность с целыми от 1 до 1000000000 включительно.

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

На каждый кейс:

• Одна строка с одним числом - количеством отрезков, сумма чисел в которых делится на данный делитель d.

Саша, Гоша и Лев Вячеславович проделали большую работу по подготовке контеста. Осталось последнее — доделать монитор. Они уже написали код, который считает количество решенных задач и штрафное время. Осталось только узнать, кто какое место занимает и вывести таблицу участников, упорядоченную по местам, начиная с первого...

Места начинаются с единицы. Место определяется следующими правилами:

• выше тот, у кого больше решенных задач,
• выше тот, у кого меньше штрафное время,
• при равенстве количества задач и штрафного времени участники делят место: a участников могут иметь i-е место, при этом участник (участники), которые идут за ними, занимают место i + a.

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

Первое число — количество тест-кейсов. В каждом тесте до 100 кейсов. Общее количество позиций (участников, которые в каждом кейсе считаются разными) не более 200000. Далее на каждый кейс:

• В первой строке n — количество команд в списке.
• В следующих n строках через пробел:
  • название команды (не более 20 латинских букв),
  • неотрицательное целое число меньше или равное 8 — количество решенных задач,
  • неотрицательное целое число меньше или равное 4000 — штрафное время.

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

На каждый кейс:

• n строк, в которых через пробел:
  • место,
  • порядковый номер команды из начального списка,
  • название команды,
  • количество решенных задач,
  • штрафное время.

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

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