Задача A. Три подвижные частицы ≡

Условие

Пусть имеются три частицы, положение которых в момент времени t = 0 задается двумерными координатами: (x₁, y₁), (x₂, y₂) и (x₃, y₃).

Полагается, что в течение всего последующего времени каждая i-я частица, независимо от остальных,
совершает прямолинейное движение с некоторой постоянной скоростью (u_i, v_i).

Требуется определить наиболее ранний момент времени T ≥ 0, когда они окажутся на одной прямой.

Формат входного файла

Входной файл "input.txt" содержит последовательность целых чисел:
x₁, y₁, u₁, v₁, x₂, y₂, u₂, v₂, x₃, y₃, u₃, v₃.

Формат выходного файла

Выходной файл "output.txt" должен содержать значение T, указанное с точностью до 5-го знака после запятой.

В случае если подходящее решение не может быть найдено, в выходной файл необходимо вывести  − 1.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 10⁴ ≤ (x_i, y_i, u_i, v_i) ≤ 10⁴.

Примеры тестов

 2500  2500 -3000 -3000
-1000     0  1000  4000
    0 -1000  4000  3000

 0.48990

-1097   236  1000  1000
  200   178  1500   500
    0  -500 -1240   356

-1

Задача B. Наибольшее число цепочек ≡

Условие

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

Требуется вычислить значения A(n, d) для всех натуральных n, не превосходящих заданного m, при некотором фиксированном d.

Формат входного файла

Входной файл "input.txt" содержит два натуральных числа: d и m.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность значений A(n, d), расположенных в порядке возрастания величины n = 1, 2, …, m.

Ограничения

d ≤ m ≤ 10⁵

Примеры тестов

1 10

1 1 2 1 2 3 2 1 3 4

2 10

1 1 1 2 1 2 1 2 3 2

Задача C. Составные блоки ≡

Условие

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

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

Совпадающие между собой ребра (в которых две и более ячейки соприкасаются друг с другом) полагаются тождественными и рассматриваются как одно общее ребро. Так, например, блок размером 2 × 2 × 2 состоит из 8-ми ячеек и содержит в себе 54 ребра.

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

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: m и n.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если заданный блок существует;

0 — в противном случае.

Ограничения

0 < m < 2³², 0 < n < 2⁶⁴

Примеры тестов

8 54

1

6 43

0

Задача D. Нули в окончании числа ≡

Условие

Обозначим за P(A, B) результат произведения всех натуральных чисел от A до B включительно.

Для заданных значений A, B и q требуется определить количество нулевых разрядов, которыми оканчивается q-ичная запись числа P(A, B).

Формат входного файла

Входной файл "input.txt" содержит три натуральных числа: A, B и q.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно единственное число, указывающее количество нулевых разрядов.

Ограничения

0 < A ≤ B < 2⁶⁴, 2 ≤ q < 2³²

Примеры тестов

1 100 10

24

9 75 120

17

Задача E. Натуральные степени ≡

Условие

Требуется подсчитать общее количество пар натуральных чисел (p, n) таких, что p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Формат входного файла

Входной файл "input.txt" содержит два натуральных числа: A и B.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученный ответ.

Ограничения

2 ≤ A ≤ B < 2⁶⁴

Примеры тестов

10 100

13

37 48

0

Задача F. Приведение многочлена ≡

Условие

Пусть имеется многочлен, представленный в следующем виде: C₀ ⋅ (x − C₁) ⋅ …  ⋅ (x − C_n), где все C_i принадлежат кольцу вычетов по некоторому заданному модулю p.

Требуется привести его к каноническому виду: A₀ + A₁ ⋅ x + …  + A_n ⋅ xⁿ.

Формат входного файла

В начале входного файла "input.txt" содержится значение модуля p и натуральное число n. Далее следует набор значений C_i, где i = 0, 1, …, n.

Формат выходного файла

Выходной файл "output.txt" должен содержать массив коэффициентов A_i.

Ограничения

2 ≤ p < 2⁶⁴, 0 ≤ C_i < p, 0 ≤ n ≤ 500

Примеры тестов

100 5
2
13
4
37
6
29

48
68
90
90
22
2

2 4
1
0
1
0
1

0
0
1
0
1

Задача G. Представление дробей ≡

Условие

Пусть имеется некоторая простая дробь, заданная своим числителем A и знаменателем B.
Требуется преобразовать указанную дробь, представив ее в одном из следующих форматов:

• правильная дробь: <числитель> / <знаменатель> ;
• смешанная дробь: <целая_часть> ( <числитель> / <знаменатель> ) ;
• десятичная дробь: <целая_часть>.<дробная_часть> ;
• целое число: <целая_часть> .

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

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

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: A и B.

Формат выходного файла

