POLSKI SPOJ

Na stole bilardowym ułożonych jest n rzędów bil w kształt trójkąta. Oznaczmy każdą bilę numerem rzędu oraz jej pozycją w tym rzędzie. Układ dla przykładowego n = 5 wygląda następująco:

(1,1)
(2,1) (2,2)
(3,1) (3,2) (3,3)
(4,1) (4,2) (4,3) (4,4)
(5,1) (5,2) (5,3) (5,4) (5,5)

Bilą brzegową nazwiemy bilę znajdującą się na pierwszej lub ostatniej pozycji w danym rzędzie. Bile brzegowe numerowane są w kolejności ich występowania od strony lewej do prawej. Oznacza to, że dla naszego przykładu bila (5,1) ma numer 1, (4,1) ma numer 2, ..., (5,5) ma numer 9.

Przy stole znajduje się q zawodników, każdy z nich wykona jedno uderzenie w pozycję, na której znajduje się wybrana wcześniej bila brzegowa. Zawodnik wykona uderzenie w wybrane miejsce nawet jeżeli ktoś już wcześniej w nie celował. W momencie uderzenia usuwane są wszystkie bile z trójkąta, którego górnym wierzchołkiem jest wybrana bila brzegowa, zaś dolne wierzchołki znajdują się w ostatnim rzędzie. Przykładowo dla powyższego trójkąta po uderzeniu w bilę (3,3) oprócz niej samej usunięte zostaną również kule: (4,3) (4,4) (5,3) (5,4) (5,5)

Twoim zadaniem jest wypisanie ile bil pozostało w trójkącie oraz ile zostało usuniętych po każdym z q uderzeń.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [5;10⁶] i q ∈ [1;2×10⁵] opisane powyżej. W każdej z kolejnych q linii znajduje się dokładnie jedna liczba całkowita b ∈ [1;2×n-1] określająca pozycję (numer bili brzegowej), w którą wykonywane jest kolejne uderzenie.

Wyjście

Dla każdego z q uderzeń należy wypisać w osobnej linii liczbę bil jakie pozostały w trójkącie oraz liczbę bil jakie zostały usunięte po danym ruchu.

Przykład

Wejście

5 6 
1
8
4
5
6
4

Wyjście

14 1
11 3
3 8
0 3
0 0
0 0