|8 초 (추가 시간 없음)
Eye Ceapee-sea, is a scientist who works for ACM(Abnormal Computing Mechanism). She is developing a new intelligent computing system based on a genetic computing molecules. She believes that it is able to compute NP complete problems in polynomial time so that it will definitely impact the world in the near future.
However, there is a challange before her to complete the extraordinary system. Her system is based on complex molecules, which include genetic materials such as DNA. Therefore, they have a risk of mutation during proliferation. Her system now seems not working presumably because the DNA involved in the system has been crucially damaged. She has decided to make a genetic map called “Restriction enzyme map” to check which part of the DNA is damaged.
Restriction enzyme is an enzyme that cuts a DNA at the position where a particular short DNA sequence appears. For example, SmaI divides ACACAGGGCCCTCAGGTGC into two pieces, ACACAGGG and CCCTCAGGTGC. SmaI recognizes CCCGGG and cuts the sequence at the center. There are thousands types of restriction enzymes, each of which has its own target short sequence(s).
Restriction enzyme map is a map describing the names of restriction enzymes and the positions where the DNA sequence can be cut. An example is shown below. Note that the DNA below is circular (i.e. the left side and the right side of the sequence are connected).
Figure 5: Restriction Enzyme Map
If we can reconstruct the restriction enzyme map from some experimental information, she will compare the map of the original DNA with the reconstructed restriction enzyme map to find out the damaged region of the DNA.
Fortunately, she has a good (maybe expensive!) device which can measure the accurate lengths of the DNA fragments, so she has decided to use this device.
Her strategy is like this. First, she takes thousands of copies of the DNA from her computing system, then cuts them by restriction enzyme A, after which the length of the produced fragments are measured. Next, she takes another thousands of copies of the DNA, which are then cut by another restriction enzyme B, after which the lengths of the fragments are measured in the same manner. She also measures the lengths of the fragments cut by both enzyme A and B together. It is definitely true that those fragment lengths does not directly provide us with the restriction map itself, but we are often able to reconstruct the map using those lengths obtained by these three experiments.
Suppose A = enzyme SmaI and B = enzyme EcoRI.
Figure 6: Cutting DNA by A, B, and A + B
Remind that the DNA is circular. You will get values 12 and 8 from the first experiment, where the DNA is cut by only enzyme A. When only enzyme B is used, the observed length of the fragment is 20, as this sequence has only one cutting site for EcoRI. You may assume at least one site exists for each enzyme. You may also assume the concentration of the enzymes is sufficiently high to cut every recognition site. When both enzyme A and B are used to cut the DNA, three fragments, each of which is 8, 6, 6, respectively in length, are produced. Although the measurement device tells us whether a fragment of specified length is contained in input fragments, it does not tell anything about how many types of fragments have a specified length. When more than one type of fragments is the same in length, only one value is reported, thus, in the last case, you will get only two values, 8 and 6, instead of three values, 8, 6 and 6.
Your task is to write a program to compute the restriction enzyme map from the information about the lengths of fragments cut by enzyme A, enzyme B, and enzyme A + B, respectively.
The input consists of multiple cases. Each case is described by four lines. The first line is the length of the DNA. The lengths of the fragments cut by enzyme A are given in the second line. The first integer in the line represents the number of lengths to be given. The rest of the line consists of several integers each of which represents the length of a fragment. The lengths are separated by one space. Note that these values are not necessarily sorted. The third line and the last line consist of the lengths of the fragments cut by enzyme B and enzyme A + B, respectively. Although we do not know the exact recognition sequence of enzyme A nor B, you may assume that the cleavage at any sites do not interfere each other; in a general case, the cleavage by a certain restriction enzyme may break the recognition sequences of other enzymes, but you do not have to consider the case because Ms. Ceapee-sea guarantees that is not the case. She says that the recognition sequences of enzyme A and B differ, therefore, you may assume that no sites are recognized by both enzyme A and B at once.
The length of each DNA ranges from 2 to 20.
A line containing only ‘0’ follows the last case.
For each case, output the restriction enzyme map. Remind that the input DNA is circular. The first line of the case is n, the number of cutting sites. The following n lines describe the restriction enzyme map. Each line describes one cutting site, comprising of the relative position and the type of the restiction enzyme of the site. The relative position and the type of the restriction enzyme are separated by a single space, and no other characters must be included. The cutting sites should be given in ascending order.
If multiple maps suffice the constraint given by the input, choose one in which the number of cutting sites is not larger than the others. In case there still remains more than one map after applying this rule, you may choose any one of them.
The cases must be separated by a blank line.
6 2 2 4 1 3 2 1 2 10 2 2 4 1 2 2 2 1 0
4 0 A 1 B 2 A 4 B 8 0 A 1 B 2 A 3 B 5 B 6 A 7 B 9 B