#!/usr/bin/perl

$row_count = <STDIN>;
chomp $row_count;
$col_count = <STDIN>;
chomp $col_count;

@row_clues = ();
for (1..$row_count) {
  my $line = <STDIN>;
  chomp $line;
  my @line = split " ", $line;
  push @row_clues, \@line;
}

@col_clues = ();
for (1..$col_count) {
  my $line = <STDIN>;
  chomp $line;
  my @line = split " ", $line;
  push @col_clues, \@line;
}

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

@lines = ();   # to be fed to dance2.

%columns = ();   # columns for dancing.
%npcolumns = ();   # non-primary columns for dancing.

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

# 0 = white
# 1 = black
# more colors might be added later.

for $row (0..($row_count-1)) {
  for $col (0..($col_count-1)) {
    # occupation in the "row" realm.
    $columns{"R".$row."R".$col} = 1;

    # occupation in the "col" realm.
    $columns{"C".$row."C".$col} = 1;

    # there are max 2 units of "row color" in each space.
    # a "rod" space occupies 2 units and 1 unit past each end.
    # This ensures that rods do not overlap.
    $npcolumns{"r".$row."r".$col." 2"} = 1;

    # there are max 2 units of "column color" in each space.
    # a "rod" space occupies 2 units and 1 unit past each end.
    # This ensures that rods do not overlap.
    $npcolumns{"c".$row."c".$col." 2"} = 1;

    # These represent white squares.
    push @lines, "R".$row."R".$col." "."C".$row."C".$col;
  }
}

