Palindromic DNA#1823

Palindromic DNA

10 seconds

256 megabytes

Easy

A DNA sequence consists of a series of four possible nucleobases: Adenine, Guanine, Thymine, and Cytosine. We will refer to each base by its initial letter. For our purposes, the nucleobases have an associated cyclic order: $A$ is followed by $G$ , then $T$ , then $C$ , and then again $A$ .

Recent research in genomics has revealed that many diseases are caused by certain subsequences of bases not forming a palindromic sequence! Your mission as a leading researcher at ICPC laboratories is to take a DNA string $S$ and a series of subsets $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t of indices of characters (nucleobases) in $S$ , and transform $S$ so that each of the restrictions of the resulting string to $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t are palindromic. (The restriction of $S$ to a subset $P = {i_{1}, i_{2}, \dots, i_{k}}$ P = \{i_1, i_2, \ldots, i_k\} of indices, where $0 \leq i_{1} < i_{2} < \dots < i_{k} < ∣ S ∣$ 0 \leq i_1 < i_2 < \ldots < i_k < |S|, is the string $S_{i_{1}} S_{i_{2}} \dots S_{i_{k}}$ S_{i_1} S_{i_2} \ldots S_{i_k}.)

It is possible to inspect any base of $S$ at will, but only three transformations can be applied to a base:

Leave it unaltered.
Increase it by $1$ in the cyclic order of nucleobases (e.g., turn $C$ into $A$ ).
Decrease it by $1$ in the cyclic order (e.g., turn $T$ into $G$ ).

Moreover, due to the limitations of current technology, it is impossible to modify two bases in consecutive positions of the sequence. Is our goal achievable?

Input

The first line of each test case contains two integers $N$ and $T$ ( $1 \leq N \leq 10000$ 1 \leq N \leq 10\,000, $1 \leq T \leq 6000$ 1 \leq T \leq 6\,000), the sequence length and number of subsets to consider. The next line contains the DNA sequence of length $N$ , all of whose characters are in $A$ , $C$ , $G$ , $T$ .

The subsets are described by the following $T$ lines. Each line starts by " $L :$ ", where $L$ ( $0 \leq L \leq N$ 0 \leq L \leq N) is the number of positions in the subset, followed by $L$ distinct integers between $0$ and $N - 1$ N-1 in increasing order. Subsets may overlap partially or totally.

A blank line separates different test cases. The input file is terminated by a line containing 0 0.

Output

For each test case, print in a single line YES if the task is solvable and NO otherwise.

Examples

$S =$ AGTAT

$P_{1} = {1, 4}$ P_1 = \{1, 4\}, $P_{2} = {0, 1}$ P_2 = \{0, 1\}, $P_{3} = {0, 2, 4}$ P_3 = \{0, 2, 4\}

One solution is to increase the first character and decrease the last, yielding $S^{'} =$ S' = GGTAG. The restrictions of $S^{'}$ S' to $P_{1}, P_{2}, P_{3}$ P_1, P_2, P_3 are GG, GG, GTG respectively; all are palindromic.

A case where no solution is possible: for $S =$ CATGC and requiring subsequences at positions ${0, 3}$ and ${3, 4}$ to be palindromic. Here, characters $3$ , $0$ , and $4$ would all need to become $T$ . But this entails modifying consecutive characters $3$ and $4$ , which is not allowed.

Example 1