clepsidru

O clepsidră este un dispozitiv folosit pentru a măsura timpul. Clepsidra este alcatuită din două incinte de sticlă, conectate printr-un tub fin. Una dintre incinte este umplută cu nisip, acesta scurgându-se în cea de-a doua incintă, cu o viteză constantă. Clepsidra poate fi întoarsă, pentru a măsura o altă perioadă de timp.
Arheologii au descoperit un dispozitiv, pe care l-au denumit clepsidru, format din $n$ clepsidre identice, suprapuse, numerotate de la $1$ la $n$, prin care nisipul poate circula de la o clepsidră la alta datorită forței gravitaționale.
Studiind acest obiect, arheologii au constatat că:

• dispozitivul poate fi utilizat atât în pozitia $1$, când clepsidrele sunt în ordinea $1, 2,\dots, n$ cu clepsidra $n$ așezată pe sol, cât și în poziția $2$, cand clepsidrele sunt în ordinea $n, n-1, \dots, 1$ cu clepsidra $1$ așezată pe sol;
• viteza de trecere a nisipului de la o incintă la alta, a aceleiași clepsidre, este de $1$ bob de nisip/secunda, pentru toate clepsidrele, indiferent de poziție;
• trecerea clepsidrului dintr-o poziție în alta presupune răsturnarea acestuia și reașezarea boabelor de nisip;
• timpul de trecere a boabelor de nisip de la o clepsidră la alta este $0$.

Arheologii studiază comportarea clepsidrului realizând două experimente diferite, dupa cum urmează:

1. Se așează clepsidrul în poziția $1$, se introduc în incinta de sus a clepsidrei $1$ un numar $b$ de boabe de nisip și se determină dupa câte secunde vor ajunge toate boabele de nisip in incinta de jos a ultimei clepsidre;
2. Se așează clepsidrul în poziția $1$, se introduc în incinta de sus a clepsidrei $1$ un numar $b$ de boabe de nisip, apoi se așează clepsidrul în $k$ stari consecutive, o stare fiind caracterizată de valorile $S_i$ și $P_i$, ce reprezintă numărul de secunde, respectiv poziția, în care este menținut nemișcat clepsidrul, iar la final se determină numărul de boabe de nisip din incintele fiecărei clepsidre.

Spre exemplu, dacă clepsidrul este format din $n=2$ clepsidre, iar în incinta de sus a primei clepsidre se introduc $b=3$ boabe de nisip, la primul experiment se va obține valoarea $4$. La al doilea experiment se așează clepsidrul în $k=2$ stări, caracterizate prin $S_1=3, P_1=1$; $S_2=1, P_2=2$. Numărul de boabe de nisip din clepsidre va evolua ca în figura ce urmează:

Cerință

Să se scrie un program care citește valorile $n$ si $b$, precum și valorile $k, S_i, P_i$ și calculează valorile obținute de arheologi la realizarea celor două experimente.

Date de intrare

Prima linie a fișierului de intrare clepsidru.in conține două numere naturale nenule $n$ si $b$, separate printr-un singur spațiu, cu semnificația din enunț; a doua linie conține numărul natural nenul $k$ având semnificația din enunț, iar următoarele $k$ linii conțin fiecare câte o pereche de valori $S_i$ și $P_i$, separate printr-un singur spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire clepsidru.out va conține pe prima linie un număr natural ce reprezintă valoarea obținută la primul experiment, iar pe următoarele $n$ linii va conține câte o pereche de numere naturale, separate printr-un singur spațiu, ce reprezintă cantitățile de boabe de nisip din incintele de sus și jos ale celor $n$ clepsidre, scrise în ordinea de la $1$ la $n$ a clepsidrelor, după realizarea celui de-al doilea experiment.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$;
• $1 \leq b \leq 1 \ 000 \ 000 \ 000$;
• $1 \leq k \leq 1 \ 000$;
• $1 \leq S_i \leq 1 \ 000$;
• $P_i$ aparține mulțimii $\{1, 2\}$, $1 ≤ i ≤ k$;
• Pentru rezolvarea corectă a primei cerințe se acordă $25\%$ din punctaj, iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă $75\%$ din punctaj. Acordarea punctajului pentru a doua cerință se face numai dacă in fișierul de ieșire există un răspuns pentru prima cerință, indiferent de corectitudinea acestuia.

Exemplu

clepsidru.in

2 3
2
3 1
1 2

clepsidru.out

4
1 1
0 1

Explicație

• Clepsidrul este format din $n=2$ clepsidre și în incinta de sus a primei clepsidre se introduc $b=3$ boabe de nisip.
• Toate boabele de nisip vor ajunge în incinta de jos a ultimei clepsidre după $4$ secunde.
• Dupa ce clepsidrul este așezat $3$ secunde în pozitia $1$ și $1$ secunda în pozitia $2$, în clepsidre se vor găsi câte $(1,1), (0,1)$ boabe de nisip.