角角画伯はキュービズムの大家として知らない人がいるとかいないとか…角角画伯の今年の主題は，正方形だそうです．今日は角角画伯のアトリエにお邪魔しています．

アトリエの中央には途方もなく大きなテーブルがあります．その傍らには同じ大きさに切り揃えられた正方形がたくさん用意されています．角角画伯は一 枚の正方形をテーブルの中央に置きました．それに続いて，他の正方形を順番に並べます．その様子を観察すると，画伯の几帳面な性格を反映しているのでしょ うか，どの正方形を置くときも，必ず別の正方形に隣接して置き，隣接した正方形の辺をぴたりと揃えているようです．

さあ最初の作品が完成したようです．画伯はごきげんのようです．どうです，この満足そうなお顔は．

あれ？おやおや，今度は画伯は頭を抱えてしまいました．どうしたことでしょう．ははあ．この作品を入れるのにぴったりの箱を注文したいのだけれどもその長さを測るのが大変だと嘆いておられます．さあ，みんなで画伯を手伝ってあげましょう．

画伯が完成させた作品のデータが与えられますので，その幅と高さを出力するプログラムを書いて下さい．正方形の一辺の長さは1とします．画伯が同じ位置に複数の正方形を積み重ねないことを仮定して構いません．

あれあれ，下の図を眺めながら「その十字架はもっと小さい箱に入るんじゃない」なんて言ってる人がいますね．角角画伯は悲しそうな顔で首を振りながら「斜めに入れるような人は自分の画風を理解していない」と言っていますよ．

入力は複数のデータセットからなる．各データセットは，作品の制作手順を表したデータであり，その形式は次の通りである．

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

データセットの最初の行には作品を構成する正方形の数(= N)が与えられる．Nは1以上，200未満の整数である．

データセットの残りの(N-1)行は正方形の置き方を表している．“n_i d_i”は，i (≤ N-1)番の正方形の置き方を指示している．ここで，正方形の番号は，テーブルの上に一番最初に置かれたものを0とし，その後，置いた順番に1, 2, …, (N-1)と番号づけられるものとする．なお0番の正方形に対する置き方の指示はない．

i番の正方形に対する置き方の指示 “n_i d_i” は，i番の正方形をn_i番の正方形に対してd_iで示される方角に隣接して置くことを指示する．ここで，d_iは0, 1, 2, 3のいずれかをとり，それぞれ左側(= 0)，下側 (= 1)，右側 (= 2)，上側 (= 3)を表す．

例えば以下はSample Inputの四つのデータセットに対応した作品を図示したものである．図中の番号は，正方形の番号に相当する．

入力の終わりはひとつのゼロのみからなる行で表される．

各データセットについて，作品の幅と高さを整数として，それぞれ1行に出力しなさい．幅と高さの間は1文字の空白で区切り，各出力行はこれら以外の文字を含んではならない．

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

日本語では「迷路」と呼ぶことが多い maze だが，英語と発音を似せて「迷図」と呼ぶ人もいる．迷図を通り抜けられないようでは，国内予選を通過するのも難しいかも!

この問題の迷図は，四角を縦横に並べた長方形の領域である．この領域は出入口を除いて壁で囲まれている．迷図の入口は長方形の上辺の最も左側で，つまり最上段の最左の四角の上辺は開いている．出口は同様に下辺の最も右側にある．

迷図の中では縦または横に隣り合う四角に行くことができる．しかし隣とは壁で隔てられていることがあり，その場合直接には行き来できない．

あなたの仕事は，入口から出口までの最短経路の長さを求めることである．最短経路が複数あることもあれば，ひとつもないこともあるのに注意されたい．

入力はそれぞれが迷図を表すひとつ以上のデータセットからなる．

データセットの最初の行には迷図の幅 w と高さ h を与えるふたつの整数値がこの順に入っている．

