Edward 是 Enigma 公司的創辦人兼負責人，該公司是市面上最安全保險箱的製造商。Enigma 保險箱由一個 5 位數密碼的密碼鎖保護。該鎖由五個轉輪和一個「打開」按鈕組成。每個轉輪包含從 0 到 9 的所有數字（按此順序）；在數字 9 之後，數字 0 會再次出現。

一次操作定義為將任意一個轉輪向任一方向旋轉一個位置，例如將數字 9 變為 8 或 0。兩個密碼之間的距離是將一個已輸入的密碼轉換為另一個密碼所需的最小可能操作次數。例如，38911 和 68000 之間的距離是 $3 + 0 + 1 + 1 + 1 = 6$。

保險箱製造商統計了最常用的密碼——給你 $n$ 個這樣的密碼，按熱門程度從高到低排序。Enigma 以其靈活性為傲——每位客戶都可以選擇他們希望避開 $n$ 個最熱門密碼中的前多少個。然後，Edward 會選擇一個密碼，使得該密碼到所選最熱門密碼序列前綴中所有密碼的最小距離最大。

對於從 1 到 $n$ 的每個 $k$，你的任務是找出某個密碼到前 $k$ 個最熱門密碼中最近密碼的最大可能距離，並統計有多少個密碼能達到該距離。

輸入格式

第一行包含一個整數 $n$（$1 \le n \le 99\,999$），表示熱門密碼的數量。

接下來的 $n$ 行，每行包含一個由 5 個 0–9 數字組成的字串，可能含有前導零。這些是按熱門程度從高到低排列的密碼。所有密碼兩兩相異。

輸出格式

輸出 $n$ 行；第 $k$ 行應包含兩個由空格隔開的整數——到前 $k$ 個最熱門密碼中最近密碼的最大可能距離，以及達到該距離的密碼數量。

範例

範例輸入 1

3
00000
00001
12345

範例輸出 1

25 1
24 2
17 270

範例輸入 2

3
12345
23456
67890

範例輸出 2

25 1
22 20
12 15270

說明

對於 $k = 1$，到密碼 00000 的最大可能距離為 25，僅由密碼 55555 達到。

對於 $k = 2$，到密碼 00000 和 00001 中較近者的最大可能距離為 24，由兩個密碼達到：55555 和 55556。第一個密碼距離 00001 為 24，第二個密碼距離 00000 為 24。

對於 $k = 3$，到密碼 00000、00001 和 12345 中最近者的最大可能距離為 17，由 270 個不同的密碼達到，例如 55570 和 55580。第一個密碼距離 12345 為 17，第二個密碼距離 00000 為 17。