Problem A: Gangs

The downtown core of Inner City is laid out as a grid, with numbered streets running north-south from 1st Street in the west to 20th Street in the east, and numbered avenues running east-west from 1st Avenue in the north to 20th Avenue in the south. The area is controlled by two gangs, the Blips and the Cruds. The boundary between their territory is the Green Line, running diagonally from the intersection of 1st Street and 1st Avenue to the intersection of 20th Street and 20th Avenue. The Blips control the area to the southwest of the Green Line, and the Cruds the area to the northeast.

To prove their virility, the Blips go on "runs" through Crud territory, starting at 1st Avenue and 1st Street and ending at a point on the Green Line that varies from night to night. A run may return to the Green Line in between but never crosses it. A run uses avenues only in the east direction and streets only in the south direction. Thus a run can be described by a string of E's and S's of length 2N-2; such a run ends at Nth Street and Nth Avenue.

The Blips judge the runs made on a given night (all of which have the same length) by how "OG" they are. A run R1 is more OG than a run R2 if and only if:

R2 returns to the Green Line for the first time at an earlier point than when R1 returns to the Green Line, or
R1 and R2 return to the Green Line at the same point, but the portion of R1 to that point (ignoring the initial E and final S) is more OG than the portion of R2 to that point (also ignoring the initial E and final S), or
R1 and R2 return to the Green Line at the same point and are identical to that point, but the rest of R1 is more OG than the rest of R2.

Examples corresponding to these three cases:

EESS is more OG than ESES.
EEESSS is more OG than EESESS
EESSEESS is more OG than EESSESES.

If all the runs of a given length are ordered according to how OG they are, then the rank of a run is its position in the resulting list. EESS has rank 1 and ESES has rank 2.

Your task is to write a program to help the Blips plan and judge their nightly activities. The input to the program is a series of instances followed by 0 0. An instance consists of a line containing a positive integer N, representing the terminus of that night's run (Nth Street and Nth Avenue), followed by positive integer M. The output corresponding to each instance is the run of length 2N-2 of rank M, or ERROR if there are fewer than M runs of length 2N-2.

Sample Input

Output for Sample Input

EESS
ESES
ERROR

Problem B: Smeech

Professor Octastichs has invented a new programming language, Smeech. An expression in Smeech may be a positive or negative integer, or may be of the form (p e₁ e₂) where p is a real number between 0 and 1 (inclusive) and e₁ and e₂ are Smeech expressions. The value represented by a Smeech expression is as follows:

An integer represents itself
With probability p, (p e₁ e₂) represents x+y where x is the value of e₁ and y is the value of e₂; otherwise it represents x-y.

Given a Smeech expression, what is its expected value?

Input consists of several Smeech expressions, one per line, followed by a line containing (). For each expression, output its expected value to two decimal places.

Sample Input

7
(.5 3 9)
()

Output for Sample Input

7.00
3.00

Problem C: The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem.

The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predators, the geese population was out of control. The people of Loowater mostly kept clear of the geese. Occasionally, a goose would attack one of the people, and perhaps bite off a finger or two, but in general, the people tolerated the geese as a minor nuisance.

One day, a freak mutation occurred, and one of the geese spawned a multi-headed fire-breathing dragon. When the dragon grew up, he threatened to burn the Kingdom of Loowater to a crisp. Loowater had a major problem. The king was alarmed, and called on his knights to slay the dragon and save the kingdom.

The knights explained: "To slay the dragon, we must chop off all its heads. Each knight can chop off one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height."

Would there be enough knights to defeat the dragon? The king called on his advisors to help him decide how many and which knights to hire. After having lost a lot of money building Mir Park, the king wanted to minimize the expense of slaying the dragon. As one of the advisors, your job was to help the king. You took it very seriously: if you failed, you and the whole kingdom would be burnt to a crisp!

Input Specification:

The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of knights in the kingdom. The next n lines each contain an integer, and give the diameters of the dragon's heads, in centimetres. The following m lines each contain an integer, and specify the heights of the knights of Loowater, also in centimetres.

The last test case is followed by a line containing:

0 0

Output Specification:

For each test case, output a line containing the minimum number of gold coins that the king needs to pay to slay the dragon. If it is not possible for the knights of Loowater to slay the dragon, output the line:

Loowater is doomed!

Sample Input:

Output for Sample Input:

11
Loowater is doomed!

Problem D: Tournament

Every September, the Kingdom of Loowater holds a jousting tournament. In each of a series of event, a pair of knights attempt to knock each other from their respective horses. The winning knight is paired with another, while the loser is elimnated. This process continues until all but one knight is eliminated; this knight is declared champion.

The tournament schedule is organized so that no knight needs to compete in more than e events to be champion, for the minimum possible e given k, the number of knights. In order to construct the schedule, it may be necessary to identify several knights who compete in fewer than e events; these knights are said to be awarded a bye and are excluded from the first round of competition.

The first round of competition involves pairing as many knights as possible among those who are not awarded a bye. The competition is more interesting if the knights in each pair are as evenly matched in ability as possible. You are to determine which knights should be awarded a bye so as to make the first round as interesting as possible.

Standard input consists of several test cases followed by a line containing 0. Each test case begins with an integer 1 < k ≤ 2500 , the number of knights. i lines follow, each giving the name and ability of a knight. The name is a string of lower case letters not longer than 20; the ability is a real number.

The mismatch between knights with abilities a and b respectively is defined to be (a-b)². For each test case, output the names of the knights to be given a bye such that the sum of all mismatch values for pairs of knights competing in the first round is minimized. If there are several solutions, any will do. Output an empty line between test cases.

Sample Input

3
gallahad 10
lancelot 11
mccartney 2
0

Output for Sample Input

mccartney

Problem E: Wedding

Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.

The input consists of a number of test cases, followed by a line containing 0 0. Each test case gives n, the number of couples, followed by the number of adulterous pairs, followed by the pairs, in the form "4h 2w" (husband from couple 4, wife from couple 2), or "10w 4w", or "3h 1h". Couples are numbered from 0 to n-1 with the bride and groom being 0w and 0h. For each case, output a single line containing a list of the people that should be seated on the same side as the bride. If there are several solutions, any one will do. If there is no solution, output a line containing "bad luck".

Sample Input

10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

Possible Output for Sample Input

1h 2h 3w 4h 5h 6h 7h 8h 9h