서열 분석 2

Wikipedia에서 가져온 이미지, 퍼블릭 도메인

당신은 코로나바이러스로 더 잘 알려진 2019-nCoV 바이러스의 유전체를 서열 분석하는 연구소에서 일한다. 서열 분석을 통해 바이러스의 DNA 서열이 어떻게 생겼는지 알아내는데, 바이러스의 DNA 서열은 길이가 $n$이고 문자 G, T, A, C로 이루어진 문자열이다.

당신의 연구소에서 사용하는 서열 분석 방법으로는 한 번에 DNA 서열의 작은 조각 하나만 알아낼 수 있다. 예를 들어 바이러스의 DNA 서열 길이가 $6$라면, 이 방법으로 바이러스의 DNA 서열에서 문자 $1$부터 문자 $4$까지의 DNA 조각을 분석하고, 이어서 바이러스의 DNA 서열에서 문자 $3$부터 문자 $6$까지의 DNA 조각을 분석할 수 있다. 첫 번째 분석에서 DNA 조각 GCAT을 얻고 두 번째 분석에서 DNA 조각 ATTC을 얻었다면, 바이러스의 DNA 서열이 실제로 GCATTC임을 추론할 수 있다.

이러한 방식으로 바이러스의 DNA 서열에서 서로 다른 위치에서 시작하는 여러 조각의 서열 분석을 마쳤으며, 이제 남은 일은 조각들을 합쳐 바이러스의 전체 DNA 서열을 알아내는 것뿐이다. 그런데 이런! 분석을 마친 DNA 조각을 모두 바닥에 떨어뜨려서, 이제 각 조각이 어느 방향을 향하는지 알 수 없다. 예를 들어 위의 두 번째 조각은 CTTA이 되었을 수도 있다.

분석을 마친 조각들이 정방향 또는 역방향으로 주어지고 각 조각이 바이러스의 DNA 서열에서 시작하는 위치가 주어질 때, 이들을 합쳐 가능한 바이러스의 DNA 서열 하나를 찾는 프로그램을 작성한다.

채점

그룹 | 점수 | 제한

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

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

3 | 20 | 각 조각의 길이는 정확히 $3$이다

4 | 20 | 각 조각의 길이는 정확히 $15$이다

5 | 20 | 추가 제한 없음

입력의 첫째 줄에는 정수 $n$과 $m$ ($1 \leq n, m \leq 500$)이 주어진다. 각각 바이러스의 DNA 서열 길이와 서열 분석을 마친 조각의 개수이다.

이어서 서열 분석을 마친 각 조각에 대해 한 줄씩, 총 $m$개의 줄이 주어진다. 각 줄은 정수 $s$ ($1 \leq s \leq n$)로 시작하며, 이는 이 조각이 바이러스의 DNA 서열에서 시작하는 위치이다. 그 뒤에는 조각 자체가 주어지며, 이는 길이가 $k$ ($1\leq k \leq n-s+1$)이고 문자 G, T, A, C로 이루어진 문자열이다.

가능한 바이러스의 DNA 서열 하나를 이루는 문자들을 한 줄에 출력한다. 가능한 DNA 서열이 여러 개라면 그중 아무거나 출력해도 된다. 가능한 DNA 서열이 없다면 Villa만 포함하는 한 줄을 출력한다.