Edward เป็นผู้ก่อตั้งและหัวหน้าบริษัท Enigma ผู้ผลิตตู้เซฟที่ปลอดภัยที่สุดในตลาด ตู้เซฟของ Enigma ได้รับการปกป้องด้วยกุญแจรหัสผ่านแบบตัวเลข 5 หลัก ตัวล็อกประกอบด้วยวงล้อห้าวงและปุ่ม "เปิด" แต่ละวงล้อมีตัวเลขทั้งหมดตั้งแต่ 0 ถึง 9 (ตามลำดับนี้) หลังจากเลข 9 แล้ว เลข 0 จะปรากฏขึ้นอีกครั้ง

การดำเนินการ (operation) หนึ่งครั้งนิยามว่าเป็นการหมุนวงล้อใดก็ได้หนึ่งตำแหน่งไปในทิศทางใดทิศทางหนึ่ง เช่น การเปลี่ยนเลข 9 เป็น 8 หรือ 0 ระยะห่าง (distance) ระหว่างรหัสสองรหัสคือจำนวนการดำเนินการที่น้อยที่สุดที่เป็นไปได้ในการเปลี่ยนรหัสหนึ่งที่ป้อนไว้ไปเป็นอีกรหัสหนึ่ง ตัวอย่างเช่น ระยะห่างระหว่าง 38911 และ 68000 คือ $3 + 0 + 1 + 1 + 1 = 6$

ผู้ผลิตตู้เซฟได้เก็บสถิติของรหัสที่ถูกใช้บ่อยที่สุด — คุณจะได้รับรหัสดังกล่าวจำนวน $n$ รหัส เรียงตามลำดับจากที่นิยมมากที่สุดไปยังนิยมน้อยที่สุด Enigma ภูมิใจในความยืดหยุ่น — ลูกค้าแต่ละรายสามารถเลือกได้ว่าต้องการหลีกเลี่ยงรหัสที่นิยมที่สุดกี่อันดับแรกจาก $n$ รหัส จากนั้น Edward จะเลือกรหัสที่ทำให้ระยะห่างที่น้อยที่สุดไปยังรหัสในส่วนนำ (prefix) ที่เลือกไว้ของลำดับรหัสยอดนิยมมีค่ามากที่สุด

สำหรับแต่ละ $k$ ตั้งแต่ 1 ถึง $n$ งานของคุณคือการหาระยะห่างที่มากที่สุดที่เป็นไปได้จากรหัสใดๆ ไปยังรหัสที่ใกล้ที่สุดในบรรดา $k$ รหัสที่นิยมที่สุด และนับว่ามีกี่รหัสที่ได้ระยะห่างดังกล่าว

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 99\,999$) แทนจำนวนรหัสยอดนิยม

แต่ละบรรทัดใน $n$ บรรทัดถัดไปประกอบด้วยสตริงที่ประกอบด้วยตัวเลข 0–9 จำนวน 5 หลัก ซึ่งอาจมีเลขศูนย์นำหน้าได้ รหัสเหล่านี้คือรหัสยอดนิยมเรียงตามลำดับจากนิยมมากที่สุดไปน้อยที่สุด รหัสทั้งหมดแตกต่างกันเป็นคู่ๆ

ข้อมูลส่งออก

พิมพ์ $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 รหัสแรกอยู่ห่างจาก 00001 เป็นระยะ 24 และรหัสที่สองอยู่ห่างจาก 00000 เป็นระยะ 24

สำหรับ $k = 3$ ระยะห่างที่มากที่สุดที่เป็นไปได้ไปยังรหัสที่ใกล้ที่สุดในบรรดา 00000, 00001 และ 12345 คือ 17 ซึ่งทำได้โดยรหัสที่แตกต่างกัน 270 รหัส ตัวอย่างเช่น 55570 และ 55580 รหัสแรกอยู่ห่างจาก 12345 เป็นระยะ 17 และรหัสที่สองอยู่ห่างจาก 00000 เป็นระยะ 17