Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Fantasy chess is a variant of chess composition. Puzzles of this variant contain changes to some of the accepted rules of the game or utilize unusual pieces or boards.
Amazon is a fantasy chess piece which can move as either a queen or a knight. It is usually represented on diagrams as a horse with the crown. You can see all possible moves of this piece on a picture below. Amazon is so strong and independent that it can checkmate the enemy king without the help of another friendly piece.
White amazon and black king are positioned on a normal chess board. Determine whether the king is checkmated.
First line of input contains two integers separated by space: x_{1} and y_{1} — coordinates of the white amazon. Second line contains coordinates of the black king x_{2} and y_{2} in the same format. Piece positions are guaranteed to be different.
Output Yes
or No
— answer to the problem's question.
1 ≤ x_{1}, x_{2}, y_{1}, y_{2} ≤ 8
See the picture. In the second sample the king can capture the amazon.
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Oh, those math lessons! Today, for example was the fourth test on the subject. To those who finished ahead of time the teacher offered an extra task for bonus points.
Two ndigit numbers are written on the blackboard, first composed of only the digit d_{1}, second — of only the digit d_{2}. Determine which digit occupies position k in the sum of those numbers. Positions are numbered left to right starting from 1.
You want bonus points, don't you?
Four lines of input contain four integers: n, d_{1}, d_{2} and k. It is guaranteed that k is correct.
Output a single decimal digit — answer to the problem.
1 ≤ n ≤ 10^{9}
1 ≤ k ≤ n + 1
1 ≤ d_{1}, d_{2} ≤ 9
Sample has n = 2 (adding twodigit numbers), d_{1} = 5 (first number is 55), d_{2} = 8 (second number is 88). Sum is 55 + 88 = 143. k = 1 (teacher asks the first digit of the result). The digit at first position of the number 143 is 1.
No.  Standard input  Standard output 

1 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let there be a set of triangles represented by 3dimensional vertex coordinates.
You must determine all maximal subsets of triangles such that triangles of each set belong to a single plane.
Input contains integer N, followed by 9 × N integers, representing vertex coordinates:
(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), where i = 0, 1, …, (N − 1).
Output must contain the number of subsets M, followed by M records of the following structure.
The number of triangles present in the set, followed by their indices in input (indexing starts at 0).
Both sets and triangles may be output in arbitrary order.
It is guaranteed that there are no degenerate (zero area) triangles in input.
− 1000 ≤ (Xki, Yki, Zki) ≤ 1000,
2 ≤ N ≤ 10^{5}.
No.  Standard input  Standard output 

1 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let there be a rectangular ASCIIart image of a digital circuit, composed of logical elements and wires connecting them.
Logical elements are represented as rectangular areas bordered by '#' (ASCII 35) characters.
Each element always contains a description composed of digits and small Latin letters.
Description may be split into several parts, separated by spaces, and span multiple lines.
Wires are represented as sequences of '.' (ASCII 46) characters.
The rest of the circuit is filled with spaces.
Any two elements can not be adjacent to each other (there is always space between them).
Wires can only connect at 90^{ ∘ } angle.
Parallel wires can not be adjacent to each other (there is always space between them).
An element is considered connected to a wire if their characters are adjacent either horizontally or vertically.
Wires can not cross area occupied by an element.
Bus is a set of connected wires.
Given the image, determine the set of logical elements and buses connected to them.
Input contains an ASCII image.
Output the number of logical elements N,
followed by N lines, with each line containing a description of a single element.
Parts of a description must be separated by spaces.
Order of elements in output must correspond to the order at which elements occur
in the input image when traversing by rows from the topleft corner.
Next, output the number of buses M, followed
by sets of connected elements.
Each set starts with a number of elements in it,
followed by element indices
(starting from zero).
Total number of characters in the image does not exceed 10^{6}.
No.  Standard input  Standard output 

1 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Consider a set of all possible strings of exactly n characters, consisting of digits and small Latin letters.
Hamming distance H(A, B) is equal to the number of positions i from 1 to n
where A[i] ≠ B[i].
Let us define P(A, B) as a set of strings of length n equidistant from A and B
({ C: H(A, C) = H(B, C)}).
Determine the number of strings in the set P(A, B).
Since the answer may be too large, output the remainder of it divided by 10^{9}.
Input contains two strings: A и B.
Output a single integer — the answer.
1 ≤ n ≤ 10^{4}.
No.  Standard input  Standard output 

1 


2 


