All Problems

Links

Problem A

Equal Total Scores

Taro and Hanako have numbers of cards in their hands. Each of the cards has a score on it. Taro and Hanako wish to make the total scores of their cards equal by exchanging one card in one's hand with one card in the other's hand. Which of the cards should be exchanged with which?

Note that they have to exchange their cards even if they already have cards of the same total score.

Input

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

n m
s₁
s₂
...
s_n
s_n+1
s_n+2
...
s_n+m

The first line of a dataset contains two numbers n and m delimited by a space, where n is the number of cards that Taro has and m is the number of cards that Hanako has. The subsequent n+m lines list the score for each of the cards, one score per line. The first n scores (from s₁ up to s_n) are the scores of Taro's cards and the remaining m scores (from s_n+1 up to s_n+m) are Hanako's.

The numbers n and m are positive integers no greater than 100. Each score is a non-negative integer no greater than 100.

The end of the input is indicated by a line containing two zeros delimited by a single space.

Output

For each dataset, output a single line containing two numbers delimited by a single space, where the first number is the score of the card Taro gives to Hanako and the second number is the score of the card Hanako gives to Taro. If there is more than one way to exchange a pair of cards that makes the total scores equal, output a pair of scores whose sum is the smallest.

In case no exchange can make the total scores equal, output a single line containing solely -1. The output must not contain any superfluous characters that do not conform to the format.

Sample Input

Output for the Sample Input

(End of Problem A) A B C D E F

Problem B

Monday-Saturday Prime Factors

Chief Judge's log, stardate 48642.5. We have decided to make a problem from elementary number theory. The problem looks like finding all prime factors of a positive integer, but it is not.

A positive integer whose remainder divided by 7 is either 1 or 6 is called a 7N+{1,6} number. But as it is hard to pronounce, we shall call it a Monday-Saturday number.

For Monday-Saturday numbers a and b, we say a is a Monday-Saturday divisor of b if there exists a Monday-Saturday number x such that ax = b. It is easy to show that for any Monday-Saturday numbers a and b, it holds that a is a Monday-Saturday divisor of b if and only if a is a divisor of b in the usual sense.

We call a Monday-Saturday number a Monday-Saturday prime if it is greater than 1 and has no Monday-Saturday divisors other than itself and 1. A Monday-Saturday number which is a prime in the usual sense is a Monday-Saturday prime but the converse does not always hold. For example, 27 is a Monday-Saturday prime although it is not a prime in the usual sense. We call a Monday-Saturday prime which is a Monday-Saturday divisor of a Monday-Saturday number a a Monday-Saturday prime factor of a. For example, 27 is one of the Monday-Saturday prime factors of 216, since 27 is a Monday-Saturday prime and 216 = 27 × 8 holds.

Any Monday-Saturday number greater than 1 can be expressed as a product of one or more Monday-Saturday primes. The expression is not always unique even if differences in order are ignored. For example, 216 = 6 × 6 × 6 = 8 × 27 holds.

Our contestants should write a program that outputs all Monday-Saturday prime factors of each input Monday-Saturday number.

Input

The input is a sequence of lines each of which contains a single Monday-Saturday number. Each Monday-Saturday number is greater than 1 and less than 300000 (three hundred thousand). The end of the input is indicated by a line containing a single digit 1.

Output

