Edward es el fundador y director de la empresa Enigma, el fabricante de las cajas fuertes más seguras del mercado. Las cajas fuertes Enigma están protegidas por una cerradura de combinación con un código de 5 dígitos. La cerradura consta de cinco ruedas y un botón de «abrir». Cada rueda contiene todos los dígitos del 0 al 9 (en este orden); después del dígito 9, vuelve a aparecer el dígito 0.
Una operación se define como girar cualquier rueda una posición en cualquiera de las dos direcciones, por ejemplo cambiando el dígito 9 a 8 o a 0. La distancia entre dos códigos es el mínimo número posible de operaciones necesarias para cambiar un código introducido por el otro. Por ejemplo, la distancia entre 38911 y 68000 es $3 + 0 + 1 + 1 + 1 = 6$.
Los fabricantes de cajas fuertes llevan estadísticas de los códigos más utilizados — se te dan $n$ de tales códigos en orden del más popular al menos popular. Enigma se enorgullece de su flexibilidad — cada cliente puede elegir cuántos de los $n$ códigos más populares desea evitar. Edward elige entonces un código que maximiza la menor distancia a los códigos del prefijo seleccionado de la secuencia de los códigos más populares.
Para cada $k$ de 1 a $n$, tu tarea es encontrar la mayor distancia posible desde algún código hasta el más cercano entre los $k$ códigos más populares, y contar cuántos códigos alcanzan dicha distancia.
Entrada
La primera línea contiene un entero $n$ ($1 \le n \le 99\,999$), que denota el número de códigos populares.
Cada una de las siguientes $n$ líneas contiene una cadena formada por 5 dígitos 0–9, posiblemente con ceros a la izquierda. Estos son los códigos populares en orden del más popular al menos popular. Todos los códigos son distintos dos a dos.
Salida
Imprime $n$ líneas; la $k$-ésima línea debe contener dos enteros separados por un espacio — la mayor distancia posible al código más cercano entre los $k$ más populares, y el número de códigos con esa distancia.
Ejemplos
Entrada 1
3 00000 00001 12345
Salida 1
25 1 24 2 17 270
Entrada 2
3 12345 23456 67890
Salida 2
25 1 22 20 12 15270
Nota
Para $k = 1$, la mayor distancia posible desde el código 00000 es 25, alcanzada únicamente por el código 55555.
Para $k = 2$, la mayor distancia posible al más cercano de los códigos 00000 y 00001 es 24, alcanzada por dos códigos: 55555 y 55556. El primero está a distancia 24 de 00001, y el segundo está a distancia 24 de 00000.
Para $k = 3$, la mayor distancia posible al más cercano entre los códigos 00000, 00001 y 12345 es 17, alcanzada por 270 códigos diferentes, por ejemplo 55570 y 55580. El primero está a distancia 17 de 12345, y el segundo está a distancia 17 de 00000.