Problem A. Assignment ≡

Statement

Let the assignment expression be described by the following grammar

Comma = ",", { " " };

Digit = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
Number = "0" | ( Digit, { Digit | "0" } );

Letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
       | "c" | "d" | "e" | "f" | "g" | "h" | "i"
       | "j" | "k" | "l" | "m" | "n" | "o" | "p"
       | "q" | "r" | "s" | "t" | "u" | "v" | "w"
       | "x" | "y" | "z" ;

Variable = Letter, { Letter | Digit | "0" };

Value = Variable | Number | EnclosedValueList | EmptyList;
ValueList = Value, { Comma, Value }, [ Comma ];
EnclosedValueList = "(", ValueList , ")";
EmptyList = "(", { " " }, ")";

Destination = Variable | EnclosedDestinationList;
DestinationList = Destination, { Comma, Destination }, ( [ Comma, "*", Variable ] | [ Comma ] );
EnclosedDestinationList = "(", DestinationList, ")";

Assignment = ( DestinationList | EnclosedDestinationList ), " = ", ( ValueList | EnclosedValueList );

Both sides are treated as potentially nested lists. A variable on the left side is assigned a value placed at the same position on the right side. A value therefore may be a Number, a Variable or a list. A list must be enclosed in parenthesis and have at least one comma, i.e. (a,) is a list and (a) is equivalent to simply a. Additionally, parenthesis at the top level may be omitted. The assignment is performed from top to bottom, left to right, meaning that a Variable may be used as Value on the right side if it has already been assigned a Value. In a special case that a Variable is preceded by an asterisk it is assigned a potentially empty list of the rest of the Values at that level. The assignment fails if a Variable or a Value doesn't have a corresponding item on the other side or if a Variable is used as a Value before it has been assigned a Value.

Your program must decompose such assignment into a list of simple assignments: one Variable is assigned one Number or a list of Numbers.

Input format

Input consists of a single line — the assignment expression to be executed.

Output format

If the assignment cannot be performed output a single number -1. Otherwise, output must contain a simple assignment expression for each variable in lexicographical order one per line. The simple assignment is defined by the following grammar

SimpleAssignment = Variable, " = ", NumberOrList;
NumberOrList= Number | ( "(", NumberOrList, { Comma, NumberOrList }, [ Comma ] ")" ) | EmptyList;

Constraints

The assignment expression is guaranteed to be grammatically correct.

Length of the input is no more than 10⁴ symbols.

Sample tests

a, b, c = 42, 23, (23, 42)

a = 42
b = 23
c = (23, 42)

a, *b = 1, 2, 3, 4, 5

a = 1
b = (2, 3, 4, 5)

a, (b, c) = 42, (23, a)

a = 42
b = 23
c = 42

a, b = 42, 23, 10

-1

Problem B. Mirror for numbers ≡

Statement

A backwater city of N is populated by natural numbers. Today they have a holiday, so the amusement park has a new attraction — the numeric mirror. It works like this: number is translated into binary numeral system, its digits are mirrored in reverse order (if the binary representation was tailed by one or more zeroes, they are discarded). The resulting binary string is translated back to a natural number. For example, if the number 26 will come to the mirror, its binary representation 26₁₀ = 11010₂ will be reversed to 1011₂ (resulting leading zero is discarded) and everybody will see number 11 in the mirror.

Every number with binary representation of exactly d digits has come to the mirror one by one. Determine how many of them have seen their image in the mirror to be ...

1. less than the original number;
2. equal to the original number;
3. greater than the original number.

Input format

Input contains a natural number d.

Output format

Output three integers, one per line — answer to the problem.

Constraints

1 ≤ d ≤ 50

Notes on the sample

In the sample d = 4. Mirror was approached by all numbers with the binary length of 4 digits, i.e. numbers from 8 to 15.

Number 8 is mirrored as 1, 9 as 9, 10 as 5, 11 as 13, 12 as 3, 13 as 11, 14 as 7 and 15 as 15.

In total, five numbers are mirrored as lesser than originals (8, 10, 12, 13 and 14), two do not change (9 and 15), one is mirrored as greater than original (11).

Sample tests

4

5
2
1

Problem C. Cell painting ≡

Statement

Timofey was painting the margins of his notebook during a boring class. In the first line he painted one cell, two in the second, and in the following lines one less or one more then the previous line. At the end of the class it turned out that he painted exactly n cells. How many ways was there for him to do that? The margins are narrow, so Timofey never painted more than three cells in a single line.

Input format

The single line of input contains a positive integer n — number of painted cells.

Output format

Output a single nonnegative integer — the number of different ways to paint. It's guaranteed to be no more than 10¹⁸.

Constraints

1 ≤ n ≤ 200

Notes on the sample

See picture below.

Sample tests

14

6

Problem D. Decisive throw ≡

Statement

