Problem D
Raðgreining 2

Image from Wikipedia, public domain

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\le n,m\le 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\le s\le n$), the position at which this section starts, followed by the section itself which is a string of length $k$ ($1\le k\le 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

9 3
1 GCAT
3 CTTA
7 AAC

GCATTCAAC

10 2
3 AAAA
8 GGG

GTAAAAAGGG

10 2
3 AAAA
6 GGG

Villa