Poligono

Poligono è un gioco per un giocatore che comincia con un poligono di N vertici, come quello mostrato nella figura 1, dove N=4. Ogni vertice è etichettato con un intero e ogni lato è etichettato con il simbolo + (addizione) o con il simbolo * (moltiplicazione). I lati sono numerati da 1 a N.

Figura 1. Rappresentazione grafica di un poligono

Alla prima mossa, uno dei lati viene eliminato.

Le mosse successive procedono come segue:

si prende un lato E e i due vertici V₁ e V₂ che sono collegati da E; e
si sostituiscono con un nuovo vertice, etichettato con il risultato dell'operazione indicata in E applicata alle etichette di V₁ e V₂.

Il gioco finisce quando non ci sono più lati, e il suo punteggio è l'etichetta del vertice rimanente.

Esempio di gioco

Si consideri il poligono della figura 1. Il giocatore comincia eliminando il lato 3. L'effetto è mostrato nella figura 2.

Figura 2. Rimozione del lato 3

Dopodiché, il giocatore sceglie il lato 1,

Figura 3. Scelta del lato 1

poi il lato 4,

Figura 4. Scelta del lato 4

e, infine, il lato 2. Il punteggio è 0.

Figura 5. Scelta del lato 2

Il problema

Scrivete un programma che, dato un poligono, calcola il massimo punteggio possibile e lista tutti i lati che, se eliminati alla prima mossa, possono condurre a un gioco con quel punteggio.

Dati in input

Il file POLYGON.IN descrive un poligono con N vertici. Contiene due righe.

Sulla prima riga c'è il numero N.
La seconda riga contiene le etichette dei lati 1, ..., N, alternate con le etichette dei vertici (prima quella del vertice tra i lati 1 e 2, poi quella del vertice tra i lati 2 e 3, e così via, fino a quella del vertice tra i lati N e 1), tutte separate da uno spazio. Le etichette dei lati sono date dalla lettera t (che rappresenta +) o dalla lettera x (che rappresenta *).

Esempio di input

4
t -7 t 4 x 2 x 5

Questo è il file di input per il poligono mostrato nella figura 1. La seconda riga comincia con l'etichetta del lato 1.

Dati in output

Sulla prima riga del file POLYGON.OUT il vostro programma deve scrivere il massimo punteggio che è possibile ottenere con il poligono in input. Sulla seconda riga dovete listare tutti i lati che, se eliminati alla prima mossa, possono condurre a un gioco con quel punteggio. I lati devono essere emessi in ordine crescente, separati da uno spazio.

Esempio di output

33
1 2

Questo è il file di output per il poligono mostrato nella figura 1.

Vincoli

3 <= N <= 50
Per qualunque sequenza di mosse, le etichette dei vertici sono nell'intervallo [-32768,32767].