Выходной файл "output.txt" должен содержать дробь A / B,
отформатированную в соответствии с условием задачи.

Ограничения

0 < (A, B) < 2⁶⁴

Примеры тестов

1736744720710
5067073484375

11977549798 / 34945334375

57295346800
351486000

163 ( 7822 / 878715 )

10298463668
40000000

257.4615917

1675223508
13509867

124

Задача H. Возведение большого числа в степень ≡

Условие

Пусть имеется неотрицательное целое число A, представленное в виде массива своих цифр.
Требуется возвести его в некоторую заданную степень n.

Формат входного файла

Первая строка входного файла "input.txt" представляет собой десятичную запись числа A.
Следующая строка содержит показатель степени n.

Формат выходного файла

Выходной файл "output.txt" должен содержать результат возведения в степень,
представленный в десятичной системе счисления.

Ограничения

0 ≤ A ≤ 10⁵⁰, 0 < n ≤ 1000

Примеры тестов

10203756485819806252197658031528043601970
2

104116646421909761950282879573175588809976767764774752111453905887721451787880900

55786
17

490827381405222212342433355512086149590506305271663102056527621790991920279453696

Задача I. НОД больших чисел ≡

Условие

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

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

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

Формат входного файла

В начале входного файла "input.txt" хранятся два натуральных числа q и n, после чего следует ровно n q-ичных разрядов, для которых требуется решить поставленную задачу.
При этом для обозначения цифр, лежащих в диапазоне от 10 до 35, используются строчные символы латинского алфавита.

Формат выходного файла

Выходной файл "output.txt" должен содержать искомый делитель, также записанный в q-ичной системе счисления.

Ограничения

2 ≤ q ≤ 36, 0 < n ≤ 4000

Примеры тестов

36 41
10360k898faq2lvf8j4rxhifkd9ilnnobm9il766r

6kzw4bjxrz9chm64eqktymn29

2 25
1000000000000000000000000

1000000000000000000000000

Задача J. Возведение числа в большую степень ≡

Условие

Пусть имеются два длинных целых числа A и B, записанные в десятичной системе счисления.

Требуется возвести A в степень B, взяв остаток от деления по модулю P, представленному в виде произведения взаимно простых чисел: P = p₁ ⋅ p₂ ⋅ …  ⋅ p_k.

Полученный результат следует вывести в десятичной системе счисления.

Формат входного файла

Первые две строки входного файла "input.txt" содержат числа A и B.
Далее указано число k, за которым следует ровно k значений p_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученный результат, представленный в десятичной системе счисления.

Ограничения

2 ≤ (A, B) ≤ 10²⁰⁰⁰,

2 ≤ p_i ≤ 10⁹, НОД(p_i, p_j) = 1, ∀ i ≠ j,

1 ≤ k ≤ 10³

Примеры тестов

1234567890
101201230123401234501234560123456701234567801234567890

10
13 47 337501 37 1806000 19 29 11209 79 11013109

48424710506557820285677213386000

30
20

10
13 47 337501 37 1806000 19 29 11209 79 11013109

348678440100000000000000000000

Задача K. Очередь в поликлинике ≡

Условие

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

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени t_i, указанных в талоне каждого i-го пациента, и времени m_i, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

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

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = t_max.

Формат входного файла

В начале входного файла "input.txt" содержится пара натуральных чисел t_max и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел t_i и m_i. При этом полагается, что все они упорядочены по возрастанию t_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать два значения: максимальную длину очереди и время завершения последнего приема.

Ограничения

0 < t_max ≤ 10⁶, 0 < (t_i, m_i) ≤ t_max, t_i < t_i + 1

Примеры тестов

1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3

0 1208

1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3

2 1210

Задача L. Социальная сеть ≡

Условие

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

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

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

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

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

Формат входного файла

В начале входного файла "input.txt" содержится натуральное N — число пользователей в сети.

Далее следует натуральное M после которого идет набор из M записей (A_i, B_i), где A_i и B_i — номера пользователей, связанных отношением дружбы.
При этом полагается, что нумерация пользователей начинается с нуля, где 0 — номер Васи.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученные слои, расположенные в порядке удаленности от Васи и записанные в следующем виде.

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

Ограничения

2 ≤ N ≤ 1000, 1 ≤ M ≤ (N ⋅ (N − 1)) / 2,

A_i ≠ B_i

Примеры тестов

10 12
0 1
0 2
0 3
2 4
3 5
3 6
5 6
6 7
4 8
7 4
1 9
4 3

3 2 3 1
4 9 4 5 6
2 7 8

Задача M. Призовые места ≡

Условие

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

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

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

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

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

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

Формат входного файла

В начале входного файла "input.txt" указано общее число участников n и количество поступающих запросов m.

