Problem A. Appropriate names ≡

Statement

A company wants to name a new product. Marketing department determined, that a name for a product is appropriate, if:

1. it consist of exactly N small English letters;
2. it has alternating vowels and consonants;
3. it does not contain any of given M offensive substrings.

Your program must calculate the number of possible appropriate names. Note that English vowels are: 'a', 'e', 'i', 'o', 'u', 'y'.

Input file format

First line of input file contains two integers N M — name length and number of offensive substrings.

Following M lines contain offensive substrings s_i, one per line.

Output file format

Output file must contain a single integer — number of appropriate names modulo 10⁹ + 7.

Constraints

1 ≤ N ≤ 50, 0 ≤ M ≤ 50, 1 ≤ length(s_i) ≤ N.

Sample tests

2 3
b
ca
b

227

5 0

374400

Задача B. Binary king ≡

Условие

Юная разработчица компьютерных игр Алиса создала новую игру и разослала её друзьям на бета-тестирование.

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

На последнем уровне Вася столкнулся с главным боссом — Бинарным королём. В начале боя Бинарный король игры генерирует последовательность K из N двоичных цифр. После этого Вася должен предоставить свою бинарную последовательность V такой же длины.

Васина последовательность оценивается следующим образом. Для каждой позиции i, если V_i = 1 и K_i = 0, Вася получает 1 балл; если V_i = 0 и K_i = 1, Вася теряет 2 балла.

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

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

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

Входной файл содержит N символов 0 или 1 — последовательность Короля.

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

Выходной файл должен содержать N символов 0 или 1 — последовательность Васи, набирающую наибольшее количество баллов. Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵

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

111111111111

000000111111

111011001000

001011001011

Problem C. Covering the ring ≡

Statement

Let us consider a rectangular domain D = {(x, y): Ax ≤ x ≤ Bx, Ay ≤ y ≤ By} covered by the uniform grid (two-dimensional array of cells):

Ω_{i j} = {(x, y): x_i < x < x_i + 1, y_j < y < y_j + 1}, where x_i = Ax + (i − 1) ⋅ Sx, y_j = Ay + (j − 1) ⋅ Sy, i = 1, 2, …, Nx, j = 1, 2, …, Ny,

Sx = (Bx − Ax) / Nx, Sy = (By − Ay) / Ny — grid steps for x and y respectively.

The grid is defined by four real parameters (Ax, Ay, Sx, Sy) and two integer parameters (Nx, Ny).

Note that cells are open rectangles not including their boundaries.

Your program must count grid cells that have common points with the ring defined by its center (x₀, y₀), internal and external radius (r₁, r₂).

Input file format

Input file contains parameters of the grid: Ax, Ay, Sx, Sy, Nx, Ny, followed by parameters of the ring: x₀, y₀, r₁, r₂.

Output file format

Output file must contain a single integer — number of cells intersecting the ring.

Constraints

All input values have no more than 5 digits after the decimal point.

 − 10 < (Ax, Ay) < 10, 1 ≤ (Bx − Ax) < 10, 1 ≤ (By − Ay) < 10, 0 < (Nx, Ny) ≤ 10⁶,

 − 10 < (x₀, y₀) < 10, 0 ≤ r₁ ≤ r₂ < 10

Sample tests

-1.00000 -1.00000 0.12500 0.12500 16 16
 0.00000  0.00000 0.50000 0.90000

160

 0.00000  0.00000 0.05000 0.07143 20 14
 0.00000  0.00000 0.20000 0.74000

128

Problem D. Document signing ≡

Statement

You have a document that needs to be signed by university president. It's hard to get president's time, but luckily you know his current location in the university campus. You also know that he is heading to his office now, so you can try to intercept him on the way and ask for a signature. Even more, everyone at university knows that president always takes fastest path wherever he goes. However, if there are several fastest paths, the president chooses any of them.

You need to write a program that determines whether you can guarantee meeting the president no matter which of the fastest path he picks, if you start moving from your room at the same time as the president.

More formally, university campus map is given as an undirected graph. i-th edge is given by its vertices (a_i, b_i) and traversal time t_i (this is a traversal time for any human, either you or the president). Initially, the president is located at vertex p₁ and is taking one of the fastest paths to his office located at vertex f. You are initially located at vertex p₂. You can get the signature if you meet the president at vertex v such that:

• The president is guaranteed to go through v on his way to the office.
• You can get to v not later than he.

Input file format

Input file starts with two integers: n — the number of vertices and m — the number of edges.

Then m edges are given by integers a_i, b_i, t_i. Vertices are numbered starting from 0.

Finally, there are three integers f, p₁, and p₂.

Output file format

Output file must contain the number of vertices where it is possible to get the signature, followed by the list of vertex numbers in ascending order.

Constraints

It is guaranteed that the graph is connected, i.e. it's possible to get from any vertex to any other vertex.

There is no more than one edge between each pair of vertices (a_i, b_i).

2 ≤ n ≤ 1000, 1 ≤ m ≤ n(n − 1) / 2

0 ≤ a_i, b_i, p₁, p₂, f < n

a_i ≠ b_i, p₁ ≠ p₂

0 < t_i ≤ 1000

Sample tests

8 9

0 1 1
5 1 1
5 6 2
6 4 3
5 4 7
1 2 2
2 4 4
3 7 5
7 4 6

3
0
5

4
1 3 4 7

8 9

5 6 1
6 4 4
0 1 2
1 7 1
7 2 2
1 4 4
1 2 4
4 2 1
2 3 7

3
0
5

0

Задача E. Emitting light ≡

Условие

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

