Edward は、市場で最も安全な金庫を製造する企業 Enigma 社の創設者であり代表です。Enigma の金庫は 5 桁の暗証番号を持つダイヤル錠で保護されています。この錠は 5 つのダイヤル輪と「開く」ボタンで構成されています。各ダイヤル輪には 0 から 9 までのすべての数字がこの順番で並んでおり、数字 9 の次には再び数字 0 が現れます。

1 回の操作とは、任意のダイヤル輪をどちらかの方向に 1 目盛り回転させること（たとえば数字 9 を 8 または 0 に変えること）として定義されます。2 つの暗証番号間の距離とは、入力された一方の暗証番号を他方に変えるために必要な最小操作回数です。たとえば、38911 と 68000 の間の距離は $3 + 0 + 1 + 1 + 1 = 6$ です。

金庫メーカーは最もよく使われる暗証番号の統計を取っており、人気順（最も人気のあるものから順に）に $n$ 個の暗証番号が与えられます。Enigma 社は柔軟性を誇りとしており、各顧客は最も人気のある $n$ 個の暗証番号のうち上位何個を避けたいかを選ぶことができます。すると Edward は、最も人気のある暗証番号の列の選ばれた接頭辞に含まれる暗証番号への最小距離を最大化するような暗証番号を 1 つ選びます。

1 から $n$ までの各 $k$ について、ある暗証番号から上位 $k$ 個の最も人気のある暗証番号のうち最も近いものまでの距離としてあり得る最大値を求め、さらにその距離を達成する暗証番号が何個あるかを数えてください。

入力

1 行目には、人気のある暗証番号の個数を表す整数 $n$ ($1 \le n \le 99\,999$) が与えられます。

続く $n$ 行のそれぞれには、0–9 の 5 個の数字からなる文字列（先頭にゼロを含む場合もあります）が与えられます。これらは最も人気のあるものから順に並んだ暗証番号です。すべての暗証番号は互いに異なります。

出力

$n$ 行出力してください。$k$ 行目には空白で区切られた 2 つの整数 — 上位 $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 であり、2 つの暗証番号 55555 と 55556 によって達成されます。1 つ目は 00001 から距離 24 にあり、2 つ目は 00000 から距離 24 にあります。

$k = 3$ のとき、暗証番号 00000、00001、12345 のうち最も近いものへの最大可能距離は 17 であり、たとえば 55570 や 55580 など 270 個の異なる暗証番号によって達成されます。1 つ目は 12345 から距離 17 にあり、2 つ目は 00000 から距離 17 にあります。