Pablo Squarson is a well-known cubism artist. This year's theme for Pablo Squarson is "Squares". Today we are visiting his studio to see how his masterpieces are given birth.

At the center of his studio, there is a huuuuuge table and beside it are many, many squares of the same size. Pablo Squarson puts one of the squares on the table. Then he places some other squares on the table in sequence. It seems his methodical nature forces him to place each square side by side to the one that he already placed on, with machine-like precision.

Oh! The first piece of artwork is done. Pablo Squarson seems satisfied with it. Look at his happy face.

Oh, what's wrong with Pablo? He is tearing his hair! Oh, I see. He wants to find a box that fits the new piece of work but he has trouble figuring out its size. Let's help him!

Your mission is to write a program that takes instructions that record how Pablo made a piece of his artwork and computes its width and height. It is known that the size of each square is 1. You may assume that Pablo does not put a square on another.

I hear someone murmured "A smaller box will do". No, poor Pablo, shaking his head, is grumbling "My square style does not seem to be understood by illiterates".

The input consists of a number of datasets. Each dataset represents the way Pablo made a piece of his artwork. The format of a dataset is as follows.

N
n₁ d₁
n₂ d₂
...
n_N-1 d_N-1

The first line contains the number of squares (= N) used to make the piece of artwork. The number is a positive integer and is smaller than 200.

The remaining (N-1) lines in the dataset are square placement instructions. The line “n_i d_i” indicates placement of the square numbered i (≤ N-1). The rules of numbering squares are as follows. The first square is numbered "zero". Subsequently placed squares are numbered 1, 2, ..., (N-1). Note that the input does not give any placement instruction to the first square, which is numbered zero.

A square placement instruction for the square numbered i, namely “n_i d_i”, directs it to be placed next to the one that is numbered n_i, towards the direction given by d_i, which denotes leftward (= 0), downward (= 1), rightward (= 2), and upward (= 3).

For example, pieces of artwork corresponding to the four datasets shown in Sample Input are depicted below. Squares are labeled by their numbers.

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

For each dataset, output a line that contains the width and the height of the piece of artwork as decimal numbers, separated by a space. Each line should not contain any other characters.

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

1 1
3 3
4 4
5 6

You are requested to solve maze problems. Without passing through
these mazes, you might not be able to pass through the domestic
contest!

A maze here is a rectangular area of a number of squares, lined up
both lengthwise and widthwise, The area is surrounded by walls except
for its entry and exit. The entry to the maze is at the leftmost part
of the upper side of the rectangular area, that is, the upper side of
the uppermost leftmost square of the maze is open. The exit is
located at the rightmost part of the lower side, likewise.

In the maze, you can move from a square to one of the squares
adjoining either horizontally or vertically. Adjoining squares,
however, may be separated by a wall, and when they are, you cannot go
through the wall.

Your task is to find the length of the shortest path from the entry to
the exit. Note that there may be more than one shortest paths, or
there may be none.

The input consists of one or more datasets, each of which represents a
maze.

The first line of a dataset contains two integer numbers, the
width w and the height h of the rectangular area, in
this order.

The following 2 × h − 1 lines of a dataset describe
whether there are walls between squares or not. The first line starts
with a space and the rest of the line contains w − 1
integers, 1 or 0, separated by a space. These indicate whether walls
separate horizontally adjoining squares in the first row. An integer
1 indicates a wall is placed, and 0 indicates no wall is there. The
second line starts without a space and contains w integers, 1 or 0,
separated by a space. These indicate whether walls separate
vertically adjoining squares in the first and the second rows. An
integer 1/0 indicates a wall is placed or not. The following lines
indicate placing of walls between horizontally and vertically
adjoining squares, alternately, in the same manner.

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

The number of datasets is no more than 100. Both the widths and the
heights of rectangular areas are no less than 2 and no more than 30.

