小达莎收到了一份新礼物，是一个游戏。游戏的盒子被划分为 $h \times w$ 个大小相同的方格。盒子里装有若干多格骨牌（polyomino）碎片。每个多格骨牌完全占据三到五个方格，且所占区域是边连通的。这些多格骨牌可以逐个从盒子里自由取出，由于它们的两个表面都有颜色，因此在游戏过程中可以进行旋转和翻转。此外，盒子里还有一个折叠起来的棋盘，其大小为 $2h \times 2w$ 个方格。
达莎把棋盘铺在地板上，并将所有的多格骨牌放置在棋盘上，使得每个多格骨牌都完全占据若干个方格，没有超出棋盘边界，且任意两个多格骨牌不重叠。
现在到了把游戏收回盒子里的时候了。达莎开始尝试将多格骨牌放回盒子里，但结果发现这并不容易：她成功放入了一些，但剩余多格骨牌的形状导致无法在不与已放入的多格骨牌重叠的情况下将它们全部放入。达莎把所有的多格骨牌都放回了棋盘上，坐在旁边思考。
请解决达莎问题的推广版本。给定多格骨牌在棋盘上的配置，输出一种将它们全部放入盒子中的方法，使得每个多格骨牌完全占据若干个方格，没有超出盒子边界，且任意两个多格骨牌不重叠。
输入格式
第一行包含两个整数 $h$ 和 $w$：盒子的高度和宽度（$20 \le h, w \le 100$）。 随后给出包含盒子内容的棋盘：接下来的 $2h$ 行，每行包含恰好 $2w$ 个字符。如果字符是 “.”（点，ASCII 码 46），则对应的方格为空。否则，该字符是英文字母大写（“A”–“Z”）。每个多格骨牌是一个由相同字母组成的区域，包含 3、4 或 5 个方格，且是边连通的。
输出格式
输出恰好 $h$ 行，每行包含恰好 $w$ 个字符：将多格骨牌放入盒子中的方式。使用与给定棋盘相同的格式，但有一个明显的区别：不能留下任何空方格。
每个多格骨牌都可以旋转和翻转。每个多格骨牌对应的字母可以任意更改。但是，输入中的所有多格骨牌都必须放入盒子中。
样例
输入 1
20 20 ........................................ ..C.........LL..........T.BBBBB...H..... ..C...PPP..LL..S.......TT.........H..... ..C...P.P.....SSS...X.TT.........HHH.... ..CBBB......I......XX.........RRRR...... ..CB.......II...X...X.......FF...AA..... ...M......II....XXX.......M.FF..AAA..... ..MMM........S...X.YYY...MM.F........... ...M....M....S....YY...CC.M............. ..GGGG.MMM...S.........CC............... ..G.....M...GGG.FFFFF.......KK...K...... ...........II............C.KKGG..KK..... ...........II............C...G...K...... ................MM......CC.......K...... .KKK.............M......C..EEE.......... ..K..............MM.........E........... W..EEZZZZ...................E........... W...EZ..P...............RRR.H.....EEE... WFFFFF..P...............RAAAH.N....E.... W....G.PPP...........O..R..AH.NNN..E.... W...GG..............OO......H...N....MM. .....GG..............O......HS.....R.M.. ..UJJJJJ............O........SCCC..R.... ..U............I....O..XXX...S.C...RR... ..UU.QQ.P.....FIIIOOO........S.C...R.... .....Q..PPPM..F............CCS..P....... ...I....P.MM..FLLL.........CC.PPP....... ...I......MM..F....OOO..........P....... ..III.....A...F..X.O.....N.............. ..UUU.....AAA..XXX.......N......LLLLL... ....UU....A......X.......N.............. ...TTLLLLL........VVA....N..........LLLL .TTT...E.........VV.A..PP..............L .......E.........P..A..PP....AAAAA....G. .....D.E..P.....PP.....B.U............G. ....DDDE..P....PPU....BB.UU...........G. .......E.PPPE..Z.U....BJUU...........GG. ....Y.......EZZZ.U.H...JJJ......LLLL.... ..YYY.....EEE.Z..U.HDDDJ........L....... ..Y................HHHDD................
输出 1
PPLLLNFFFFPPLLLPPPPP PPLLNNNJFPPLLJJJJJNN PJJJJNJJJPFFFFFNNNJN NNNJPFPPPNNNLLLHNJJN LNPPPFFFJJNLLHHHNLJN LNJJPFJJJPNJJJJJHLLL LJJHHHNPPPLLLPPPHHHL LJHHNNNLPNNLNNPLLHNN LPPPFFFLLNNLNNLLPPPN HLLLPJJJLJJJJJHHHHPL HHHLPPPJPPFFNNFFFFFL HPNLPHNJPPLFNPPDDDDL JPNNNHNNNLLLHHPNHHHH JPPPNHHHPDPPHHJNNNNP JJLFFFFFPDDPPLJJJJPP PPLLLLJPPPDLLLBBBBBP NPPPHJJJNNNNNLPPPFFN NNNHHHDJLPFFFFFPPFPN PNPNHDDDLPPNNNNNFFPN PPPNNNNLLLPPLLLLLPPP