零崎的朋友很多Ⅲ

题目描述

零崎有很多朋友，其中有一个叫jhljx。

jhljx大家很熟悉了，他数学不好也是出了名的，大家都懂。

现在jhljx遇到了矩阵乘法，他当时就懵了。数都数不清的他，矩阵乘法怎么可能会算的清楚呢？虽然零崎觉得还不如让你们来算，不过好歹也要给jhljx个面子，给她留下一个证明自己数学实力的机会。为了减小jhljx的计算量，让他赶快算出不正确答案来（估计他算上几遍都不一定能出一个正确答案），零崎请你们帮助jhljx。

输入

多组输入数据。

每组数据以N开始，表示矩阵链的长度。接下来一行N+1个数表示矩阵的行/列数。

1<=N<=300

输出

对于每组样例，输出一行最少运算次数的方案，每两个矩阵相乘都用“()”括起来，详见样例

如果存在多种解决方案,最终输出结果选取先计算左边的矩阵，详见Hint

输入样例

3
10 30 5 60
3
10 20 5 4

输出样例

((A1A2)A3)
((A1A2)A3)

Hint

对于输入的第二组数据,

如果计算顺序为((A1A2)A3)，结果为10×20×5 + 10×5×4= 1200,

如果计算顺序为A1(A2A3), 结果为20×5×4 + 10×20×4 = 1200

那么输出结果选取第一个