それに続く 2 × h − 1 行は，隣接する四角の間の壁の有無を示している．最初の行の先頭は空白で，その後には w −1 個の 1 または 0 が空白ひとつで区切られて並んでいる．これらは一番上の行の横に隣り合う四角の間の壁の有無を示すものである．1 は壁があることを，0 はないことを意味する． 次の行の先頭には空白はなく，w 個の 1または 0 が空白ひとつを区切りに続く．これらは最初と次の行の縦に隣り合う四角の間の壁の有無を表す．整数 1/0 は壁の有/無を示す．引き続く行は交互に横と縦に隣り合う四角の間の壁の有無を同様に表す．

入力の終わりは二つのゼロを含む行で表される．

データセット数は100以下である．長方形領域の高さも幅も2以上30以下である．

各データセットについて，入口から出口までの最短経路長を表す整数ひとつを持つ行を出力せよ．ここでは経路の長さは通過する四角の数で表す．迷図を通り抜ける経路がない場合には，ゼロひとつを含む行を出力せよ．出力行にはこの数値以外の文字を含んではならない．

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

あなたの勤め先のピカソニアン・キュービズム国際センター(ICPC)の事務局では，若き芸術家のための美術館を新たに建設する．そのためセンターでは建物の設計コンペを開催することになった．

コンペに提出される図面は，下に示すように，かの有名なゲームの画面のようなものになる．

それというのも，センターが指定する工法が「ピース」と呼ばれる規格化されたユニットを積み重ねて建築するというものだからである．各ピースは4つの立方体のブロックをつなげて作られている．センターはさらに，応募される設計に次のような条件を課している．

• ピースはブロック単位で位置を揃えてある．つまりピースとピースが接する場合，両者のブロックの面どうしはぴったり重なるような置き方しか許されない．
• ピースは安定していなければいけない．ピースは積み重ねられるだけなので，崩れてしまわないように重心の位置を慎重に定めなければいけない．
• ピースは樹状に積み重ねられ，それによって若き芸術家達の無限の可能性を象徴する．つまり，地面に接しているピースは唯1つだけで，それ以外の各ピースの下面が接しているピースは丁度1つだけに限られている．
• 建物は平らな形に限られる．これは建設予定地が下図に示すようなお堀と高速道路にはさまれた狭い所で，お堀と高速道路の間にはブロック1個分の幅しかないためである．

建物の安定性を完全に調べるには，複雑な構造計算が必要なため何日もかかる．そこであなたは安定性の簡易診断を行うことを命じられた．簡易診断の方法は次のようである．

以下では各ブロックの重心はブロックの中心にあり，全てのブロックは同じ重さだと仮定する．また，ブロックの位置をブロックの左下のxy座標によって表す．単位はブロックの辺の長さである．

ピースを構成するブロックで下面が他のピースまたは地面に接しているもののうち，一番左のものの左端のx座標を x_L，一番右のものの右端のx座標を x_R とする．また，このピースによって直接または間接に支えられているすべてのピースとこのピース自身をあわせた全体の重心のx座標をMとする．このときx_L < M < x_R が成り立てばピースは安定であり，そうでなければ不安定である．建物を構成するピースが1つでも不安定であれば，その建物は不安定である．

上記の診断方法は，実際には崩れないような設計を不安定と判定する場合もあることに注意せよ．例えば，下図左の設計は不安定と判定される．

またこの診断方法は境界状態にある場合は不安定と判定することにも注意せよ．例えば，上図右の設計における上のピースの重心は，下のピースの右端の真上にあるが，これは不安定と判定される．

簡易診断方法によって各設計の安定性を診断するプログラムを書け．

入力は複数のデータセットからなる．入力の終わりは空白1つで区切られた2個のゼロからなる行によって与えられる．各データセットは建物の正面図を表し，その形式は以下の通りである．

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

