#P1292. 拼图

拼图

潘帕斯草原最近流行起了一种拼图游戏,@潘帕斯雄鹰为了显示自己是最强的鹰,想尽办法要在这个游戏上赢过其他鹰……

这个拼图游戏要求将一些图形拼成一个正方形,图形的个数从15。如下图所示,图形个数是4

<o:p></o:p>

<v:shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></v:path><o:lock v:ext="edit" aspectratio="t"></o:lock></v:shapetype>

图形不能旋转,拼的时候不能重叠,拼完后的正方形里面不能有空隙。所有给定的图形都要使用。

<o:p></o:p>

左面的图表示这样拼不行,右面是一个成功的拼法。<o:p></o:p>

现在@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰如果可以请输出一种完成这个游戏的方案。<o:p></o:p>

<o:p></o:p> 

Input

本题有多组数据。文件的第一行是一个整数n,表示图形的个数,范围从1到5。
接下来有n个部分,每个部分的第一行是2个整数i和j,表示下面的i行j列用来描述一个图形。图形用0和1表示,1表示图形占有这个位置,0表示不占有,中间没有空格。例如上图中图形A的描述是
2 3
111
101
所有图形的长与宽都不超过5。
根据图形给出的顺序给每个图形编号,从1开始,至多到5。
保证数据无多解情况。

Output

如果不能拼成一个正方形,就输出“No solution possible”;否则,输出一种拼的方案:一个正方形的数阵,每个位置上的数字是占有这个位置的图形的编号,中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4,那么就可以输出
1112
1412
3422
3442

Sample Input

4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001

5 2 2 11 11 2 3 111 100 3 2 11 01 01 1 3 111 1 1 1

Sample Output

</p>
No solution possible
1133
1153
2223
2444

HINT

Source