Problem A. Average thrice ≡

Statement

Artem made up three integers and told Eugene the average value of every pair of them. Eugene easily restored original integers. Now you try to do the same!

Input format

Input contains three numbers: x, y and z. Numbers are either integers or have fractional part of exactly 0.5. At least one number is not zero.

Output format

Output original integers in non-descending order (input data are such that the original numbers will turn out to be integer).

Constraints

 − 10⁸ ≤ x, y, z ≤ 10⁸

Notes on sample

In the sample x = 1.5, y = 2 and z = 3.5. These are pairwise averages for a = 0, b = 3 and c = 4. Indeed:

a + b2 = 0 + 32 = 1.5 = x;

a + c2 = 0 + 42 = 2 = y;

b + c2 = 3 + 42 = 3.5 = z.

Sample tests

1.5 2 3.5

0 3 4

Problem B. Bread crusts ≡

Statement

In the "Three minnows" tavern for a gold coins you can buy three bread crusts and get back some change, or, for b gold coins — five bread crusts and some change. How many bread crumbs you are guaranteed to get for c golden coins?

One gold coin is equal to 100 silver coins. There are no other coin types in the country. One bread crust price is a whole number of silver coins. To get three bread crusts and a change for a gold coins means that three crusts cost strictly less than a golden coins, but four crusts cost more than a gold coins.

Input format

Input contains three integers a, b and c, one per line. Input data is such that the answer exists.

Output format

Output a single integer — problem answer.

Constraints

1 ≤ a < b ≤ 10⁹

1 ≤ c ≤ 10⁹

Sample tests

8
13
100

38

Problem C. Current year problem ≡

Statement

Find the smallest positive integer which is divisible by n and starts from digits 2021 in decimal notation.

Input format

Input contains a single integer n — the divisor of the required number.

Output format

Output a single integer — the answer.

Constraints

1 ≤ n ≤ 10¹²

Sample tests

2022

20211912

Problem D. Dynamic Cinderella ≡

Statement

In the Brothers Grimm's fairy tale, one of the tests for Cinderella was an episode when the evil stepmother scattered cereals in a heap on the floor and ordered her to sort them out on plates. The cereals vary depending on the version. In one fairy tale, Cinderella was sorting through millet and poppy seeds. In another, she arranged beans and lentils. In the third, barley was separated from oats. There were peas with rice, and buckwheat with millet, and bags of red and white beans. Which version is true is unknown, so in this problem the stepmother formed a bunch of decimal digits and demanded that Cinderella count the number of each digit in the heap.

In total, there are n levels in the heap, at the topmost there is a single digit d, on each next level there is one more digit than at the higher level. For convenience, let's imagine a heap (for n = 4 and d = 8) as shown in the picture.

Heap of numbers was formed by the stepmother according to certain rules. The very first number on the levels starting from the second is equal to the first number on the higher level, increased by 1 and taken modulo 10. For example, the first number on the second level is (8 + 1)% 10 = 9. The first number on the third level is (9 + 1)% 10 = 0, and so on.

The rest of the digits in the heap are formed as follows: take two numbers — to the left in the same level and on a higher level above the number just taken, they are added and the result is taken modulo 10. For example, the second number at the second level is (9 + 8) % 10 = 7.

If Cinderella knew what dynamic programming is, then the rules for filling the heap would look like this:

DP[1, 1] = d;
DP[i, 1] = (DP[i - 1, 1] + 1) % 10;
DP[i, j] = (DP[i, j - 1] + DP[i - 1, j - 1]) % 10.

Input format

Input contains two numbers: n and d.

Output format

Output ten integers — number of digits from 0 to 9 in the heap.

Constraints

2 ≤ n ≤ 10⁵

1 ≤ d ≤ 9

Sample tests

4 8

2 2 0 0 0 0 2 1 1 2

Problem E. Enclosed by curves ≡

Statement

Novice programmer Vasya develops his own vector graphics editor. In addition to the usual primitives (like rectangles, circles, straight lines) his editor also supports working with objects of complex shapes, which are described using spline curves.

Each such curve consists of several pieces, in sequence one after the other, each of which is given by a parametric equation of the following form:

X_i(t) = AX_i ⋅ t³ + BX_i ⋅ t² + CX_i ⋅ t + DX_i;

Y_i(t) = AY_i ⋅ t³ + BY_i ⋅ t² + CY_i ⋅ t + DY_i,

where t — scalar parameter, changing in range of [0, 1].

