Problem A. 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 B. 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 C. 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 D. 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 E. 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 F. 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 G. 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 H. 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 I. 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 J. 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 K. 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 L. 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 M. 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 #### ******