#include <stdio.h>
#include <stdlib.h>

/************** <HINT> ******************/
// ピクロスのヒントの構造体
typedef struct{
    int length;
    int *data;
	int sum;
} hint;
// ヒントのデータ割り当て
hint* new_hint(int length)
{
    hint *h = (hint*)calloc(1,sizeof(hint));
    h->length = length;
    h->data = (int*)calloc(length,sizeof(int));
    return h;
}
// ヒントのデータコピー（戻り値０で正常）
int copy_hint(hint *src, hint *dst)
{
    int i;
    int len = src->length;
    // サイズチェック
    if(src->length != dst->length) return -1;
    // コピー
    for(i=0;i<len;i++){
        dst->data[i] = src->data[i];
    }
	dst->sum = src->sum;
    return 0;
}
// ヒントのクローンを作成
hint* clone_hint(hint *h)
{
    hint *h2 = new_hint(h->length);
    copy_hint(h,h2);
    return h2;
}
// ヒントのデータ解放
void delete_hint(hint *h)
{
    free(h->data);
    free(h);
}
// ヒントの合計値をセットする
int set_sum_hint(hint *h)
{
    int i;
    int len = h->length;
	h->sum = 0;
    for(i=0;i<len;i++){
		// 入力チェックも兼ねる
		if(h->data[i] < 1){
			return 0;
		}
        h->sum += h->data[i];
    }
	return h->sum;
}
// ヒントの最大長を得る
int maxlen_hints(hint **h, int count)
{
    int i,len,max=0;
    for(i=0;i<count;i++){
        len = h[i]->length;
        if(max<len) max = len;
    }
    return max;
}
/************** </HINT> ******************/

/************** <CELL> ******************/
// セルの状態（不明・塗りつぶし・空白・決定不可能）
typedef enum{
    UNKNOWN, FILL, SPACE, ND
} stat;
// セルの構造体
typedef struct{
    stat stat;
} cell;
// セルのデータ割り当て
cell* new_cell(void)
{
    cell *c = (cell*)calloc(1,sizeof(cell));
    c->stat = UNKNOWN;
    return c;
}
// セルのデータコピー（戻り値０で正常）
int copy_cell(cell *src,cell *dst)
{
    dst->stat = src->stat;
    return 0;
}
// セルのデータ解放
void delete_cell(cell *c)
{
    free(c);
}
/************** </CELL> ******************/

/************** <PICLOS> ******************/
// ピクロスの大きさの構造体
typedef struct{
    int x; // よこ
    int y; // たて
} size;
// ピクロスのデータ
typedef struct{
    size size; // 大きさ
    hint **hintX, **hintY; // ヒント
    cell ***cell; // セル
} piclos;
// ピクロスのデータ割り当て
piclos* new_piclos(int x, int y)
{
    int i,j;
    piclos *p = (piclos*)calloc(1,sizeof(piclos));
    p->size.x = x;
    p->size.y = y;
    // ヒント割り当て
    p->hintX = (hint**)calloc(x,sizeof(hint*));
    p->hintY = (hint**)calloc(y,sizeof(hint*));
    // セル割り当て
    p->cell = (cell***)calloc(x,sizeof(cell**));
    for(i=0;i<x;i++){
        p->cell[i] = (cell**)calloc(y,sizeof(cell*));
        for(j=0;j<y;j++){
            p->cell[i][j] = new_cell();
        }
    }
    return p;
}
// ピクロスのデータコピー（戻り値０で正常）
int copy_piclos(piclos *src, piclos *dst)
{
    int i,j,len;
    int x = src->size.x;
    int y = src->size.y;
    // サイズチェック
    if(src->size.x != dst->size.x) return -1;
    if(src->size.y != dst->size.y) return -1;
    // ヒントコピー
    for(i=0;i<x;i++){
        dst->hintX[i] = clone_hint(src->hintX[i]);
    }
    for(i=0;i<y;i++){
        dst->hintY[i] = clone_hint(src->hintY[i]);
    }
    // セルコピー
    for(i=0;i<x;i++){
        for(j=0;j<y;j++){
            copy_cell(src->cell[i][j],dst->cell[i][j]);
        }
    }
    return 0;
}
// ピクロスのクローンを作成
piclos* clone_piclos(piclos *p)
{
    piclos* p2 = new_piclos(p->size.x,p->size.y);
    copy_piclos(p,p2);
    return p2;
}
// ピクロスのデータ解放(del_hint = 1でヒントのデータも同時に開放/*解放忘れ防止*/)
void delete_piclos(piclos *p, int del_hint)
{
    int i,j;
    int x = p->size.x;
    int y = p->size.y;
    // セル解放
    for(i=0;i<x;i++){
        for(j=0;j<y;j++){
            delete_cell(p->cell[i][j]);
        }
        free(p->cell[i]);
    }
    free(p->cell);
    // ヒント解放
    if(del_hint){
        for(i=0;i<x;i++){
            delete_hint(p->hintX[i]);
        }
        for(i=0;i<y;i++){
            delete_hint(p->hintY[i]);
        }
    }
    free(p->hintX);
    free(p->hintY);
    free(p);
}
/************** </PICLOS> ******************/

