Polygon este un joc pentru un singur jucător care începe pe un poligon cu N vârfuri, precum cel din Figura 1, unde N = 4. Fiecare vârf este etichetat cu un număr întreg, iar fiecare muchie este etichetată fie cu simbolul + (adunare), fie cu simbolul * (produs). Muchiile sunt numerotate de la 1 la N.

La prima mutare, una dintre muchii este eliminată. Mutările ulterioare implică următorii pași:

• alegerea unei muchii E și a celor două extremități V1 și V2 care sunt legate prin E
• înlocuirea lor cu un vârf nou, etichetat cu rezultatul efectuării operației indicate în E pe etichetele lui V1 și V2.

Jocul se termină când nu mai există muchii, iar scorul său este eticheta vârfului unic rămas.

Exemplu de joc: Luați în considerare poligonul din Figura 1. Jucătorul a început prin a îndepărta muchia 3. Efectele sunt prezentate în Figura 2.

Apoi să presupunem că alegem muchia etichetată cu 1. Obținem

Apoi muchia 4 și rămâne:

În final, eliminăm muchia 2 și rămâne un singur nod de etichetă 0. Deci scorul este 0.

Cerința

Scrieți un program care, dat fiind un poligon, calculează cel mai mare scor posibil și listează toate muchiile care, dacă sunt eliminate din prima mutare, pot conduce la un joc cu scorul maxim.

Date de intrare

Fișierul de intrare polygon.in descrie un poligon cu N vârfuri și N muchii. În fișier sunt două linii. Pe prima linie este N. A doua linie conține etichetele muchiilor 1, 2, …, N, intercalate cu etichetele vârfurilor (mai întâi cea a vârfului dintre muchiile 1 și 2, apoi cea a vârfului dintre muchiile 2 și 3 și așa mai departe, până la cea a vârfului dintre muchiile N și 1), toate separate de un spațiu. O etichetă de muchie este fie litera t (reprezentând adunarea), fie litera x (reprezentând produsul).

Date de ieșire

Pe prima linie a fișierului polygon.out programul trebuie să scrie cel mai mare scor care se poate obține pentru poligonul de intrare. Pe a doua linie trebuie să scrie lista tuturor muchiilor care, dacă sunt eliminate la prima mutare, pot duce la un joc cu acel
scor. Muchiile trebuie scrise în ordine crescătoare, separate câte un spațiu.

Restricții și precizări

• 3 ≤ n ≤ 50
• Pentru orice secvență de mutări, valorile etichetelor sunt întregi din intervalul [-32768, 32767].

Exemplu:

polygon.in

4
t -7 t 4 x 2 x 5

polygon.out

33
1 2

Explicație

Datele din fișierul de intrare corespund cu imaginea din prima figură. A doua linie din intrare începe cu eticheta de pe muchia 1.