Далее следует ровно m таких запросов, представленных в виде пар целых чисел: a_i — номер участника; b_i — начисленные баллы/штрафы.

При этом полагается, что нумерация участников начинается с нуля.

Формат выходного файла

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

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

Далее записываются номера соответствующих им участников.

Ограничения

0 < n ≤ 10⁵, 0 < |b_i| ≤ 1000, 0 < m ≤ 2 ⋅ 10⁵.

Примеры тестов

10
8
6 23
0 17
1 20
4 50
1 3
0 6
1 27
0 39

1 6
2 6 0
3 6 1 0
3 4 6 1
3 4 1 6
3 4 0 1
3 1 4 0
3 0 1 4

10
8
4 70
9 56
9 47
4 2
9 -31
9 -72
4 -72
7 13

1 4
2 4 9
2 9 4
2 9 4
2 4 9
1 4
0
1 7

Задача N. Форматированные строки ≡

Условие

Пусть имеются две строки, содержащие набор слов, состоящих из цифр и символов латинского алфавита, и отделенных друг от друга пробелами либо знаками препинания ('-', '.', ',', ':', ';', '!', '?'). Регистр символов, а также количество подряд идущих пробелов роли не играет (любое число пробелов воспринимается как один символ). Пробелы, расположенные по краям строки либо отделяющие знаки препинания, игнорируются.

Для определения формата текста в пределах каждой такой строки используются теги следующих видов:

<b>текст</b> — жирный шрифт;

<i>текст</i> — курсив.

Также допускается использование нескольких вложенных друг в друга тегов. При этом внутренний тег сохраняет форматирование внешнего фрагмента.

Теги могут разбивать слово на части: <i><b>тек</b>ст</i>. В этом случае, отдельные части слова будут иметь различное форматирование.

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

Требуется сравнить две такие строки.

Формат входного файла

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

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

2 — текст в обеих строках совпадает и имеет одинаковый формат;

1 — текст в обеих строках совпадает, но имеет разный формат;

0 — обе строки содержат разный текст.

Ограничения

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

Длина каждой строки не превосходит 3 ⋅ 10⁶.

Примеры тестов

<i>THIS </i><i>IS   <b>SPARTA!!!</b></i>
<i>this   is    <b>Sparta  ! !!</b></i>

2

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>this is</i> <b>Sparta!!!</b>

1

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>This Is   <b>Sparta!</b></i>

0

Задача O. Константные выражения ≡

Условие

Пусть имеется программа, записанная на императивном языке программирования, поддерживающем команды следующего вида:

<переменная> = <выражение> — присвоить переменной результат заданного выражения.

Выражение может состоять из арифметических операций ('+', '-', '*', '/'), круглых скобок, переменных и целочисленных констант. Между ними также допускается произвольное число пробелов. При этом знак минуса используется здесь для обозначения как бинарной, так и унарной операции. Операции ('+', '-') имеют меньший приоритет, чем ('*', '/'). Операции, обладающие одинаковым приоритетом, выполняются слева направо.

В качестве имен переменных выступают символы латинского алфавита (регистр их написания неважен). Полагается, что все они принадлежат к знаковому 32-разрядному целому типу и могут принимать значения из диапазона от  − 2³¹ до 2³¹ − 1. Константы представляют собой числа, записанные в десятичной системе счисления и лежащие в диапазоне от 0 до 2³¹ − 1.

Изначально всем переменным присваиваются нулевые значения. Арифметическое переполнение и деление на ноль приводят к неопределенному результату, для обозначения которого используется символ '#' (ASCII 35). Все операции с неопределенным значением (кроме умножения на ноль) также возвращают '#'.

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

Формат входного файла

Во входном файле "input.txt" построчно содержатся команды указанного языка.

Формат выходного файла

В выходной файл "output.txt" следует вывести пары: <переменная> <значение>. При этом переменные, которые отсутствуют в левых частях выражений, могут быть проигнорированы.

Ограничения

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

Число открывающихся скобок также ограничено и не превосходит 30.

Входная программа состоит как минимум из одной команды. Общее число команд не превосходит 1000.

Примеры тестов

i = 1045
B = (a + i) * 23 - 190
c = B
i = - 4 + i / 10
c = i - 138

b 23845
c -38
i 100

i = B + 14903 * A
B = 100 / (i * 2)
C = b /(c +a * E)
i = i - u * C
B = i + 350

b 350
c #
i 0

Задача P. Число вхождений подстроки ≡

Условие

Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.

Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.

Формат входного файла

В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.

Формат выходного файла

Выходной файл "output.txt" должен содержать число найденных подстрок.

Ограничения

0 < |T| ≤ 5 ⋅ 10⁴, 0 ≤ |S| ≤ 2 ⋅ 10⁷

