Эдвард — основатель и глава компании Enigma, производителя самых надёжных сейфов на рынке. Сейфы Enigma защищены кодовым замком с 5-значным кодом. Замок состоит из пяти колёсиков и кнопки «открыть». Каждое колёсико содержит все цифры от 0 до 9 (в таком порядке); после цифры 9 снова идёт цифра 0.

Операцией называется поворот любого колёсика на одну позицию в любом направлении, например изменение цифры 9 на 8 или 0. Расстоянием между двумя кодами называется минимально возможное количество операций, необходимое для превращения одного введённого кода в другой. Например, расстояние между 38911 и 68000 равно $3 + 0 + 1 + 1 + 1 = 6$.

Производители сейфов ведут статистику наиболее часто используемых кодов — вам даны $n$ таких кодов в порядке от самого популярного к наименее популярному. Компания Enigma гордится своей гибкостью — каждый клиент может выбрать, сколько из $n$ самых популярных кодов он хочет избежать. Затем Эдвард выбирает код, который максимизирует наименьшее расстояние до кодов из выбранного префикса последовательности самых популярных кодов.

Для каждого $k$ от 1 до $n$ ваша задача — найти наибольшее возможное расстояние от некоторого кода до ближайшего среди $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. Первый находится на расстоянии 24 от 00001, а второй — на расстоянии 24 от 00000.

При $k = 3$ наибольшее возможное расстояние до ближайшего среди кодов 00000, 00001 и 12345 равно 17 и достигается 270 различными кодами, например 55570 и 55580. Первый находится на расстоянии 17 от 12345, а второй — на расстоянии 17 от 00000.