空白で区切られた整数wおよびhはそれぞれ配置の列数と行数を表す．ここで 1 ≤ w ≤
10 かつ 1 ≤ h ≤ 60 と仮定してよい．続くh行はピースの配置を与える．p_xyの文字は座標(x,y)のブロックの状態を表し，何もないことを表す「.」あるいはピースを構成するブロックを表す「1」から「9」までの数字のどれかである．(すでに述べたように，ブロックの位置はブロックの左下のxy座標によって表す．)

同じ数字を持つ2つのブロックが上下あるいは左右を接している場合，それらのブロックは同一のピースの部分である．(同じ数字を持つ異なる2つのピースが有り得ることに注意せよ．)座標(x,0)にあるブロックの下面は地面に接している．

各データセットは，ピースを樹状に積み重ねているものと仮定してよい．

それぞれのデータセットについて，設計が上記の条件に従って安定な場合にはSTABLE, そうでない場合はUNSTABLEと全て大文字で書かれた行を出力せよ．出力にそれ以外の文字を含めてはならない．

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

昔々，多くの「魔法の紋様」を発明した魔法使いがいた．
彼の発明した魔法の紋様が床に描かれた部屋では，
呪文を唱えることで，誰でも魔法が使えるようになるのだ！
ただし，使える呪文は紋様によってまちまちである．
あなたの仕事は，指定された魔法の紋様に対し，
それによって使用可能となる呪文のうち，最強のものを突き止めることだ．

呪文は，英小文字の文字列であり，
特に辞書順で早ければ早い呪文であるほど，強い呪文である．
ここで文字列 w が文字列 u より辞書順で早いとは，
w と u とで異なる最初の文字が a<b<...<z の順序で小さいか，
または w が u の接頭辞であることを言う．
例として，"abcd" は "abe" より早く（文字 c は e より小さいため），
また，"abe" は "abef" より早い（接頭辞になっているため）．

魔法の紋様は，番号のついた 節点 と，それらを結ぶ矢印
からなる図形である．
矢印には ラベル と呼ばれる小文字の文字列がついている．
また，スター とゴールド と呼ばれる，
二つの特別な節点がある．
魔法の紋様によって使えるようになる呪文とはすなわち，
その紋様のスターからゴールドへと矢印をたどって得られるラベルを順に結合して得られる文字列である．

次に，四つの節点と7本の矢印からなる例を図示する．

0 がスター，2 がゴールドである．
この魔法の紋様によって，例えば

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

という経路から得られる呪文 "abracadabra" が使えるようになる．他には，

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

から得られる "oilcadabraketdadabra" などもある．
"abracadabra" と "oilcadabraketdadabra" では前者の方が辞書順で早いので，より強い呪文である．
実は，この魔法の紋様で使用可能となる呪文で "abracadabra" 以上に強いものは存在しない．
従ってこの場合，あなたが求めるべき答えは "abracadabra" となる．

もしも，最強の呪文が定められないときには，"NO" と答えて欲しい．
これには二つの場合がある．一つは，スターからゴールドへ到達できない場合である．
もう一つは，どんな呪文をとっても，
それよりさらに強い呪文が存在するような場合である．
たとえば次の図のような魔法の紋様では，
"b" よりも "ab" が強く，
"ab" よりも "aab" が強いといったように，
どの呪文をとってもさらに一つ a を増やすと，辞書順で早い，より強い呪文となる．

入力は最大で150個のデータセットからなる．
各データセットの形式は次のとおりである．

n a s g

x₁ y₁ lab₁

x₂ y₂ lab₂

...

x_a y_a lab_a

データセットの最初の行は4個の整数を含む．n は節点の数，a は矢印の数を表す．
s と g はそれぞれスターとゴールドの番号を示す．
続く a 行はそれぞれ2個の整数と1個の文字列からなり，矢印の情報を表す．
x_i y_i lab_i という行は，
節点 x_i から出て節点 y_i を指す，
ラベルが lab_i の矢印を表している．
データセット中の値は次の条件を満たす：
2 ≤ n ≤ 40,
0 ≤ a ≤ 400,
0 ≤ s, g, x_i , y_i < n.
s ≠g,
lab_i は長さ1以上6以下の，英小文字のみからなる文字列である．
矢印の両端が同一節点の場合 (x_i = y_i ) や，
節点の対を複数の矢印が結ぶ場合
(異なる i, j に対し
x_i = x_j かつ y_i = y_j )
もあり得ることに注意して欲しい．

