Problem
Das Rufnummernsystem in Russland ist wie folgt aufgebaut. Alle Telefonnummern haben die gleiche Länge von — M Ziffern. Die Nummer besteht aus zwei Teilen: Die ersten Ziffern der Nummer bilden den Ortscode, die anderen Ziffern bestimmen die Nummer des Teilnehmers innerhalb dieser Stadt.
Während der Entwicklung des Netzwerks ändern sich die Codes der Städte regelmäßig, wobei die Codes der verschiedenen Städte notwendigerweise unterschiedlich sind. Ansonsten können die Codes völlig willkürlich sein, auch wenn der Code einer Stadt der Anfang einer anderen ist (zum Beispiel der Code von Nischni Nowgorod 831 und der Code von Sarow 83130) usw. Wenn die Codes mehrerer Städte der Anfang einer M-stelligen Nummer eines Teilnehmers sind, wird der Stadtcode dieser Nummer als der längste dieser Codes angesehen. Wenn es also nur vier Städte gibt: Nischni Nowgorod, Balachna, Dzerzhinsk und Sarow mit den Codes 831, 83144, 8313 und 83130 und M = 9, dann: Telefone 831123456 und 831412345, Telefone von Nischni Nowgorod, 831312345, Telefon von Dzerzhinsk, 831301234 und 831441234, und Telefone von Sarow.
Bei dieser Aufgabe werden wir die verschiedenen anderen Einschränkungen für Telefonnummern, die in Wirklichkeit existieren, nicht berücksichtigen (zum Beispiel kann in Wirklichkeit keine Telefonnummer in einer Stadt mit 03 beginnen, da es sich um ein Notruftelefon handelt). Wir gehen davon aus, dass jede der 10M möglichen M-Ziffern eine gültige Telefonnummer ist.
Eine nicht triviale Aufgabe ist es, zu bestimmen, wie viele Telefonnummern in jeder Stadt ausgegeben werden können. Im obigen Beispiel können beispielsweise 10 000 Telefonnummern (alle vierstelligen Nummern) in Balahna und Sarow ausgegeben werden, 90.000 Telefonnummern können in Dzerzhinsk ausgegeben werden, alle fünfstelligen Telefonnummern außer den mit Null beginnenden Nummern, und 890 000 Nummern können in Nischni Nowgorod ausgegeben werden, alle sechsstelligen Nummern, außer denen, die mit der Ziffer 3 beginnen, sowie die Sequenz 44.
Schreiben Sie ein Programm, das diese Aufgabe für einen beliebigen Satz von Stadtcodes löst.
Eingabe
Die erste Zeile der Eingabedatei enthält zwei Zahlen N und M — Anzahl der Städte und die Länge der vollständigen Telefonnummer (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 9). Es folgen N Zeilen, von denen jede den Code der nächsten Stadt und den Namen der Stadt enthält, zwischen denen sich genau ein Leerzeichen befindet. Der Name der Stadt besteht nur aus Großbuchstaben und kleinen lateinischen Buchstaben und überschreitet nicht die Länge von 20 Zeichen. Es wird garantiert, dass in jeder dieser Zeilen der Eingabedatei genau ein Leerzeichen zwischen dem Stadtcode und dem Namen der Datei vorhanden ist.
Die Städte in der Eingabedatei sind in alphabetischer Reihenfolge der Codes sortiert. Es ist garantiert, dass keine zwei Codes und keine zwei Stadtnamen übereinstimmen.
Ausgabe
Geben Sie N Zeilen in die Ausgabedatei aus. Geben Sie in jeder Zeile den Namen der Stadt und die Anzahl der Telefonnummern ein, die in dieser Stadt ausgegeben werden können. Trennen Sie den Namen der Stadt und die Anzahl der Nummern durch mindestens ein Leerzeichen. Sie können auch zusätzliche Leerzeichen am Anfang und Ende jeder Zeile ausgeben. sie werden ignoriert.
Städte können in beliebiger Reihenfolge angezeigt werden.
|
Eingabe |
Ausgabe |
|
4 9
831 NizhnyNovgorod
8313 Dzerzhinsk
83130 Sarov
83144 Balakhna
|
Sarov 10000
Dzerzhinsk 90000
Balakhna 10000
NizhnyNovgorod 890000
|