Примеры тестов

ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ

4

ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+

5

Задача Q. Перемешанные символы ≡

Условие

Пусть имеется текстовая строка, состоящая из произвольных печатных символов (ASCII 33-126).

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

Формат входного файла

Входной файл "input.txt" содержит исходную строку.

Формат выходного файла

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

В случае, если это невозможно, выходной файл следует оставить пустым.

Ограничения

Полагается, что длина исходной строки
лежит в диапазоне от 1 до 2 ⋅ 10⁷.

Примеры тестов

AAAAAbbbbbaaaaaAAAaaaacccAAcccbb

aAabcAabcAabcAabcAabcAabAaAaAbAc

32213312222222032022992211222222

Задача R. Разноцветные кубики ≡

Условие

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

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

Формат входного файла

В заголовке входного файла "input.txt" хранится число доступных разновидностей наклеек n. Далее следует набор из n значений A_i, указывающих число наклеек каждого вида.

Формат выходного файла

Выходной файл "output.txt" должен содержать максимально возможное число кубиков.

Ограничения

0 < n ≤ 10⁶, 0 < A_i ≤ 10⁹

Примеры тестов

8

23
31
742
4
5
84
6
19

6

5

12
145
7
94
2

0

Задача S. Палиндромная сортировка ≡

Условие

Для строки S = S₁, S₂, …, S_m определим коэффициент ее палиндромности: q[S] = k / m, где k — максимальное число позиций i в которых выполняется условие: S_i  =  S_{m − i + 1}.

Так, например, для строк "abcba" и "abba" коэффициент палиндромности равен 100%. В то время, как для строк "abdca" и "abca" — 60% и 50% соответственно.

Требуется выполнить сортировку заданного набора слов по убыванию коэффициентов их палиндромности.

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

Формат входного файла

В начале входного файла "input.txt" хранится натуральное число n. Далее следует набор из n слов, состоящих из цифр и строчных букв латинского алфавита.

При этом каждое такое слово располагается в отдельной строке.

Формат выходного файла

Выходной файл "output.txt" должен содержать индексы исходных слов, расположенные в порядке их следования в отсортированном массиве.

При этом полагается, что нумерация слов начинается с нуля.

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 500.

0 < n ≤ 5 ⋅ 10⁴

Примеры тестов

10
76i3600c1
8r2xsdc44cdsxsr8
7q9wxw9q7
alf4dx3d3xdgfla
njuuiuiui0n
ierxx0es
s028338u0s
nac9ps4can
t44agihgh44t
3vtkbbkv3

2
1
3
6
8
4
7
9
5
0

10
15nuie40t04eiun51
l8320aa0138l
20qwzwq02
a
2e1ff1e2
4euee33e7ue4
e80t
6fesehtesif6
ml
i42iirptub

0
2
3
4
1
5
7
6
8
9

Задача T. Сортировка записей ≡

Условие

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

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

При сравнении отдельных полей необходимо придерживаться следующих правил: вещественные значения должны быть упорядочены по возрастанию; знаковые целые — по убыванию; беззнаковые — по возрастанию; символьные значения — по убыванию своих позиций в таблице ASCII; упорядочение строк производится по возрастанию (в лексикографическом порядке).

Формат входного файла

В первой строке входного файла "input.txt" содержится пара натуральных чисел n и m, указывающих общее количество таких записей и число их полей. Во второй строке содержится массив из m символьных значений (разделенных пробелами), указывающих тип каждого поля в соответствии со следующей таблицей:

• 'd' — вещественное число, записанное с точностью до 5-го знака после запятой;
• 'i' — целое знаковое число, лежащее в диапазоне от -2⁶³ до 2⁶³-1;
• 'u' — целое беззнаковое число, лежащее в диапазоне от 0 до 2⁶⁴-1;
• 'c' — символьное значение (ASCII 32-126);
• 's' — строка (содержит от 0 до 24 символов).

Далее следует массив из m целых чисел p_i, устанавливающих приоритеты указанных полей. Начиная с четвертой строки располагается массив записей. При этом значение каждого поля занимает ровно одну строку.

Формат выходного файла

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

Ограничения

n ≤ 2 ⋅ 10⁴, m ≤ 10, 0 ≤ p_i < 10

Примеры тестов

5 4
i s d c
2 9 7 0
-1
QWERTY
3.90000
a
-9
ASUS
0.47000
t
75
QWERTY
0.10000
x
9
ASKOLD
8.05000
b
0
ASUS
-0.00075
y

3
4
1
2
0

5 4
i u d c
9 8 1 3
-1
48
-3.50000
a
-9
15
0.90000
w
-9
10
4.70000
b
-1
48
-0.70000
z
-1
48
1.56000
p

3
4
0
2
1