Billing Tables

In telecommunications, calls to different phone numbers may be charged under different rates or billing plans. A phone carrier keeps a billing table that decides which plan applies to each call.

Every phone number has exactly 11 digits. The old billing table has n lines. Each line describes a range of number prefixes written as A - B, followed by a billing plan name. The line matches every phone number whose leading digits fall inside that range. For example, the line 7919 - 921 matches every phone number that begins with 7919, 7920, or 7921.

To find the plan for a call, the table is read from top to bottom and the first matching line decides the plan. If no line matches, the number is invalid and needs no plan. A line may use the special plan name invalid as another way to mark numbers as invalid. The same plan name may appear on several lines that describe very different numbers.

The old table may contain redundant entries, so the carrier wants a cleaner table. The new table is a list of plain prefixes (no ranges), each with a plan name, in which no prefix is a prefix of another prefix in the table. A single dictionary lookup then gives the plan of any phone number. The plan invalid must not appear in the new table — invalid numbers are exactly the numbers with no matching prefix. Among all tables that reproduce the old table's decisions exactly, report one with the fewest lines.

The first line contains one integer n (1 ≤ n ≤ 100) — the number of lines in the old billing table.

Each of the next n lines describes one rule as four space-separated tokens: prefix A, a minus sign -, prefix B, and the billing plan name. Each prefix has 1 to 11 digits and each plan name has 1 to 20 lowercase letters.

Write |A| and |B| for the number of digits in A and B. The prefixes satisfy 1 ≤ |B| ≤ |A| ≤ 11, and the last |B| digits of A, read as a string, are lexicographically less than or equal to B. The rule matches every phone number whose first |A| − |B| digits equal the first |A| − |B| digits of A and whose next |B| digits lie between the last |B| digits of A and B, inclusive.

On the first line print one integer k — the minimum number of lines the new table needs to describe the old table exactly.

Then print k lines giving the new table in lexicographic order of the prefixes. Each line has two space-separated tokens: the prefix (at least one digit) and its billing plan name.

If every phone number is invalid, print just the single number 0.