Andrei şi Tudor au devenit pasionaţi de un nou joc care conţine n cartonaşe, pe fiecare fiind scris un număr natural. La începutul jocului, cărţile se amestecă şi apoi se aşază cu faţa în sus, într-un şir orizontal. Jucătorii aleg alternativ câte o carte de la unul dintre cele două capete ale şirului. Va câştiga cel pentru care suma numerelor de pe cartonaşe este maximă. Sarcina ta este ca, pe baza numerelor de pe cărţi şi a şirului de alegeri făcute de Andrei şi Tudor, să decizi câştigătorul.

Cerinţă

Scrieţi un program care să determine suma obţinută de copilul câştigător şi cine câştigă jocul.

Date de intrare

Fişierul de intrare joc20.in conţine pe prima linie un număr natural n, reprezentând numărul de cartonaşe. Pe următoarea linie se dau cele n numere naturale care se găsesc pe cartonaşe, în ordinea în care ele sunt aşezate în şirul orizontal. Pe a treia linie se dă şirul alegerilor făcute de cei doi copii: 1, dacă se alege un număr de la început (capătul din stânga) şi 2, dacă se alege un număr de la sfârşitul şirului de cartonaşe (capătul din dreapta). Numerele scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieșire

Fişierul joc20.out va conţine o singură linie pe care vor fi scrise două numere naturale separate printr-un spaţiu: suma maximă obţinută de copilul câştigător, urmată de valoarea 1, dacă Andrei câştigă jocul, respectiv de 2 – în cazul în care câştigătorul este Tudor, sau de 0, dacă cei doi copii au obţinut sume egale.

Restricţii

• Andrei începe jocul.
• 1 ≤ n≤ 1000
• n este număr par
• Fiecare cartonaş conţine un număr natural cuprins între 1 şi 1000.
Exemple

joc20.in joc20.out Explicaţii
6
7 3 1 3 8 5
1 1 2 1 1 2 15 1 Sunt 6 cartonaşe cu valorile: 7 3 1 3 8 5. A treia linie din fişierul joc.in arată ce alegeri vor face cei doi copii: Andrei ia un cartonaş de la începutul şirului, apoi Tudor, tot de la început, urmează Andrei, de la sfârşit, apoi Tudor - de la început, dupa aceea, Andrei - de la inceput, şi în cele din urmă Tudor – de la sfârşit.
Andrei începe jocul, alegând prima valoare, adică 7. Şirul rămas este: 3 1 3 8 5. Apoi Tudor alege prima valoare din acest şir, adică 3. Şirul rămas este: 1, 3, 8, 5. Urmează Andrei, care alege ultima valoare, adică 5. Şirul ramas este: 1, 3, 8. Tudor va alege prima valoare, adică 1. Vor rămane două valori: 3 şi 8. Andrei va lua primul număr, adică 3 şi, în sfârşit, Tudor va lua valoarea 8. Andrei obţine 7+3+5=15. Tudor obţine: 3+1+8=12. Evident câştigă Andrei.
4
6 3 4 5
2 1 2 2 9 0 Andrei alege 5, apoi Tudor va lua valoarea 6. Urmează Andrei, care va lua 4, după care Tudor va lua 3. Ambii copii au obţinut aceeaşi sumă egală cu 9.