Input file:  Standard input  Time limit:  1 sec  
Output file:  Standard output  Memory limit:  512 Mb 
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 consists of a single line — the assignment expression to be executed.
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;
The assignment expression is guaranteed to be grammatically correct.
Length of the input is no more than 10^{4} symbols.
No.  Standard input  Standard output 

1 


2 


3 


4 


Author:  Anton Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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_{10} = 11010_{2} will be reversed to 1011_{2} (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 ...
Input contains a natural number d.
Output three integers, one per line — answer to the problem.
1 ≤ d ≤ 50
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).
No.  Standard input  Standard output 

1 


Author:  Anton Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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.
The single line of input contains a positive integer n — number of painted cells.
Output a single nonnegative integer — the number of different ways to paint. It's guaranteed to be no more than 10^{18}.
1 ≤ n ≤ 200
See picture below.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Timofey and his friends became interested in tabletop roleplaying 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 sixsided 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.
The only line of input contains three integers: a, n и m.
Output two integers — nominator and denominator of irreducible fraction representing the probability of victory.
1 ≤ a ≤ 6
1 ≤ m ≤ n ≤ 15
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.
No.  Standard input  Standard output 

1 


2 


Author:  Anton Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
"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^{2} − 1^{2} = 24, 5^{2} − 3^{2} = 16, 3^{2} − 1^{2} = 8.
Given the value of the coin, determine all of its possible sizes.
Input contains an integer n — coin value. It is guaranteed that n is divisible by eight.
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.
8 ≤ n ≤ 10^{12}
In the sample the coin value 72 is given. There are three corresponding sizes: 9^{2} − 3^{2} = 81 − 9 = 72, 11^{2} − 7^{2} = 121 − 49 = 72 и 19^{2} − 17^{2} = 361 − 289 = 72.
No.  Standard input  Standard output 

1 


Author:  Anton Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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^{n}⌋ 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 contains a positive integer n — function value.
Output a single positive integer — an argument the function has the desired value at. It's guaranteed to be unique.
1 ≤ n ≤ 10^{18}
No.  Standard input  Standard output 

1 


Author:  Anton Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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.
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.
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.
2 ≤ n ≤ 10^{5}
1 ≤ x_{i}, y_{i}, z_{i} ≤ 10^{9}
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.
No.  Standard input  Standard output 

1 


Author:  А. Лепёха  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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 rightangled.
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 rightangled triangle.
First line of input contains integers x_{1} and y_{1}, second line contains integers x_{2} and y_{2}, third line contains integers x_{3} and y_{3} — coordinates of three points. All points are pairwise different.
Output must contain YES
, if given points form right triangle or NO
otherwise.
− 10^{4} ≤ x_{i}, y_{i} ≤ 10^{4}
No.  Standard input  Standard output 

1 


2 


Input file:  Standard input  Time limit:  1 sec  
Output file:  Standard output  Memory limit:  512 Mb 
Following the founding of a new institute in a wellknown 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:
Write a program that transforms a string into a correct hash by rearranging symbols in it or determines that it is impossible.
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.
For each string s_{i} output in a separate line:
1 ≤ T ≤ 10^{4}.
The length of s_{i} is no more than 5 ⋅ 10^{5}. The total length of all strings in a single test is no more than 5 ⋅ 10^{5}.
No.  Standard input  Standard output 

1 


2 


Input file:  Standard input  Time limit:  1 sec  
Output file:  Standard output  Memory limit:  512 Mb 
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 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 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.
No.  Standard input  Standard output 

1 


2 


Author:  А. Лепёха  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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:
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.
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 must contain Aboba
, if Aboba wins,
and Boba
otherwise.
1 ≤ n ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 