For each input Monday-Saturday number, it should be printed, followed by a colon `:' and the list of its Monday-Saturday prime factors on a single line. Monday-Saturday prime factors should be listed in ascending order and each should be preceded by a space. All the Monday-Saturday prime factors should be printed only once even if they divide the input Monday-Saturday number more than once.

Sample Input

Output for the Sample Input

205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998

(End of Problem B) A B C D E F

Problem C

How can I satisfy thee? Let me count the ways...

Three-valued logic is a logic system that has, in addition to "true" and "false", "unknown" as a valid value. In the following, logical values "false", "unknown" and "true" are represented by 0, 1 and 2 respectively.

Let "-" be a unary operator (i.e. a symbol representing one argument function) and let both "*" and "+" be binary operators (i.e. symbols representing two argument functions). These operators represent negation (NOT), conjunction (AND) and disjunction (OR) respectively. These operators in three-valued logic can be defined in Table C-1.

Table C-1: Truth tables of three-valued logic operators

-X		(X*Y)		(X+Y)

Let P, Q and R be variables ranging over three-valued logic values. For a given formula, you are asked to answer the number of triples (P,Q,R) that satisfy the formula, that is, those which make the value of the given formula 2. A formula is one of the following form (X and Y represent formulas).

Constants: 0, 1 or 2
Variables: P, Q or R
Negations: -X
Conjunctions: (X*Y)
Disjunctions: (X+Y)

Note that conjunctions and disjunctions of two formulas are always parenthesized.

For example, when formula (P*Q) is given as an input, the value of this formula is 2 when and only when (P,Q,R) is (2,2,0), (2,2,1) or (2,2,2). Therefore, you should output 3.

Input

The input consists of one or more lines. Each line contains a formula. A formula is a string which consists of 0, 1, 2, P, Q, R, -, *, +, (, ). Other characters such as spaces are not contained. The grammar of formulas is given by the following BNF.

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

All the formulas obey this syntax and thus you do not have to care about grammatical errors. Input lines never exceed 80 characters.

Finally, a line which contains only a "." (period) comes, indicating the end of the input.

Output

You should answer the number (in decimal) of triples (P,Q,R) that make the value of the given formula 2. One line containing the number should be output for each of the formulas, and no other characters should be output.

Sample Input

(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.

Output for the Sample Input

(End of Problem C) A B C D E F

Problem D

Twirling Robot

Let's play a game using a robot on a rectangular board covered with a square mesh (Figure D-1). The robot is initially set at the start square in the northwest corner facing the east direction. The goal of this game is to lead the robot to the goal square in the southeast corner.

Figure D-1: Example of a board

The robot can execute the following five types of commands.

"Straight":: Keep the current direction of the robot, and move forward to the next square.
"Right":: Turn right with 90 degrees from the current direction, and move forward to the next square.
"Back":: Turn to the reverse direction, and move forward to the next square.
"Left":: Turn left with 90 degrees from the current direction, and move forward to the next square.
"Halt":: Stop at the current square to finish the game.

Each square has one of these commands assigned as shown in Figure D-2. The robot executes the command assigned to the square where it resides, unless the player gives another command to be executed instead. Each time the player gives an explicit command, the player has to pay the cost that depends on the command type.

Figure D-2: Example of commands assigned to squares

The robot can visit the same square several times during a game. The player loses the game when the robot goes out of the board or it executes a "Halt" command before arriving at the goal square.

Your task is to write a program that calculates the minimum cost to lead the robot from the start square to the goal one.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows.

w h
s(1,1) ... s(1,w)
s(2,1) ... s(2,w)
...
s(h,1) ... s(h,w)
c₀ c₁ c₂ c₃

The integers h and w are the numbers of rows and columns of the board, respectively. You may assume 2 ≤ h ≤ 30 and 2 ≤ w ≤ 30. Each of the following h lines consists of w numbers delimited by a space. The number s(i, j) represents the command assigned to the square in the i-th row and the j-th column as follows.

0: "Straight"
1: "Right"
2: "Back"
3: "Left"
4: "Halt"

You can assume that a "Halt" command is assigned to the goal square. Note that "Halt" commands may be assigned to other squares, too.

The last line of a dataset contains four integers c₀, c₁, c₂, and c₃, delimited by a space, indicating the costs that the player has to pay when the player gives "Straight", "Right", "Back", and "Left" commands respectively. The player cannot give "Halt" commands. You can assume that all the values of c₀, c₁, c₂, and c₃ are between 1 and 9, inclusive.

Output

For each dataset, print a line only having a decimal integer indicating the minimum cost required to lead the robot to the goal. No other characters should be on the output line.

Sample Input

8 3
0 0 0 0 0 0 0 1
2 3 0 1 4 0 0 1
3 3 0 0 0 0 0 4
9 9 1 9
4 4
3 3 4 0
1 2 4 4
1 1 1 0
0 2 4 4
8 7 2 1
2 8
2 2
4 1
0 4
1 3
1 0
2 1
0 3
1 4
1 9 3 1
0 0

Output for the Sample Input

1
11
6

(End of Problem D) A B C D E F

Problem E

Roll-A-Big-Ball

ACM University holds its sports day in every July. The "Roll-A-Big-Ball" is the highlight of the day. In the game, players roll a ball on a straight course drawn on the ground. There are rectangular parallelepiped blocks on the ground as obstacles, which are fixed on the ground. During the game, the ball may not collide with any blocks. The bottom point of the ball may not leave the course.

To have more fun, the university wants to use the largest possible ball for the game. You must write a program that finds the largest radius of the ball that can reach the goal without colliding any obstacle block.

The ball is a perfect sphere, and the ground is a plane. Each block is a rectangular parallelepiped. The four edges of its bottom rectangle are on the ground, and parallel to either x- or y-axes. The course is given as a line segment from a start point to an end point. The ball starts with its bottom point touching the start point, and goals when its bottom point touches the end point.

The positions of the ball and a block can be like in Figure E-1 (a) and (b).

Figure E-1: Possible positions of the ball and a block

Input

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

N
sx sy ex ey
minx₁ miny₁ maxx₁ maxy₁ h₁
minx₂ miny₂ maxx₂ maxy₂ h₂
...
minx_N miny_N maxx_N maxy_N h_N

A dataset begins with a line with an integer N, the number of blocks (1 ≤ N ≤ 50). The next line consists of four integers, delimited by a space, indicating the start point (sx, sy) and the end point (ex, ey). The following N lines give the placement of blocks. Each line, representing a block, consists of five integers delimited by a space. These integers indicate the two vertices (minx, miny), (maxx, maxy) of the bottom surface and the height h of the block. The integers sx, sy, ex, ey, minx, miny, maxx, maxy and h satisfy the following conditions.

-10000 ≤ sx, sy, ex, ey ≤ 10000
-10000 ≤ minx_i < maxx_i ≤ 10000
-10000 ≤ miny_i < maxy_i ≤ 10000
1 ≤ h_i ≤ 1000

The last dataset is followed by a line with a single zero in it.

Output

For each dataset, output a separate line containing the largest radius. You may assume that the largest radius never exceeds 1000 for each dataset. If there are any blocks on the course line, the largest radius is defined to be zero. The value may contain an error less than or equal to 0.001. You may print any number of digits after the decimal point.

Sample Input

2
-40 -40 100 30
-100 -100 -50 -30 1
30 -70 90 -30 10
2
-4 -4 10 3
-10 -10 -5 -3 1
3 -7 9 -3 1
2
-40 -40 100 30
-100 -100 -50 -30 3
30 -70 90 -30 10
2
-400 -400 1000 300
-800 -800 -500 -300 7
300 -700 900 -300 20
3
20 70 150 70
0 0 50 50 4
40 100 60 120 8
130 80 200 200 1
3
20 70 150 70
0 0 50 50 4
40 100 60 120 10
130 80 200 200 1
3
20 70 150 70
0 0 50 50 10
40 100 60 120 10
130 80 200 200 3
1
2 4 8 8
0 0 10 10 1
1
1 4 9 9
2 2 7 7 1
0

Output for the Sample Input

30
1
18.16666666667
717.7857142857
50.5
50
18.16666666667
0
0

(End of Problem E) A B C D E F

Problem F

ICPC: Intelligent Congruent Partition of Chocolate

The twins named Tatsuya and Kazuya love chocolate. They have found a bar of their favorite chocolate in a very strange shape. The chocolate bar looks to have been eaten partially by Mam. They, of course, claim to eat it and then will cut it into two pieces for their portions. Since they want to be sure that the chocolate bar is fairly divided, they demand that the shapes of the two pieces are congruent and that each piece is connected.

The chocolate bar consists of many square shaped blocks of chocolate connected to the adjacent square blocks of chocolate at their edges. The whole chocolate bar is also connected.

Cutting the chocolate bar along with some edges of square blocks, you should help them to divide it into two congruent and connected pieces of chocolate. That is, one piece fits into the other after it is rotated, turned over and moved properly.

Figure F-1: A partially eaten chocolate bar with 18 square blocks of chocolate

For example, there is a partially eaten chocolate bar with 18 square blocks of chocolate as depicted in Figure F-1. Cutting it along with some edges of square blocks, you get two pieces of chocolate with 9 square blocks each as depicted in Figure F-2.

Figure F-2: Partitioning of the chocolate bar in Figure F-1

You get two congruent and connected pieces as the result. One of them consists of 9 square blocks hatched with horizontal lines and the other with vertical lines. Rotated clockwise with a right angle and turned over on a horizontal line, the upper piece exactly fits into the lower piece.

Figure F-3: A shape that cannot be partitioned into two congruent and connected pieces

Two square blocks touching only at their corners are regarded as they are not connected to each other. Figure F-3 is an example shape that cannot be partitioned into two congruent and connected pieces. Note that, without the connectivity requirement, this shape can be partitioned into two congruent pieces with three squares (Figure F-4).

Figure F-4: Two congruent but disconnected pieces

Your job is to write a program that judges whether a given bar of chocolate can be partitioned into such two congruent and connected pieces or not.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows.

w h
r(1, 1) ... r(1, w)
r(2, 1) ... r(2, w)
...
r(h, 1) ... r(h, w)

The integers w and h are the width and the height of a chocolate bar, respectively. You may assume 2 ≤ w ≤ 10 and 2 ≤ h ≤ 10. Each of the following h lines consists of w digits delimited by a space. The digit r(i, j) represents the existence of a square block of chocolate at the position (i, j) as follows.

'0': There is no chocolate (i.e., already eaten).
'1': There is a square block of chocolate.

You can assume that there are at most 36 square blocks of chocolate in the bar, i.e., the number of digit '1's representing square blocks of chocolate is at most 36 in each dataset. You can also assume that there is at least one square block of chocolate in each row and each column.

You can assume that the chocolate bar is connected. Since Mam does not eat chocolate bars making holes in them, you can assume that there is no dataset that represents a bar in a shape with hole(s) as depicted in Figure F-5.

Figure F-5: A partially eaten chocolate bar with a hole (You can assume that there is no dataset like this example)

Output

For each dataset, output a line containing one of two uppercase character strings "YES" or "NO". "YES" means the chocolate bar indicated by the dataset can be partitioned into two congruent and connected pieces, and "NO" means it cannot be partitioned into such two pieces. No other characters should be on the output line.

Sample Input

2 2
1 1
1 1
3 3
0 1 0
1 1 0
1 1 1
4 6
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 0
0 1 1 0
1 1 1 0
7 5
0 0 1 0 0 1 1
0 1 1 1 1 1 0
0 1 1 1 1 1 0
1 1 1 1 1 1 0
1 0 0 0 1 1 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0
9 7
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
7 6
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
10 10
0 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0
0 0

Output for the Sample Input

YES
NO
YES
YES
YES
NO
NO
YES

(End of Problem F) A B C D E F