問題文

ロシアではいま睡眠が大ブームです．ロシアでは老若男女，誰もが睡眠をとります．ロシアでは睡眠をとらない人なんていません．

乗るしかない，このビッグウェーブに．寝ましょう！あなたも，わたしも，そこの君も，そのディスプレイの前で問題文を読んでいる人も！

おや，いまここには，寝たい人が N 人いるようですね．さっそく寝ましょう！この N 人がひとつのベッドで寝た日には，われわれはもうロシア中のヒーローですよ！

さあ寝ましょう寝ましょう，みなさん眠りましょう．ソビエトロシアでは，睡眠があなたをとる！

しかし，さすがに他人どうしが同じベッドで寝るというのは，いささかハードルが高いようですね？これは困った……と，思ったら，実はこの中には知り合いどうしである方々もいらっしゃる？それならば話は早い！知り合いどうしが隣り合って寝ればよいのです！

さらに都合の良いことに，知り合いどうしの関係はとても分かりやすい形をしている！なんと，いま適当に人を 0 番から N-1 番まで番号づけしたところ，i 番目の人は i-1 番目と i+1 番目の人とのみ知り合いである，となりました！ロシアンミラクル！！おっともちろん，-1 番目の人とは N-1 番目の人のこととして，N 番目の人とは 0 番目の人のこととしますよ．

少々おしゃべりが過ぎましたかね．さてさてそれではみなさんお待ちかねのことと思いますが，寝ましょう！さあ体をベッドに横たえて，目を閉じて深呼吸！気づけばもうあなたは眠りの中です！起きた時にはロシアのヒーローです！！お楽しみに！！！

えっ？それでもまだ寝方が分からないから怖い？ばっかお前……プログラムがついてるだろ．

課題

寝たい人が N 人いる．この N 人をひとつの長方形グリッドで表されるベッドに敷き詰めて寝かせたい．このとき，2 つの条件を満たす必要がある．

1 つめの条件はそれぞれの人の体勢についてである．それぞれの人はグリッド上のちょうど K 個のマス目によって表される．このとき，K 個のマスが一列に連結になっていなければ骨が折れてしまう．マスの集合が一列に連結であるとは，次のような条件を満たすように各マスに 1 から K までの番号をつけることができることを言う: どのマスも自分の番号との差が 1 であるようなマスとのみ隣り合う．また，2 つのマスが隣り合っているとは，それらのマスが辺を共有していることを言う．

次に示すのは K = 5 のときの正しい寝る体勢の例である(人のいるマスを文字 X で表し，そうでないマスを文字 . で表す):

XXX    XX.
..X    .XX
..X    ..X

次に示すのは K = 5 のときに正しくない寝る体勢の例である:

XXX    XXX    XX.
.XX    X..    .X.
...    .X.    .X.

1 つ目の例は一列に連結となるようにマスを番号づけることができない．2 つ目の例は 5 つのマスが連結でない．3 つ目の例はマスが 4 つしかない．

2 つめの条件は人どうしが隣り合う関係についてである．N 人の人には 0 番から N-1 番までの番号がつけられており，i 番目の人は i-1 番目の人と i+1 番目の人とのみ隣り合っていなければならない．ここで -1 番目の人とは N-1 番目の人とし，N 番目の人とは 0 番目の人であるとする．また，2 人の人が隣り合っているとは，それぞれの人を表すマスであって隣り合っているようなものが存在することを言う．

次に示すのは K = 5 のときに隣り合っている 2 人の寝方の例である(1人目のいるマスを文字 X で表し，2人目のいるマスを文字 Y で表し，そうでないマスを文字 . で表す):

XXX    XXXXX
YYX    Y....
.YX    YY...
.YY    .YY..

次に示すのは K = 5 のときに隣り合っていない 2 人の寝方の例である:

XXX    XXXXX
..X    .....
Y.X    YYY..
YY.    ..Y..
.YY    ..Y..

ベッドを表す長方形グリッドの横幅と縦幅は自由に決めて良いが，グリッドのマス数は 100,000 を超えてはいけない．そのもとで，上に述べた 2 条件を満たすような N 人の寝方を 1 つ求めよ．もちろん，あるマスに同時に 2 人の人がいることはできない．

採点基準

• すべての入力データに対し，課題中の条件を満たすような出力をした場合は 1 点を与える．
• 上に加え，すべての入力データに対し出力に含まれる文字 . の個数が N + K 以下である場合にはさらに 99 点を与える．

注意: この問題では「すべての入力データに対し，条件を満たすような出力をした」場合を「Accepted」として扱います．従って，提出した結果がACであっても点数が 1 点である可能性があります．

入力例

4 4

出力例

5 4
BB.A.
BAAA.
B.DDD
CCCCD