# Adapted from javascript at http://alexle.net/wp-content/uploads/2006/04/matrix.html
# Calculate the best parenthization for matrix multiplication using
# Dynamic Programming approach.
sub find_optimal_chain_for_matrix_multiply ( @rows_cols_interleaved ) {
    my @rows = @rows_cols_interleaved[ 0  ..^ @rows_cols_interleaved.end ];
    my @cols = @rows_cols_interleaved[ 0 ^..  @rows_cols_interleaved.end ];

    my $n = @rows.elems;

    my @matrix   = (^$n).map({ [ 0 xx $n ] });
    my @sequence = (^$n).map({ [ 0 xx $n ] });

    # Run the algorithm
    my $max_int = 2**31 - 1;
    for 1..$n -> $d { # diagonal --> the length of the chain
        for ^($n-$d) -> $i { # sub problems from
            my $j = $i + $d;
            @matrix[$i][$j] = $max_int;
            for $i..^$j -> $k {
                my $m = @matrix[$i  ][$k]
                      + @matrix[$k+1][$j]
                      + @rows[$i] * @cols[$k] * @cols[$j];

                if $m < @matrix[$i][$j] {
                    @matrix[    $i][$j] = $m;
                    @sequence[  $i][$j] = $k;
                }
            }
        }
    }

    # Return a string representing the best parenthesis groupings.
    # Uses @sequence as a global.
    sub parenthesize ( $i, $j ) {
        return "A{$i+1}" if $i >= $j;
        my $sij = @sequence[$i][$j];
        return '('
             ~ parenthesize( $i,     $sij )
             ~ parenthesize( $sij+1, $j   )
             ~ ')';
    }

    say parenthesize( 0, $n-1 );
}

for $*IN.lines {
    my @nums = .split( /\s+/ )».Int;

    if +@nums < 2 {
        say "Input must consist of at least two integers.";
        next;
    }

    find_optimal_chain_for_matrix_multiply( @nums );
}