Vasya uses closed spline curves to describe complex shapes. One of his tasks is to determine for every given point whether it lies inside such a figure.

Input format

The beginning of the input contains an integer N, followed by 8 × N real numbers, specifying the coefficients of the corresponding splines

AX_i, BX_i, CX_i, DX_i,
AY_i, BY_i, CY_i, DY_i.

Next there is integer M, followed by 2 × M real numbers, specifying the coordinates of the points (X_j, Y_j).

Output format

Output must contain M integers (answers to each query):
1 — if the point is inside the contour,
0 — if it is outside.

Constraints

Within the specified accuracy, the contour is continuous and does not have self-intersections.

The distance from each point to the boundary of the contour is not less than 10^− 5.

The contour lies entirely within the rectangular area [ − 10, 10] × [ − 10, 10].

1 ≤ N ≤ 1000, 1 ≤ M ≤ 10⁵.

Sample tests

6
 3.53200 -4.87400  1.66600 -0.46000
 0.67600 -0.70800  0.26600 -0.20200
 1.74000 -2.86600  0.84800 -0.13600
 1.29000 -1.88200  0.61200  0.03200
-1.40400  2.10600 -0.51200 -0.41400
-0.17200  0.25800  0.10600  0.05200
-1.40000  1.57000  0.00000 -0.22400
-0.22200  0.01600 -0.00000  0.24400
-3.42400  4.60600 -1.06000 -0.05400
 0.11600  0.22800 -0.63400  0.03800
 0.60200 -0.07000 -1.06000  0.06800
 1.77400 -2.52800  0.80400 -0.25200

8
-0.23000 -0.27000
-0.37094 -0.10086
 0.00000  0.15040
-0.39010  0.20360
-0.31067  0.04029
-0.20000 -0.08960
 0.03000 -0.05071
-0.18603  0.17014

0
1
1
0
1
1
0
1

Problem F. Fine segments ≡

Statement

The young programmer Ilya was presented with a sequence of numbers a_i of length n for his birthday. Ilya decided to select fine segments from this sequence. A fine segment is a sequence of successive elements of a_i containing some element equal to the sum of its first and last elements. For example, the sequence [1, 2, 5, 4] is fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is in this sequence; the sequence [1, 2, 3, 4] is not fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is not in this sequence. Your program must count the number of fine segments in a given sequence.

Input format

The first line contains an integer n — the length of the sequence. The second line contains n integers a_i — the elements of the sequence. All elements of the sequence are different.

Output format

Output a single integer — number of fine segments in the sequence.

Constraints

1 ≤ n ≤ 10³

1 ≤ a_i ≤ 10⁵

Notes on samples

First sample has one fine segment: [3, 7, 5, 4].

Second sample has two fine segments: [1, 5, 4] и [1, 5, 4, 7, 6].

Sample tests

5
3 7 5 4 8

1

5
1 5 4 7 6

2

Problem G. Generator of palindromes ≡

Statement

A palindrome is a string of characters that reads equally in both directions (left to right and right to left).

Given an arbitrary string S, consider an lexicographically ordered list of all the different palindromes that can be obtained by deleting and rearranging characters in the original string.

It is required to exclude from the specified list those palindromes which are lexicographically less than given string T.
If after that list is still longer than n, the extra palindromes from the end should also be removed.

Input format

The first two lines of the input contain strings S and T, consisting of digits and lowercase letters of the Latin alphabet.
They are followed by an integer n.

Output format

The output must contain all the remaining palindromes in the list in lexicographic order.

If there are none, the output should be an empty string.

Constraints

0 < |T| ≤ |S| ≤ 100,

0 < n ≤ 2 ⋅ 10⁴

Sample tests

abcbac
aca
15

aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c

123243
21a
50

22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4

Problem H. Hide the dot ≡

Statement

We are already used to advanced algorithms for automatic image processing. With their help, it costs us nothing to remove the background from the photo, cover up the wrinkles and even make a joint collage with any celebrity. But have you ever wondered how such programs work? Is it difficult to write them? You are presented with a simple task: find and remove a single extra character from an ASCII picture.

A picture of size n × m contains an image of an empty rectangle one pixel thick and one extra pixel, denoted by "#" symbols (ASCII code 35). The rectangle is at least three pixels long and three pixels wide, and its sides are parallel to the edges of the image. The background of the picture is filled with "." (ASCII code 46).

Input format

The first line of the input contains two integers: n and m. The next n lines contain strings of length m, consisting of the characters "#" and ".".

