إدوارد هو مؤسس ورئيس شركة 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.