#!/usr/bin/perl

$ROOTLEVEL = shift @ARGV;

@terms = sort numerically @ARGV;

foreach (@terms) {
  push @foo, $_;
}

######### temp

foreach (@terms) {
  push @f, $_;
  push @f, $_;
}

########## used for partition iteration

sub start_partition {
  return (0) x $_[0];
}

sub increment_partition {
  my @next;
  $next[0] = 1;
  for (1..$#_) {
    $next[$_] = $next[$_-1] + (($next[$_-1] == $_[$_]) ? 1 : 0);
  }
#print "NN ", join " ", @next, "\n";
  my $at = $#_;
  while ($at > 0) {
    if ($_[$at]+1 <= $next[$at-1]) {
      $_[$at]++;
      return @_;
    } else {
      $_[$at] = 0;
      $at--;
    }
  }
  return -1;
}

########## used for numerical sort
sub numerically { return $a <=> $b; }

sub byscanon {
  if ($stuff[$a*2] != $stuff[$b*2]) {
    return ($stuff[$a*2] <=> $stuff[$b*2]);
  } else {
    return ($stuff[$a*2+1] cmp $stuff[$b*2+1]);
  }
}

sub decrement {
  my @result = @_;
  my $pos = 0;
  while ($result[$pos] == 0) {
    $result[$pos] = 1;
    $pos++;
  }
  $result[$pos] = 0;
  return @result;
}

sub decrementbroot {
  my @result = @_;
  my $pos = 0;
  while ($result[$pos] == 0) {
    $result[$pos] = ($ROOTLEVEL+1);
    $pos++;
  }
  --$result[$pos];
  return @result;
}

sub sum {
  my $answer = 0;
  for (@_) {
    $answer += $_;
  }
  return $answer;
}

sub prod {
  my $answer = 1;
  for (@_) {
    $answer *= $_;
  }
  return $answer;
}

sub canonicalize {
  @stuff = @_;
  my $count = (scalar @stuff)/2;
  my @index = ();
  for (0..($count-1)) {
    push @index, $_;
  }
  sort byscanon @index;
  my @answer = ();
  for (@index) {
    push @answer, $stuff[$_*2];
    push @answer, $stuff[$_*2 + 1];
  }
  return @answer;
}

sub decimalpoint {
  my @answer = ();
  my $value = $_[0];
  push @answer, $value;
  while ($value >= 1) {
    $value /= 10;
    push @answer, $value;
  }
  return @answer;
}