For each dataset, output a line having an integer indicating the
length of the shortest path from the entry to the exit. The length of
a path is given by the number of visited squares. If there exists
no path to go through the maze, output a line containing a single
zero. The line should not contain any character other than this
number.

2 3
 1
0 1
 0
1 0
 1
9 4
 1 0 1 0 0 0 0 0
0 1 1 0 1 1 0 0 0
 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1
 0 0 0 1 0 0 1 1
0 0 0 0 1 1 0 0 0
 0 0 0 0 0 0 1 0
12 5
 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0
 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 1 0 1 1 0
 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0
0 0

4
0
20

You are working for an administration office of the International
Center for Picassonian Cubism (ICPC), which plans to build a new art
gallery for young artists. The center is organizing an architectural
design competition to find the best design for the new building.

Submitted designs will look like a screenshot of a well known
game as shown below.

This is because the center specifies that
the building should be constructed by stacking regular units
called pieces, each of which consists of four cubic blocks.
In addition, the center requires the competitors to submit designs
that satisfy the following restrictions.

• All the pieces are aligned. When two pieces touch each other, the faces of
  the touching blocks must be placed exactly at the same position.
• All the pieces are stable. Since pieces are merely stacked,
  their centers of masses must be carefully positioned so as not to
  collapse.
• The pieces are stacked in a tree-like form
  in order to symbolize boundless potentiality of young artists.
  In other words, one and only one
  piece touches the ground, and each of other pieces touches one and
  only one piece on its bottom faces.
• The building has a flat shape.
  This is because the construction site
  is a narrow area located between a
  straight moat and an expressway where
  no more than one block can be placed
  between the moat and the
  expressway as illustrated below.

It will take many days to fully check stability of designs as it requires
complicated structural calculation.
Therefore, you are
asked to quickly check obviously unstable designs by focusing on
centers of masses. The rules of your quick check are as follows.

Assume the center of mass of a block is located at the center of the
block, and all blocks have the same weight.
We denote a location of a block by xy-coordinates of its
left-bottom corner. The unit length is the edge length of a block.

Among the blocks of the piece that touch another piece or the ground on their
bottom faces, let x_L be the leftmost x-coordinate of
the leftmost block, and let x_R be the rightmost
x-coordinate of the rightmost block.
Let the x-coordinate of its accumulated center of mass of
the piece be M, where the accumulated center of mass of a piece P
is the center of the mass of the pieces that are directly and indirectly
supported by P, in addition to P itself. Then the piece is
stable, if and only if
x_L < M < x_R. Otherwise, it is
unstable. A design of a building is unstable if any of its pieces is unstable.

Note that the above rules could judge some designs to be unstable even
if it would not collapse in reality. For example, the left one of the
following designs shall be judged to be unstable.

Also note that the rules judge boundary cases to be unstable. For example, the top piece in the above right design has its center of mass exactly above the right end of the bottom piece. This shall be judged to be unstable.

Write a program that judges stability of each design based on the above quick check rules.

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, which represents a front view of a building, is formatted as follows.

w h

p_0(h-1)p_1(h-1)...p_(w-1)(h-1)

...

p₀₁p₁₁...p_(w-1)1

p₀₀p₁₀...p_(w-1)0

The integers w and h separated by a space are the numbers of columns
and rows of the layout, respectively. You may assume 1 ≤ w ≤
10 and 1 ≤ h ≤ 60. The next h lines specify the placement of
the pieces. The character p_xy indicates the status of a block at
(x,y), either `.', meaning empty, or one digit character between
`1' and `9', inclusive, meaning a block of a piece.
(As mentioned earlier, we denote a location of a block by xy-coordinates of its
left-bottom corner.)

When two blocks with the same number touch each other by any of their
top, bottom, left or right face, those blocks are of the same piece.
(Note that there might be two different pieces that are denoted by
the same number.)
The bottom of a block at (x,0) touches the ground.

