Description

Dr. Grey is a data analyst, who visualizes various aspects of data received from all over the world everyday. He is extremely good at sophisticated visualization tools, but yet his favorite is a simple self-made histogram generator.

Figure 1 is an example of histogram automatically produced by his histogram generator. A histogram is a visual display of frequencies of value occurrences as bars. In this example, values in the interval 0-9 occur five times, those in the interval 10-19 occur three times, and 20-29 and 30-39 once each.

Dr. Grey's histogram generator is a simple tool. First, the height of the histogram is fixed, that is, the height of the highest bar is always the same and those of the others are automatically adjusted proportionately. Second, the widths of bars are also fixed. It can only produce a histogram of uniform intervals, that is, each interval of a histogram should have the same width (10 in the above example). Finally, the bar for each interval is painted in a grey color, where the colors of the leftmost and the rightmost intervals are black and white, respectively, and the darkness of bars monotonically decreases at the same rate from left to right. For instance, in Figure 1, the darkness levels of the four bars are 1, 2/3, 1/3, and 0, respectively.

In this problem, you are requested to estimate ink consumption when printing a histogram on paper. The amount of ink necessary to draw a bar is proportional to both its area and darkness.

Input

The input consists of multiple datasets, each of which contains integers and specifies a value table and intervals for the histogram generator, in the following format.

n w
v₁
v_1
.
.
v_n

n is the total number of value occurrences for the histogram, and each of the n lines following the first line contains a single value. Note that the same value may possibly occur multiple times.

w is the interval width. A value v is in the first (i.e. leftmost) interval if 0v < w , the second one if wv < 2w , and so on. Note that the interval from 0 (inclusive) to w (exclusive) should be regarded as the leftmost even if no values occur in this interval. The last (i.e. rightmost) interval is the one that includes the largest value in the dataset.

You may assume the following.

1n100
10w50
0vi100	for 1in

You can also assume that the maximum value is no less than w . This means that the histogram has more than one interval. The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output a line containing the amount of ink consumed in printing the histogram. One unit of ink is necessary to paint one highest bar black. Assume that 0.01 units of ink per histogram is consumed for various purposes except for painting bars such as drawing lines and characters (see Figure 1). For instance, the amount of ink consumed in printing the histogram in Figure 1 is:

	1×1 + × + × +0× + 0.01
=	1 +  +  + 0.01
=	1.47666...

Each output value should be in a decimal fraction and may have an error less than 10^-5 .

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hideyuki is allowed by his father Ujisato some 1000 yen bills every month for his pocket money. In the first day of every month, the number of bills is decided as follows. Ujisato prepares n pieces of m -sided dice and declares the cutback k . Hideyuki rolls these dice. The number of bills given is the sum of the spots of the rolled dice decreased by the cutback. Fortunately to Hideyuki, Ujisato promises him to give at least one bill, even if the sum of the spots does not exceed the cutback. Each of the dice has spots of 1 through m inclusive on each side, and the probability of each side is the same.

In this problem, you are asked to write a program that finds the expected value of the number of given bills.

For example, when n = 2 , m = 6 and k = 3 , the probabilities of the number of bills being 1, 2, 3, 4, 5, 6, 7, 8 and 9 are  +  + ,,,,,,, and  , respectively. Therefore, the expected value is ( +  + )×1 + ×2 + ×3 + ×4 + ×5 + ×6 + ×7 + ×8 + ×9 , which is approximately 4.11111111.

Input

The input is a sequence of lines each of which contains three integers n , m and k in this order. They satisfy the following conditions.

1n

2m

0k < nm

nm×mn < 100000000(108)

The end of the input is indicated by a line containing three zeros.

Output

