Problem 0A. Astrological prediction ≡

Statement

Astrologer Timofey considers a year to be happy if different consecutive digits are used in its notation. For example, the nearest such year will occur in 2031. Determine, by the year number, how many years it will take for a happy year to come?

Input format

The input consists of a single line containing a natural number n — the year number.

Output format

Output a single non-negative integer — the answer to the problem.

Constraints

1 ≤ n ≤ 9876543210

Sample tests

2023

8

2031

0

Problem 0B. Bricks in the wall ≡

Statement

Let's consider a set of n two-dimensional bricks with arbitrary widths W_i and height 1.
It is required to build a wall of width L and maximum possible height (but no greater than 5) using minimum possible count of the bricks.

The bricks are arranged in layers, and each layer should be fully filled, meaning no gaps between bricks are allowed.

One is not allowed turn the bricks. They all should remain a horizontal position.

Input format

The input contains the number n, followed by exactly n integers W_i representing the widths of the bricks.
Next is the number L specifying the width of each layer.

Output format

The output should contain a sequence of brick numbers, arranged in the order of layer formation:
the bricks of the first layer, followed by those of the second layer, and so on.
It is assumed that the bricks are numbered starting from zero.

Constraints

0 < W_i ≤ L ≤ 20, 0 < n ≤ 100

Sample tests

8
1 2 5 1 4 1 3 1
5

4 7 1 6 2

7
1 2 5 5 2 3 3
6

5 6 0 3

6
1 1 1 1 1 1
7

Problem 0C. Counting ones ≡

Statement

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

The jury has a two-dimensional matrix with N rows and M columns filled with numbers, where each number can be either 1 or 0. Rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to M from left to right.

Your program can make queries of the form "? Xi Yi Ai Bi", where i is the query number, X_i, Y_i represent the coordinates of the top-left corner of the rectangle, denoting the row and column numbers, respectively. On the other hand, A_i, B_i indicate the dimensions of the rectangle, representing the number of rows and columns, respectively. In response to the query, the jury's program will report the number of ones in the rectangle specified by the query.

Each rectangle must be entirely within the matrix, meaning the following inequalities must be satisfied:

1 ≤ X_i, A_i ≤ N and 1 ≤ Y_i, B_i ≤ M

X_i + A_i − 1 ≤ N and Y_i + B_i − 1 ≤ M

There are also constraints on the sizes of rectangles. The first rectangle must be smaller than the matrix on each side without considering orientation, and each subsequent rectangle must be smaller than the previous one on each side without considering orientation. More formally, the following inequalities must be satisfied:

min(A₁, B₁) < min(N, M) and max(A₁, B₁) < max(N, M)

min(A_i, B_i) < min(A_i − 1, B_i − 1) and max(A_i, B_i) < max(A_i − 1, B_i − 1) by i > 1

The goal is to determine the number of ones in the matrix by making any number of queries. It is guaranteed that the values in the matrix are predefined and do not depend on the queries.

Input format

The first line of input contains two integers N and M, the dimensions of the matrix.

Interaction protocol

To make the i-th query, your program should output "? Xi Yi Ai Bi", where X_i, Y_i are integers, the coordinates of the top-left corner of the rectangle, row and column numbers respectively. On the other hand A_i, B_i are integers, the dimensions of the rectangle, representing the number of rows and columns, respectively.

After the query, the jury's program responds to your program with an integer S, the number of ones in the specified rectangle.

When your program determines the answer to the task, it should output "! S", where S is an integer, the number of ones in the matrix. After outputting the answer, the program should terminate.

If your program makes incorrect query, it will receive "Presentation error" verdict.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Constraints

10 ≤ N, M ≤ 100

0 ≤ S ≤ 10⁴

Notes on samples

The matrices from the examples are represented in the picture.

Sample tests

11 13

34

0

0

? 1 1 10 12

? 1 11 11 3

? 10 1 2 10

! 34

10 10

38

28

23

16

13

5

3

3

0

? 1 2 9 9

? 3 1 8 8

? 4 2 7 7

? 2 4 6 6

? 5 5 5 5

? 3 7 4 4

? 8 8 3 3

? 1 1 2 2

? 10 10 1 1

! 44

