描述

这是一个非常有趣的智力游戏，它规则简单而又变化多端。

游戏在一个m*n的方格里进行。游戏开始时所有的格子都是白色。游戏的目标是通过给出的线索按要求选择一些方格涂黑。这些线索是写在每一行和每一列前面的一些数字，它告诉了你该行或者该列应该出现的几组黑色方格各有多少个。

下面是一个简单的例子。在某一行中，线索给出了“2 1 4”三个数字，那么从这一行的某个位置起将依次出现两个相邻的黑色方格、若干白色方格、一个黑色方格、若干白色方格、四个连续的黑色方格，并且不再有其它的黑色方格。一种可能的情况如下图所示。

２１４□■■□□□■□■■■■

你需要选择一些方格涂成黑色，使得这些黑色方格满足所有行和所有列的要求。

例如，下图给出了某个谜题的一个可能的解（第二列没有数字表示这一列没有黑色方格）。

１
＼２　１２
１□□■□
１１■□□■
１２■□■■

给出这样一个谜题，请打印出该问题的解。

格式

输入格式

第一行有两个用空格隔开的正整数m,n，他们分别表示该谜题的方格列数和行数。

接下来m行从左至右描述了谜题的纵向信息。每一行有若干个数字，这些数字表示该列从上至下将会出现的连续黑色方格数。每一行用一个数字0作为结束。

接下来n行从上至下描述了谜题的横向信息。每一行有若干个数字，这些数字表示该行从左至右将会出现的连续黑色方格数。每一行用一个数字0作为结束。

对于30%的数据，m,n<=3；
对于50%的数据，m,n<=10；
对于100%的数据，m,n<=20。

输出格式

将谜题的解打印出来。

每一个方格用两个字符表示。其中，一个白色方格用“ ”（两个空格）表示，一个黑色方格用“##”表示。因此，输出数据一共有n行，每行2m个字符。

我们保证输入数据有唯一解。

样例1

样例输入1

4 3
2 0
0
1 1 0
2 0
1 0
1 1 0
1 2 0

样例输出1

    ##  
##    ##
##  ####

限制

各个测试点5s

来源

Matrix67原创