The output should be comprised of lines each of which contains a single decimal fraction. It is the expected number of bills and may have an error less than 10^-7 . No other characters should occur in the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the middle of Tyrrhenian Sea, there is a small volcanic island called Chronus. The island is now uninhabited but it used to be a civilized island. Some historical records imply that the island was annihilated by an eruption of a volcano about 800 years ago and that most of the people in the island were killed by pyroclastic flows caused by the volcanic activity. In 2003, a European team of archaeologists launched an excavation project in Chronus Island. Since then, the project has provided many significant historic insights. In particular the discovery made in the summer of 2008 astonished the world: the project team excavated several mechanical watches worn by the victims of the disaster. This indicates that people in Chronus Island had such a highly advanced manufacturing technology.

Shortly after the excavation of the watches, archaeologists in the team tried to identify what time of the day the disaster happened, but it was not successful due to several diffculties. First, the extraordinary heat of pyroclastic flows severely damaged the watches and took away the letters and numbers printed on them. Second, every watch has a perfect round form and one cannot tell where the top of the watch is. Lastly, though every watch has three hands, they have a completely identical look and therefore one cannot tell which is the hour, the minute, or the second (It is a mystery how the people in Chronus Island were distinguishing the three hands. Some archaeologists guess that the hands might be painted with different colors, but this is only a hypothesis, as the paint was lost by the heat). This means that we cannot decide the time indicated by a watch uniquely; there can be a number of candidates. We have to consider different rotations of the watch. Furthermore, since there are several possible interpretations of hands, we have also to consider all the permutations of hands.

You are an information archaeologist invited to the project team and are asked to induce the most plausible time interval within which the disaster happened, from the set of excavated watches.

In what follows, we express a time modulo 12 hours. We write a time by the notation hh : mm : ss , where hh , mm , and ss stand for the hour (hh = 00, 01, 02,..., 11) , the minute (mm = 00, 01, 02,..., 59) , and the second (ss = 00, 01, 02,..., 59) , respectively. The time starts from 00:00:00 and counts up every second 00:00:00, 00:00:01, 00:00:02, ^... , but it reverts to 00:00:00 every 12 hours.

The watches in Chronus Island obey the following conventions of modern analog watches.

• A watch has three hands, i.e. the hour hand, the minute hand, and the second hand, though they look identical as mentioned above.
• Every hand ticks 6 degrees clockwise in a discrete manner. That is, no hand stays between ticks, and each hand returns to the same position every 60 ticks.
• The second hand ticks every second.
• The minute hand ticks every 60 seconds.
• The hour hand ticks every 12 minutes.

At the time 00:00:00, all the three hands are located at the same position.

Because people in Chronus Island were reasonably keen to keep their watches correct and pyroclastic flows spread over the island quite rapidly, it can be assumed that all the watches were stopped in a short interval of time. Therefore it is highly expected that the time the disaster happened is in the shortest time interval within which all the excavated watches have at least one candidate time.

You must calculate the shortest time interval and report it to the project team.

Input

The input consists of multiple datasets, each of which is formatted as follows.

n
s₁ t₁ v₁
s₂ t₂ v₂
...
s_n t_n v_n
The first line contains a single integer n (2n10) , representing the number of the watches. The three numbers s_i , t_i , u_i in each line are integers such that 0s_i, t_i, u_i59 and they specify the positions of the three hands by the number of ticks relative to an arbitrarily chosen position.

Note that the positions of the hands of a watch can be expressed in many different ways. For example, if a watch was stopped at the time 11:55:03, the positions of hands can be expressed differently by rotating the watch arbitrarily (e.g. 59 55 3, 0 56 4, 1 57 5, etc.) and as well by permuting the hour, minute, and second hands arbitrarily (e.g. 55 59 3, 55 3 59, 3 55 59, etc.).

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

Output

For each dataset, output the shortest time interval within which all the watches given in the dataset have at least one candidate time. The output must be written in a single line in the following format for each dataset.

hhmmssh'h'm'm's's'

Each line contains a pair of times hhmmss and h'h'm'm's's' , indicating that the shortest interval begins at hhmmss and ends at h'h'm'm's's' inclusive. The beginning time and the ending time are separated by a single space and each of them should consist of hour, minute, and second in two digits separated by colons. No extra characters should appear in the output.