入力の終わりは4個のゼロからなる行によって与えられる．

各データセットについて，最も強い呪文が存在すれば，それぞれ1行に出力しなさい．
存在しない場合は NO を1行に出力しなさい．
各出力行はこれ以外の文字を含んではならない．

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

西暦4272年，プログラミング文学の巨匠，アイザック・コーネル・パンサーキャロル博士は
三度の世界コンピューターウイルス大戦を奇跡的に生き残り，
今年で丁度90歳になったところでノーベル文学賞を受賞した．
メディアは彼の一生を細大漏らさず報道したが，一つだけ報道できなかったことがあった――それは彼がまだ小学生の頃に書いた作文だった．
彼は作文を保管しておいたので，それを報道陣に見せることを快諾したのだが，
最大の問題は，第三次世界コンピューターウイルス大戦の際に保管していた媒体が
コンピューターウイルスに何回か感染していたので，文章が改ざんされているかもしれない点だ．

更に調査を進めたところ，保管していた作文はやはり改ざんされていることが分かった．なぜ分かったのか？
80年以上前に，彼のクラスメートは感染する前に元の作文を脳に転送していたのだ．
半導体脳の発明により，人は脳に転送した文章を何世紀にもわたって完全に保持することができる．
容量が限られているため，文章全体を覚えている人はいなかったが，
我々はなんとかして文章の一部をクラスメートの一人の脳から引き出した．悲しいことに，それは手元に保管していた作文と完全には一致していなかった．
これはウイルス感染が無ければありえないことだ．

現在，そのコンピューターウイルスについて分かっていることは，ウイルスが作文に感染するたびに以下のうちどれか一つを行うことである．

1. ウイルスはランダムな文字を文章中のランダムな位置に挿入する．（例："ABCD" → "ABCZD"）
2. ウイルスは文章中の文字を1文字ランダムに選び，その文字を別の文字に変換する．（例："ABCD" → "ABXD"）
3. ウイルスは文章中の文字を1文字ランダムに選び，その文字を文章中から取り除く．（例："ABCD" → "ACD"）

また，侵入ログの量から推定することでウイルス感染が起こりえた回数の最大値も貴方は知っている．
幸運なことに，彼のクラスメートのほとんどは彼の作文の少なくとも一部（以降ピースと呼ぶ）を覚えていてくれたようなのだ．
全ての証拠を総合すれば，元の作文を復元できるかもしれない．
貴方はジャーナリスト兼コンピュータ科学者として，元の作文に書かれていた文章としてどのようなものがあり得るのか，与えられたピースや改ざんされてしまった手元の文章を元に計算するコンピュータープログラムを書きたい．

入力は複数のデータセットからなる．データセット数は100以下である．
データセットは以下の形式をしている．

d n

改ざん文章

ピース₁

ピース₂

...

ピース_n

データセットの1行目は二つの正の整数 d (d ≤ 2) と n (n ≤ 30) からなり，
dは作文にウイルスが感染した回数の最大値を，nはピースの数を表している．

データセットの2行目は，手元にある改ざんされた文章である．以降これを「改ざん文章」と呼ぶ．
改ざん文章の長さは40文字以下である．

データセット中の残りの行はピースと呼ばれ，彼のクラスメートが覚えていた元の作文の一部である．
各々のピースは20文字以下で，最低13文字ある．ピースは全て同じ長さである．
改ざん文章やピースに現れる文字は，英語アルファベット大文字（`A'から`Z'）とピリオド（`.'）である．
彼が用いていた言語は分かち書きをしないので，ピースや改ざん文章中に空白文字は現れない．

