Ana şi Bogdan au inventat un nou joc, pe care l-au denumit Strips. Este un joc de strategie, dar şi de antrenare a memoriei, deoarece se joacă pe o tablă care nu este vizibilă pentru cei doi jucători în timpul jocului.
Tabla de joc este o bandă albă de lungime N cm, pe care sunt marcate poziţii de lungime 1 cm. Poziţiile sunt numerotate pe tablă de la 0 la N-1, poziţia 0 fiind marcată la începutul tablei (capătul din stânga), iar poziţia N-1 fiind marcată la sfârşitul tablei (capătul din dreapta).
La începutul jocului fiecare jucător are Nr benzi colorate, toate de aceeaşi lungime L cm. Benzile Anei sunt de culoare roşie, iar benzile lui Bogdan sunt de culoare verde.
Jucătorii mută alternativ, prima la mutare fiind Ana. La o mutare, jucătorul care este la rând alege o poziţie de pe tabla de joc şi dacă poziţia este validă, pe tabla de joc va fi plasată o bandă a jucătorului respectiv, cu capătul din stânga în poziţia aleasă. Dacă poziţia nu este validă, mutarea nu va fi executată, iar jucătorul respectiv va primi 1 punct de penalizare şi pierde banda care ar fi trebuit plasată pe tablă la poziţia respectivă (aceasta este eliminată din joc).
O poziţie este considerată validă, dacă pe tabla de joc poate fi plasată o bandă de lungime L cu capătul din stânga al benzii fixat la poziţia specificată, astfel încât banda să fie integral pe tabla de joc, fără a se suprapune sau a se atinge cu o zonă de pe bandă colorată în culoarea adversarului.
Jocul se termină când jucătorii nu mai au benzi. Fiecare jucător are ca scop să obţină o zonă pe bandă de lungime cât mai mare colorată în culoarea sa. O zonă de pe bandă este constituită din poziţii consecutive, colorate cu aceeaşi culoare.

Cerința

Scrieţi un program care citeşte lungimea tablei de joc, numărul de benzi colorate pe care le are fiecare jucător la începutul jocului, lungimea benzilor, precum şi poziţiile specificate de jucători pe parcursul jocului şi rezolvă următoarele două cerinţe:

• determină numărul de puncte de penalizare pentru fiecare dintre cei doi jucători;
• determină pentru fiecare jucător care este lungimea maximă a unei zone de pe tabla de joc colorată în culoarea sa la sfârşitul jocului.

Date de intrare

Fișierul de intrare strips.in conţine pe prima linie un număr natural C care reprezintă cerinţa care urmează a fi rezolvată (1 sau 2). Pe cea de-a doua linie se află trei numere naturale separate prin câte un spaţiu N Nr L, cu semnificaţia din enunţ. Celelalte linii ale fişierului de intrare conţin în ordine poziţiile specificate de jucători pe parcursul jocului, câte o poziţie pe o linie.

Date de ieșire

Fișierul de ieșire strips.out va conţine o singură linie pe care vor fi scrise două numere naturale rezA rezB, separate printr-un singur spaţiu. Dacă C=1 atunci rezA este numărul de puncte de penalizare acumulate de Ana, iar rezB numărul de puncte de penalizare acumulate de Bogdan. Dacă C=2 atunci rezA este lungimea maximă a unei zone de culoare roşie la sfârşitul jocului, iar rezB este lungimea maximă a unei zone de culoare verde la sfârşitul jocului.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000.000
• 1 ≤ Nr ≤ 50.000
• 1 ≤ L ≤ 20.000
• Se garantează că pentru datele de test, la finalul jocului, pentru fiecare dintre cei doi jucători numărul de zone disjuncte de pe tabla de joc colorate în culoarea jucătorului respectiv este ≤ 5000.
• Poziţiile sunt numere naturale mai mici decât N.
• Fiindcă sunt începători, Ana şi Bogdan încă nu joacă optim.
• Pentru teste valorând 50 de puncte cerinţa este 1.
• Pentru teste valorând 40 de puncte 1 ≤ N ≤ 1.000.000, 1 ≤ L ≤ 1000 şi 1 ≤ Nr ≤ 1000.

Exemplul 1:

strips.in

1
20 4 3
9
15
2
13
5
17
0
12

strips.out

0 1

Exemplul 2:

strips.in

2
20 4 3
9
15
2
13
5
17
0
12

strips.out

8 7

Explicație

Tabla de joc are 20 de cm, poziţiile fiind numerotate de la 0 la 19.
Jucătorii au fiecare câte 4 benzi de lungime 3.
La prima mutare Ana aplică o bandă roşie peste poziţiile 9, 10, 11.
La a doua mutare Bogdan aplică o bandă verde peste poziţiile 15, 16, 17.
La a treia mutare Ana aplică o bandă roşie peste poziţiile 2, 3, 4.
La a patra mutare Bogdan aplică o bandă verde peste poziţiile 13, 14, 15.
La a cincea mutare Ana aplică o bandă roşie peste poziţiile 5, 6, 7.
La a şasea mutare Bogdan aplică o bandă verde peste poziţiile 17, 18, 19.
La a şaptea mutare Ana aplică o bandă roşie peste poziţiile 0, 1, 2.
La a opta mutare Bogdan a ales o poziţie invalidă (pentru că atinge o zonă de culoare roşie), ca urmare mutarea nu va fi executată (va avea 1 punct de penalizare).
Tabla de joc la finalul jocului va arăta astfel: