Description

It is 2050 and human live with alien. There are two kind of alien: good alien and evil alien. Good alien were our friend because they help us to develop good technology for our earth. Evil alien were very very bad, they develop heavy and dangerous weapons that can destroy earth. Alien were very hard to kill because of their ultra regeneration skill. Luckily, we have developed a kind of bomb that can kill alien in an instant. This weapon is very expensive so we must use it wisely.

Given a map of 10 × 10, each element in the map will be:

• '.' represents empty region.
• 'g' represents good alien.
• 'e' represents evil alien.

Calculate how many evil alien that can be killed without killing any good alien, and how many bombs we need to do that. A bomb has a 3 × 3 area of effect, so all of the 8 adjacent neighbors will also be destroyed. You can put bomb anywhere in the map, even if there is an alien in that cell. For example,

e..
.Xe
..e

Bombing at X will kill three evil aliens.

Our spy has reported that the number of alien groups from each side is less than 16.

Input

First line in the input will be T (1 ≤ T ≤ 100) number of cases. Each case will have a map of 10 × 10 represent the city. Between each city will be separated by a blank line.

Output

For each case, output two numbers: a and b, where a is the maximum number of evil aliens that you can kill and b is the minimum number of bombs you need to do that.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The game of Yahtzee involves 5 dice, which are thrown in 13 rounds. A score card contains 13 categories; each round may be scored in a category of the player's choosing, but each category may be scored only once in the game. The 13 categores are scored as follows:

• ones - sum of all ones thrown
• twos - sum of all twos thrown
• threes - sum of all threes thrown
• fours - sum of all fours thrown
• fives - sum of all fives thrown
• sixes - sum of all sixes thrown

• chance - sum of all dice

• three of a kind - sum of all dice, provided at least three have same value
• four of a kind - sum of all dice, provided at least four have same value
• five of a kind - 50 points, provided all five dice have same value
• short straight - 25 points, provided four of the dice form a sequence (that is, 1,2,3,4 or 2,3,4,5 or 3,4,5,6)
• long straight - 35 points, provided all dice form a sequence (1,2,3,4,5 or 2,3,4,5,6)
• full house - 40 points, provided three of the dice are equal and the other two dice are also equal. (for example, 2,2,5,5,5)

Each of the last six categories may be scored as 0 if the criteria are not met.

The score for the game is the sum of all 13 categories plus a bonus of 35 points if the sum of the first six categores (ones to sixes) is 63 or greater.

Your job is to compute the best possible score for a sequence of rounds.

Input

Each line of input contains 5 integers between 1 and 6, indicating the values of the five dice thrown in each round. There are 13 such lines for each game, and there may be any number of games in the input data.

Output

Your output should consist of a single line for each game containing 15 numbers: the score in each category (in the order given), the bonus score (0 or 35), and the total score. If there is more than one categorization that yields the same total score, any one will do.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“How am I ever going to solve this problem?” said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a square area with edge length N. The lower left corner is (0, 0) and the upper right corner is (N, N). There is one person stand on each point (x, y). (0 ≤ x, y ≤ N) x and y are integers. Suppose you are the one at (0, 0), please calculate the number of people you can see directly. For example, the edge length of the sqaure is 2. You can see (0, 1), (1, 0), (1, 2), (2, 1) and (1, 1) directly.

Input

There are multiple test cases. The first line contains an integer T (T ≤ 100) which represents the number of test case. The next T lines, each line contains an interger N (0 < N ≤ 1000000), which represents the length of the square.

Output

Please output the number of people for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

To Mr. Solitarius, who is a famous solo play game creator, a new idea occurs like every day. His new game requires discs of various colors and sizes.

To start with, all the discs are randomly scattered around the center of a table. During the play, you can remove a pair of discs of the same color if neither of them has any discs on top of it. Note that a disc is not considered to be on top of another when they are externally tangent to each other.

Figure. Seven discs on the table

For example, in figure, you can only remove the two black discs first and then their removal makes it possible to remove the two white ones. In contrast, gray ones never become removable.

You are requested to write a computer program that, for given colors, sizes, and initial placings of discs, calculates the maximum number of discs that can be removed.

Input

The input consists of multiple datasets, each being in the following format and representing the state of a game just after all the discs are scattered.

n
x₁ y₁ r₁ c₁
x₂ y₂ r₂ c₂
…
x_n y_n r_n c_n