Problem 0D. Doubly-periodic world ≡

Statement

The scientists of Flatland have discovered that the universe they live in is topologically similar to the surface of a torus.

This means that along each coordinate axis x and y, the periodicity condition is satisfied with a respective period Lx and Ly.
In other words, points at coordinates (x + u ⋅ Lx, y + v ⋅ Ly) with any integer values u and v are identical.

For the purpose of a scientific experiment, a ray is emitted from a point with coordinates (0, 0), directed by the vector D⃗ = (dx, dy).
It is required to determine the distance the ray will travel before reaching the initial point.

The result should be expressed in units equal to the length of the vector D⃗,
In other words, the task is to find the minimum coefficient λ  > 0, such that by shifting the vector, one can reach the initial point.

The obtained number should be represented as an irreducible fraction: λ  = αβ.

Input format

The beginning of the input data contains a natural numbe n, followed by exactly n queries,
each specified by a set of integers: Lx_i, Ly_i, dx_i и dy_i.

Output format

The output data should contain the values α_i и β_i,
obtained in response to each i-th query.

Constraints

1 ≤ (Lx_i, Ly_i) ≤ 10⁶,  − 10⁶ ≤ (dx_i, dy_i) ≤ 10⁶, |dx_i| + |dy_i| > 0,
1 ≤ n ≤ 10⁵.

Sample tests

4

17 18 -6 -8
15 16 6 8
13 14 4 0
10 12 0 2

153 2
10 1
13 4
6 1

Problem 0E. Erasing numbers ≡

Statement

In the research institute where Timofey works, a successful study of the sequence of natural numbers is underway. Every day, his colleagues discover new and new properties of this sequence, and Timofey tries to keep up with them. Today, as usual, Timofey wrote down a row of natural numbers from 1 to n on the board and tries to answer the question of whether it is possible to erase several (at least one) consecutive numbers in the middle of the list so that the sum of the remaining numbers on the left is equal to the sum of the remaining numbers on the right.

Input format

The input consists of a single line containing a natural number n.

Output format

The output should include a non-negative integer, representing the number of different ways to erase numbers.

Constraints

3 ≤ n ≤ 10⁵

Explanations for examples

In the first example, n = 5. Let's list all the ways to erase numbers in the middle of the row:

• 1 # 3 4 5
• 1 2 # 4 5
• 1 2 3 # 5
• 1 # # 4 5
• 1 2 # # 5
• 1 # # # 5

In none of them does the required property hold.

In the second example, n = 21. Let's list all the good ways to erase numbers in the middle of the row:

• 1 2 3 4 5 6 # # # ## ## ## ## ## ## ## ## ## ## ## 21
• 1 2 3 4 5 6 7 8 9 10 11 12 ## ## ## ## ## 18 19 20 21

In the first list, the sum of the numbers on the left and right is 21, in the second — 78. There are two ways in total.

Sample tests

5

0

21

2

Problem 0F. Flag of Chita ≡

Statement

The flag of Chita is a rectangular cloth divided into four elements. The ratio of the width of the flag to its length is 2:3. In the hoist part of the flag is an equilateral triangle of yellow color, which has a base equal to the width of the flag (vertical size of the cloth) and a height equal to half of its length (horizontal size of the cloth). The triangle is flanked by equal-sized stripes of green, white, and red colors.

The colors of the flag reflect the colors of the coat of arms of the urban district of "City of Chita", carrying the traditional heraldic meaning:

• yellow (gold) — a symbol of wealth and justice;
• red (crimson) — a symbol of courage, bravery, and fearlessness;
• green (greenery) — a symbol of hope, joy, and abundance;
• white (silver) — a symbol of purity, perfection, and independence.

A flag of Chita with height of h is drawn on the coordinate plane as shown in the figure (in the first quadrant, the lower left corner coincides with the origin). Determine the color of the point with the specified coordinates.

Input format

Three lines of the input file contain three natural numbers, separated by a space: h - the height of the flag, as well as x and y — the coordinates of the point. It is guaranteed that h is divisible by 12.

Output format

Print Green, White, Red or Yellow — the answer to the problem. Print Line if the point lies on the boundary of the flag or on the line separating two or three colored areas.

