La atelierul de făcut potcoave lucrează doi muncitori A şi B. Pentru fiecare dintre următoarele n zile se ştie câte potcoave ar putea face fiecare dintre cei doi muncitori: a₁, a₂, …, a_n, şi respectiv b₁, b₂, …, b_n. Atelierul fiind mic, doar un muncitor poate lucra într-o zi, iar schimbarea muncitorului de la o zi la alta nu e o bună soluţie.

Cerinţă

Ştiind că se acceptă o singură dată schimbarea muncitorului, aflaţi numărul maxim de potcoave ce pot fi produse în cele n zile, ce muncitor trebuie sa înceapă munca şi după câte zile e schimbat de celălalt muncitor.

Date de intrare

Fişierul de intrare atelier.in conţine pe prima linie numărul natural n, reprezentând numărul de zile, iar pe următoarele n linii câte două numere întregi separate de câte un spaţiu, în ordine, valorile a_i şi b_i
(i=1,2,…,n) numărul de potcoave pe care le poate face în ziua i muncitorul A şi respectiv muncitorul B.

Date de ieşire

Fişierul de ieşire atelier.out va conţine 3 linii. Prima linie va conţine numărul maxim de potcoave care se pot fabrica în cele n zile. Linia a doua va conţine un caracter A sau B, reprezentând muncitorul care începe munca, iar linia a treia va conţine un număr natural, reprezentând numărul de zile după care se va schimba muncitorul. Dacă sunt mai multe soluţii posibile se va alege soluţia în care muncitorul care începe munca este A, iar dacă sunt mai multe soluţii care încep cu acelaşi muncitor se va alege cea în care A lucrează mai multe zile.

Restricţii

• 3 ≤ n ≤ 10000
• 1 ≤ a_i, b_i ≤ 10000, pentru 1≤i≤n
• Fiecare  muncitor lucrează cel puţin o zi.

Exemple