Problem H
Raðgreining 1
You work at a research lab where the genetic data of the virus 2019-nCoV, better known as COVID, is being sequenced. Using sequencing the structure of its DNA is being analyzed. The DNA sequence of the virus is a string of length $n$ containing only the letters G, T, A and C.
The method your research lab uses can only sequence a small section of the DNA sequence at a time. As an example, if the DNA sequence of the virus is of length $6$, the method could be used to sequence the section starting with letter number $1$ and ending with letter number $4$ in its DNA and then sequence the section starting with letter number $3$ and ending with letter number $6$. If the first sequencing returned GCAT and the second returned ATTC, then it could be deduced that the DNA sequence of the virus is GCATTC.
Using this method various pieces of the DNA sequence of the virus have been sequenced and all that is left to do is piece them together.
Given the pieces that have been sequenced and where each of those pieces start, write a program that pieces them together to find out as much as possible about the DNA sequence of the virus.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 500$), the length of the DNA sequence and the number of sections that have been sequenced.
Then there are $m$ lines, one for each section that has been sequenced. Each of these lines starts with an integer $s$ ($1 \leq s \leq n$), the position at which this section starts, followed by the section itself which is a string of length $k$ ($1 \leq k \leq n - s + 1$) which contains only the letters G, T, A and C.
Output
Print a single line containing the letters of the DNA sequence of the virus. If there are many possibilities for some particular letter in the sequence, denote it by ‘?’. If some data is contradictory, like a letter having different values in different sections, instead simply print a single line containing Villa.
Scoring
|
Group |
Points |
Constraints |
|
1 |
33 |
$m=1$ |
|
2 |
33 |
No contradictions will occur |
|
3 |
34 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
9 3 1 GCAT 3 ATTC 7 AAC |
GCATTCAAC |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 2 3 AAAA 8 GGG |
??AAAA?GGG |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 2 3 AAAA 6 GGG |
Villa |
