# Problem D

Raðgreining 2

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. Whoops! You drop all the DNA sections that have
been sequenced onto the floor and now you don’t know how they
are oriented. For example the second section sequenced could
now be `CTTA`.

Given the pieces that have been sequenced, each being either correct or reversed, and where each of those pieces start, write a program that pieces them together to find the a possible 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 a possible DNA
sequence for the virus. If many possible DNA sequences are
possible, any of them can be printed. If no DNA sequence is
feasible, instead simply print `Villa`.

## Stigagjöf

Group |
Points |
Constraints |

1 |
20 |
$n\leq 100$, $m\leq 10$ |

2 |
20 |
$n\leq 25$, $m\leq 100$ |

3 |
20 |
Each section has length exactly $3$ |

4 |
20 |
Each section has length exactly $15$ |

5 |
20 |
No further constraints |

Sample Input 1 | Sample Output 1 |
---|---|

9 3 1 GCAT 3 CTTA 7 AAC |
GCATTCAAC |

Sample Input 2 | Sample Output 2 |
---|---|

10 2 3 AAAA 8 GGG |
TAAAAAAGGG |

Sample Input 3 | Sample Output 3 |
---|---|

10 2 3 AAAA 6 GGG |
Villa |