The first line consists of a positive integer n representing the number of discs. The following n lines, each containing 4 integers separated by a single space, represent the colors, sizes, and initial placings of the n discs in the following manner:

• (x_i, y_i), r_i, and c_i are the xy-coordinates of the center, the radius, and the color index number, respectively, of the i-th disc, and
• whenever the i-th disc is put on top of the j-th disc, i < j must be satisfied.

You may assume that every color index number is between 1 and 4, inclusive, and at most 6 discs in a dataset are of the same color. You may also assume that the x- and y-coordinates of the center of every disc are between 0 and 100, inclusive, and the radius between 1 and 100, inclusive.

The end of the input is indicated by a single zero.

Output

For each dataset, print a line containing an integer indicating the maximum number of discs that can be removed.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Running a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible, there is also a need to schedule all the taxi rides which have been booked in advance. Given a list of all booked taxi rides for the next day, you want to minimise the number of cabs needed to carry out all of the rides.

For the sake of simplicity, we model a city as a rectangular grid. An address in the city is denoted by two integers: the street and avenue number. The time needed to get from the address a, b to c, d by taxi is |a - c| + |b - d| minutes. A cab may carry out a booked ride if it is its first ride of the day, or if it can get to the source address of the new ride from its latest, at least one minute before the new rides scheduled departure. Note that some rides may end after midnight.

Input

3On the first line of the input is a single positive integer N, telling the number of test scenarios to follow. Each scenario begins with a line containing an integer M, 0 < M < 500, being the number of booked taxi rides. The following M lines contain the rides. Each ride is described by a departure time on the format hh:mm (ranging from 00:00 to 23:59), two integers a b that are the coordinates of the source address and two integers c d that are the coordinates of the destination address. All coordinates are at least 0 and strictly smaller than 200. The booked rides in each scenario are sorted in order of increasing departure time.

Output

For each scenario, output one line containing the minimum number of cabs required to carry out all the booked taxi rides.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

kerker 是個胖子，這次他想要穿過一座森林去尋找小妹妹。這座森林位於一山谷之間，kerker 因為實在太胖，經常在森林裏的樹或山壁之間被卡住無法通過，所以他下定決心要減肥，好讓他可以順利地走到森林的另一頭。

如下圖所示，我們將森林表示成一個 L × W 的通道，其上下兩側屬於平行 (且長度為 L ，相距為 W) 的山壁。森林裏的樹木以面積可以忽略的點來表示，而 kerker 則以一個圓來代表，且此圓不能被壓縮變形。

圖：範例輸入

請計算 kerker 要減肥到代表他的圓的直徑為多少時，可以存在一條路徑使他能不被樹或山壁卡住 (無法通過距離小於直徑的兩棵樹、樹和某一側山壁或兩側山壁之間) 以通過森林。

Input

輸入的第一行為一整數，代表檔案裏所包含的測試資料筆數。

每一筆測試資料的第一行為兩個以空白隔開的整數 L (0 ≤ L ≤ 100) 和 W (0 ≤ W ≤ 100)，代表森林的長度與寬度。第二行有一整數 N (0 ≤ N ≤ 100)，代表森林裏有幾棵樹。接下來的 N 行，每一行包含兩個由空白隔開的整數 X (0 ≤ X ≤ L) 和 Y (0 ≤ Y ≤ W)，代表樹木的座標。

Output

對於每一筆測試資料，輸出一行 “Maximum size in test case T is R.”。其中 T 代表測試資料的編號 (從 1 開始)，而 R 則是可以使 kerker 順利通過森林下，可能的最大直徑，該數字須四捨五入至小數點以下第 4 位。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N. No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.

Input

The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0.

Output

The output contains for each block except the last in the input file one line containing the number of critical places.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Johnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents don't give out candy), and returns to a meeting point arranged in advance.

There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny's gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny's interest is in eating the candy as soon as possible.

Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane.

At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy.

Input

Each test case starts with a line indicating the number n of houses (1 ≤ n ≤ 50,000). The next n lines describe the positions of the houses; each of these lines contains two floating point numbers x and y (-200,000 ≤ x, y ≤ 200,000), the coordinates of a house in meters. All houses are at different positions.

A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case.

Output