Output format

Output n lines of m characters each — the same image with an extra pixel removed.

Constraints

3 ≤ n, m ≤ 100

Sample tests

5 5
..#..
.####
.#..#
.####
.....

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

3 3
###
###
###

###
#.#
###

7 8
........
.#####..
.#...#..
.#...#..
.#####..
........
...#....

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

Problem I. Interactive and bidirectional ≡

Statement

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

Jury made up a secret bit string X of length N.

Your program must make a queries of the form "? M L R". Answer to the query is a result of left-to-right and right-to-left comparison of two substrings of M bits: starting with position L and staring from position R. Bits are numbered right to left.

You must determine the value of X by making of not more than ⌈ N + 12⌉ queries.

Input format

First line of input contains integer N — number of bits in X.

Interaction protocol

To make a query, your program must output "? M L R", where M — number of bits to compare, L and R — positions to compare. Jury program answers each query with two characters — results of left-to-right and right-to-left comparisons. Possible comparison results are:  < ,  >  и  = . Queries must not require access to bits outside boundaries of X.

When your program determines X, it must output "! X", where X — string of bits X. After printing the answer your program must finish execution.

If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds allowed number of queries, it will receive "Wrong answer" 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

1 ≤ N ≤ 60

0 < X < 2^N

1 ≤ M ≤ N

0 ≤ L, R < N

L + M, R + M ≤ N

Notes on samples

In the first sample secret number is 01101. First query compares 101 with 011 and 101 with 110, thus the answer is  >  < .

Sample tests

5

><

<<

==

? 3 0 2

? 1 1 3

? 2 3 0

! 01101

3

==

? 2 0 1

! 111

Problem J. Juxtaposition joke ≡

Statement

The blackboard in the math classroom had number n written on it. There were no zeros anywhere in the number. While passing along, Timofey decided to play a joke and swapped neighboring digits in the number k times. What is the largest possible resulting number?

Input format

Input contains integers n and k, one per line.

Output format

Output a single integer — problem answer.

Constraints

11 ≤ n ≤ 10²⁵⁰

k ≤ 10⁹

Notes on samples

In the first sample n = 97 and a single swap, giving 79.

In the second sample it is optimal to move three to the first place and get 312

Sample tests

97
1

79

123
2

312

5833917
9

9875331

Problem K. Kode work? ≡

Statement

A group of students decided to create a startup to replace QR codes with new improved system. They decided to represent binary data as a string of digit patterns for 0 and 1, displayed on a picture below. Picture also contains a representation of a binary string 1001.

Digits in the code are separated by one column of '.' characters, first and last digit are located right on the edges of the code. If the image taken by camera does not exactly coincide with the digit patterns, then the number of differing pixels is called recognition error.

System must determine the minimal recognition error which can be obtained by picking the bit string most closely resembling given image.

Input format

First line of input contains integer n — image width. Following three lines contain the image. Each character is either '#' (ASCII 35), or '.' (ASCII 46).

Output format

Output single integer — minimum possible recognition error.

Constraints

2 ≤ n ≤ 100000

Sample tests

5
.#..#
##.##
.#..#

0

14
.#.#.#.##.#..#
##.#.#.##.#.##
.#####.####..#

14

Problem L. Learning distribution ≡

Statement

Two students are preparing for exam, when they will get a single question out of n possible ones. They decided to split questions to study as follows:

First student picks a number a from 1 to n and learns a questions numbered a, a + 1, a + 2, ... , a + a − 1. If some number exceeds n, numbering continues from 1. For example, if n = 5 and a = 1, the first student will only learn question 1, when a = 2 he will learn questions 2 and 3, when a = 4 — questions 4, 5, 1 and 2, when a = 5 — all questions.

Second student also picks a number b ≠ a from 1 to n and learns b questions numbered b, b + 1, b + 2, ... , b + b − 1. Similarly, if some number exceeds n, numbering continues from 1.

Given number of questions n determine number of different ways to choose a and b, such that every question will be learned by at least one of students.

Input format

Input contains an integer n.

Output format

Output an integer — number of ways to choose a and b.

Constraints

2 ≤ n ≤ 10⁶

Notes on samples

In the first sample all possible choices of a и b result in learning all questions.

In the second sample there are four questions. If a = 1, and b = 2, question number 4 will not be learned by either student.

If a = 1, and b = 3, question number 2 will not be learned by either student.

In other cases all questions will be studied.

Sample tests

3

6

4

8