Problem F: Cleaning Robot 2.0
アシモフ博士は、ロボット工学の研究者である。彼が開発した掃除ロボット (Problem Bを見よ) を売り出したところ、注文が殺到し、大変な売れ行きを見せた。博士の元には多額の収益が舞い込んできて、彼はあっという間に大富豪になった。
博士はこの収益で、まず家を改築した。かつては9個の部屋が正方形状に並んでいた博士の家は、今では N × N 個の部屋が正方形状に並ぶようなった。そして博士は、全ての部屋に黒か白のカーペットを敷き詰めることにした。
それでもまだ十分な金が残ったので、彼はそれを、全てロボットの開発のために注ぎ込んだ。そしてついに、新しい掃除ロボットが完成したのである。
新しいロボットは、N × N 個の部屋のどれかに、東西南北のどれかの方角を向いた状態で設置され、次のように動作する：
- ロボットは、搭載しているカメラによって、自身が今いる部屋のカーペットの色を調べる。次にロボットの前方の部屋・右隣の部屋・左隣の部屋（もしあれば）のカーペットの色をそれぞれ調べ、今いる部屋のカーペットの色と同じ色がただ 1 つだけあれば、その部屋の方角を向いて前進し、その部屋を掃除する。そうでなければ停止する。停止したロボットはそれ以上掃除をしないことに注意せよ。
以下に、ロボットの移動の例を示す。
Figure 1. 部屋の例
Figure 1 において、
- (1,1) にいる北向きのロボットは、東を向いて (1,2)へ動く。
- (0,2) にいる北向きのロボットは、西を向いて (0,1)へ動く。
- (0,0) にいる西向きのロボットは、停止する。
- ロボットは全ての部屋に設置されている非接触式充電器によって電力を供給されるので、前回のロボットのようにバッテリー切れにより動かなくなることはない。(上で説明された)停止命令が発されるか壊れる(下で説明される)まで、永久に動き続ける。
博士の家は改築によって広くなった。なので、たった1体のロボットに全ての部屋を掃除させることは非効率的である。幸い博士の資金は豊富にあるので、彼は複数のロボットを作り、それらを一斉に稼働させることにした。
ロボットは、次のように相互作用する。
- 1つの部屋に2体以上のロボットを設置することはできない。
- ある部屋のカーペットの色を調べようとするとき、その部屋に他のロボットがいても、正しくカーペットの色を調べることが出来る。
- 全てのロボットは、同時に前進する。
- ロボットが衝突したとき (すなわち、2体以上のロボットが移動の後同じ部屋にいたとき、あるいは2体のロボットが移動の後で位置を交換したとき)、衝突した全てのロボットは壊れ、停止する。
博士の家の部屋には、ゆるやかに、しかし確実に埃が積もり続ける。博士は家を綺麗に保つために、全ての部屋について、どの時刻に積もった埃もいつかは掃除されるようにロボットを動かしたい。
しばらく考えた後、博士はどのようにロボットを配置しても、この条件を満たすことができないようなカーペットの敷き方があることに気が付いた。それでは、この条件が満たされるようなロボットの初期配置が存在するカーペットの敷き方を出力するプログラムを書いてほしい。そのような敷き方は複数通りあるかもしれないので、その中で辞書順で K 番目のものを出力せよ。
Input
入力ファイルは、複数のデータセットから構成される。 一つのデータセットは、以下の形式で与えられる。
N K
N と K は整数で、問題文中で説明されたものと同じである。
入力の終了は、N = K = 0 であるデータセットによって示される。このケースに対して出力してはならない。
Output
もし辞書順で K 番目のカーペットの敷き方が存在すればそれを、そうでなければ "No" と（引用符抜きで）出力せよ。
カーペットの敷き方は、それぞれ N 文字を含んだ N 行の文字列によって表される。黒いカーペット・白いカーペットが敷かれた部屋はそれぞれ、文字 'E' , '.' によって表される。 カーペットの敷き方の辞書順は、それを表す N 行の文字列を 1 行目, 2 行目, …, N 行目 の順に連結して得られる文字列の辞書順として定義される。文字を比較するとき、 'E' > '.' となることに注意せよ。
それぞれのデータセットの後に、空行を1つ出力せよ。
Constraints
- データセットの数は 100 を越えない。
- 1 ≤ N < 64
- 1 ≤ K < 263
Sample Input
2 1 2 3 6 4 0 0
Output for the Sample Input
.. .. No ..EEEE ..E..E EEE..E E..EEE E..E.. EEEE..