Timofey and his friends became interested in tabletop role-playing games. They spend all their pocket money on character figures, dungeon maps, beautiful dice and, of course, interesting games. Today a group of friends gathered for the first time for a new game "Olympus". After four hours, they reached the high point of the game — the outcome of the game depends on Timothy's final move.

Timofey must throw n ordinary six-sided dice with numbers from 1 to 6. If at least m of them land successfully, the team of friends wins. A dice falls successfully if the number on the upper face is at least a. For example, with a = 5, n = 3 and m = 2 Timofey must roll three dice in order to win so that at least two of them have the numbers 5 or 6.

Your program must output the probability of friends' victory in the form of an irreducible fraction.

Input format

The only line of input contains three integers: a, n и m.

Output format

Output two integers — nominator and denominator of irreducible fraction representing the probability of victory.

Constraints

1 ≤ a ≤ 6

1 ≤ m ≤ n ≤ 15

Notes on samples

In the first sample there are 36 different outcomes of throwing two dice, 27 of them are successful — the number on at least one of the dice if greater or equal than four. Therefore, probability of success is 27 / 36 or, after the reduction, 3 / 4.

Sample tests

4 2 1

3 4

5 3 2

7 27

Problem E. Square coins ≡

Statement

"Sensational discovery!", "Archaeologists have found an ancient civilization!", "Scientists are amazed at the development of ancient technologies!" — news were full of such headlines. The artifacts discovered under the thick sand of the Sahara Desert were indeed amazing: perfect instruments and mechanisms, manuscripts and parchments with incomprehensible records, objects of art and everyday life - everything pointed to a highly developed civilization that once existed in this region. Scientists prepared for long and painstaking work.

Numismatists, of course, were interested in the monetary system of the Ancient Saharians (this is how the discovered civilization was dubbed). Gold coins of various sizes were found, all exclusively square in shape and with a square hole in the middle. Interestingly, all sizes (both sides of coins and sides of holes) were odd numbers. It was suggested that the value of the coin corresponded to its area: for example, 24 points were minted on a coin of size 5 with hole 1, 16 points were found on a coin of size 5 with hole 3, and 8 points are clearly visible on a coin of size 3 with hole 1. Everything indicated that the value of the coin was equal to the difference between the squares of the side of the coin and the side of the hole: 5² − 1² = 24, 5² − 3² = 16, 3² − 1² = 8.

Given the value of the coin, determine all of its possible sizes.

Input format

Input contains an integer n — coin value. It is guaranteed that n is divisible by eight.

Output format

On the first line output integer k — number of different possible coin sizes. On each of the the next k lines output two numbers: size of the coin and the size of the hole. Order lines by ascending coin size.

Constraints

8 ≤ n ≤ 10¹²

Notes on sample

In the sample the coin value 72 is given. There are three corresponding sizes: 9² − 3² = 81 − 9 = 72, 11² − 7² = 121 − 49 = 72 и 19² − 17² = 361 − 289 = 72.

Sample tests

72

3
9 3
11 7
19 17

Problem F. New function ≡

Statement

Timofey came up with a new function and named it after himself. Now his name proudly stands besides the name of Euler, Möbius and Riemann — some functions were also named after them. Unfortunately, Timofey hasn't found a practical use case for his discovery yet, but he is actively working on it.

Timofey's function is defined on positive integers as follows: f(x) = x + ⌊ x10⌋  + ⌊ x100⌋  + ⌊ x1000⌋  + …, where ⌊ x10ⁿ⌋ is rounding down to an integer. For example, f(404) = 404 + ⌊ 40410⌋  + ⌊ 404100⌋  = 404 + 40 + 4 = 448.

While Timofey is writing a paper for a mathematical journal, find number x such that f(x) = n.

Input format

Input contains a positive integer n — function value.

Output format

Output a single positive integer — an argument the function has the desired value at. It's guaranteed to be unique.

Constraints

1 ≤ n ≤ 10¹⁸

Sample tests

448

404

Problem G. Siblings ≡

Statement

Siblings is a term used in social anthropology and other studies, meaning children who have the same parents. Full siblings are the ones who have the same mother and father, and half siblings only have one parent in common. Psychologists, studying sibling rivalry, got their hands on a database, containing data on people living in the same building. Help them find the largest group of full siblings for further studies.

The data is represented as a table with n rows and 3 columns. The first column is a person id. The second and third columns are ids of that person's parents in any order.

Input format

The first line of the input contains a single positive integer n — number of rows in the database. The next n lines each have three positive integers x_i, y_i, z_i, separated by a whitespace, — ids as described above.

Output format

