Yamada, cel mai bun jucător al jocului Forest of Savior, se pregătește pentru a participa într-o bătălie împreună cu coechipierii săi. Pentru a câștiga această luptă, Yamada trebuie să se folosească de diverse obiecte magice pe care le-a obținut de-a lungul timpului. Obiectele cu puteri magice ale lui Yamada sunt de trei tipuri:

• Cărți de vrăji. Dacă personajul are puterea P și citește o carte de putere magică x, atunci puterea personajului va deveni Px.
• Poțiuni. Dacă personajul are puterea P și bea o poțiune de putere magică x, atunci noua lui putere va fi P + x.
• Nestemate. Dacă personajul are puterea P și sparge o piatră prețioasă de putere magică x, atunci noua putere obținută va fi P • x.

Personajul lui are o putere inițială P0, iar fiecare dintre aceste obiecte, după ce este folosit, îi va schimba puterea acestuia în mod ireversibil. De exemplu, dacă personajul lui Yamada începe cu puterea inițială P0 = 3, după folosirea unei poțiuni de putere magică 2 puterea personajului crește și devine egală cu 5. Utilizarea ulterioară a unei cărți de vrăji de putere magică 3 îi va crește personajului puterea la 125. Yamada își poate folosi obiectele în orice ordine, dar fiind copleșit de numărul de moduri în care își poate folosi obiectele, vă cere ajutorul vostru!

Cerința

Ajutați-l pe Yamada să determine:
1. Dintre toate obiectele avute la dispoziție, care este cea mai puternică carte de vrăji, care este cea mai puternică poțiune și care este cea mai puternică nestemată.
2. În ce ordine ar trebui să se folosească de obiectele magice astfel încât, la final, puterea personajului său să fie maximă.
3. Care este puterea maximă pe care o poate atinge personajul său. Fiindcă acest număr poate fi foarte mare, Yamada vrea doar să afle care ar fi restul împărțirii acestui număr la 1.000.000.007.

Date de intrare

Pe prima linie din fișierul de intrare apgreid.in se va află valoarea T, care reprezintă cerința care trebuie rezolvată și poate avea una din valorile 1, 2 sau 3. Pe următoarea linie se află numerele naturale M și P0, reprezentând, în ordine, numărul total de obiecte pe care le are Yamada, respectiv
puterea inițială a personajului său. Pe fiecare dintre următoarele M linii se află descrierea câte unui obiect magic. Linia i (1 ≤ i ≤ M) conține un caracter de tip literă li, care reprezintă tipul obiectului (c – carte de vrăji, p – poțiune și n – nestemată) și un număr xi, reprezentând puterea magică în funcție de tipul obiectului. Valorile li și xi sunt despărțite printr-un spațiu.

Date de ieșire

Pentru cerința T = 1, pe prima linie a fișierului de ieșire apgreid.out se vor afișa trei numere naturale reprezentând, în ordine, cea mai mare puterea magică a unei cărți de vrăji, a unei poțiuni respectiv a unei nestemate.

Pentru cerința T = 2, în fișierul de ieșire se vor afișa pe M linii diferite perechile de caractere și numere, reprezentând tipul și puterea obiectelor în ordinea în care Yamada ar trebui să le folosească pentru a maximiza puterea personajului său. Fiecare linie va conține un caracter l (care va fi unul dintre c, p sau n) separat printr-un spațiu de un număr x care reprezintă puterea magică a obiectului respectiv. Dacă există mai multe moduri de a obține puterea maximă, oricare dintre ele va fi considerat corect.

Pentru cerința T = 3, pe prima linie a fișierului de ieșire se va afișa un număr întreg, reprezentând restul împărțirii puterii maxime pe care o poate atinge personajul lui Yamada la 1.000.000.007.

Restricții și precizări

• 1 ≤ T ≤ 3
• 1 ≤ M ≤ 100.000
• 1 ≤ P0 ≤ 100.000
• li ∊ {c, n, p} pentru orice 1 ≤ i ≤ M și 1 ≤ xi ≤ 1.000.000.000 pentru orice 1 ≤ i ≤ M
• Dacă T = 1, atunci Yamada are cel puțin un obiect magic din fiecare din cele trei tipuri.
• Pentru 19 puncte, T = 1
• Pentru 13 puncte, T = 2, 1 ≤ M ≤ 1000
• Pentru 17 puncte, T = 2
• Pentru 9 puncte, T = 3, 1 ≤ M ≤ 1000, 1 ≤ xi ≤ 1000
• Pentru 11 puncte, T = 3, 1 ≤ xi ≤ 1000
• Pentru 12 puncte, T = 3, 1 ≤ M ≤ 1000
• Pentru 19 puncte, T = 3

Exemplul 1:

apgreid.in

1
6 3
p 1
n 3
c 10
n 2
p 12
p 8

apgreid.out

10 12 3

Exemplul 2:

apgreid.in

2
2 3
c 3
p 2

apgreid.out

p 2
c 3

Exemplul 3:

apgreid.in

32
3
p 2
c 3

apgreid.out

125