Author:  A. Usmanov  Time limit:  1 sec  
Input / output:  interactive  Memory limit:  512 Mb 
This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.
Chess board is a field of 8 by 8 of alternating white and black cells. Columns are indicated by letters from A to H, rows — by digits from 1 to 8.
Cell coordinates are encoded as [column][row]
, for example E2.
The cell A1 in the bottom left is black.
There is a bishop on the chess board at some cell of a given color. Recall that the bishop is a piece which can move over diagonals in any direction for any number of cells. The goal is to determine actual position of the bishop by monitoring some rectangular areas of the board.
Your program must make requests of the form "? A B
", where A and B — coordinates of two board cells, bottom left and top right of the rectangle you want to monitor.
After every request the bishop makes a move and your will receive a reply communicating which of the monitored rectangles contain the bishop after the move.
Your program must determine the bishop position by making no more than 6 requests. It is guaranteed that bishop moves are predetermined and do not depend on requests.
First line of input contains string color, with value of either white
or black
—
color of the cell initially occupied by bishop.
To make a request, your program must output line "? A B
",
where A, B — strings of two characters, coordinates of the bottom left and top right of the rectangle you want to monitor.
After setting the monitoring bishop moves and jury program replies to your program with the string S of characters 1 or 0 — with ith characters equals 1, if bishop is inside the ith monitored rectangle.
When your program determines the current bishop position X, it must output "! X
",
where X
— string of two characters, bishop cell coordinates.
After outputting the answer your program must terminate.
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 endofline (\n
).
Output buffers must be flushed after every line:
Language  C++  Pascal  Java  Python 
Code  cout.flush() 
flush(output) 
System.out.flush() 
stdout.flush() 
"A1"
≤ A, B, X ≤ "H8"
A ≤ B
Bishop movements and monitored areas from the first sample are presented on the picture.
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let there be two disjoint sets of nodes of some oriented graph: A and B.
For each node of A, set of all nodes of B reachable from it is also given.
It is known that any node of A should not have incoming edges, and that any node of B should not have outgoing edges.
There can be set of intermediate nodes C in the graph that connected with nodes from A and B.
But any two nodes from C should not be connected to each other.
You are to obtain a graph with minimal number of edges satisfying this description.
If several optimal variants exist, choose a graph with minimal number of nodes.
The answer is the number of nodes and edges in the obtained graph.
Input contains two integers: N — size of A and M — size of B,
followed by the subsets of nodes of B reachable from every node of A.
Each subset starts with a number of nodes in it (may be zero),
followed by the indices of nodes (indexing starts from zero).
Output must contain two integers: number of nodes and edges.
1 ≤ (N, M) ≤ 1000
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
The city of N has a happy event! On the single street of the city, new street lamp will be installed and the new pharmacy will open. Help the city governor to find optimal places for these objects.
The street is represented by a segment of coordinate axis, where the leftmost house has coordinate 0. Let's assume house sizes to be negligibly small compared to the street length and represent houses as points on the axis.
The lamp has "brightness" parameter expressing the largest distance from the lamp where the light reaches. For example when brightness is equal to 10, lamp installed at the point x = 25 will light the street on the segment from 15 to 35 inclusive.
The pharmacy has "remoteness" parameter expressing the largest distance from it to the house such that people from that house will still visit. For example when remoteness is equal to 100, pharmacy located at point x = 25, will be visited by people living in houses with coordinates from 0 to 125 inclusive (there are no houses with negative coordinates).
First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. Next n lines contain two spaceseparated integers each: x_{i}, q_{i} — coordinate of the house and number of people living in it (houses may be empty).
Output two integers — maximum number of houses illuminated by the lamp and maximum number of people who will visit the pharmacy. Both lamp and pharmacy may be located between the houses as well as at points with the coordinate of some house.
1 ≤ n, a, b ≤ 10^{5}
0 ≤ x_{i}, q_{i} ≤ 10^{9}
Sample contains five houses, lamp brightness 15 and pharmacy remoteness 20. Lamp can be installed at either point 15, or point 25, in both cases 4 houses will be illuminated. Pharmacy may be located at point 20, in which case all city inhabitants will be able to visit.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Zhenya Slavin is a first human born on Mars. He is yet a little boy and likes to look at the digital clock hanging opposite of his bed. Most of all he likes the moments when all digits on the clock become identical. In those moments he always claps joyfully.
Since the period of rotation of Mars around its axis is different from that of the Earth, Martian colonists decided that:
Current time on Mars is h_{M} hours, m_{M} minutes and s_{M} seconds. After how many seconds will Zhenya clap? Time on the Martian digital clocks is displayed with leading zeroes in all positions. Extra positions are not used.
Input contains six integers, one per line: h, m and s — description of Martian day subdivision, followed by h_{M}, m_{M} and s_{M} — current time.
Output a single integer — number of seconds until the moment when all digits on the clock become identical.
0 ≤ h_{M} < h ≤ 10^{6}
0 ≤ m_{M} < m ≤ 10^{6}
0 ≤ s_{M} < s ≤ 10^{6}
It the first sample Martian days are no different from Earth ones (24 hours of 60 minutes of 60 seconds). Now it is 23 hours 50 minutes exactly (clock displays digits 23:50:00
). After 10 minutes (or 600 seconds) the clock will display zeroes in all positions.
It the second sample Martian days contain 627 hours of 5 minutes of 777 seconds. Now it is 49 hours 3 minutes and 2 seconds (clock displays digits 049:3:002
). After 61 hours 3 minutes and 109 seconds (or 239425 Martian seconds) the clock will display ones in all positions.
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Marina Tsvetaeva, Andrej Belyj and Sasha Chernyj are spending the evening playing chess. For each game two of them are playing and the third person is waiting to take the place of the loser. The winner of each game plays next game with white pieces.
After playing n games silver age poets were surprised to find out that white side had been repeatedly winning k times in a row, followed by a black victory every time.
Andrej Belyj likes to play with white pieces, Sasha Chernyj — with black, Marina Tsvetaeva likes either of the colors. Determine the number of games where both players played with the color they like. First game was between Andrej Belyj (played with white) and Sasha Chernyj (played with black). No game was a draw.
Two lines of input contain two integers n and k.
Output a single integer — problem answer.
1 ≤ n ≤ 10^{9}
1 ≤ k ≤ 100
4 games were played. White player had been winning one game, and then losing the next one.
In the first game Belyj — Chernyj both play the color they like. Andrej wins, playing with white.
In the second game Belyj — Tsvetaeva both play the color they like. Andrej loses, playing with white.
In the third game Tsvetaeva — Chernyj both play the color they like. Marina wins, playing with white.
In the final game Tsvetaeva — Belyj only Marina plays the color she likes. So the answer is 3 games.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.
There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?
Two lines of input contain integers n and d.
Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output 1.
1 ≤ (d, n) ≤ 10^{5}
In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.
In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.
No.  Standard input  Standard output 

1 


2 