/************** <OUTPUT> ******************/
void print_piclos_sub(piclos *p, char *s)
{
    int i,j,idx,len,lenX,lenY;
    int x = p->size.x;
    int y = p->size.y;
    lenX = maxlen_hints(p->hintX, x);
    lenY = maxlen_hints(p->hintY, y);
    // 横方向のヒントの表示
    for(i=0;i<lenX;i++){
        for(j=0;j<lenY;j++) printf("   ");
        for(j=0;j<x;j++){
            len = p->hintX[j]->length;
            idx = len-lenX+i;
            if(idx >= 0){
                printf("%3d",p->hintX[j]->data[idx]);
            }else{
                printf("   ");
            }
        }
        printf("\n");
    }
    for(j=0;j<y;j++){
        // 縦方向のヒントの表示
        for(i=0;i<lenY;i++){
            len = p->hintY[j]->length;
            idx = len-lenY+i;
            if(idx >= 0){
                printf("%3d",p->hintY[j]->data[idx]);
            }else{
                printf("   ");
            }
        }
        // セルの表示
        for(i=0;i<x;i++){
            switch(p->cell[i][j]->stat)
            {
            case UNKNOWN: printf("   "); break;
            case FILL:    printf(" ##"); break;
            case SPACE:   printf(s); break;
            default:      printf(" ? "); break;
            }
        }
        printf("\n");
    }
    printf("\n");
}
void print_piclos(piclos *p)
{
	print_piclos_sub(p, " x ");
}
void print_piclos_fin(piclos *p)
{
	print_piclos_sub(p, "   ");
}
/************** </OUTPUT> ******************/

/************** <INPUT> ******************/
int s_count(char *s, char d)
{
    int i=0;
    while(*s) if(*s++==d) i++;
    return i;
}
int i_split(char *s, char d, int* res, int len)
{
    int i=0,a=0;
    char c;
    while(c=*s++){
        if(c==d){
            i++;a=0;
            if(i>=len) return -2;
        }else{
            if(c < '0' || c > '9') return 0;
            a *= 10;
            a += (int)(c - '0');
            res[i] = a;
        }
    }
    return 1;
}

int input_piclos_hints(piclos *p)
{
    int i,j,x,y,len,sum,res=1;
    char str[255];
    x = p->size.x;
    y = p->size.y;
    gets(str);//バッファクリア
    puts("ピクロスのヒント（列方向）を入力してください。(空白区切りで各列ごとに改行)");
    for(i=0;i<x;i++){
        gets(str);
        len = s_count(str,' ') + 1;
        p->hintX[i] = new_hint(len);
        if(!i_split(str,' ',p->hintX[i]->data,len))
		{
			res = 0; puts("入力エラーを検出しました。");
		}else{
			sum = set_sum_hint(p->hintX[i]);
			if(sum==0 || (sum+len-1)>p->size.y){
				res = 0; puts("入力エラーを検出しました。");
			}
		}
    }
    puts("ピクロスのヒント（行方向）を入力してください。(空白区切りで各列ごとに改行)");
    for(i=0;i<y;i++){
        gets(str);
        len = s_count(str,' ') + 1;
        p->hintY[i] = new_hint(len);
        if(!i_split(str,' ',p->hintY[i]->data,len)){
			res = 0; puts("入力エラーを検出しました。");
		}else{
			sum = set_sum_hint(p->hintY[i]);
			if(sum==0 || (sum+len-1)>p->size.x){
				res = 0; puts("入力エラーを検出しました。");
			}
		}
    }
	return(res);
}
/************** </INPUT> ******************/

/************** <DETECT> ******************/

