Gigel incearca sa duca o viata sanatoasa si s-a apucat de alergat, el participa in fiecare an la multe concursuri dar bineinteles cursa lui preferata este Cupa Berii. Cupa berii se desfasoara pe un drum de lungime $N$ Km. Drumul este rectilinu, incepe la pozitia $0$ si se termina la pozitia $N$. Drumul are o banda pe fiecare sens. Exista $M <= 4*N$ marci de bere care sponsorizeaza cursa, fiecare marca va avea o zona in care va oferi bere concurentilor. Pentru fiecare marca se da intervalul $x,y$ in care acea marca ofera bere(daca $x<y$ atunci standul este pe sensul de mers de la stanga la dreapta, altfel standul este pe sensul dreapta stanga). Mai multe standuri se pot suprapune in acelasi interval.
Cupa berii nu este o competitie ca oricare alta, concurentii trebuie sa bea neaparat o bere la fiecare KM in care exista un stand de bere, ei isi pot alege ce fel de bere vor bea daca au mai multe optiuni.

Totusi concurentii nu trebuie sa parcurga musai tot traseul $(0->N->0)$. Ei pot incepe de pe orice pozitie $P1$ (numar natural) si se pot deplasa fie in stanga sau in dreapta catre o alta pozitie $P2$ (numar natural), parcurgand drumul $P1 -> P2$. Ei sunt obligati sa faca insa si drumul de intors, si anume $P2 -> P1$.

Totusi concurentii nu trebuie sa parcurga musai tot traseul $(0->N->0)$. Ei pot incepe de pe orice pozitie $P1$ (numar natural) si trebuie sa se deplaseze IN DREAPTA catre o alta pozitie $P2 > P1$ (numar natural), parcurgand drumul $P1 -> P2$. Ei sunt obligati sa faca insa si drumul de intors, si anume $P2 -> P1$.

Gigel doreste sa participe la cupa berii dar mai are o cerinta un pic speciala. El vrea sa bea numarul maxim de beri din cel putin un brand de bere si mai doreste sa faca acest lucru ori la inceput traseului(P1->...) ori imediat dupa intoarcere(<-P2). Gigel va cere ajutorul si va intreaba in cate moduri isi poate alege traseul.(Analizati exemplul pt clarificari)