Constraints

12 ≤ h ≤ 10⁹

0 ≤ x ≤ 3 × h2

0 ≤ y ≤ h

Example explanation

See the picture.

Sample tests

12
17
7

White

Problem 0G. Grading ≡

Statement

In the class, there are N students, conveniently numbered from 1 to N.

One day, the computer science teacher gave a very challenging test. Naturally, some students will copy it, while others will attempt it independently and receive the maximum score (the school uses a K-point grading system, meaning a student can receive a grade as a natural number in the range from 1 to K). However, if student U copies from student V, and student V's score is X, then student U's score will be X − 1 (if X = 1, then the student will receive a grade of 1, as there is no lower grade).

Due to the limited time for the test, it could happen that the first student copied from the second, the second copied from the third, ..., the T-th copied from the first. In this case, all students would have empty answer sheets, and therefore, they would receive a grade of 1.

You know who copied from whom. Help the class and determine the grade each student will receive!

Input format

The first line contains natural numbers N и K — the number of students and the grading system value. The next line contains a sequence A of N natural numbers, where the i-th number indicates that the i-th student copied from the A_i-th student.

Output format

In a single line, output N numbers, where the i-th number indicates the grade received by the i-th student.

Constraints

1 ≤ K ≤ N ≤ 10⁵, 1 ≤ A_i ≤ N

Example explanation

The first student copied from the second, the second copied from the fourth, the fourth copied from the first. These three students received a grade of 1. The third student did the work independently and received a grade of 3, while the fifth copied the work from the third and received a grade of 2.

Sample tests

5 3
2 4 3 1 3

1 1 3 1 2

Problem 0H. Historical search ≡

Statement

Young historian Vasya, as part of his dissertation work, is engaged in comparing records from documents stored in the archive.

Each document covers a specific time interval and contains information about events that occurred during that time.

Vasya is interested in how the same event was covered in different sources.

To achieve this, he has to search for documents each time that could contain a record of the event he is interested in.

As there could be too many such events, you are required to write a program that, for a given event, would perform a search for all relevant documents.

Input format

At the beginning of the input data there is a natural number N, followed by 2 × N integers specifying the time interval [A_i, B_i] for each document.

Then, there is a number M and exactly M queries containing the time of the event C_j.

Output format

The output data should contain a set of answers to each of these queries.
It starts with the number of detected documents, followed by their numbers.

It is assumed that the numbering of documents starts from zero.

Constraints

Constraints: The total number of documents in the output does not exceed 10⁶.

 − 10⁶ ≤ A_i ≤ B_i ≤ 10⁶,  − 10⁶ ≤ C_j ≤ 10⁶, 1 ≤ N ≤ 2 ⋅ 10⁴, 1 ≤ M ≤ 10⁵

Sample tests

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

8
-1
 0
 2
 3
 1
-2
 4
 5

3 0 1 2
2 0 2
1 4
2 4 5
0
0
1 3
0

Problem 0I. Image correction ≡

Statement

Matrix of camera represents a rectangular table of dimensions [n × m], consisting of photosensitive elements (cells). At the moment of shooting, each cell of this table is assigned a real value X_{i j}, indicating its state (intensity).

It is known that when reading the state of a particular cell, a weighted sum of the states of the surrounding cells is added to it, forming an ordered set of layers (see the figure). In this case, each subsequent layer has half the influence of the previous one.

The influence coefficient of each such cell on the obtained value is equal to 1 / (2^l ⋅ N_l), where l is the number of the layer containing it, and, N_l is the number of cells in the l-th layer.

Also, for a separately taken camera model, the maximum number of layers k, influencing the measurement result is known.

For a given matrix Y, obtained as a result of measurements and an impact radius k it is required to restore the original values X_{i j}.

The values of dummy cells (located outside the matrix) are considered to be zero.

Input format

At the beginning of the input data three natural numbers are stored: n, m и k. Then follows the matrix of measurement results Y, recorded in row format.

Output format

The output data should contain the restored matrix X. All values should be specified with an accuracy of up to 5 decimal places.

Constraints

0 ≤ Y_{i j} ≤ 10, 0 < n ⋅ m ≤ 40 000, 0 < k ≤ 6

