Description

 Stringld(left delete) is a function that gets a string and deletes its leftmost character (for instance Stringld(``acm") returns ``cm").

You are given a list of distinct words, and at each step, we apply stringld on every word in the list. Write a program that determines the number of steps that can be applied until at least one of the conditions become true:

1. A word becomes empty string, or
2. a duplicate word is generated.

For example, having the list of words aab, abac, and caac, applying the function on the input for the first time results in ab, bac, and aac. For the second time, we get b, ac, and ac. Since in the second step, we have two ac strings, the condition 2 is true, and the output of your program should be 1. Note that we do not count the last step that has resulted in duplicate string. More examples are found in the sample input and output section.

Input

There are multiple test cases in the input. The first line of each test case is n (1≤n≤100) , the number of words.

Each of the next n lines contains a string of at most 100 lower case characters.

The input terminates with a line containing `0'.

Output

For each test case, write a single line containing the maximum number of stringld we can call.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ethan wants to draw a painting on an m×n board. He can draw some strips on the board using a paintbrush of width one. In each step, he must choose a new color and paint a full column or a full row. He has a great image to be drawn on the board, but he doesn't know which color to use first. You must help him in finding out the order of colors.

Input

There are multiple test cases in the input. The first line of each test case contains two integers m and n , the size of the board (0 < m, n < 100) . Following the first line, there are m lines with n integers denoting the color in each cell. All the colors are positive integer numbers less than 10000. The input is terminated with a single line containing two consecutive zeros.

Output

For each test case, write a single line containing the order of colors used to paint the board. If there are several answers, output the one which is lexicographically smallest (considering each number as a symbol).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After years as a brick-layer, you've been called upon to analyze the instability of brick walls. The instability of a wall can be approximated by the maximum damage to a wall in case of taking one brick out. A brick will fall if all bricks that are directly underneath it are removed. Note that if the space underneath a brick is partially empty, it does not fall. You are given the description of all bricks in a wall, and must determine the instability of the wall as described in the following sections.

Input

There are multiple test cases in the input. Each test case consists of a single line, ``M N " (1≤M, N≤100) where M and N indicate the height and width (in units), respectively, of the input wall.

Each of the next M lines is a string of N digits which specifies a row in the wall. Each brick in a row is represented by a substring of the row (like s ) such that every digit in s is the same, which is equal to the length of s too. For example, 333 and 22 are two bricks of length 3 and 2 respectively, but 111 specifies three bricks of length one. A 0 in a row means there is no brick in that place of wall. Note that the height of each brick is one. The input terminates with a line containing `0 0'. You may assume that the input is correct. This means:

1. There is no brick such that the length of the brick does not conform to the digits in the brick (like 222 in the row 12221).
2. No brick can fall initially.

Output

For each test case, write a single line containing maximum sum of the bricks' lengths that will fall if we take one brick out (including that brick).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A new computer game has just arrived and as an active and always-in-the-scene player, you should finish it before the next university term starts. At each stage of this game, you have to shoot an enemy robot on its weakness point. The weakness point of a robot is always the ``center of mass" of its 2D shape in the screen. Fortunately, all robot shapes are simple polygons with uniform density and you can write programs to calculate exactly the center of mass for each polygon.

Let's have a more formal definition for center of mass (COM). The center of mass for a square, (also circle, and other symmetric shapes) is its center point. And, if a simple shape C is partitioned into two simple shapes A and B with areas S_A and S_B , then COM(C) (as a vector) can be calculated by

COM(C) = .

As a more formal definition, for a simple shape A with area S_A :

COM(A) = 

Input

The input contains a number of robot definitions. Each robot definition starts with a line containing n , the number of vertices in robot's polygon (n≤100) . The polygon vertices are specified in the next n lines (in either clockwise or counter-clock-wise order). Each of these lines contains two space-separated integers showing the coordinates of the corresponding vertex. The absolute value of the coordinates does not exceed 100. The case of n = 0 shows the end of input and should not be processed.

Output

The i -th line of the output should be of the form ``Stage #i : x y " (omit the quotes), where (x, y ) is the center of mass for the i -th robot in the input. The coordinates must be rounded to exactly 6 digits after the decimal point.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have just run out of disk space and decided to delete some of your directories. Rationally, you will first have an exploration of what you have in your file system. And more rationally, you will do this exploration through a command line interface. The interface used in this problem is called ``MSDOS-", since it is something like MSDOS with fewer features. The commands of MSDOS- are as follows:

• cd < directory >
  Assuming < directory > to be the name of a relative descendant of current directory, this command changes the current directory to < directory > . For example, when the current directory is ``AB" and one of its descendants is ``CD", the execution of ``cd CD" will change the current directory to ``ABCD".

• cd 

  This command changes the current directory to ``" (the root of the file system). For example, when the current directory is ``AB", the execution of ``cd " will change the current directory to ``".

• cd ..

  Assuming the current directory to be anything except ``", this command changes the current directory to its parent directory. For example, when the current directory is ``AB", the execution of ``cd .." will change the current directory to ``A".

• cd  < directory >

  This command is equivalent to the execution of the following two commands:

  cd

  cd < directory >

• dir

  This command lists the name of files and directories directly in the current directory, each on a separate line. These filedirectory names are made up of (lowercase and uppercase) letters, digits, and dots (``."). Directory names precede the file names in the list, and each one, comes alone in a single line. On the contrary, each file name is accompanied by its size separated by a space. A sample output of ``dir" is as follows:

  HW1 HW1.old Syllab.pdf 10000 notes.txt 3241  

• deltree < directory >

  Assuming < directory > to be the name of a relative descendant of current directory, this command tries to delete < directory > and all its descendant files and subdirectories (and thus, freeing that much of space). For example, when the current directory is ``AB" and one of its descendants is ``CD", the execution of ``deltree CD" will try to delete directory ``ABCD" and all of its descendant files and directories.

• deltree  < directory >

  This command is equivalent to the execution of the following two commands:

  cd

  deltree < directory >

• exit

  This command terminates the command line interface.

A ``scenario" is an exploration (a consistent series of ``cd" and ``dir" commands and their results, starting from root) followed by exactly one ``deltree" command. Given a scenario, you are to find the maximum space guaranteed to be freed by executing its ``deltree" command.

Input

Input contains multiple independent scenarios. There is an empty line after each scenario. The input ends with an ``exit" command. There is a ``>" sign before each command in the input (with no spaces in between). The length of each file name does not exceed 50. You may assume that the input is correct.

Output

Write the result of the i -th scenario as a single integer on the i -th line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A new Solar Eclipse is going to happen in Mars. Scientists from different parts of the world are travelling to Mars to watch and study this phenomenon. You just managed to calculate exactly the best point of Mars lands for your study of the eclipse, and want to land your flying saucer on that place. But, you notice that there are already other spacecrafts landed on near that area.

In the bird's eye view, all the spacecrafts (including yours) are circles with constant radius R . Logically, you hate to land your spacecraft on the others (no intersection of areas is allowed, but touching the other crafts is acceptable), though, the other saucers did not obey this rule on their own landings (i.e. their circles might have positive-area intersections with each other). In order to land your own craft on Mars, you want to find the place which minimizes the distance between the center of your flying saucer and your already calculated best point (and obeys the no-intersection rule). That's what you should do in this problem.

Input

The input has multiple test cases. Each test case starts with a line containing an integer n (number of already landed spacecrafts), and a real number R . The land is small enough for us to be modeled by a two-dimensional plane, and (0,0) is conventionally the best point for us to land. Each of the next n lines specifies the location of a landed flying saucer by giving two real numbers x and y as the coordinates of its center.

The input ends with a case of n = R = 0 which must not be processed. Assume n≤100 , R > 0 , and their absolute value does not exceed 1000.

Output

Write the result of the i -th test case on the i -th line of the output. You should just write the minimum possible distance between the center of your landed craft and the origin of the plane, rounded to exactly 6 digits after the decimal point.

Sample Input  Download

Sample Output  Download

Tags

Discuss