Едвард — засновник і голова компанії 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.