In calculating the shortest interval, you can exploit the facts that every watch has at least one candidate time and that the shortest time interval contains 00:00:00 only if the interval starts from 00:00:00 (i.e. the shortest interval terminates before the time reverts to 00:00:00).

If there is more than one time interval that gives the shortest, output the one that first comes after 00:00:00 inclusive.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Taro attempts to tell digits to Hanako by putting straight bars on the floor. Taro wants to express each digit by making one of the forms shown in Figure 2.

Since Taro may not have bars of desired lengths, Taro cannot always make forms exactly as shown in Figure 2. Fortunately, Hanako can recognize a form as a digit if the connection relation between bars in the form is kept. Neither the lengths of bars nor the directions of forms affect Hanako's perception as long as the connection relation remains the same. For example, Hanako can recognize all the awkward forms in Figure 3 as digits. On the other hand, Hanako cannot recognize the forms in Figure 4 as digits. For clarity, touching bars are slightly separated in Figures 2, 3 and 4. Actually, touching bars overlap exactly at one single point.

In the forms, when a bar touches another, the touching point is an end of at least one of them. That is, bars never cross. In addition, the angle of such two bars is always a right angle.

To enable Taro to represent forms with his limited set of bars, positions and lengths of bars can be changed as far as the connection relations are kept. Also, forms can be rotated.

Keeping the connection relations means the following.

• Separated bars are not made to touch.
• Touching bars are not made separate.
• When one end of a bar touches another bar, that end still touches the same bar. When it touches a midpoint of the other bar, it remains to touch a midpoint of the same bar on the same side.
• The angle of touching two bars is kept to be the same right angle (90 degrees and -90 degrees are considered different, and forms for 2 and 5 are kept distinguished).

Your task is to find how many times each digit appears on the floor. The forms of some digits always contain the forms of other digits. For example, a form for 9 always contains four forms for 1, one form for 4, and two overlapping forms for 7. In this problem, ignore the forms contained in another form and count only the digit of the ``largest" form composed of all mutually connecting bars. If there is one form for 9, it should be interpreted as one appearance of 9 and no appearance of 1, 4, or 7.

Input

The input consists of a number of datasets. Each dataset is formatted as follows.

n
x1a	y1a	x1b	y1b
x2a	y2a	x2b	y2b
xna	yna	xnb	xnb

represents the number of bars in the dataset. For the rest of the lines, one line represents one bar. Four integers x_a , y_a , x_b , y_b , delimited by single spaces, are given in each line. x_a and y_a are the x- and y - coordinates of one end of the bar, respectively. x_b and y_b are those of the other end. The coordinate system is as shown in Figure 5. You can assume 1n1000 and 0x_a, y_a, x_b, y_b1000 .

The end of the input is indicated by a line containing one zero.

You can also assume the following conditions.

• More than two bars do not overlap at one point.
• Every bar is used as a part of a digit. Non-digit forms do not exist on the floor.
• A bar that makes up one digit does not touch nor cross any bar that makes up another digit.
• There is no bar whose length is zero.

Output

For each dataset, output a single line containing ten integers delimited by single spaces. These integers represent how many times 0, 1, 2,... , and 9 appear on the floor in this order. Output lines must not contain other characters.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A long time ago in a galaxy, far, far away, there were N spheres with various radii. Spheres were mirrors, that is, they had reflective surfaces ...

You are standing at the origin of the galaxy (0, 0, 0), and emit a laser ray to the direction (u, v, w) . The ray travels in a straight line.

When the laser ray from I hits the surface of a sphere at Q , let N be a point outside of the sphere on the line connecting the sphere center and Q . The reflected ray goes to the direction towards R that satisfies the following conditions: (1) R is on the plane formed by the three points I , Q and N , (2) IQN = NQR , as shown in Figure 6.

After it is reflected several times, finally it goes beyond our observation. Your mission is to write a program that identifies the last reflection point.

Input

The input consists of multiple datasets, each in the following format.

N
u	v	w
x1	y1	z1	r1
xN	yN	zN	rN

 
The first line of a dataset contains a positive integer N which is the number of spheres. The next line contains three integers u , v and w separated by single spaces, where (u, v, w) is the direction of the laser ray initially emitted from the origin.