For each test case, print two numbers in a line separated by a space: the coordinate x of the meeting point on the line y = 0 that minimizes the time the last child arrives, and this time itself (measured in seconds after midnight). Your answer should be accurate to within an absolute or relative error of 10^-5.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider the following exercise, found in a generic linear algebra textbook.

Let A be an n × n matrix. Prove that the following statements are equivalent:

(a) A is invertible.

(b) Ax = b has exactly one solution for every n × 1 matrix b.

(c) Ax = b is consistent for every n × 1 matrix b.

(d) Ax = 0 has only the trivial solution x = 0.

The typical way to solve such an exercise is to show a series of implications. For instance, one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d), and finally that (d) implies (a). These four implications show that the four statements are equivalent.

Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies (b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d). However, this way requires proving six implications, which is clearly a lot more work than just proving four implications!

I have been given some similar tasks, and have already started proving some implications. Now I wonder, how many more implications do I have to prove? Can you help me determine this?

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line containing two integers n (1 ≤ n ≤ 20000) and m (0 ≤ m ≤ 50000): the number of statements and the number of implications that have already been proved.
• m lines with two integers s₁ and s₂ (1 ≤ s₁, s₂ ≤ n and s₁ ≠ s₂) each, indicating that it has been proved that statement s₁ implies statement s₂.

Output

Per testcase:

• One line with the minimum number of additional implications that need to be proved in order to prove that all statements are equivalent.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever he wants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuring that the stack doesn’t fall over. After he finishes watching the movie, he places it at the top of the stack.

Since the stack of movies is so big, he needs to keep track of the position of each movie. It is sufficient to know for each movie how many movies are placed above it, since, with this information, its position in the stack can be calculated. Each movie is identified by a number printed on the movie box.

Your task is to implement a program which will keep track of the position of each movie. In particular, each time Mr. K. I. removes a movie box from the stack, your program should print the number of movies that were placed above it before it was removed.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

one line with two integers n and m (1 ≤ n, m ≤ 100,000): the number of movies in the stack and the number of locate requests.

one line with m integers a₁, …, a_m (1 ≤ a_i ≤ n) representing the identification numbers of movies that Mr. K. I. wants to watch.

For simplicity, assume the initial stack contains the movies with identification numbers 1, 2, …, n in increasing order, where the movie box with label 1 is the top-most box.

Output

Per test case:

one line with m integers, where the i-th integer gives the number of movie boxes above the box with label a_i, immediately before this box is removed from the stack.

Note that after each locate request a_i, the movie box with label a_i is placed at the top of the stack.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

World-renowned Prof. A. N. Agram's current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups.

A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.

Input

The input contains words composed of lowercase alphabetic characters, separated by whitespace. It is terminated by EOF.

Output

Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As you can deduce from the company name, their business is beads. Their PR department found out that customers are interested in buying colored bracelets. However, over 90 percent of the target audience insists that the bracelets be unique. (Just imagine what happened if two women showed up at the same party wearing identical bracelets!) It's a good thing that bracelets can have different lengths and need not be made of beads of one color. Help the boss estimating maximum profit by calculating how many different bracelets can be produced.

A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.

Input

Every line of the input file defines a test case and contains two integers: the number of available colors c followed by the length of the bracelets s. Input is terminated by c = s = 0. Otherwise, both are positive, and, due to technical difficulties in the bracelet-fabrication-machine, cs ≤ 32, i.e. their product does not exceed 32.

Output

For each test case output on a single line the number of unique bracelets. The figure below shows the 8 different bracelets that can be made with 2 colors and 5 beads.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are to write an interpreter for a simple computer. This computer uses a processor with a small number of machine instructions. Furthermore, it is equipped with 32 byte of memory, one 8-bit accumulator (accu) and a 5-bit program counter (pc). The memory contains data as well as code, which is the usual von Neumann architecture.
The program counter holds the address of the instruction to be executed next. Each instruction has a length of 1 byte - the highest 3 bits define the type of instruction and the lowest 5 bits define an optional operand which is always a memory address (xxxxx). For instructions that don't need an operand the lowest 5 bits have no meaning (-----). Here is a list of the machine instructions and their semantics:
000xxxxx   STA x   store the value of the accu into memory byte x
001xxxxx   LDA x   load the value of memory byte x into the accu
010xxxxx   BEQ x   if the value of the accu is 0 load the value x into the pc
011-----   NOP     no operation
100-----   DEC     subtract 1 from the accu
101-----   INC     add 1 to the accu
110xxxxx   JMP x   load the value x into the pc
111-----   HLT     terminate program
In the beginning, program counter and accumulator are set to 0. After fetching an instruction but before its execution, the program counter is incremented. You can assume that programs will terminate.

