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.

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_{1} 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.

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.

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.

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_{0}c_{1}c_{2}c_{3}

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_{0}, c_{1}, c_{2}, and c_{3}, 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_{0}, c_{1}, c_{2}, and c_{3}
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.

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 sxsyexey minx_{1}miny_{1}maxx_{1}maxy_{1}h_{1} minx_{2}miny_{2}maxx_{2}maxy_{2}h_{2}
... 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.

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.

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.

IBM Japan, Ltd. Beacon Information Technology Inc. CSK Holdings Corporation Lincrea Mixi, Inc. NTT Corporation

DG Technologies, Inc. Fujitsu Ltd. Google, Inc. Hitachi, Ltd. IMS Lab, Inc. KDDI R&D Laboratories, Inc. Kozo Keikaku Engineering, Inc. Mitsubishi Electric Corporation NEC Corporation NTT Data Corporation NTT Software Ricoh Co., Ltd. Sony Computer Science Laboratories, Inc. Toshiba Corporation