회문 DNA

DNA 서열은 네 가지 염기 — 아데닌(Adenine), 구아닌(Guanine), 티민(Thymine), 사이토신(Cytosine) — 으로 이루어진 문자열이며, 각각을 첫 글자 A, G, T, C로 나타낸다. 염기에는 순환 순서가 있다. A 다음은 G, G 다음은 T, T 다음은 C, C 다음은 다시 A이다.

최근 유전체 연구에 따르면 어떤 염기 묶음이 회문(앞뒤로 읽어도 같은 문자열)을 이루지 못하면 특정 질병과 연관될 수 있다고 한다. $0$번부터 번호를 매긴 DNA 문자열 $S$와 위치들의 부분집합 $P_1, \dots, P_t$가 주어진다. 각 부분집합에 대해, 그 위치들에 있는 $S$의 문자들이 앞뒤로 읽어도 같도록 $S$를 변형해야 한다. 엄밀히 말하면, 부분집합 $P = {i_1, i_2, \dots, i_k}$ ($0 \le i_1 < i_2 < \dots < i_k < |S|$)에 대한 $S$의 제한은 문자열 $S_{i_1} S_{i_2} \cdots S_{i_k}$이며, 모든 제한이 회문이어야 한다.

어떤 염기든 확인할 수 있지만, 각 염기는 다음 세 가지 방법으로만 바꿀 수 있다.

그대로 둔다.
순환 순서에서 한 칸 앞으로 보낸다 (예: C는 A가 된다).
한 칸 뒤로 보낸다 (예: T는 G가 된다).

또한 기술적 한계 때문에, 서열에서 연속한 두 위치의 염기를 동시에 바꿀 수는 없다. 목표를 달성할 수 있는지 판단하라.

예를 들어 서열 AGTAT에 부분집합 $P_1 = {1, 4}$, $P_2 = {0, 1}$, $P_3 = {0, 2, 4}$가 주어졌다고 하자. 첫 염기를 한 칸 앞으로, 마지막 염기를 한 칸 뒤로 보내면 GGTAG가 되고, 세 제한은 각각 GG, GG, GTG로 모두 회문이며, 바뀐 두 위치($0$번과 $4$번)는 서로 이웃하지 않는다.

반대로 서열 CATGC에 두 부분집합 ${0, 3}$과 ${3, 4}$가 주어지면 해가 없다. 위치 $0$, $3$, $4$가 모두 같은 염기(예: T)로 바뀌어야 하는데, 그러면 연속한 위치 $3$과 $4$를 함께 바꿔야 하므로 규칙에 어긋난다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $T$ ($1 \le N \le 10000$, $1 \le T \le 6000$)가 주어진다. $N$은 서열의 길이, $T$는 부분집합의 개수이다. 다음 줄에는 길이가 $N$이고 문자가 모두 ACGT에 속하는 DNA 서열이 주어진다.

이어지는 $T$개의 줄은 각각 하나의 부분집합을 나타낸다. 각 줄은 L:로 시작하며, $L$ ($0 \le L \le N$)은 부분집합에 속한 위치의 개수이고, 그 뒤에 $0$부터 $N - 1$ 사이의 서로 다른 위치 $L$개가 오름차순으로 이어진다. 부분집합끼리는 일부 또는 전부 겹칠 수 있다.

서로 다른 테스트 케이스는 빈 줄로 구분된다. 입력은 0 0이 적힌 줄로 끝나며, 이 줄은 처리하지 않는다.

문제

입력

출력