Polygon
Polygon er et spil for én spiller. Det starter med en polygon med N hjørner, fx. som på figur 1, hvor N=4. Kanterne er nummereret fra 1 til N. Desuden er hvert hjørne mærket med et heltal og hver kant er mærket med en af regneoperationerne + (addition) og * (multiplikation)

I det første træk fjernes en kant.

Hvert af de følgende træk består af følgende:

  • Vælg en kant E og dermed de to hjørner V1 og V2 som er forbundet med E
  • Erstat disse med et nyt hjørne, mærket med det resultat der fås ved at udføre regneoperationen fra kanten E på tallene som er skrevet på hjørnerne V1 og V2.
Spillet slutter når der ikke er flere kanter, og resultatet er det tal som står på det eneste hjørne som er tilbage.

Eksempel på et spil

Betragt polygonen på figur 1. Spilleren valgte at starte med at fjerne kant nummer 3. Virkningen ses på figur 2. Herefter valgte spilleren kant nummer 1, så kant nummer 4, og endelig kant nummer 2. Resultatet af spillet er 0.

Figur 1. Grafisk repræsentation af en polygon

Figur 2. Kant nummer 3 er fjernet
Figur 3. Kant nummer 1 er valgt

Figur 4. Kant nummer 4 er valgt
Figur 5. Kant nummer 2 er valgt
Opgave

Skriv et program som, givet en polygon, beregner det størst mulige resultat og opregner alle de kanter, som kan være første træk i et spil der fører til dette resultat.

Input data

Filen POLYGON.IN beskriver en polygon med N hjørner. Filen består af to linjer. Den første linje indeholder tallet N. Den anden linje indeholder regneoperationerne som er skrevet på kanterne 1,…,N , adskilt af tallene på hjørnerne (først tallet på hjørnet mellem kant 1 og kant 2, så det mellem kant 2 og 3, osv. indtil hjørnet mellem kanterne N og 1), alle elementer separeret af ét mellemrum. Regneoperationerne på kanterne repræsenteres ved enten bogstavet t (som repræsenterer +) eller bogstavet x (som repræsenterer *).

Eksempel på input

4
t -7 t 4 x 2 x 5

Denne inputfil beskriver polygonen i figur 1. Filens anden linje starter med regneoperationen på kant nummer 1.

 Output data

Den første linje skal indeholde det største resultat man kan opnå for input-polygonen.

Den anden linje skal indeholde alle de alle de kanter, som kan være første træk i et spil der fører til dette resultat. Kanterne skal stå i voksende rækkefølge, adskilt af ét mellemrum.

Eksempel på output

33
1 2

Dette er den korrekte outputfil til figur 1.
 

Begrænsninger

3 £ N £ 50

For enhver serie af træk vil hjørnetallene ligge i intervallet [-32768,32767].