You may assume that the pieces in each dataset are stacked in a tree-like form.

For each dataset, output a line containing a word STABLE
when the design is stable with respect to the above quick check rules.
Otherwise, output UNSTABLE. The output
should be written with uppercase letters, and should not contain any other extra characters.

4 5
..33
..33
2222
..1.
.111
5 7
....1
.1..1
.1..1
11..1
.2222
..111
...1.
3 6
.3.
233
23.
22.
.11
.11
4 3
2222
..11
..11
4 5
.3..
33..
322.
2211
.11.
3 3
222
2.1
111
3 4
11.
11.
.2.
222
3 4
.11
.11
.2.
222
2 7
11
.1
21
22
23
.3
33
2 3
1.
11
.1
0 0

STABLE
STABLE
STABLE
UNSTABLE
STABLE
STABLE
UNSTABLE
UNSTABLE
UNSTABLE
UNSTABLE

Long long ago, there lived a wizard who invented a lot of "magical patterns."
In a room where one of his magical patterns is drawn on the floor,
anyone can use magic by casting magic spells!
The set of spells usable in the room depends on the drawn magical pattern.
Your task is to compute, for each given magical pattern,
the most powerful spell enabled by the pattern.

A spell is a string of lowercase letters.
Among the spells, lexicographically earlier one is more powerful.
Note that a string w is defined to be lexicographically earlier than a string u
when w has smaller letter
in the order a<b<...<z on the first position at which they differ,
or w is a prefix of u.
For instance, "abcd" is earlier than "abe" because 'c' < 'e',
and "abe" is earlier than "abef" because the former is a prefix of the latter.

A magical pattern is a diagram consisting of uniquely numbered nodes
and arrows connecting them.
Each arrow is associated with its label, a lowercase string.
There are two special nodes in a pattern, called the star node
and the gold node.
A spell becomes usable by a magical pattern if and only if the spell emerges
as a sequential concatenation of the labels of a path from the star to the gold along the arrows.

The next figure shows an example of a pattern with four nodes and
seven arrows.

The node 0 is the star node and 2 is the gold node.
One example of the spells that become usable by this magical pattern is "abracadabra",
because it appears in the path

    
0 --"abra"--> 1 --"cada"--> 3 --"bra"--> 2.

Another example is "oilcadabraketdadabra", obtained from the path

    
0 --"oil"--> 1 --"cada"--> 3 --"bra"--> 2 --"ket"--> 3 --"da"--> 3 --"da"--> 3 --"bra"--> 2.

The spell "abracadabra" is more powerful than "oilcadabraketdadabra"
because it is lexicographically earlier.
In fact, no other spell enabled by the magical pattern is more powerful than "abracadabra".
Thus "abracadabra" is the answer you have to compute.

When you cannot determine the most powerful spell, please answer "NO".
There are two such cases.
One is the case when no path exists from the star node to the gold node.
The other case is when for every usable spell there always exist more powerful spells.
The situation is exemplified in the following figure:
"ab" is more powerful than "b", and "aab" is more powerful than "ab", and so on.
For any spell, by prepending "a", we obtain a lexicographically earlier
(hence more powerful) spell.

The input consists of at most 150 datasets.
Each dataset is formatted as follows.

n a s g

x₁ y₁ lab₁

x₂ y₂ lab₂

...

x_a y_a lab_a

The first line of a dataset contains four integers.
n is the number of the nodes, and a is the number of the arrows.
The numbers s and g indicate the star node and the gold node, respectively.
Then a lines describing the arrows follow.
Each line consists of two integers and one string.
The line "x_i y_i lab_i" represents
an arrow from the node x_i to the node y_i
with the associated label lab_i .
Values in the dataset satisfy:
2 ≤ n ≤ 40,
0 ≤ a ≤ 400,
0 ≤ s, g, x_i , y_i < n ,
s ≠g,
and
lab_i is a string of 1 to 6 lowercase letters.
Be careful that there may be self-connecting arrows (i.e., x_i = y_i ),
and multiple arrows connecting the same pair of nodes
(i.e., x_i = x_j and y_i = y_j
for some i ≠ j ).

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

