אדוורד הוא המייסד והעומד בראש חברת 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.