Edward est le fondateur et dirigeant de la société Enigma, le fabricant des coffres-forts les plus sûrs du marché. Les coffres-forts Enigma sont protégés par une serrure à combinaison avec un code à 5 chiffres. La serrure se compose de cinq molettes et d'un bouton « ouvrir ». Chaque molette contient tous les chiffres de 0 à 9 (dans cet ordre) ; après le chiffre 9, le chiffre 0 apparaît à nouveau.
Une opération est définie comme la rotation d'une molette quelconque d'une position dans un sens ou dans l'autre, par exemple en changeant le chiffre 9 en 8 ou en 0. La distance entre deux codes est le nombre minimal possible d'opérations nécessaires pour transformer un code saisi en l'autre. Par exemple, la distance entre 38911 et 68000 est $3 + 0 + 1 + 1 + 1 = 6$.
Les fabricants de coffres-forts tiennent des statistiques sur les codes les plus couramment utilisés — on vous donne $n$ de ces codes dans l'ordre du plus populaire au moins populaire. Enigma est fière de sa flexibilité — chaque client peut choisir combien des $n$ codes les plus populaires il souhaite éviter. Edward choisit alors un code qui maximise la plus petite distance aux codes du préfixe sélectionné de la séquence des codes les plus populaires.
Pour chaque $k$ de 1 à $n$, votre tâche consiste à trouver la plus grande distance possible d'un code au code le plus proche parmi les $k$ codes les plus populaires, et à compter combien de codes atteignent une telle distance.
Entrée
La première ligne contient un entier $n$ ($1 \le n \le 99\,999$), désignant le nombre de codes populaires.
Chacune des $n$ lignes suivantes contient une chaîne composée de 5 chiffres 0–9, éventuellement avec des zéros en tête. Ce sont les codes populaires dans l'ordre du plus populaire au moins populaire. Tous les codes sont deux à deux distincts.
Sortie
Affichez $n$ lignes ; la $k$-ième ligne doit contenir deux entiers séparés par un espace — la plus grande distance possible au code le plus proche parmi les $k$ plus populaires, et le nombre de codes ayant cette distance.
Exemples
Entrée 1
3 00000 00001 12345
Sortie 1
25 1 24 2 17 270
Entrée 2
3 12345 23456 67890
Sortie 2
25 1 22 20 12 15270
Note
Pour $k = 1$, la plus grande distance possible au code 00000 est 25, atteinte uniquement par le code 55555.
Pour $k = 2$, la plus grande distance possible au plus proche des codes 00000 et 00001 est 24, atteinte par deux codes : 55555 et 55556. Le premier est à une distance de 24 de 00001, et le second est à une distance de 24 de 00000.
Pour $k = 3$, la plus grande distance possible au plus proche parmi les codes 00000, 00001 et 12345 est 17, atteinte par 270 codes différents, par exemple 55570 et 55580. Le premier est à une distance de 17 de 12345, et le second est à une distance de 17 de 00000.