서열 분석 1

이미지 출처: 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 서열에서 시작하는 위치가 주어질 때, 이들을 합쳐 바이러스의 DNA 서열을 가능한 한 많이 알아내는 프로그램을 작성한다.

채점

그룹 | 점수 | 제한

1 | 33 | $m=1$

2 | 33 | 모순이 발생하지 않는다

3 | 34 | 추가 제한 없음

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

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

바이러스의 DNA 서열에 있는 문자들을 한 줄에 출력한다. DNA 서열의 특정 문자에 여러 가능성이 있다면 그 문자를 ``?'로 나타낸다. DNA 서열의 특정 문자가 서로 다른 조각에서 서로 다른 값을 갖는 경우처럼 모순이 발생한다면, Villa`이 들어 있는 한 줄만 출력한다.