Edward 是 Enigma 公司的创始人兼负责人，该公司是市面上最安全保险箱的制造商。Enigma 保险箱由一个 5 位密码的密码锁保护。该锁由五个拨轮和一个“打开”按钮组成。每个拨轮包含从 0 到 9 的所有数字（按此顺序）；在数字 9 之后，数字 0 会再次出现。

一次操作定义为将任意一个拨轮向任一方向旋转一个位置，例如将数字 9 变为 8 或 0。两个密码之间的距离是将一个输入的密码转换为另一个密码所需的最小可能操作次数。例如，38911 和 68000 之间的距离是 $3 + 0 + 1 + 1 + 1 = 6$。

保险箱制造商统计了最常用的密码——给你 $n$ 个这样的密码，按受欢迎程度从高到低排序。Enigma 以其灵活性为傲——每个客户都可以选择他们希望避开的前多少个最受欢迎的密码。然后，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。