多边形(Polygon)游戏是单人玩的游戏，开始的时候给定一个由N个顶点构成的多边形，每个顶点被赋予一个整数值，而每条边则被赋予一个符号：+(加法运算)或者*(乘法运算)，所有边依次用整数1到N标识。

首次移动(first move)允许将某条边删除；接下来的每次顺序移动包含以下步骤：

1. 选出一条边E，以及由E联接的顶点V1和V2；
2. 用一个新的顶点取代边E及其所联接的两个顶点V1和V2，新顶点的数值是对V1和V2做由E指定的运算得到的结果。

所有边被删除后仅剩一个顶点，游戏结束，得分即为该顶点的数值。

任务

编写一个程序，对于任意给定的多边形，计算可能的最高得分，并且列举出所有首次移动时删除后可得到最高得分的边编号。

输入描述

输入文件POLYGON.IN共2行：

• 第一行是整数N（N ≤ 50）；
• 第二行包含所有边（1,…,N）的符号和相邻边之间的顶点数值：第一个整数值对应与1号、2号边同时相连的顶点；第二个整数对应与2号、3号边同时相连的顶点；…；最后一个数值对应与N号、1号边同时相连的顶点。符号和数值之间由空格分隔，边的符号规则：t对应加法+，x对应乘法*。

输出描述

输出文件POLYGON.OUT共2行：

• 第一行输出输入多边形可得到的最高得分；
• 第二行升序输出所有首次移动删除后可得到最高得分的边编号，编号之间用空格分隔。

输入样例1

4
t -7 t 4 x 2 x 5

输出样例1

33
1 2

提示

样例输入对应4顶点多边形，第二行的第一个字符是1号边的符号。