for $row (0..($row_count-1)) {
  my @clues = @{$row_clues[$row]};

  my @minstart = 0;
  my @maxstart = $col_count - $clues[$#clues];
  for $id (0..($#clues-1)) {
    push @minstart, $minstart[$#minstart] + $clues[$id];
  }
  for $nid (1..$#clues) {
    $id = $#clues - $nid;
    unshift @maxstart, $maxstart[0] - $clues[$id];
  }

  for $id (0..$#clues) {  # id of the rod
    $columns{"r".$row."i".$id} = 1;  # this clue is satisfied somewhere
    if ($id != 0) {
      $npcolumns{"r".$row."o".$id." ".$col_count} = 1;  # order
    }
    my $len = $clues[$id];
    for $start ($minstart[$id]..$maxstart[$id]) {
      last if (($start+$len) > $col_count);
      my @feed = ();  # feed to dance2
      push @feed, "r".$row."i".$id;

      if ($start-1 >= 0) {
        push @feed, "r".$row."r".($start-1);
      }

      # intervening spaces are black
      for $i ($start..($start+$len-1)) {
        push @feed, "R".$row."R".$i;
        push @feed, "r".$row."r".$i." 2";
      }

      if ($start+$len < $col_count) {
        push @feed, "r".$row."r".($start+$len);
      }

      if ($id != 0) {
        push @feed, "r".$row."o".$id." ".($col_count-$start);
      }
      if ($id != $#clues) {
        push @feed, "r".$row."o".($id+1)." ".($start+$len);
      }

      push @lines, (join " ", @feed);
    }
  }
}

for $col (0..($col_count-1)) {
  my @clues = @{$col_clues[$col]};

  my @minstart = 0;
  my @maxstart = $row_count - $clues[$#clues];
  for $id (0..($#clues-1)) {
    push @minstart, $minstart[$#minstart] + $clues[$id];
  }
  for $nid (1..$#clues) {
    $id = $#clues - $nid;
    unshift @maxstart, $maxstart[0] - $clues[$id];
  }

  for $id (0..$#clues) {  # id of the rod
    $columns{"c".$col."i".$id} = 1;  # this clue is satisfied somewhere
    if ($id != 0) {
      $npcolumns{"c".$col."o".$id." ".$row_count} = 1;  # order
    }
    my $len = $clues[$id];
    for $start ($minstart[$id]..$maxstart[$id]) {
      last if (($start+$len) > $row_count);
      my @feed = ();  # feed to dance2
      push @feed, "c".$col."i".$id;

      if ($start-1 >= 0) {
        push @feed, "c".($start-1)."c".$col;
      }

      # intervening spaces are black
      for $i ($start..($start+$len-1)) {
        push @feed, "C".$i."C".$col;
        push @feed, "c".$i."c".$col." 2";
      }

      if ($start+$len < $row_count) {
        push @feed, "c".($start+$len)."c".$col;
      }

      if ($id != 0) {
        push @feed, "c".$col."o".$id." ".($row_count-$start);
      }
      if ($id != $#clues) {
        push @feed, "c".$col."o".($id+1)." ".($start+$len);
      }

      push @lines, (join " ", @feed);
    }
  }
}

unshift @lines, (join " ", (sort keys %columns), "|", (sort keys %npcolumns));

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

open FHAND, ">tempfile.nonogram";
print FHAND (join "\n", @lines);
print FHAND "\n";
close FHAND;

open FHAND, "./dance2 1 200 <tempfile.nonogram |";

my @tempgrid_r = ();
my @tempgrid_c = ();
my $lastlev;
my @rollback;

my $solnum;
my @solutions;

for $row (0..($row_count-1)) {
  for $col (0..($col_count-1)) {
    $tempgrid_r[$row][$col] = "?";
    $tempgrid_c[$row][$col] = "?";
  }
}

sub roll {
  my $line = $_[0];
    if ($line =~ /R(\d+)R(\d+)/ and 
        $line =~ /C(\d+)C(\d+)/) {
      my $row = $1;
      my $col = $2;
      $tempgrid_r[$row][$col] = '?';
      $tempgrid_c[$row][$col] = '?';
    } elsif ($line =~ /R(\d+)R(\d+)/) {
      while ($line =~ s/R(\d+)R(\d+)//) {
        my $row = $1;
        my $col = $2;
        $tempgrid_r[$row][$col] = '?';
      }
    } elsif ($line =~ /C(\d+)C(\d+)/) {
      while ($line =~ s/C(\d+)C(\d+)//) {
        my $row = $1;
        my $col = $2;
        $tempgrid_c[$row][$col] = '?';
      }
    }
}

while ($line = <FHAND>) {
  print "A ", $line;
  if ($line =~ /^(\d+)\:/) {
    $solnum = $1;
  } elsif ($line =~ /^L(\d+)/) {
    my $level = $1;
    while ($level <= $lastlev) {
      roll($rollback[$lastlev]);
      $lastlev--;
    }

    if ($line =~ /R(\d+)R(\d+)/ and 
        $line =~ /C(\d+)C(\d+)/) {
      my $row = $1;
      my $col = $2;
      $tempgrid_r[$row][$col] = '-';
      $tempgrid_c[$row][$col] = '-';
    } elsif ($line =~ /R(\d+)R(\d+)/) {
      while ($line =~ s/R(\d+)R(\d+)//) {
        my $row = $1;
        my $col = $2;
        $tempgrid_r[$row][$col] = 'X';
      }
    } elsif ($line =~ /C(\d+)C(\d+)/) {
      while ($line =~ s/C(\d+)C(\d+)//) {
        my $row = $1;
        my $col = $2;
        $tempgrid_c[$row][$col] = 'X';
      }
    }
    $rollback[$level] = $line;

    $lastlev = $level;

   # system("clear");
    print "Level $level, choice $choicenum of $len\n";
    for $mrow (0..($row_count-1)) {
      for $mcol (0..($col_count-1)) {
        print "", $tempgrid_r[$mrow][$mcol];
      }
      print " ";
      for $mcol (0..($col_count-1)) {
        print "", $tempgrid_c[$mrow][$mcol];
      }
      print "\n";
    }
    print "\n";
  } else {
    if ($line =~ /R(\d+)R(\d+)/ and 
        $line =~ /C(\d+)C(\d+)/) {
      my $row = $1;
      my $col = $2;
      $solutions[$solnum][$row][$col] = "-";
    } else {
      while ($line =~ s/R(\d+)R(\d+)//) {
        my $row = $1;
        my $col = $2;
        $solutions[$solnum][$row][$col] = "X";
      }
    }
  }
}

for $s (1..$solnum) {
  print "Solution $s:\n";
  for $mrow (0..($row_count-1)) {
    for $mcol (0..($col_count-1)) {
      print " ", $solutions[$s][$mrow][$mcol];
    }
    print "\n";
  }
  print "\n";
}