#!/usr/bin/perl

$foo = $ARGV[0];

@sums = split " = ", $foo;
foreach (@sums) {
  s/ \+ / /g;
}

%letters = ();
%nozeroes = ();

$maxlen = 0;
foreach (@sums) {
  foreach (split '') {
    next if ($_ eq ' ');
    $letters{$_} = 1;
  }
  foreach (split ' ') {
    $maxlen = length $_ if ($maxlen < length $_);
    $nozeroes{substr($_, 0, 1)} = 1;  
  }
}

# print "Letters are ", join('', keys(%letters)), "\n";
die "Too many letters" if (scalar keys %letters > 10);

@formulae = ();
@modulus = ();
@letters = ();

$tens = 1;

foreach $count (1..($maxlen+1)) {
  my @temp = ();
  foreach $sum (0..$#sums) {
    my @wlist = ();
    foreach $word (split ' ', $sums[$sum]) {
      $ss = ($count >= length $word) ? $word : substr($word, -$count);
      push @wlist, $ss;
      foreach (split '', $ss) {
        if ($letters{$_} == 1) {
          push @letters, $_;
          $letters{$_} = 0;
        }
      }
    }
    push @temp, join(' ', @wlist);
  }
  $formulae[$count-1] = \@temp;
  $tens *= 10;
  $tens = 1000000000000 if ($count == $maxlen+1);
  push @modulus, $tens;
}

sub getval {
  my @letters = split '', $_[0];
  my $answer = 0;
  foreach (@letters) {
    return -1 if ($value{$_} == -1);
    $answer *= 10;
    $answer += $value{$_};
  }
  return $answer;
}

sub getsum {
  my @words = split ' ', $_[0];
  my $answer = 0;
  foreach (@words) {
    my $temp = getval($_);
    return -1 if ($temp == -1);
    $answer += $temp;
  }
  return $answer;
}

sub evaluate {
  my $modulus = shift @_;
#print "modulus is $modulus\n";
  my $value = getsum(shift @_);
#print "value is $value\n";
  return -1 if ($value == -1);
  $value %= $modulus;
  while ($#_ >= 0) {
    my $temp = getsum(shift @_);
#print "temp is $temp\n";
    return -1 if ($temp == -1);
    $temp %= $modulus;
    return 0 if ($temp != $value);
  }
  return 1;
}

sub recurse {
  if ($_[0] == (scalar(@letters))) {
    foreach (@letters) {
      print $_;
      print " ";
      print $value{$_};
      print " ";
    }
    print "\n";
    return;
  }
  my $pos = $_[0];
  my $try;
  my $start = (exists $nozeroes{$letters[$pos]}) ? 1 : 0;
  for $try ($start..9) {
    next if ($assigned{$try} ne "");
    my $letter = $letters[$pos];
    $assigned{$try} = $letter;
    $value{$letter} = $try; 
# print "-" x $pos, " $letter $value{$letter}\n";
    my $bad = 0;
    foreach (0..$#formulae) {
      my $result = evaluate($modulus[$_], @{$formulae[$_]});
      $bad = 1 if ($result == 0);
#if ($bad == 1) {
#  print "bad: ";
#  print join " = ", @{$formulae[$_]};
#  print "\n"; 
#  for (@letters) {
#    print $_, " ", $value{$_}, " ; ";
#  }
#  print "\n";
#}
      last if ($bad == 1);
      last if ($result == -1);
    }
    if ($bad == 0) {
      recurse($pos+1);
    }
    $value{$letter} = -1;
    $assigned{$try} = "";
  }
}

sub numerically {
   return $a <=> $b;
}

foreach (0..11) {
  $assigned{$_} = "";
}
for (@letters) {
  $value{$_} = -1;
}

recurse(0);