use warnings;
use strict;
use Math::BigInt;
use Math::Prime::Util qw/znprimroot powmod next_prime vecmin vecmax/;

undef $/;
$|=1;
my $rawprogram = <>;
my @rawprogram = ($rawprogram =~ /(\d+)/g);

my $counters = $rawprogram[1];
($counters + 1) ** 2 == @rawprogram or die "Program is the wrong size";
$counters<2 and die "Cannot compile a 0- or 1-counter program";

my @triggers;
my @values;
my $haltindex = undef;
my $reset = Math::BigInt->bzero;
my $inconsistent = 0;
for my $y (0..$counters) {
    my $trigger = [];
    my $ishalt = 1;
    $values[$y] = Math::BigInt->new(shift @rawprogram);
    for my $x (1..$counters) {
        my $cell = Math::BigInt->new(shift @rawprogram);
        push @$trigger, $cell;
        $cell > 0 and $ishalt = 0;
        if ($x == $y && $x != 1 && $cell != $reset) {
            $inconsistent = 1;
        }
        if ($x == $y && $cell > $reset) {
            $reset = $cell;
        }
    }
    $triggers[$y] = $trigger;
    $ishalt and defined $haltindex and
        die "Two halt counters; $haltindex, $y-1";
    $ishalt and $haltindex = $y-1;
}
defined $haltindex or die "No halt counter";
shift @triggers;
shift @values;

sub printprog {
    print STDERR "Program:\n";
    print STDERR "$counters counters.\n";
    print STDERR "Initial values: [@values]\n";
    print STDERR "Triggers:\n";
    printf STDERR "[@{$triggers[$_]}]%s\n",
        $_ == $haltindex ? " (halt)" : "" for 0..$#triggers;
    printf STDERR "%self-reset: $reset\n",
        $inconsistent ? "Highest s" : "S";
    print STDERR "\n";
}

printprog();

if ($inconsistent) {
    print STDERR "Adjusting to give a consistent self-reset.\n";
    for my $y (0..$counters-1) {
        my $adjustment = $reset - $triggers[$y][$y];
        for my $x (0..$counters-1) {
            $triggers[$y][$x] += $adjustment;
        }
    }
    $inconsistent = 0;

    printprog();
}


my $countercells = next_prime(2*$counters) - 1;
if ($countercells != 2*$counters) {
    print STDERR "2*$counters+1 = ", 2*$counters+1,
        " is not prime; padding to ", $countercells/2, " counters.\n";
    while ($countercells != 2*$counters) {
        $counters++;
        push @values, $reset;
        my $trigger = [];
        push @$trigger, $reset for 0..$counters-1;
        push @$_, $reset for @triggers;
        push @triggers, $trigger;
    }

    printprog();
}

print STDERR "Generating a modularly distinct Golomb ruler of order ",
    $countercells, ".\n";
my $primroot = znprimroot($countercells + 1);
print STDERR "Smallest primitive root of ", $countercells + 1,
    " is $primroot.\n";
print STDERR "Formula is thus 2*$countercells*i - ($primroot**i)%",
    $countercells+1, " + 1.\n";
my @ruler;
$ruler[$_] = 2*$countercells*$_
    - powmod($primroot, $_, $countercells+1) + 1
    for 0..$countercells-1;
print STDERR "Ruler is [@ruler].\n";
my @modruler = map $_ % $counters, @ruler;
print STDERR "Modulo the number of counters, this is [@modruler].\n";
my @differences;
my %seendifferences;
for my $i (1..$#ruler) {
    for my $j(0..$i-1) {
        my $difference = $ruler[$i]-$ruler[$j];
        push @differences, $difference;
        ++$seendifferences{$difference} >= 2 and die
            "Duplicate difference on the ruler: $difference";
    }
}
@differences = sort {$a <=> $b} @differences;
print STDERR "List of differences on the ruler: [@differences].\n";
print STDERR "\n";

my @counterloc;
my @fallbackloc;
for my $i (0..$#ruler) {
    if (defined $fallbackloc[$modruler[$i]]) {
        defined $counterloc[$modruler[$i]] and die
            "Triplicate modulus: $modruler[$i]";
        $counterloc[$modruler[$i]] = $ruler[$i];
    } else {
        $fallbackloc[$modruler[$i]] = $ruler[$i];
    }
}

print STDERR "For each modulus:\n";
print STDERR "- Its first appearance is the fallback location.\n";
print STDERR "- Its second appearance is the counter location.\n";
print STDERR "Counter locations: [@counterloc].\n";
print STDERR "Fallback locations: [@fallbackloc].\n";
my @ccdistance;
$ccdistance[$_] = $counterloc[($_+1)%$counters] - $counterloc[$_]
    for 0..$counters-1;
my @modccdistance;
$modccdistance[$_] = $ccdistance[$_]%$counters for 0..$counters-1;
my @fcdistance;
$fcdistance[$_] = $counterloc[($_+1)%$counters] - $fallbackloc[$_]
    for 0..$counters-1;
my @modfcdistance;
$modfcdistance[$_] = $fcdistance[$_]%$counters for 0..$counters-1;
print STDERR "Distance from each counter to the next: [@ccdistance].\n";
print STDERR "Modulo $counters, the number of counters: [@modccdistance].\n";
print STDERR "Distance from each fallback to the next counter: ",
    "[@fcdistance].\n";