// 現状とヒントから決定可能なセルを埋める(指定行/列)
// 引数：row=行指定,col=列指定（0起点、行指定時はcol=-1,列指定時はrow=-1）
// 戻り値：確定セルの増分（Nセル決定状態→N+Mセル決定状態：戻り値M）
int detect_line(piclos *p, int row, int col)
{
	hint *h; // 対象ヒント
	stat *w0,*w1; // 作業用セル状態
	int *blank; // 黒セルの間隔
	int blank_left, blank_right; // 左右の空白セル数
	// x,y:セル選択用イテレータ; dx,dy:イテレータの増分; idx,i,j:カウンタ変数; k:対象方向のセル数; n:blankの数; sum:合計値; ptr:現在操作中のblankを指す
	int dx,dy,x,y,idx,i,j,k,n,sum,ptr;
	int f0, f1; // フラグ
	// count:確定セル(新);count0:確定セル(旧);
	int count=0, count0=0;
	// 引数チェック
	if(!(row==-1 || col==-1)) return -1;
	// 計算方向の初期化
	if(row==-1){ dx = 0; dy = 1; x = col; y = 0; k = p->size.y; h = p->hintX[x]; n = h->length; }
	if(col==-1){ dx = 1; dy = 0; x = 0; y = row; k = p->size.x; h = p->hintY[y]; n = h->length; }
	// 確定セルを数える
	x *= dy; y *= dx; // イテレータ初期化
	for(i=0;i<k;i++){
		if(p->cell[x][y]->stat != UNKNOWN) count0++;
		x += dx; y += dy;
	}
	if(count0 == k) return 0; // すべて確定しているようなので終了
	// 作業領域の準備
	w0 = (stat*)calloc(k,sizeof(stat));
	w1 = (stat*)calloc(k,sizeof(stat));
	x *= dy; y *= dx; // イテレータ初期化
	for(i=0;i<k;i++){
		w0[i] = p->cell[x][y]->stat;
		x += dx; y += dy;
	}
	// blank初期化
	blank = (int*)calloc(n,sizeof(int));
	for(i=0;i<n-1;i++){
		blank[i] = 1;
	}
	// 決定可能なセルの探索
	ptr = 0;
	f0 = 1;
	while(f0){
		// 現構成における合計値の計算
		sum = h->sum;
		for(i=0;i<n-1;i++) sum += blank[i];
		// 選択可能なすべての左右の空白セル数に対して
		for(blank_left = 0; blank_left <= (k-sum); blank_left++){
			blank_right = (k-sum) - blank_left;
			// 仮データの生成
			idx=0;
			for(i=0;i<blank_left;i++)		w1[idx++] = SPACE;
			for(i=0;i<n;i++){
				for(j=0;j<(h->data[i]);j++)	w1[idx++] = FILL;
				for(j=0;j<(blank[i]);j++)	w1[idx++] = SPACE;
			}
			for(i=0;i<blank_right;i++)		w1[idx++] = SPACE;
			// 確定済のデータとの整合性は取れているのか
			f1 = 1;
			x *= dy; y *= dx; // イテレータ初期化
			for(i=0;i<k;i++){
				if(p->cell[x][y]->stat != UNKNOWN){
					if(p->cell[x][y]->stat != w1[i]) f1 = 0;
				}
				x += dx; y += dy;
			}
			// 整合性が取れているのであれば比較して新しい候補を作る
			if(f1 == 1){
				for(i=0;i<k;i++){
					if(w0[i] == UNKNOWN){
						w0[i] = w1[i];
					}else{
						if(w0[i]!=w1[i]) w0[i] = ND; 
					}
				}
			}
		}
		// 次の構成を生成する
		if(n == 1 && h->data[0] == sum){ // 全塗りの場合
			f0 = 0;
		}else{
			ptr = (sum == k)?ptr+1:0;
			blank[ptr]++;
			for(i=0;i<ptr;i++) blank[i] = 1;
			f0 = (blank[n-1]==0);
		}
	}
	// 結果の上書き
	x *= dy; y *= dx; // イテレータ初期化
	for(i=0;i<k;i++){
		if(w0[i] == ND){
			p->cell[x][y]->stat = UNKNOWN;
		}else{
			p->cell[x][y]->stat = w0[i];
		}
		x += dx; y += dy;
	}
	// 作業領域の破棄
	free(blank);
	free(w0);
	free(w1);
	// 確定セルを数える
	x *= dy; y *= dx; // イテレータ初期化
	for(i=0;i<k;i++){
		if(p->cell[x][y]->stat != UNKNOWN) count++;
		x += dx; y += dy;
	}
	// if(count-count0 != 0) print_piclos(p);
	return count-count0;
}
int detect_all(piclos *p)
{
	int i,count=0;
	for(i=0;i<(p->size.x);i++)
		count += detect_line(p,-1,i);
	for(i=0;i<(p->size.y);i++)
		count += detect_line(p,i,-1);
	return count;
}
void detect(piclos *p)
{
	while(detect_all(p)){
		// print_piclos(p);
	}
}
/************* </DETECT> ******************/