For each dataset, output a line containing the most powerful spell for the magical pattern.
If there does not exist such a spell, output "NO" (without quotes).
Each line should not have any other characters.

4 7 0 2
0 1 abra
0 1 oil
2 0 ket
1 3 cada
3 3 da
3 2 bra
2 3 ket
2 2 0 1
0 0 a
0 1 b
5 6 3 0
3 1 op
3 2 op
3 4 opq
1 0 st
2 0 qr
4 0 r
2 1 0 1
1 1 loooop
0 0 0 0

abracadabra
NO
opqr
NO

In 4272 A.D., Master of Programming Literature, Dr. Isaac Cornell Panther-Carol,
who has miraculously survived through the three World Computer Virus Wars and reached 90 years old this year,
won a Nobel Prize for Literature.
Media reported every detail of his life.
However, there was one thing they could not report — that is, an essay written by him when he was an elementary school boy.
Although he had a copy and was happy to let them see it,
the biggest problem was that his copy of the essay was infected by a computer virus several times during the World Computer Virus War III
and therefore the computer virus could have altered the text.

Further investigation showed that his copy was altered indeed. Why could we know that?
More than 80 years ago his classmates transferred the original essay to their brain before infection.
With the advent of Solid State Brain, one can now retain a text perfectly over centuries once it is transferred to his or her brain.
No one could remember the entire text due to the limited capacity,
but we managed to retrieve a part of the text from the brain of one of his classmates; sadly, it did not match perfectly to the copy at hand.
It would not have happened without virus infection.

At the moment, what we know about the computer virus is that each time the virus infects an essay it does one of the following:

1. the virus inserts one random character to a random position in the text. (e.g., "ABCD" → "ABCZD")
2. the virus picks up one character in the text randomly, and then changes it into another character. (e.g., "ABCD" → "ABXD")
3. the virus picks up one character in the text randomly, and then removes it from the text. (e.g., "ABCD" → "ACD")

You also know the maximum number of times the computer virus infected the copy, because you could deduce it from the amount of the intrusion log.
Fortunately, most of his classmates seemed to remember at least one part of the essay (we call it a piece hereafter).
Considering all evidences together, the original essay might be reconstructed.
You, as a journalist and computer scientist, would like to reconstruct the original essay by writing a computer program to calculate the possible original text(s) that fits to the given pieces and the altered copy at hand.

The input consists of multiple datasets. The number of datasets is no more than 100.
Each dataset is formatted as follows:

d n

the altered text

piece₁

piece₂

...

piece_n

The first line of a dataset contains two positive integers d (d ≤ 2) and n (n ≤ 30),
where d is the maximum number of times the virus infected the copy and n is the number of pieces.

The second line is the text of the altered copy at hand. We call it the altered text hereafter.
The length of the altered text is less than or equal to 40 characters.

The following n lines are pieces, each of which is a part of the original essay remembered by one of his classmates.
Each piece has at least 13 characters but no more than 20 characters. All pieces are of the same length.
Characters in the altered text and pieces are uppercase letters (`A' to `Z') and a period (`.').
Since the language he used does not leave a space between words, no spaces appear in the text.

A line containing two zeros terminates the input.

His classmates were so many that you can assume that any character that appears in the original essay is covered by at least one piece.
A piece might cover the original essay more than once; the original essay may contain repetitions.
Please note that some pieces may not appear in the original essay because some of his classmates might have mistaken to provide irrelevant pieces.

Below we explain what you should output for each dataset.
Suppose if there are c possibilities for the original essay that fit to the given pieces and the given altered text.
First, print a line containing c.
If c is less than or equal to 5, then print in lexicographical order c lines, each of which contains an individual possibility.
Note that, in lexicographical order, '.' comes before any other characters.
You can assume that c is always non-zero.
The output should not include any characters other than those mentioned above.

