Задача A. Износ клавиатуры ≡

Условие

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

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

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

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

Первая строка входного файла содержит целое число n — количество клавиш на клавиатуре. Вторая строка содержит n целых чисел — c₁, c₂, …, c_n, где c_i — количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k — общее количество нажатий клавиш, и последняя строка содержит k целых чисел p_j (1 ≤ p_j ≤ n) — последовательность номеров нажатых клавиш.

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ k, c_i ≤ 10⁵

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

5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

yes
no
no
no
yes

Задача B. Неправильное сложение ≡

Условие

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

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

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

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

Входной файл содержит целые числа a b c.

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

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

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

Ограничения

1 ≤ a, b, c ≤ 10⁶

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

30 239 566

YES
7945
71215

643 733 553

NO
18129

Задача C. Сплошные числа ≡

Условие

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

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

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

Примечание

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

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

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

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

Ограничения

1 ≤ n ≤ 50000

1 ≤ C ≤ 10⁸

1 ≤ k ≤ 18

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

3 11 2
111

3

19 9 1
0123456789876543210

1

1 8 3
9

0

Задача D. Перестановки с НОД ≡

Условие

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S =  {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} — нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой — множество {9, 3, 6, 8}.

Примечание

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

Входной файла содержит целые числа числа — n m k, за которыми следуют n различных натуральных чисел s_i.

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

Выходной файл должен содержать m-ую k-перестановку заданного множества или  − 1, если такой нет.

Ограничения

1 ≤ n ≤ 16

1 ≤ m, k, s_i ≤ 10⁹

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

4 1 2
6 8 3 9

3 9 6 8

4 4 2
6 8 3 9

9 3 6 8

4 5 2
6 8 3 9

-1