Each of the following N lines contains four integers separated by single spaces. The i -th line corresponds to the i -th sphere, and the numbers represent the center position (x_i, y_i, z_i) and the radius r_i .

N, u, v, w, x_i, y_i, z_i and r_i satisfy the following conditions.

1N100

-100u, v, w100

-100x_i, y_i, z_i100

5r_i30

The ray is known to be reflected by the sphere surfaces at least once, and at most five times. You can assume that the angle between the ray and the line connecting the sphere center and the reflection point, which is known as the angle of reflection (i.e.  in Figure 6), is less than 85 degrees for each point of reflection.

The last dataset is followed by a line containing a single zero.

Output

For each dataset in the input, you should print the x - , y - and z - coordinates of the last reflection point separated by single spaces in a line. No output line should contain extra characters. No coordinate values in the output should have an error greater than 0.01.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

On a small planet named Bandai, a landing party of the starship Tadamigawa discovered colorful cubes traveling on flat areas of the planet surface, which the landing party named beds. A cube appears at a certain position on a bed, travels on the bed for a while, and then disappears. After a longtime observation, a science officer Lt. Alyssa Ogawa of Tadamigawa found the rule how a cube travels on a bed.

A bed is a rectangular area tiled with squares of the same size.

• One of the squares is colored red,
• one colored green,
• one colored blue,
• one colored cyan,
• one colored magenta,
• one colored yellow,
• one or more colored white, and
• all others, if any, colored black.

Initially, a cube appears on one of the white squares. The cube's faces are colored as follows.

The cube can roll around a side of the current square at a step and thus rolls on to an adjacent square. When the cube rolls on to a chromatically colored (red, green, blue, cyan, magenta or yellow) square, the top face of the cube after the roll should be colored the same. When the cube rolls on to a white square, there is no such restriction. The cube should never roll on to a black square.

Throughout the travel, the cube can visit each of the chromatically colored squares only once, and any of the white squares arbitrarily many times. As already mentioned, the cube can never visit any of the black squares. On visit to the final chromatically colored square, the cube disappears. Somehow the order of visits to the chromatically colored squares is known to us before the travel starts.

Your mission is to find the least number of steps for the cube to visit all the chromatically colored squares in the given order.

Input

The input is a sequence of datasets. A dataset is formatted as follows:

w d
c₁₁ .. c_w1
...
c_1d ... c_wd
v₁v₂v₃v₄v₅v₆

The first line is a pair of positive integers w and d separated by a space. The next d lines are w -character-long strings c₁₁ ^... c_w1, ^... , c_1d ^... c_wd with no spaces. Each character c_ij is one of the letters r, g, b, c, m, y, wand k, which stands for red, green, blue, cyan, magenta, yellow, white and black respectively, or a sign #. Each of r, g, b, c, m, y and # occurs once and only once in a dataset. The last line is a six-character-long stringv₁v₂v₃v₄v₅v₆ which is a permutation of ``rgbcmy".

The integers w and d denote the width (the length from the east end to the west end) and the depth (the length from the north end to the south end) of a bed. The unit is the length of a side of a square. You can assume that neither w nor d is greater than 30.

Each character c_ij shows the color of a square in the bed. The characters c₁₁ , c_w1 , c_1d and c_wd correspond to the north-west corner, the north-east corner, the south-west corner and the southeast corner of the bed respectively. If c_ij is a letter, it indicates the color of the corresponding square. If c_ij is a #, the corresponding square is colored white and is the initial position of the cube.

The string v₁v₂v₃v₄v₅v₆ shows the order of colors of squares to visit. The cube should visit the squares colored v₁, v₂, v₃, v₄, v₅ and v₆ in this order. The end of the input is indicated by a line containing two zeros separated by a space.

Output

For each input dataset, output the least number of steps if there is a solution, or ``unreachable" if there is no solution. In either case, print it in one line for each input dataset.

Sample Input  Download

Sample Output  Download

Tags

Discuss