Restriction Enzyme Map

A researcher is building a computing device out of genetic material. The DNA inside it looks damaged by mutation, so she decided to build a restriction enzyme map to find out which part is damaged.

A restriction enzyme cuts DNA at the positions where a particular short sequence appears. SmaI, for example, recognizes CCCGGG and cuts it in the middle, so it splits ACACAGGGCCCTCAGGTGC into ACACAGGG and CCCTCAGGTGC. There are thousands of restriction enzymes, and each one recognizes its own sequence.

A restriction enzyme map records which enzyme cuts the DNA at which position. The figure below is an example. The DNA in the figure is circular, so the left end and the right end of the sequence are joined.

Figure 1: restriction enzyme map

She cannot read the map directly, but she has a device that measures fragment lengths exactly. The experiment goes like this. First she takes thousands of copies of the DNA, cuts them with enzyme A, and measures the lengths of the fragments. Next she takes thousands of other copies, cuts them with enzyme B, and measures the lengths the same way. Finally she cuts the DNA with A and B together and measures those fragments too. The lengths do not give the map directly, but the three experiments together are often enough to reconstruct it.

Suppose A is SmaI and B is EcoRI.

Figure 2: cutting the DNA by A, by B, and by A and B together

Remember that the DNA is circular. Cutting this DNA of length 20 with A alone gives 12 and 8. Cutting it with B alone gives 20, because there is only one EcoRI site and therefore only one fragment. Cutting it with A and B together produces three fragments of length 8, 6, and 6. The device only tells you whether a fragment of a given length is present, not how many fragments have that length. When several fragments share a length, that value is reported once, so the last experiment gives 8 and 6 instead of 8, 6, and 6.

Here is the formal setting. The DNA is a circle of length $L$, and the positions on it are numbered $0$ to $L-1$. The length of a fragment produced by an enzyme is the distance along the circle between two neighboring cutting sites of that enzyme. If an enzyme has a single cutting site, there is a single fragment and its length is $L$. Each enzyme has at least one cutting site, and the enzyme concentration is high enough that every recognition site is cut.

Given the fragment lengths for enzyme A, for enzyme B, and for A and B together, write a program that computes the restriction enzyme map.

The input consists of several test cases. Each case takes four lines.

The first line holds the length $L$ of the DNA. ($2 \le L \le 20$)

The second line holds the lengths of the fragments cut by enzyme A. The first integer on the line is the number of values that follow, and the remaining integers are the values themselves. The values are separated by one space and are not sorted. When several fragments share a length, that value appears only once.

The third line and the fourth line hold the result for enzyme B and the result for A and B together, in the same format.

Enzyme A and enzyme B recognize different sequences, so no position is cut by both enzymes. A cut made by one enzyme never breaks a recognition sequence of the other. Every case has at least one map that satisfies the given data.

A line holding a single 0 follows the last case.

For each case, print the restriction enzyme map.

The first line holds $n$, the number of cutting sites. The following $n$ lines describe one cutting site each. Each of those lines holds the position of the site and the name of the enzyme that cuts there, separated by a single space, with no other characters. A position is an integer between $0$ and $L-1$, and the sites are printed in increasing order of position.

If several maps satisfy the data, print one with the fewest cutting sites. If several maps still remain, print the lexicographically smallest one. Two maps are compared by their sequences of (position, enzyme) pairs from the front: a smaller position comes first, and at the same position A comes before B. Because the DNA is circular, rotating a whole map keeps it valid, so the map chosen by this rule always has an A site at position 0.

Print a blank line between two consecutive cases.