print STDERR "Modulo $counters, the number of counters: [@modfcdistance].\n";
my $maxmoverange = vecmax @fcdistance;
print STDERR "Greatest distance between counters: $maxmoverange.\n";
my $haltdistance = $counterloc[$haltindex] - $fallbackloc[$haltindex];
print STDERR "Distance from halt counter (", $counterloc[$haltindex],
    ") to its fallback (", $fallbackloc[$haltindex], "): -$haltdistance.\n";
print STDERR "\n";

# Adjustments:
# Counter location - counter location: twice the zeroing trigger amount
#   (minus 2, if the next counter)
# Fallback location - next counter: -2
# 0: twice the self-reset value
# Counter location - own fallback: twice the self-reset value
#   (except for the halt counter, which doesn't change its own fallback)
# Counter location - previous fallback: minus twice the self-reset value
# Fallback location - previous fallback: minus twice the self-reset value
my %adjustments;
$adjustments{0} = $reset * 2;
for my $x (0..$counters-1) {
    my $prevx = $x - 1;
    $prevx < 0 and $prevx += $counters;
    my $nextx = ($x + 1) % $counters;
    for my $y (0..$counters-1) {
        my $dist = $counterloc[$y] - $counterloc[$x];
        $adjustments{$dist} = 2 * $triggers[$x][$y] - ($y == $nextx ? 2 : 0);
    }
    my $dist = $counterloc[$nextx] - $fallbackloc[$x];
    $adjustments{$dist} = -2;
    $dist = $fallbackloc[$x] - $counterloc[$x];
    $adjustments{$dist} = 2 * $reset unless $x == $haltindex;
    $dist = $fallbackloc[$prevx] - $counterloc[$x];
    $adjustments{$dist} = -2 * $reset;
    $dist = $fallbackloc[$prevx] - $fallbackloc[$x];
    $adjustments{$dist} = -2 * $reset;
}
my $minadjustrange = vecmin map Math::BigInt->new($_), keys %adjustments;
my $maxadjustrange = vecmax map Math::BigInt->new($_), keys %adjustments;

my $lastcounterindex = $ruler[$#ruler];
my $maxwriteindex = $lastcounterindex + $maxadjustrange;
my $minreadindex = -$haltdistance;
my $maxreadindex = $lastcounterindex + $maxmoverange;
print STDERR "Written portion of the tape: $minadjustrange to $maxwriteindex",
    " (i.e. 0 - ", -$minadjustrange,
    " to $lastcounterindex + $maxadjustrange).\n";
print STDERR "Read portion of the tape: $minreadindex to $maxreadindex",
    " (i.e. 0 - $haltdistance to $lastcounterindex + $maxmoverange).\n\n";

if ($minadjustrange < $minreadindex) {
    print "Move to the first read cell: ",
        "some cells are written that won't be read\n";
    print ">" x ($minreadindex - $minadjustrange), "\n";
}
print "Set initial values of cells\n";
# Initial values:
# Unread cells: doesn't matter, set to 0
# Fallbacks: 0 (except the last, that's set to twice the reset value)
# Counters: twice their value (the first is pre-decremented)
# Other read cells: 1 (so that they never zero; all adjustments are even)
my %initvalue;
$initvalue{$_} = 1 for $minreadindex..$maxreadindex;
$initvalue{$_} = 0 for @fallbackloc;
$initvalue{$fallbackloc[$counters-1]} = $reset*2;
$initvalue{$counterloc[$_]} = $values[$_] * 2 for 0..$counters-1;
$initvalue{$counterloc[0]} -= 2;
for my $i ($minreadindex..$maxreadindex) {
    $i == $minreadindex or print ">";
    $initvalue{$i} == 1 or print "\n";
    print "+" x $initvalue{$i};
    $initvalue{$i} <= 1 or print "\n";
}
print "\nMove to the location of the last fallback counter\n";
print "<" x ($maxreadindex - $fallbackloc[$counters-1]);
print "\n\n";
print "Loop as long as we aren't on the halt counter\n";
print "That is: we don't have a 0 the same distance to our left\n";
print "as the halt counter's fallback is from the halt counter\n";
print "<" x $haltdistance, "\n[\n  ", ">" x $haltdistance, "\n\n";

print "  This is a good time to show debug info (when available)\n";
print "  #\n\n";

print "  Move to the next counter or its fallback: it's ",
    "$maxmoverange minus some multiple of $counters away\n";
print "  If the counter is 0 we find it; otherwise we find its fallback\n";
print "  ", ">" x $maxmoverange, "\n";
print "  [", "<" x $counters, "]\n\n";

print "  Conditionally adjust each counter and fallback location\n";
print "  The conditionals are based on which counter or fallback we reached\n";
print "  and are implemented via changing cells at offsets which will hold\n";
print "  odd (that is: irrelevant) values unless we're in the right place\n";
print "  ", "<" x -$minadjustrange;
for my $i ($minadjustrange .. $maxadjustrange) {
    $i == $minadjustrange or print ">";
    if ($adjustments{$i}) {
        print "\n  ";
        $adjustments{$i} < 0 and print "-" x -$adjustments{$i};
        $adjustments{$i} > 0 and print "+" x $adjustments{$i};
        print "\n  ";
    }
}
print "<" x $maxadjustrange, "\n\n";

print "  Continue looping as long as we aren't on the halt counter\n";
print "  Same test as when we entered the loop\n";
print "  ", "<" x $haltdistance, "\n";
print "]\n";