다각형

$N$개의 꼭짓점을 가진 다각형 위에서 진행하는 1인용 게임이다. 그림 1은 $N = 4$인 경우의 예이다. 각 꼭짓점에는 정수가 하나씩, 각 변에는 +(덧셈) 또는 *(곱셈) 중 하나가 적혀 있다. 변에는 $1$번부터 $N$번까지 번호가 매겨져 있다.

그림 1. 다각형의 예.

첫 번째 이동에서는 변 하나를 제거한다. 이후의 각 이동은 다음 두 단계로 이루어진다.

• 변 $E$와 그 변이 잇는 두 꼭짓점 $V_1$, $V_2$를 고른다.
• 이 둘을 하나의 새 꼭짓점으로 합친다. 새 꼭짓점의 값은 $V_1$과 $V_2$의 값에 변 $E$의 연산을 적용한 결과로 정한다.

변이 하나도 남지 않으면 게임이 끝나고, 마지막에 남은 꼭짓점의 값이 점수가 된다.

예를 들어 그림 1의 다각형을 생각하자. 플레이어가 먼저 3번 변을 제거하면 다음과 같다.

그림 2. 3번 변 제거.

이어서 1번 변을 고르고,

그림 3. 1번 변 선택.

그다음 4번 변을 고르고,

그림 4. 4번 변 선택.

마지막으로 2번 변을 고르면 점수는 0이 된다.

그림 5. 2번 변 선택.

다각형이 주어졌을 때 얻을 수 있는 가장 높은 점수를 구하고, 첫 번째 이동에서 제거했을 때 그 최고 점수를 얻는 게임이 가능한 모든 변을 나열하는 프로그램을 작성하라.

입력은 $N$개의 꼭짓점을 가진 다각형을 나타내며 두 줄로 이루어진다.

첫째 줄에는 정수 $N$이 주어진다.

둘째 줄에는 $1$번부터 $N$번까지의 변의 값과 꼭짓점의 값이 번갈아 가며, 모두 공백 하나로 구분되어 다음 순서로 주어진다: 1번 변의 값, 1번 변과 2번 변 사이 꼭짓점의 값, 2번 변의 값, 2번 변과 3번 변 사이 꼭짓점의 값, …, 마지막으로 $N$번 변의 값과 $N$번 변과 1번 변 사이 꼭짓점의 값.

각 변의 값은 문자 t(+를 의미) 또는 문자 x(*를 의미)이다.

첫째 줄에 주어진 다각형에서 얻을 수 있는 가장 높은 점수를 출력한다.

둘째 줄에는 첫 번째 이동에서 제거했을 때 그 최고 점수를 얻을 수 있는 모든 변을 출력한다. 변은 증가하는 순서로 공백 하나로 구분하여 출력한다.