Маша расположила лазер в точке с координатами (0,y) и направила лазерный луч в направлении (1,  − 1). Маша хочет подобрать расстояние между зеркалами h так, чтобы луч прошёл через точку с координатами (x_t,y_t). Сам лазер при этом должен находиться внутри волновода, то есть h ≥ y. Лазерный луч всегда отражается от зеркал под углом в 45 градусов.

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

Входной файл содержит три целых числа: y, x_t, y_t — координаты лазера и цели.

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

Программа должна вывести единственное целое число — значение h, при котором лазерный луч пройдёт через цель. Если есть несколько решений, выведите минимальное возможное значение h. Если решений нет, выведите одно число  − 1.

Ограничения

1 ≤ y, x_t, y_t ≤ 10⁹

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

5 2 2

-1

5 6 1

5

2 16 2

2

Problem F. Fixing lottery ≡

Statement

Well-known store chain "Three cats" decided to create a marketing lottery. Customers were given tickets with sequential integer numbers, and each month a single ticket number was selected as a winner.

To promote company image, it was decided that winning number must be divisible by 3.

For the first month of the lottery, company selected a ticket and printed it on a large banner to hang inside the store. Unfortunately, a person from marketing who selected a ticket did not know math, and selected ticket number which is not divisible by 3.

To quickly fix the banner, your program must change exactly one digit in the number so that:

1. Result is divisible by 3.
2. Result is less than original number.
3. Result has no leading zeroes.

Input file format

Input file contains a string of N decimal digits. First digit is non-zero.

Output file format

Output file must contain a string of N decimal digits — fixed ticket number. If there is more than one solution, output numerically smallest of them. If there is no solution, output string IMPOSSIBLE.

Constraints

2 ≤ N ≤ 100

Sample tests

13

12

200

IMPOSSIBLE

55

15

Problem G. Gathering ants ≡

Statement

Let us consider 3-dimensional area that is split by uniform rectangular grid. Some cells contain ants. Each second every ant can either stay put or move to the neighboring cell in any of the six directions: up, down, right, left, forward and backward.

Your program must, given coordinates of starting cell for each ant, find minimum possible number of seconds (starting from zero) until any two ants meet in the same cell.

Input file format

Input file contains integer N followed by N triples of integer indices X_i, Y_i, Z_i — coordinates of starting cells for each ant.

Output file format

Output file must contain a single integer — minimal number of seconds until two ants meet.

Constraints

 − 10⁶ ≤ (X_i, Y_i, Z_i) ≤ 10⁶, 2 ≤ N ≤ 5 ⋅ 10⁴

Sample tests

5
1 19 37
-9 5 10
4 3 6
9 8 7
17 20 5

6

5
6 49 58
-9 -1 3
2 8 9
-1 2 0
2 8 9

0

Задача H. Horticulture ≡

Условие

Юный программист Джеймс решил заняться садоводством и принёс домой N растений в горшках.

Растение номер i изначально имеет высоту a_i и растет со скоростью v_i сантиметров в день. У Васи есть девушка, Алиса, которая пока находится в отъезде. Алиса не любит высоких растений, поэтому Вася решил время от времени обрезать растения.

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

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

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

Первая строка входного файла содержит целые числа N, T, M, X.

Вторая строка содержит N целых чисел a_i — начальные высоты растений.

Третья строка содержит N целых чисел v_i — скорости роста растений в день.

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

Выходной файл должен содержать единственное целое число — минимально возможный уровень самого высокого растения через T дней.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ T ⋅ M ≤ 10⁵

1 ≤ X, a_i, v_i ≤ 10⁵

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

4 1 2 4
8 9 10 11
8 8 3 2

13

1 100000 1 100000
100000
100000

100000

Задача I. Implicit array ≡

Условие

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

Напишите программу, которая восстановит массив в явном виде (все элементы по порядку).

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

Первая строка входного файла содержит целое число N — количество элементов в массиве.

Следующие N строк содержат неявные описания элементов массива: размер множества s_i и s_i различных целых чисел a_ij — множество, состоящее из i-го элемента массива и его соседей.

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

Выходной файл должен содержать N целых чисел — элементы исходного отсортированного массива.

Ограничения

1 ≤ N ≤ 10⁵

 − 10⁹ ≤ a_ij ≤ 10⁹

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

7
1 1
1 1
2 1 2
2 1 2
2 2 3
2 2 3
1 3

1 1 1 2 2 3 3

1
1 7

7

Problem J. Jubilees ≡

Statement

Let's define that a positive integer is a jubilee if it is divisible by 5 and is no less than 10. (i.e. 10, 15, 20, …).

Your program must, given a sequence of N decimal digits, find maximum number of jubilees which can be made by splitting this sequence into disjoint subsequences. In other words, every digit of sequence must be used no more than once and original order of digits must be preserved.

In the first sample, sequence 2535 can be split into 25 and 35.

In the second sample, sequence 1115005000 can be split into 10, 10, 10, 50 and 50.

Input file format

Input file contains a string of N decimal digits. First digit is non-zero.

Output file format

Output file must contain a single integer — number of jubilees.

Constraints

1 ≤ N ≤ 100

Sample tests

2535

2

1115005000

5

Problem K. K ≡

Statement

Your program must output large letter 'K'.

Letter is drawn using '#' (ASCII 35) characters and is composed of vertical line of V characters, upper diagonal of H characters, and lower diagonal of L characters.

Letter image must be the smallest possible rectangle including the letter. Parts of rectangle not occupied by the letter must be filled with '.' (ASCII 46) character.

Input file format

Input file contains three integers V H L.

Output file format

Output file must contain letter image.

Constraints

3 ≤ V ≤ 20

1 ≤ H, L ≤ 20

Sample tests

6 3 2

...#
#.#.
##..
#...
##..
#.#.
#...

7 1 2

#..
#..
##.
#..
##.
#.#
#..