/************* <ELIMINATE> ****************/
// 未確定のセルを数える
int countUNKNOWN_piclos(piclos *p)
{
	int i,j,cnt=0;
	for(i=0;i<p->size.x;i++)
		for(j=0;j<p->size.y;j++)
			if(p->cell[i][j]->stat == UNKNOWN)
				cnt++;
	return cnt;
}
// 行の整合性を判定
int line_enable(piclos *p, int row, int col)
{
	hint *h; // 対象ヒント
	stat *w; // 作業用セル状態
	int *blank; // 黒セルの間隔
	int blank_left, blank_right; // 左右の空白セル数
	// x,y:セル選択用イテレータ; dx,dy:イテレータの増分; idx,i,j:カウンタ変数; k:対象方向のセル数; n:blankの数; sum:合計値; ptr:現在操作中のblankを指す
	int dx,dy,x,y,idx,i,j,k,n,sum,ptr;
	int f0, f1; // フラグ
	int enable = 0;
	// 引数チェック
	if(!(row==-1 || col==-1)) return -1;
	// 計算方向の初期化
	if(row==-1){ dx = 0; dy = 1; x = col; y = 0; k = p->size.y; h = p->hintX[x]; n = h->length; }
	if(col==-1){ dx = 1; dy = 0; x = 0; y = row; k = p->size.x; h = p->hintY[y]; n = h->length; }
	// 作業領域の準備
	w = (stat*)calloc(k,sizeof(stat));
	// blank初期化
	blank = (int*)calloc(n,sizeof(int));
	for(i=0;i<n-1;i++){
		blank[i] = 1;
	}
	// 決定可能なセルの探索
	ptr = 0;
	f0 = 1;
	while(f0){
		// 現構成における合計値の計算
		sum = h->sum;
		for(i=0;i<n-1;i++) sum += blank[i];
		// 選択可能なすべての左右の空白セル数に対して
		for(blank_left = 0; blank_left <= (k-sum); blank_left++){
			blank_right = (k-sum) - blank_left;
			// 仮データの生成
			idx=0;
			for(i=0;i<blank_left;i++)		w[idx++] = SPACE;
			for(i=0;i<n;i++){
				for(j=0;j<(h->data[i]);j++)	w[idx++] = FILL;
				for(j=0;j<(blank[i]);j++)	w[idx++] = SPACE;
			}
			for(i=0;i<blank_right;i++)		w[idx++] = SPACE;
			// 確定済のデータとの整合性は取れているのか
			f1 = 1;
			x *= dy; y *= dx; // イテレータ初期化
			for(i=0;i<k;i++){
				if(p->cell[x][y]->stat != UNKNOWN){
					if(p->cell[x][y]->stat != w[i]) f1 = 0;
				}
				x += dx; y += dy;
			}
			if(f1 == 1) enable++;
		}
		// 次の構成を生成する
		if(n == 1 && h->data[0] == sum){
			f0 = 0;
		}else{
			ptr = (sum == k)?ptr+1:0;
			blank[ptr]++;
			for(i=0;i<ptr;i++) blank[i] = 1;
			f0 = (blank[n-1]==0);
		}
	}
	// 作業領域の破棄
	free(blank);
	free(w);
	return enable;
	
}
// 全セルの整合性を判定
int piclos_enable(piclos *p)
{
	int i,res=1;
	for(i=0;i<p->size.x;i++)
		if(line_enable(p,-1,i) == 0) res = 0;
	for(i=0;i<p->size.y;i++)
		if(line_enable(p,i,-1) == 0) res = 0;
	return res;
}
// 終了判定
int is_finish_piclos(piclos *p)
{
	return((countUNKNOWN_piclos(p) == 0) && piclos_enable(p));
}
// 選択が有効であるかを判定する
int elm_selection_enable(piclos *src, int x, int y, stat st)
{
	int enable;
	piclos *p = clone_piclos(src);
	p->cell[x][y]->stat = st;
	enable = (line_enable(p,-1,x) && line_enable(p,y,-1));
	delete_piclos(p,1);
	return enable;
}
// 塗潰せるセルを選ぶ(組み合わせが最も少ない場所から選ぶことで消去法の繰り返しを減らす)
int elm_select(piclos *p, int *x, int *y)
{
	int min=9999; // 全ての行・列について組み合わせ可能なパターンの個数を調べた場合の最小値
	int orient=0; // 組み合わせ数が最小となるものの方向。行方向:0; 列方向:1;
	int index=-1; // 組み合わせ数が最小となるもの行・列番号
	int a,i,k,dx,dy;
	// 最小探索
	for(i=0;i<p->size.y;i++){
		a = line_enable(p,i,-1);
		if(a > 1 && a < min){ min = a; orient=0; index=i; }
	}
	for(i=0;i<p->size.x;i++){
		a = line_enable(p,-1,i);
		if(a > 1 && a < min){ min = a; orient=1; index=i; }
	}
	// おかC
	if(index==-1) return 0;
	// イテレータ初期化
	if(orient){ dx = 0; dy = 1; *x = index; *y = 0; k = p->size.y; }
	else{ dx = 1; dy = 0; *x = 0; *y = index; k = p->size.x; }
	// 探索
	for(i=0;i<k;i++){
		if(p->cell[*x][*y]->stat == UNKNOWN){
			if(elm_selection_enable(p,*x,*y,FILL)){
				return 1;
			}
		}
		*x+=dx;*y+=dy;
	}
	return 0;
}
// 消去法の実装
int elmination(piclos *src)
{
	int x,y;
	piclos *p = clone_piclos(src);
	if(elm_select(p,&x,&y)){
		// 塗潰し可能なセルを塗潰したと仮定して解いてみる
		p->cell[x][y]->stat = FILL;
		detect(p);
		if(!piclos_enable(p)){
			// 仮定が間違っている場合、空白にして解いてみる。
			copy_piclos(src,p);
			p->cell[x][y]->stat = SPACE;
			detect(p);
			if(!piclos_enable(p)){
				// 塗潰しでも空白でもだめなので親の仮定がまちがい
				delete_piclos(p,1);
				return 0;
			}
		}
		if(is_finish_piclos(p)){
			// 終了判定をクリアすればめでたく終了
			copy_piclos(p, src);
			delete_piclos(p,1);
			return 1; // やったね！
		}else{
			// クリアできていないので再帰的に消去法を用いる
			if(elmination(p)){
				// 消去法の継続により解が求められた。
				copy_piclos(p, src);
				delete_piclos(p,1);
				return 1;
			}else{
				if(p->cell[x][y]->stat == SPACE){
					// 塗潰しでも空白でもだめなので親の仮定がまちがい
					delete_piclos(p,1);
					return 0;
				}
				// 空白にして解いてみる。
				copy_piclos(src,p);
				p->cell[x][y]->stat = SPACE;
				detect(p);
				if(!piclos_enable(p)){
					// 塗潰しでも空白でもだめなので親の仮定がまちがい
					delete_piclos(p,1);
					return 0;
				}
				// 終了判定をクリアすればめでたく終了
				if(is_finish_piclos(p)){
					copy_piclos(p, src);
					delete_piclos(p,1);
					return 1; // やったね！
				}else{
					// クリアできていないので再帰的に消去法を用いる
					if(elmination(p)){
						// 消去法で解が求められた。
						copy_piclos(p, src);
						delete_piclos(p,1);
						return 1;
					}else{
						// 塗潰しでも空白でもだめなので親の仮定がまちがい
						delete_piclos(p,1);
						return 0;
					}
				}
			}
		}
	}else{
		// 選択可能なセルがないので親の仮定がまちがい
		delete_piclos(p,1);
		return 0;
	}
}
/************* </ELIMINATE> ****************/

int main(void)
{
    piclos *p;
    int x,y;
	puts("ピクロスの列の数を入力してください。");scanf("%d",&x);if(x<1){puts("ERROR.");return 0;}
    puts("ピクロスの行の数を入力してください。");scanf("%d",&y);if(y<1){puts("ERROR.");return 0;}
    p = new_piclos(x,y);
    if(!input_piclos_hints(p)){
	    delete_piclos(p,1);
		return 0;// ERROR
	}
	detect(p);
	if(!is_finish_piclos(p)) elmination(p);
    print_piclos_fin(p);
    delete_piclos(p,1);
    return 0;
}