1 4
AABBCCDDEEFFGGHHIJJKKLLMMNNOOPP
AABBCCDDEEFFGG
CCDDEEFFGGHHII
FFGGHHIIJJKKLL
JJKKLLMMNNOOPP
2 3
ABRACADABRA.ABBRACADABRA.
ABRACADABRA.A
.ABRACADABRA.
BRA.ABRACADAB
2 2
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
2 3
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXAXXXXXX
XXXXXXBXXXXXX
XXXXXXXXXXXXX
0 0

1
AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP
5
.ABRACADABRA.ABRACADABRA.
ABRACADABRA.A.ABRACADABRA.
ABRACADABRA.AABRACADABRA.A
ABRACADABRA.ABRACADABRA.
ABRACADABRA.ABRACADABRA.A
5
AAAAAAAAAAAAAA
AAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAA
257

A laser beam generator, a target object and some mirrors are
placed on a plane.
The mirrors stand upright on the plane,
and both sides of the mirrors are flat and can reflect beams.
To point the beam at the target,
you may set the beam to several directions because of different reflections.
Your job is to find the shortest beam path
from the generator to the target and answer the length of the path.

Figure G-1 shows examples of possible beam paths,
where the bold line represents the shortest one.

Figure G-1: Examples of possible paths

The input consists of a number of datasets. The end of the input is indicated by a line containing a zero.

Each dataset is formatted as follows.
Each value in the dataset except n is an integer no less than 0 and no more than 100.

n

PX₁ PY₁ QX₁ QY₁

...

PX_n PY_n QX_n QY_n

TX TY

LX LY

The first line of a dataset contains an integer n (1 ≤ n ≤ 5),
representing the number of mirrors.
The following n lines list the arrangement of mirrors on the plane.
The coordinates
(PX_i, PY_i) and
(QX_i, QY_i) represent
the positions of both ends of the mirror.
Mirrors are apart from each other.
The last two lines represent the target position (TX, TY)
and the position of the beam generator (LX, LY).
The positions of the target and the generator are apart from each other,
and these positions are also apart from mirrors.

The sizes of the target object and the beam generator are small enough to be ignored.
You can also ignore the thicknesses of mirrors.

In addition, you can assume the following conditions on the given datasets.

• There is at least one possible path from the beam generator to the target.
• The number of reflections along the shortest path is less than 6.
• The shortest path does not cross or touch a plane containing a mirror
  surface at any points within 0.001 unit distance from either end of the mirror.
• Even if the beam could arbitrarily select reflection or passage
  when it reaches each plane containing a mirror surface
  at a point within 0.001 unit distance from one of the mirror ends,
  any paths from the generator to the target would not be
  shorter than the shortest path.
• When the beam is shot from the generator in an arbitrary direction and
  it reflects on a mirror or passes the mirror within 0.001 unit distance from the mirror,
  the angle θ formed by the beam and the mirror
  satisfies sin(θ) > 0.1,
  until the beam reaches the 6th reflection point (exclusive).

Figure G-1 corresponds to the first dataset of the Sample Input below.
Figure G-2 shows the shortest paths for the subsequent datasets of the Sample Input.

Figure G-2: Examples of the shortest paths

For each dataset, output a single line containing the length of the shortest path from
the beam generator to the target.
The value should not have an error greater than 0.001.
No extra characters should appear in the output.

2
30 10 30 75
60 30 60 95
90 0
0 100
1
20 81 90 90
10 90
90 10
2
10 0 10 58
20 20 20 58
0 70
30 0
4
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
24 0
24 64
5
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
100 0 100 50
24 0
24 64
0

180.27756377319946
113.13708498984761
98.99494936611666
90.50966799187809
90.50966799187809