二つのゼロのみを含む行が入力の終わりを表す．

クラスメートは充分にたくさんいたので，元の作文中にあるどの文字も必ず最低一つのピースでカバーされていると仮定してよい．
一つのピースが元の作文を2回以上カバーすることがある．元の作文には繰り返しがあるかもしれない．
また，彼のクラスメートは勘違いをして関係ないピースを提出したかもしれないので，幾つかのピースは元の作文中に現れないかもしれないことに注意せよ．

各データセットに対して何を出力すれば良いかを以下に説明する．
与えられたピースや改ざん文書と合う元の作文が c 種類有り得るとする．
最初に c を含む1行を出力せよ．
もしcが5以下の場合には，さらに辞書順で1行に一つずつそれらの可能性を表示せよ．
辞書順では '.' が他のどの文字よりも早いことに注意せよ．
cは0でないことを仮定して良い．
上記で指示されていないいかなる文字も出力してはならない．

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

レーザー光発生装置が，目標物やいくつかの鏡とともに，水平面上に設置されている．
鏡は平面上で直立しており，その両面ともに平面であり，レーザー光を反射することができる．
異なる反射を使うことにより，レーザー光を目標物に向ける方向は複数ありうる．
あなたの仕事は，装置から目標物に至るレーザー光の最短経路を求め，その長さを答えることである．

図 G-1 は，複数の経路の例を示したものであり，
太線は最短経路を表している．

図 G-1: 可能な経路の例

入力は複数のデータセットからなり，入力の終わりは，ゼロを一つだけ含む行で表される．

各データセットの形式は次のとおりである．
データセット中の n 以外の値は，すべて 0 以上 100 以下の整数である．

n

PX₁ PY₁ QX₁ QY₁

...

PX_n PY_n QX_n QY_n

TX TY

LX LY

データセットの最初の行は，鏡の枚数を表す整数 n (1 ≤ n ≤ 5) である．
引き続く n 行は，それぞれの鏡の水平面上の位置を示し，
座標 (PX_i, PY_i) と
(QX_i, QY_i) が，
鏡の両端の位置を表している．
鏡同士は，互いに離れて位置している．
最後の 2 行は，目標物の位置 (TX, TY) と，
レーザー光発生装置の位置 (LX, LY) を示している．
目標物とレーザー光発生装置の位置は互いに異なり，
また，両者とも鏡から離れている．

レーザー光発生装置及び目標物の大きさは 0 と仮定してよいほど小さい．
鏡の厚みについても無視してよい．

また，与えられたデータセットについて，以下のような仮定をしてよい．

• レーザー光発生装置から目標物に至る経路は，少なくとも一つ存在する．
• 最短経路における反射回数は 6 回未満である．
• 最短経路は，どちらかの端から 0.001 単位距離以内の点で
  鏡面を含む平面と交差もしくは接することはない．
• 仮に，ビーム光が鏡面を含む平面にどちらかの端から
  0.001 単位距離以内の点で到達した際に，
  反射するか通過するかを任意に選択できたとしても，
  レーザー光発生装置から目標物への経路が，最短経路より短くなることはない．
• 装置から任意の方向に照射されたレーザー光は，
  6 回目の反射点に到達する (6 回目の反射は含まない)までは，
  鏡で反射する際，
  もしくは鏡から 0.001 単位距離の範囲を通過する際に，
  鏡と光の経路がなす角 θ について，sin(θ) > 0.1 を満たす．

図 G-1 は，後に示す Sample Input 中の最初のデータセットに対応する．
図 G-2 は，Sample Input の引き続くデータセットに対する最短経路を示したものである．

図 G-2: 最短経路の例

各データセットに対して，レーザー光発生装置から目標物に至るレーザー光の最短経路
の長さを，一行に出力せよ．
答えには 0.001 を越える誤差があってはいけない．
それ以外の余計な文字を出力してはならない．

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