sub makeoneint {
  return $_[0] if ($#_ == 0);
  my $i;
  my @answer = ();
  for $i (0..$#_) {
    next if ($i > 0 and $_[$i] == $_[$i-1]);
    my @temp = @_;
    my @oneval = splice @temp, $i, 1;
    my $val = $oneval[0];
    my @results = makeoneint(@temp);
    foreach (@results) {
      push @answer, $val.$_;
    }
  }
  return @answer;
}

sub makeonenum {
  my @nums = makeoneint(@_);
  my @answer = ();
  foreach (@nums) {
    push @answer, decimalpoint($_);
  }
  return @answer;
}

sub makemanynums {
  return if (0 == scalar @_);
  my @answer = ();

  my @temp = makeonenum(@_);
  foreach (@temp) {
    my @ttt = ($_);
    push @answer, \@ttt;
  }

  my @signs = ();
  for (1..$#_) {
    push @signs, 1;
  }
  my $sum = sum @signs;
  while ($sum > 0) {
    @signs = decrement @signs;
    my @group = ($_[0]);
    my @others = ();
    for (0..$#signs) {
      if ($signs[$_] == 1) {
        push @group, $_[$_+1];
      } else {
        push @others, $_[$_+1];
      }
    } 
    my @nums = makeonenum(@group);
    my @othernums = makemanynums(@others);
    my ($n, $ref);
    foreach $n (@nums) {
      foreach $ref (@othernums) {
        my @ar = ($n, @{$ref});
        push @answer, \@ar;
      }
    }
    $sum = sum @signs;
  }
  return @answer;
}

sub isfraction {
  return 1 if ($_[0] =~ /prod_[nd]*n[nd]*d[nd]*_x( neg)*$/);
  return 1 if ($_[0] =~ /prod_[nd]*d[nd]*n[nd]*_x( neg)*$/);
  return 0;
}

sub display {
  while ($#_ > 0) {
    my $rounded = sprintf("%.6f", $_[0]);
    if (int $rounded == $rounded and $rounded != $_[0]) {
      $rounded = sprintf("%d", $rounded);
      print $rounded, " = ", $_[1], " [rounded]\n";
    } else {
      print $_[0], " = ", $_[1], "\n";
    }
    shift @_;
    shift @_;
  }
}

sub processnums {
#  print join " : ", @_, "\n"; return;
  my @feed = ();
  foreach (0..$#_) {
    push @feed, $_[$_];
    push @feed, $_[$_];
  }
  my @results = manip(@feed);
  display(@results);

  my @iterator = ();
  foreach (0..$#_) {
    push @iterator, ($ROOTLEVEL + 1);
  }
  my $sum = sum @iterator;
  while ($sum > 0) {
    @iterator = decrementbroot @iterator;
    @feed = ();
    my $bad = 0;
    foreach (0..$#_) {
      if ($_ > 0 and $_[$_] == $_[$_-1] and $iterator[$_] > $iterator[$_-1]) {
        $bad = 1;
      }
      my $roots = $ROOTLEVEL - $iterator[$_];
      if ($roots == -1) {
        push @feed, $_[$_];
        push @feed, $_[$_];
      } elsif ($roots == 0) {
        push @feed, (-$_[$_]);
        push @feed, join " ", $_[$_], "neg";
      } else {
        my $value = $_[$_];
        my $expr = $_[$_];
        if ($value < 0) {
          $value = -$value;
          $expr .= " neg";
        }
        if ($value != 0 and $value != 1) {
          my $i;
          for $i (1..$roots) {
            $value = sqrt($value);
            $expr .= " sqrt";
          }
          push @feed, $value;
          push @feed, $expr;
        }
      }
    }
    if ($bad != 1) {
      my @results = manip(@feed);
      display(@results);
    }
    $sum = sum @iterator;
  }
}

sub matching {
  for (0..$#{$_[0]}) {
    return 0 if (${$_[0]}[$_] ne ${$_[1]}[$_]);
  }
  return 1;
}

$layer = 0;

sub manip {
  if ((scalar @_) == 2) {
    return @_;
  }
  my @terms = @_;
#  print join " :", $layer, "MANIP", @terms, "\n"; 
# return;
  my $count = (scalar @terms);
  my $tcount = $count / 2;

  @terms = canonicalize @terms;
# print join " :", "DEBUG", @terms, "\n";

  my @part = start_partition($tcount);
  @part = increment_partition(@part);

  my @answer = ();
  
  while ($part[0] != -1) {
    my $dup_pass = 1;
    my $gmax = 0;
    for (1..($tcount-1)) {
      if ($part[$_-1] > $part[$_] and $terms[$_*2-1] eq $terms[$_*2+1]) {
        $dup_pass = 0;
        last;
      }
      $gmax = $part[$_] if ($part[$_] > $gmax);
    }
#  print join " ", "PART", @part, "\n";
    if ($dup_pass) {

      # build the groups
      my @groups = ();
      for (0..$gmax) {
        my @temp = ();
        push @groups, \@temp;
      }
      for (0..($tcount-1)) {
        if ($part[$_] != 0 and 
            matching($groups[$part[$_]-1], $groups[$part[$_]])) {
          $dup_pass = 0;
          last;
        }
        push @{$groups[$part[$_]]}, $terms[$_*2];
        push @{$groups[$part[$_]]}, $terms[$_*2+1];
      }

      if ($dup_pass) {

        my $has_sol = 1;

        for (0..$gmax) {
          my @temp = manip(@{$groups[$_]});
          $groups[$_] = \@temp;
          if (@temp == ()) {
            $has_sol = 0;
          }
        }

        if ($has_sol) {

          my @lookat = (0) x ($gmax + 1);

          my $inc = $gmax;
        
          while ($inc >= 0) {
# print join " ", "LOOKAT", @lookat, "\n";
# for (0..$#groups) {
#   print join " ", "GROUP", $_, @{$groups[$_]}, "\n";
# }
      
            my @feed = ();
            for (0..$gmax) {
              push @feed, $groups[$_][$lookat[$_]];
              push @feed, $groups[$_][$lookat[$_]+1];
            }
            push @answer, combine(@feed);

#print join " ", "ANSWER", @answer, "\n";
      
            $inc = $gmax;
            $lookat[$inc]+= 2;
            while ($inc >= 0 and 
                   $lookat[$inc] == scalar @{$groups[$inc]}) {
              $lookat[$inc] = 0;
              $inc--;
              $lookat[$inc]+= 2;
            }
          }
        }

      }

    } 
    @part = increment_partition(@part);

  }

  return @answer;
}

sub combine {
# print "DEBUGES ", join " ", @_, "\n";
  my @answer = ();
  push @answer, try_addition(@_);
  push @answer, try_multiplication(@_);
  push @answer, try_powers(@_) if (scalar @_ == 4);
  return @answer;
}

sub try_addition {
# print "SUBDEBUGES ", join " ", @_, "\n";
  my $i = 0;

  my $has_integer = 0;
  my $has_decimal = 0;
  my $has_neg_integer = 0;
  my $has_neg_decimal = 0;
  my @values = ();
  my @exprs = ();

  while ($i <= $#_) {
    if ($_[$i+1] =~ /\+( neg)?$/) {
      return;  # can't add if terms are already added.
    }
    if ($_[$i+1] =~ /^0\.[\d]+$/) {
      $has_decimal = 1;
    }
    if ($_[$i+1] =~ /^[\d]+$/) {
      $has_integer = 1;
    }
    if ($_[$i+1] =~ /^0\.[\d]+ neg$/) {
      $has_neg_decimal = 1;
    }
    if ($_[$i+1] =~ /^[\d]+ neg$/) {
      $has_neg_integer = 1;
    }
    push @values, $_[$i];
    push @exprs, $_[$i+1];
    $i += 2;
  }

  return if ($has_decimal and $has_integer);
  return if ($has_neg_decimal and $has_neg_integer);

  my $value = sum @values;
  my $expr = join " ", @exprs, ("sum".(scalar @values)."+");

#print "DEBUGES ", join " ", @_, "\n";
#print "DEBUGVALUES ", join " ", @values, "\n";
#print "DEBUGEXPRS ", join " ", @exprs, "\n";
#print "DEBUG $value = $expr\n";
  
  return expand_neg_sqrt(0, $value, $expr);
}

sub try_multiplication {
  my $i = 0;
  my @div = ();
  my @answers = ();

# print "TRYMULT ", join " ", @_, "\n";

  while ($i <= $#_) {
    if ($_[$i+1] =~ /x( neg)?( sqrt)*$/) {
      return;  # can't mult if terms are already mult (or sqrt).
    }
    push @div, 0;
    $i += 2;
  }

  while ($div[0] != 2) {
# print "DIV ", join " ", @div, "\n";
    my $value = 1;
    my $expr = "";
    my $oper = "prod_";

    my $seen_nonprimitive = 0;
    my $seen_ge_1 = 0;
    my $seen_sum = 0;
    my $seenmult = 0;
    my $seendiv = 0;

    my $bad = 0;
    for (0..$#div) {
      if ($_ > 0 and
          $div[$_] == 0 and 
          $div[$_-1] == 1 and 
          $_[$_*2+1] eq $_[$_*2-1]) {
          # if two things are the same, can't have a
          # divide followed by a multiply
        $bad = 1;
        last;
      }
      if ($_[$_*2] < 0) {
        # values cannot be negative; we'll handle that ourselves.
        $bad = 1;
        last;
      }
      if ($_[$_*2] ne $_[$_*2+1]) {
        $seen_nonprimitive = 1;
      }
      if ($_[$_*2+1] =~ /sum\d\+$/) {
        $seen_sum = 1;
      }
      if ($_[$_*2] >= 1) {
        $seen_ge_1 = 1;
      }
      if ($div[$_] == 0) {
        $seenmult = 1;
        $value *= $_[$_*2];
        $expr .= $_[$_*2+1] . " ";
        $oper .= "n";  #numerator
      } elsif ($div[$_] == 1) {
        $seendiv = 1;
        if ($_[$_*2+1] =~ /neg pow$/) {
           # never divide by a negative power, 
           # since we will multiply by the positive one
          $bad = 1;
          last;
        }
        if ($_[$_*2+1] =~ /neg root$/) {
           # never divide by a negative root,
           # since we will multiply by the positive one
          $bad = 1;
          last;
        }
        if ($_[$_*2] == 0) { # don't divide by zero
          $bad = 1;
          last;
        }
        $value /= $_[$_*2];
        $expr .= $_[$_*2+1] . " ";
        $oper .= "d";  #denominator
      }
    }

    if ($seendiv and (!$seen_nonprimitive) and (!$seen_ge_1)) {
      # if there is a division involved, and all 
      # numbers are natural < 1, then we've already done
      # this by having 10x all.
      $bad = 1;
    }
    if ($seenmult == 1 and $bad != 1) {
      $expr .= $oper . "_x";

# print "EXPANDING ", $value, " = ", $expr, "\n";
 
      # If we've seen a sum, then don't allow negative, because
      # the sum could have inverted all its signs.
      push @answers, expand_neg_sqrt((1-$seen_sum), $value, $expr);
    }

    # increment the binary div-or-mult array
    my $lookat = $#div;
    $div[$lookat]++;
    while ($lookat > 0 and $div[$lookat] == 2) {
      $div[$lookat] = 0;
      $lookat--;
      $div[$lookat]++;
    }
  }
  return @answers;
}

sub expand_neg_sqrt {
  my ($do_neg, $value, $expr) = @_;

  my @answers;

  push @answers, $value, $expr;

  my $negvalue = -$value;
  my $negexpr = $expr . " neg";

  if ($do_neg) {
    push @answers, $negvalue, $negexpr;
  }

  if ($value > 0 and $value != 1) {
    for $i (1..$ROOTLEVEL) {
      $value = sqrt($value);
      $expr = $expr . " sqrt";
      push @answers, $value, $expr;
      push @answers, -$value, ($expr." neg");
    }
  } elsif ($value < 0 and $value != -1) {
    for $i (1..$ROOTLEVEL) {
      $negvalue = sqrt($negvalue);
      $negexpr = $negexpr . " sqrt";
      push @answers, $negvalue, $negexpr;
      push @answers, -$negvalue, ($negexpr." neg");
    }
  }
  return @answers;
}

sub try_powers {
  return if (scalar @_ != 4);
  my @answer = try_powers_oneway(@_);
  if ($_[1] ne $_[3]) {
    return(@answer, try_powers_oneway($_[2], $_[3], $_[0], $_[1]));
  }
  return @answer;
}

sub try_powers_oneway {
  return if ($_[1] =~ /pow$/);   # since "a b pow c pow" 
                                 # is the same as "a b c prod2x pow"
  return if ($_[1] =~ /root$/);  # similar
  return if ($_[1] =~ /pow neg$/);   # similar
  return if ($_[1] =~ /root neg$/);  # similar

  my @answers = ();

  my ($value, $expr);

  my $bad = 0;

  if ($_[0] == 0) {  # base is 0
    # don't raise 0 ^ 0
    $bad = 1 if ($_[2] == 0);
    # since (X/Y) Z pow is the same as (Y/X) Z neg pow
    $bad = 1 if ($_[3] =~ /neg$/ and isfraction($_[1]));

    if (!$bad) {
      $value = 0;
      $expr = join " ", $_[1], $_[3], "pow";
      push @answers, expand_neg_sqrt(1, $value, $expr);

      $value = 0;
      $expr = join " ", $_[1], $_[3], "root";
      push @answers, expand_neg_sqrt(1, $value, $expr);
    }

  } else {

    # since (X/Y) Z pow is the same as (Y/X) Z neg pow
    $bad = 1 if ($_[3] =~ /neg$/ and isfraction($_[1]));

    if (!$bad) {
      $value = raise_power($_[0], $_[2]);
      $expr = join " ", $_[1], $_[3], "pow";
      if ($value ne "nan") {
        push @answers, expand_neg_sqrt(1, $value, $expr);
      }
    }
 
    # roots..
    # don't do 0th roots 
    # don't do roots of negative numbers
    # don't do a root if the power is a fraction,
    # since X (Y/Z) root is the same as X (Z/Y) pow

    if ($_[2] != 0 and $_[0] >= 0 and !isfraction($_[3])) {
      $value = raise_power($_[0], (1/$_[2]));
      $expr = join " ", $_[1], $_[3], "root";
      push @answers, expand_neg_sqrt(1, $value, $expr);
    }

  }

  return @answers;
}

sub raise_power {
  my ($base, $power) = @_;
  if ($power == 0) {
    return 1;
  } elsif (int($power) != $power) {
    return "nan" if ($base < 0);
    return exp((log $base) * $power);
  } elsif ($power > 0 and $power < 50) {
    my $answer = 1;
    for (1..$power) {
      $answer *= $base;
    }
    return $answer;
  } elsif ($power < 0 and $power > -50) {
    my $answer = 1;
    for ($power..(-1)) {
      $answer /= $base;
    }
    return $answer;
  } else {
    return "nan" if ($base < 0);
    return exp((log $base) * $power);
  }
}

sub bycanon {
  return (compar($a, $b));
}

sub compar {
  my @ar = @{$_[0]};
  my @br = @{$_[1]};
  my $answer = scalar(@ar) <=> scalar(@br);
  return $answer if ($answer != 0);
  for (0..$#ar) {
    $answer = $br[$_] <=> $ar[$_];
    return $answer if ($answer != 0);
  }
  return 0;
}

sub canonizenums {
  my @answer = ();
  foreach (@_) {
    my @temp = sort numerically @{$_};
    push @answer, \@temp;
  }
  return @answer;
}

my @manynums = makemanynums(@foo);
my @cmanynums = canonizenums(@manynums);
my @sortednums = sort bycanon(@cmanynums);

my $i = 0;
while ($i < $#sortednums) {
  if (0 == compar($sortednums[$i], $sortednums[$i+1])) {
    splice @sortednums, $i, 1;
  } else {
    $i++;
  }
}

foreach (@sortednums) {
 print STDERR join " ", @{$_}, "\n";
  processnums(@{$_});
}