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.
Input format
First line of input contains two integers separated by space: x1 and y1 — coordinates of the white amazon. Second line contains coordinates of the black king x2 and y2 in the same format. Piece positions are guaranteed to be different.
Output format
Output Yes or No — answer to the problem's question.
Constraints
1 ≤ x1, x2, y1, y2 ≤ 8
Notes on the samples
See the picture. In the second sample the king can capture the amazon.
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 n-digit numbers are written on the blackboard, first composed of only the digit d1, second — of only the digit d2. 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?
Input format
Four lines of input contain four integers: n, d1, d2 and k. It is guaranteed that k is correct.
Output format
Output a single decimal digit — answer to the problem.
Constraints
1 ≤ n ≤ 109
1 ≤ k ≤ n + 1
1 ≤ d1, d2 ≤ 9
Notes on sample
Sample has n = 2 (adding two-digit numbers), d1 = 5 (first number is 55), d2 = 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.
Let there be a rectangular ASCII-art 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 format
Input contains an ASCII image.
Output format
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 top-left 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).
Constraints
Total number of characters in the image does not exceed 106.
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 109.
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.
Input format
First line of input contains string color, with value of either white or black —
color of the cell initially occupied by bishop.
Interaction protocol
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 i-th characters equals 1, if bishop is inside the i-th 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 end-of-line (\n).
Output buffers must be flushed after every line:
Language
C++
Pascal
Java
Python
Code
cout.flush()
flush(output)
System.out.flush()
stdout.flush()
Constraints
"A1"≤ A, B, X ≤"H8"
A ≤ B
Notes on samples
Bishop movements and monitored areas from the first sample are presented on the picture.
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 format
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 format
Output must contain two integers: number of nodes and edges.
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).
Input format
First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. Next n lines contain two space-separated integers each: xi, qi — coordinate of the house and number of people living in it (houses may be empty).
Output format
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.
Constraints
1 ≤ n, a, b ≤ 105
0 ≤ xi, qi ≤ 109
Notes on sample
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.
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:
a single Martian day will be exactly h Martian hours;
a single Martian hour will be exactly m Martian minutes;
a single Martian day minute be exactly s Martian seconds.
Current time on Mars is hM hours, mM minutes and sM 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 format
Input contains six integers, one per line: h, m and s — description of Martian day subdivision, followed by hM, mM and sM — current time.
Output format
Output a single integer — number of seconds until the moment when all digits on the clock become identical.
Constraints
0 ≤ hM < h ≤ 106
0 ≤ mM < m ≤ 106
0 ≤ sM < s ≤ 106
Notes on samples
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.
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.
Input format
Two lines of input contain two integers n and k.
Output format
Output a single integer — problem answer.
Constraints
1 ≤ n ≤ 109
1 ≤ k ≤ 100
Notes on sample
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.
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?
Input format
Two lines of input contain integers n and d.
Output format
Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.
Constraints
1 ≤ (d, n) ≤ 105
Notes on sample
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.