In the first line output a single positive integer — the largest number of full siblings (it's guaranteed to be unique). In the second line output their ids in ascending order.

Constraints

2 ≤ n ≤ 10⁵

1 ≤ x_i, y_i, z_i ≤ 10⁹

Notes on the sample

It's convenient to represent the table from the sample as a graph. It shows that four people (with ids 207, 208, 411 и 511) have common parents. The other groups aren't as large.

Sample tests

11
104 48 60
511 130 120
111 1 2
112 2 1
208 120 130
120 2 1
130 32 17
207 120 130
170 32 17
191 104 111
411 130 120

4
207 208 411 511

Problem H. Right triangle ≡

Statement

Sasha graduated from high school and decided to enroll as a programmer at a local university. One of the first subjects in his course was «Geometry and Topology of Numbers». At the very first lecture, the whole group was asked to derive and prove a theorem that would make it possible to determine by three points on the plane whether the triangle formed by them is a right-angled.

Sasha was able to come up with several theorems, but for some reason his theorems give different answers. Write a program that, given the coordinates of three points, can correctly determine whether these points form a right-angled triangle.

Input format

First line of input contains integers x₁ and y₁, second line contains integers x₂ and y₂, third line contains integers x₃ and y₃ — coordinates of three points. All points are pairwise different.

Output format

Output must contain YES, if given points form right triangle or NO otherwise.

Constraints

 − 10⁴ ≤ x_i, y_i ≤ 10⁴

Sample tests

0 0
0 8
6 0

YES

1 2
3 2
4 1

NO

Problem I. Imictcoin ≡

Statement

Following the founding of a new institute in a well-known university its best programmers decided to create their own crypto currency "Imictcoin". But the chief cybersecurity expert Sergey came up with a special set of rules to compute hash for each block in a blockchain.

Hash must be a sequence of Latin letters that satisfies a single condition — not a single symbol can appear twice in a row.

For example:

• s = "abababc" is correct hash;
• s = "aabcabab" is incorrect hash;
• s = "a" is also correct hash.

Write a program that transforms a string into a correct hash by rearranging symbols in it or determines that it is impossible.

Input format

The first line of the input contains a single integer T — number of input strings. The following T lines each contain a single string s_i. Each string consists of lowercase Latin letters.

Output format

For each string s_i output in a separate line:

• -1, if the correct hash cannot be obtained;
• a string, representing a correct hash, which is a permutation of symbols of string s_i.

Constraints

1 ≤ T ≤ 10⁴.

The length of s_i is no more than 5 ⋅ 10⁵. The total length of all strings in a single test is no more than 5 ⋅ 10⁵.

Sample tests

2
aabb
aaaabb

abab
-1

1
a

a

Problem J. Chess with obstacles ≡

Statement

Young programmers Joe and Boe were sitting at the boring lecture and decided to play their own version of chess.

The chess board of size 8 × 8 contains white king, black pawn and some obstacles. White moves first. Black pawn can move exactly one cell down from top to bottom. and white king can move to any neighboring cell (see picture):

Some cells are occupied by obstacles. If the cell contains an obstacle, white king can not move to that cell. If king moves to the cell containing the pawn, then the pawn is captured. The goal of white is to capture the black pawn before it moves to the bottom row. The goal of the black is to get to the bottom row and not to be captured before that by white king.

Joe and Boe want to determine, given the staring position of the pieces, who will win, and if the winner is white, what is the minimum number of moves required. It is guaranteed that there are now obstacles on the path of black pawn. It is possible to skip the move, but only if there are no allowed cells to move to.

Input format

Input contains 8 lines, each line contains 8 characters. Characters have the following meanings:

• '0' — denotes empty cell;
• '1' — denotes cell with obstacle;
• 'K' — denotes white king;
• 'P' — denotes black pawn.

Output format

Output minimum number of moves, required for the white king to capture the pawn, or  − 1 if the white king will not be able to capture the black pawn before it reaches the bottom row.

Sample tests

00000001
00000000
00000000
0P00K000
00000000
00100000
00001000
00000000

3

00000000
00000000
00000000
00000000
000K0000
00000000
000P0000
00000000

-1

Problem K. Rock by rock ≡

Statement

Brothers Boba and Aboba decided to play a game they knew from childhood. In this game players have a row of n stones in front of them. Each stone is either small or big. During their turn a player takes the leftmost stone and does one of the following:

1. Smashes the stone to the ground and breaks it.
2. Hits the closest stone to the right. There are two possible outcomes:
   • If both stones have the same size they both break.
   • If one of them is big and the other is small, then the big one cracks and turns small, and the small one breaks. Therefore, two stones turn into one small stone.

After that the turn goes to the other player. The player who breaks the last stone (or the last two stones) during their turn wins.

Write a program that determines which of the brothers wins, if Aboba goes first.

Input format

The first line of the input contains one integer n — number of stones in the row.

The second line has n symbols, separated by a whitespace. The symbol «l» corresponds to a big stone, while «s» means a small one.

Output format

Output must contain Aboba, if Aboba wins, and Boba otherwise.

Constraints

1 ≤ n ≤ 10⁵

Sample tests

4
l s l s

Boba

2
l s

Boba