Edward jest założycielem i szefem firmy Enigma, producenta najbezpieczniejszych sejfów na rynku. Sejfy Enigmy są zabezpieczone zamkiem szyfrowym z 5-cyfrowym kodem. Zamek składa się z pięciu kółek oraz przycisku „otwórz”. Każde kółko zawiera wszystkie cyfry od 0 do 9 (w tej kolejności); po cyfrze 9 ponownie pojawia się cyfra 0.

Operację definiujemy jako obrócenie dowolnego kółka o jedną pozycję w dowolnym kierunku, na przykład zmianę cyfry 9 na 8 lub 0. Odległością między dwoma kodami nazywamy minimalną możliwą liczbę operacji potrzebnych do zmiany jednego wpisanego kodu w drugi. Na przykład odległość między 38911 a 68000 wynosi $3 + 0 + 1 + 1 + 1 = 6$.

Producenci sejfów prowadzą statystyki najczęściej używanych kodów — otrzymujesz $n$ takich kodów w kolejności od najbardziej do najmniej popularnego. Enigma szczyci się elastycznością — każdy klient może wybrać, ilu spośród $n$ najpopularniejszych kodów chce uniknąć. Edward wybiera wówczas kod, który maksymalizuje najmniejszą odległość do kodów z wybranego prefiksu ciągu najpopularniejszych kodów.

Dla każdego $k$ od 1 do $n$ Twoim zadaniem jest znalezienie największej możliwej odległości pewnego kodu od najbliższego spośród $k$ najpopularniejszych kodów oraz policzenie, ile kodów osiąga taką odległość.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 99\,999$), oznaczającą liczbę popularnych kodów.

Każdy z kolejnych $n$ wierszy zawiera napis złożony z 5 cyfr 0–9, być może z zerami wiodącymi. Są to popularne kody w kolejności od najbardziej do najmniej popularnego. Wszystkie kody są parami różne.

Wyjście

Wypisz $n$ wierszy; $k$-ty wiersz powinien zawierać dwie liczby całkowite oddzielone spacją — największą możliwą odległość do najbliższego kodu spośród $k$ najpopularniejszych oraz liczbę kodów o tej odległości.

Przykłady

Wejście 1

3
00000
00001
12345

Wyjście 1

25 1
24 2
17 270

Wejście 2

3
12345
23456
67890

Wyjście 2

25 1
22 20
12 15270

Uwaga

Dla $k = 1$ największa możliwa odległość od kodu 00000 wynosi 25 i jest osiągana tylko przez kod 55555.

Dla $k = 2$ największa możliwa odległość do bliższego z kodów 00000 i 00001 wynosi 24 i jest osiągana przez dwa kody: 55555 oraz 55556. Pierwszy jest odległy o 24 od 00001, a drugi o 24 od 00000.

Dla $k = 3$ największa możliwa odległość do najbliższego spośród kodów 00000, 00001 oraz 12345 wynosi 17 i jest osiągana przez 270 różnych kodów, na przykład 55570 oraz 55580. Pierwszy jest odległy o 17 od 12345, a drugi o 17 od 00000.