Input

The input file contains several test cases. Each test case specifies the contents of the memory prior to execution of the program. Byte 0 through 31 are given on separate lines in binary representation. A byte is denoted by its highest-to-lowest bits. Input is terminated by EOF

Output

For each test case, output on a line the value of the accumulator on termination in binary representation, again highest bits first.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
 
Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input file contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h = w = 0. Otherwise, 1 ≤ h, w ≤ 11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alice and Bob haven't met for some time. Bob isn't very happy about this, so he urges Alice to finally make time for a meeting. Let's listen to an extract from a phone call:
Alice: ... maybe we should meet on neutral territory.
Bob: I've already heard this from you --- two years ago.
Alice: I know ; I just haven't found yet a suitable place that is roughly at the same distance from both yours and mine.
Bob: Well, the geometric place of the points that are equidistant from two given points on the surface of a sphere (and the earth is a sphere rather than a disc) is a great circle (namely the one which intersects the great circle through the given points orthogonally at the center of them). If you insist only on approximately equal distances though, we get a zone of some kilometers width and about 40000 km length. Not everything in this zone is water. Thus I think it is a feasible task to find a fitting place.
Alice: Now, if I tell you to pick any, we'll certainly land up in Honolulu.
Bob: Which is not a too bad idea. So, may I pick any ?
Alice: As long as I don't have to accept --- but I'm open to suggestions.
Bob: Honolulu ?
Alice: Is it situated on aforementioned geometric place at all ??!
Bob: Not quite ...
Nice. Now let's stop the preliminaries and come to the facts: Given two locations on the earth's surface you can find the geometric place of all equidistant points on the surface. For another given location calculate its distance on the surface to this geometric place. Assume that the earth is a sphere with a radius of 6378 km.

Input

The input file consists of two parts: a list of locations and a list of queries.
The location list consists of up to 100 lines, one line per location. Each contains a string and two floating-point numbers, separated by whitespace, representing the name of the location, its latitude and its longitude. Names are unique and shorter than 30 characters and do not contain whitespace. Latitudes are between -90 (South Pole) and 90 (North Pole) inclusive. Longitudes are between -180 and 180 inclusive where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.) The location list is terminated by a line consisting of a single "#".
Each line in the query list contains three names of locations. You can assume the first location to be Alice's home, the second location to be Bob's home and the third location to be a possible meeting point. The query list is terminated by a line consisting of a single "#".

Output

For each query, output a line saying "M is x km off A/B equidistance." with M,x,A,B appropriately replaced by the location names and the calculated distance rounded to the nearest integer.
If one of the locations in the query didn't occur in the list of locations print "?" instead of the distance.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Recall the definition of the Fibonacci numbers:
f₁ := 1
f₂ := 2
f_n := f_{n - 1} + f_{n - 2} (n ≥ 3)
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a ≤ b ≤ 10¹⁰⁰. The numbers a and b are given with no superfluous leading zeros.

Output

For each test case output on a single line the number of Fibonacci numbers fi with a ≤ f_i ≤ b.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Among other things, Computational Molecular Biology deals with processing genetic sequences. Considering the evolutionary relationship of two sequences, we can say that they are closely related if they do not differ very much. We might represent the relationship by a tree, putting sequences from ancestors above sequences from their descendants. Such trees are called phylogenetic trees.
Whereas one task of phylogenetics is to infer a tree from given sequences, we'll simplify things a bit and provide a tree structure - this will be a complete binary tree. You'll be given the n leaves of the tree. Sure you know, n is always a power of 2. Each leaf is a sequence of amino acids (designated by the one-character-codes you can see in the figure). All sequences will be of equal length l. Your task is to derive the sequence of a common ancestor with minimal costs.

The costs are determined as follows: every inner node of the tree is marked with a sequence of length l, the cost of an edge of the tree is the number of positions at which the two sequences at the ends of the edge differ, the total cost is the sum of the costs at all edges. The sequence of a common ancestor of all sequences is then found at the root of the tree. An optimal common ancestor is a common ancestor with minimal total costs.

Input