Sample tests

9 6 3
0.26620 1.51042 0.59606 2.85301 0.76968 3.75000
1.51042 0.67130 3.09027 1.05324 4.38657 0.90856
0.59606 3.09027 1.13426 4.57754 1.29629 5.21412
2.88194 1.08217 4.61805 1.42940 5.60763 0.91435
0.87384 4.51388 1.43518 5.72916 1.08796 1.78819
4.13773 1.31944 5.72916 1.18055 2.03704 0.58449
0.98958 5.53819 1.12847 2.10648 0.76389 2.69097
4.98842 0.92592 1.98495 0.76389 2.95717 0.61343
0.49190 1.63773 0.54398 2.69097 0.61343 3.59375

0.00000 1.11111 0.00000 2.22222 0.00000 3.33333
1.11111 0.00000 2.22222 0.00000 3.33333 0.00000
0.00000 2.22222 0.00000 3.33333 0.00000 4.44444
2.22222 0.00000 3.33333 0.00000 4.44444 0.00000
0.00000 3.33333 0.00000 4.44444 0.00000 1.11111
3.33333 0.00000 4.44444 0.00000 1.11111 0.00000
0.00000 4.44444 0.00000 1.11111 0.00000 2.22222
4.44444 0.00000 1.11111 0.00000 2.22222 0.00000
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333

Problem 0J. Javelin-throwing ≡

Statement

Once upon a time, Eugene and Angelica found themselves at a javelin throwing competition as spectators. N athletes were participating in the competition.

Each time the i-th athlete threw the javelin, Eugene would inform Angelica about the distance the athlete threw the javelin (it happened that all the numbers Eugene mentioned were pairwise distinct). At the same time, Angelica recorded on a piece of paper the place that the i-th athlete would take after their throw.

Unfortunately, when the competition ended, Angelica lost the sheet of paper and was very upset. But Eugene remembers how many meters each athlete threw their javelin. Help the kids restore the lost sheet!

Input format

The first line of input contains a natural number N — the number of athletes.

The second line contains a sequence of distinct natural numbers L, where L_i — is the number indicating how many meters the i-th athlete threw their javelin.

Output format

In a single line, output a sequence of N natural numbers, where the i-th number indicates the place that the i-th athlete takes after their throw.

Constraints

1 ≤ N ≤ 10⁵, 1 ≤ L_i ≤ 10⁹

Example explanation

The first athlete threw the javelin and became the first in the list. The second athlete threw the javelin farther than the first and became the first in the list. The third athlete threw farther than the first but closer than the second, so the third became the second in the list. The fourth athlete threw farther than the first but closer than the second and the third, so the fourth became the third in the list.

Sample tests

4
20 40 30 25

1 1 2 3

Problem 0K. Kind of cheating ≡

Statement

Paulundra is participating in speed climbing competitions. This discipline involves participants undergoing qualification rounds, followed by paired races. The following rules apply during a paired race:

• If one participant in the paired race falls, they lose.
• If both participants finish, the participant with the better time wins.
• In case of equal times or if both participants fall, the participant with the better qualification time wins.

Paulundra won the qualification with the best time and observed the strategy of each of the n participants in the competition. She knows that participant number i plans to complete the route in t_i seconds and knows the probability in percentage that this participant will fall p_i. Paulundra also knows that she can complete the route in any time between a and b, and the probability of falling at the chosen time x can be calculated as 1 − x − ab − a.

Help Paulundra choose the optimal time x_i for each opponent so that the probability of Paulundra's victory is maximized. If there are multiple optimal times, choose the one that is smaller.

Input format

The first line of input contains two integers a and b. The second line of input contains an integer n. The following n lines each contain two integers t_i and p_i.

Output format

Output n integers x_i.

Constraints

1 ≤ n ≤ 10⁵

1 ≤ a, b, t_i ≤ 10⁹

1 ≤ p_i ≤ 100

a < b

Sample tests

1 5
5
4 10
10 50
1 99
5 50
2 90

4
5
1
5
2

Problem 0L. Long-term activity ≡

Statement

