Serial Numbers

A manufacturer keeps an ordered table of serial numbers. Each row of the table describes one contiguous range of serial numbers together with two pieces of information: a status code and a transfer code. The table has four columns, in this order: starting serial number, ending serial number, status code, transfer code.

Serial numbers and transfer codes are integers from $1$ to $2^{31}-1$ (where $2^{31}-1 = 2147483647$). A status code is a single uppercase letter. The table is kept sorted in increasing order of serial numbers, ranges never overlap, and for every serial number the table always reflects the most recent data (status code and transfer code) recorded for it.

Suppose 100,000 serial numbers are created with status A and transfer code 1. A single row can represent all of them:

1 100000 A 1

This is far more efficient than storing 100,000 identical rows. The challenge appears when serial numbers inside an already-defined range must receive a different status or transfer code. For example, if serial number 12345 must change to status B, the row above splits into three rows:

1 12344 A 1
12345 12345 B 1
12346 100000 A 1

Next, set the transfer code of every serial number in the range 12000 to 12999 to 2:

1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1

Now change every serial number from 10000 to 100000 to status C and transfer code 2:

1 9999 A 1
10000 100000 C 2

Once created, a serial number is never deleted, but ranges of undefined serial numbers may exist between defined ranges. For instance, setting every serial number from 1000000 to 1999999 to status Z and transfer code 99 gives:

1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99

Finally, the table is always kept with the minimal number of rows: there are never two adjacent rows that a single row could replace. Two adjacent rows may be combined only when they cover a continuous span of serial numbers (the second range starts exactly one after the first range ends) and share the same status code and the same transfer code. For example, this table is not minimal:

1 10 A 1
11 20 A 1
21 30 B 1

because its first two rows can be merged into one:

1 20 A 1
21 30 B 1

The next table is already minimal, because its first two rows have different transfer codes:

1 10 A 1
11 20 A 2
21 30 B 1

and the following one cannot be reduced either, because its first two rows are not continuous (serial number 11 is undefined):

1 10 A 1
12 20 A 1
21 30 B 1

Each transaction sets the status code and transfer code of every serial number in a given range, overwriting whatever those serial numbers held and defining any that were previously undefined. After applying all of a case's transactions in the given order, report the resulting table with the minimal number of rows.

The input contains one or more test cases. Each test case begins with a line containing the name of the case — a string of at most 80 characters. The name END marks the end of the input.

After the name come 1 to 100 transaction lines, each of the form A B S T, where A, B, and T are integers from 1 to $2^{31}-1$, S is an uppercase letter, and A ≤ B. Applied in the given order, each line records a transaction: every serial number from A to B inclusive is set to status code S and transfer code T. A case's list of transactions ends with a line containing only a single 0.

For each test case, print the name of the case on its own line, followed by the resulting minimal-row serial number table after all of the case's transactions have been applied. Each table row lists the starting serial number, the ending serial number, the status code, and the transfer code, separated by single spaces.