The input file contains several test cases. Each test case starts with two integers n and l, denoting the number of sequences at the leaves and their length, respectively. Input is terminated by n = l = 0. Otherwise, 1 ≤ n ≤ 1024 and 1 ≤ l ≤ 1000. Then follow n words of length l over the amino acid alphabet. They represent the leaves of a complete binary tree, from left to right.

Output

For each test case, output a line containing some optimal common ancestor and the minimal total costs.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“Hike on a Graph” is a game that is played on a board on which an undirected graph is drawn. The graph is complete and has all loops, i.e. for any two locations there is exactly one arrow between them. The arrows are coloured. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players may do a move. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same colour as the arrow between the two opponents' pieces.

In the sixties (“make love not war”) a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.

Input

The input file contains several test cases. Each test case starts with the number n. Input is terminated by n = 0. Otherwise, 1 ≤ n ≤ 50. Then follow three integers p₁, p₂, p₃ with 1 ≤ p_i ≤ n denoting the starting locations of the game pieces. The colours of the arrows are given next as a n × n matrix of whitespace-separated lower-case letters. The element m_ij denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical.

Output

For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word “impossible” if that is not possible for the given board and starting locations.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A relay is a race for two or more teams of runners. Each member of a team runs one section of the race. Your task is to help to evaluate the results of a relay race.

You have to process several teams. For each team you are given a list with the running times for every section of the race. You are to compute the average time per kilometer over the whole distance. That's easy, isn't it?

So if you like the fun and challenge competing at this contest, perhaps you like a relay race, too. Students from Ulm participated e.g. at the "SOLA" relay in Zurich, Switzerland. For more information visit http://www.sola.asvz.ethz.ch/ after the contest is over.

Input

The first line of the input specifies the number of sections n followed by the total distance of the relay d in kilometers. You may safely assume that 1 ≤ n ≤ 20 and 0.0 ≤ d ≤ 200.0. Every following line gives information about one team: the team number t (an integer, right-justified in a field of width 3) is followed by the n results for each section, separated by a single space. These running times are given in the format "h:mm:ss" with integer numbers for the hours, minutes and seconds, respectively. In the special case of a runner being disqualified, the running time will be denoted by "-:--:--". Finally, the data on every line is terminated by a newline character. Input is terminated by EOF.

Output

For each team output exactly one line giving the team's number t right aligned in a field of width 3, and the average time for this team rounded to whole seconds in the format "m:ss". If at least one of the team's runners has been disqualified, output "-" instead. Adhere to the sample output for the exact format of presentation.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: "But I want to use feet, not meters!"). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We'll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.

You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.

Input

The input file contains several test cases. Each test case starts with two numbers n and k. Input is terminated by n = k = 0. Otherwise, 1 ≤ n ≤ 100000 and there follow n integers with absolute values ≤ 10000 which constitute the sequence. Then follow k queries for this sequence. Each query is a target t with 0 ≤ t ≤ 1000000000.

Output

For each query output 3 numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with 1 and go up to n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n - 1 numbers is called the Prufer code of the tree. Your task is, given a tree, to compute its Prufer code. The tree is denoted by a word of the language specified by the following grammar:

T ::= "(" N S ")"
S ::= " " T S
      | empty
N ::= number

That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample input. To generate further sample input, you may use your solution to Problem 7455.

Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".

Input

The input contains several test cases. Each test case specifies a tree as described above on one line of the input file. Input is terminated by EOF. You may assume that 1 ≤ n ≤ 50.

Output

For each test case generate a single line containing the Prufer code of the specified tree. Separate numbers by a single space. Do not print any spaces at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n - 1 numbers is called the Prufer code of the tree.

Your task is, to reconstruct a tree, given its Prufer code. The tree should be denoted by a word of the language specified by the following grammar:

T ::= "(" N S ")"
S ::= " " T S
     | empty
N ::= number

That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample output. To generate further sample input, you may use your solution to Problem 7454.

Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".

Input

The input contains several test cases. Each test case specifies the Prufer code of a tree on one line. You will find n - 1 numbers separated by a single space. Input is terminated by EOF. You may assume that 1 ≤ n ≤ 50.

Output

For each test case generate a single line containing the corresponding tree, denoted as described above. Note that, in general, there are many ways to denote such a tree: choose your favourite one.

Sample Input  Download

Sample Output  Download

Tags

Discuss