평행 진화

2178년, 연구진이 먼 행성에서 외계 생명체를 발견했다. 이 행성에는 종이 하나뿐이고, 그 종에 속한 모든 개체의 유전 구성은 서로 같다.

한 개체의 유전 구성은 뉴클레오타이드를 나열한 배열 하나다. 뉴클레오타이드는 세 종류뿐이고 각각 A(아데닌), C(사이토신), M(무아민)으로 적는다. 한 가설에 따르면 이 행성의 진화는 기존 개체의 유전 배열 어딘가에 새 뉴클레오타이드 하나가 삽입될 때 일어난다. 새 배열이 생존에 유리하면 새 배열의 개체가 옛 배열의 개체를 빠르게 대체한다. 그래서 하나의 진화 경로는 배열을 시간 순으로 늘어놓은 것이고, 앞의 배열은 뒤의 배열의 부분 수열이다. 즉 뒤의 배열에서 글자를 0개 이상 지워 앞의 배열을 만들 수 있다.

연구진은 처음에 오늘날의 종이 뉴클레오타이드가 하나뿐인 아주 단순한 개체에서 이렇게 진화했다고 보았다. 그런데 화석 증거는 다른 곳을 가리킨다. 지금 검증하려는 것은 평행 진화 가설이다. 위와 같은 방식으로 진행된 진화 경로가 둘 있었고, 두 경로 모두 오늘날 이 행성에 사는 하나의 종에 도달했다는 가설이다.

화석에서 찾은 배열은 각각 두 경로 중 정확히 하나에 속해야 한다. 한 경로에 속한 배열을 시간 순으로 늘어놓으면 앞의 배열이 뒤의 배열의 부분 수열이어야 하고, 마지막 배열은 오늘날 사는 종의 배열의 부분 수열이어야 한다. 두 경로 중 하나는 비어 있어도 된다.

수집한 화석 배열이 평행 진화 가설과 모순되지 않는지 판정하라.

첫째 줄에 화석에서 찾은 뉴클레오타이드 배열의 개수 $n$($1 \le n \le 4000$)이 주어진다. 둘째 줄에는 오늘날 이 행성에 사는 종의 뉴클레오타이드 배열이 주어진다. 다음 $n$개 줄에는 화석에서 찾은 배열이 한 줄에 하나씩 주어진다.

모든 뉴클레오타이드 배열은 길이가 1 이상 4000 이하이고 대문자 A, C, M으로만 이루어진다. 오늘날 사는 종의 배열을 포함해 주어지는 배열은 모두 서로 다르다.

모든 화석 배열을 위 조건에 맞게 두 진화 경로에 나눌 수 있으면 possible을, 나눌 수 없으면 impossible을 출력한다.