On the board, a natural number is written. Timofey wants to maximize this number, meaning he wants all nines to be at the beginning, followed by eights, and so on. In one operation, he can swap any two adjacent digits of the number. Determine the minimum number of operations he needs to achieve this goal.

Input format

A single line of input contains a natural number n.

Output format

Output a single non-negative integer, the answer to the problem.

Constraints

1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰.

Example explanation

Initial string: 2023.

1) 2032.

2) 2302.

3) 3202.

4) 3220.

Sample tests

2023

4

Problem 0M. Must be excluded ≡

Statement

Elephant Pakhom is a novice developer. Pakhom's first task at his new workplace is to develop a program for removing personal data from text composed of Latin alphabet letters, digits, and spaces.

Personal data in this context consists of two consecutive numbers separated by a space, where the first number comprises four digits, and the second number comprises six digits (passport series and number, respectively). They need to be replaced with the character sequence "#### ******".

Pakhom smoothly handled this task. Now it's your turn.

Input format

The input contains a single line S.

Output format

Print the line S after deleting personal data.

Constraints

1 ≤ |S| ≤ 1000

Sample tests

My passport details are 1234 533224 please do not distribute them

My passport details are #### ****** please do not distribute them

A826 B1234 654321 fgfgh 3333 456789s 5432 123456 0000 000000 56554 34534 2344 32456 0000 000000

A826 B1234 654321 fgfgh 3333 456789s #### ****** #### ****** 56554 34534 2344 32456 #### ******

Задача 1A. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

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

4 4 4 4 5 8 8 8 8 8 8 6

Задача 1B. Ближайшее число ≡

Условие

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

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

Входной файл содержит целое число N за которым следует N целых чисел a_i - исходная последовательность.

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача 1C. Супергерой ≡

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города планирует напасть группа из N злодеев. Небоскрёб состоит из M этажей, пронумерованных от 1 до M. Вася прибыл на первый этаж непосредственно перед началом нападения злодеев и приготовился его отражать.

Злодей номер i появляется на этаже f_i через t_i секунд после начала нападения, и начинает творить зло со скоростью одно злое дело в секунду.

Каждую секунду Вася проделывает следующие действия:

1. Если на текущем этаже находятся злодеи, обезвреживает их.
2. Сдвигается вниз или вверх на один этаж по направлению к ближайшему злодею.
3. Если расстояния равны, Вася предпочитает подниматься вверх.
4. Если в текущий момент ни одного активного злодея в небоскрёбе нет, Вася остаётся на текущем этаже.

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

Формат входных данных

Входной файл содержит целые числа M N, за которыми следует N пар целых чисел t_i f_i.

Формат выходных данных

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

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ f_i ≤ M ≤ 10⁹

1 ≤ t_i ≤ t_i + 1 ≤ 10⁹

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

3 3
1 2
2 3
5 1

4

100 1
1 100

99

1 1
1 1

0

Задача 1D. Кошачьи шпионы ≡

Условие

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

Мяуканье представляет из себя набор из букв m, e, o, w, причем этих букв может быть много, но одинаковые буквы всегда идут подряд.

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

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

Формат входных данных

Первая строка входного файла содержит одно целое число: n - количество допрошенных особей.

В следующих n строках содержится целое число m_i и строка s_i длинны m_i.

Формат выходных данных

Выходной файл должен содержать одно целое число - количество шпионов.

Ограничения

0 < N ≤ 10⁵

0 < m_i ≤ 10⁵

0 < ∑m_i ≤ 4 * 10⁵

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

5
4 meow
11 meeeeooooow
4 miow
4 myau
5 hello

3

7
7 bonjour
7 alaykum
8 dobryden
2 ep
9 reverence
4 iiti
8 konishua

7

Задача 1E. Очередь к врачу ≡

Условие

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

Формат входных данных

Первая строка входных данных содержит два целых числа N — количество посетителей за последний день и K — длительность приема одного пациента.

Вторая строка содержит N чисел, отсортированных по возрастанию: t_i  — время, когда i − ый посетитель пришел на прием к терапевту.

Формат выходных данных

Выходные данные должны содержать одно целое число  — максимальную длину очереди за последний день.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

5 5
0 5 5 6 20

2

5 2
1 4 6 8 20

0

6 5
0 5 10 15 19 25

1