Palindromik DNT#1823

Palindromik DNT

10 saniyə

256 meqabayt

Asan

Bir DNT ardıcıllığı dörd mümkün nukleotiddən ibarətdir: Adenin, Guanin, Timin və Sitozin. Hər bir baza onun ilk hərfi ilə göstərilir. Bu məsələdə nukleotidlər dövri ardıcıllığa malikdir: $A$ -dan sonra $G$ , sonra $T$ , sonra $C$ və yenidən $A$ gəlir.

Genomika üzrə son tədqiqatlar göstərib ki, bir çox xəstəliklər bəzi baza altardıcıllıqlarının palindrom olmaması səbəbilə yaranır. ICPC laboratoriyalarının aparıcı tədqiqatçısı olaraq sizə DNT sətri $S$ və sətrdəki nukleotidlərin indekslərindən ibarət $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t altçoxluqları verilir. Tapşırığınız budur ki, $S$ sətrini elə dəyişəsiniz ki, bu altçoxluqların hər birinə uyğun $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t indekslərindəki altardıcıllıq palindrom olsun. ( $P = {i_{1}, i_{2}, \dots, i_{k}}$ P = \{i_1, i_2, \ldots, i_k\} altçoxluğuna görə məhdudlaşma, harada $0 \leq i_{1} < i_{2} < \dots < i_{k} < ∣ S ∣$ 0 \leq i_1 < i_2 < \ldots < i_k < |S|, $S_{i_{1}} S_{i_{2}} \dots S_{i_{k}}$ S_{i_1}S_{i_2}\ldots S_{i_k} sətridir.)

Siz $S$ -in istənilən bazasına baxa bilərsiniz, lakin yalnız üç əməliyyat icra oluna bilər:

Olduğu kimi saxlamaq.
Nukleotidlərin dövri ardıcıllığında bir vahid artırmaq (məsələn, $C$ -ni $A$ -ya çevirmək).
Dövri ardıcıllıqla bir vahid azaltmaq (məsələn, $T$ -ni $G$ -yə çevirmək).

Bundan əlavə, texnoloji məhdudiyyətlərə görə ardıcıllıqda iki qonşu baza dəyişdirilə bilməz. Məqsədə çatmaq mümkündürmü?

Giriş

Hər testin birinci sətrində iki tam ədəd $N$ və $T$ ( $1 \leq N \leq 10000$ 1 \leq N \leq 10\,000, $1 \leq T \leq 6000$ 1 \leq T \leq 6\,000) verilir — ardıcıllığın uzunluğu və altçoxluqların sayı. Növbəti sətrdə yalnız $A$ , $C$ , $G$ , $T$ hərflərindən ibarət DNT sətri verilir, uzunluğu $N$ -dir.

Sonra $T$ sətrdə altçoxluqlar təsvir olunur. Hər sətrin əvvəlində $L :$ ardınca $L$ ( $0 \leq L \leq N$ 0 \leq L \leq N) — altçoxluqda mövqe sayı, sonra isə $L$ fərqli və artan sıra ilə $0$ -dan $N - 1$ N-1-ə qədər ədədlər verilir. Altçoxluqlar hissəvi və ya tam kəsişə bilər.

Fərdi testləri bir boş sətr ayırır. Girişin sonunda 0 0 sətri gəlir.

Çıxış

Hər test üçün bir sətrdə əgər həll mümkündürsə YES, mümkün deyilsə NO verin.

Nümunələr

$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\}

Bir həll yolu ondan ibarətdir ki, birinci simvol artırılır, sonuncu isə azalır və nəticədə $S^{'} =$ S' = GGTAG alınır. $S^{'}$ S'-in $P_{1}, P_{2}, P_{3}$ P_1, P_2, P_3-ə uyğun altardıcıllıqları GG, GG, GTG olur; bunların hamısı palindromdur.

Həllin mümkün olmadığı bir nümunə: $S =$ CATGC və mövqelərdə ${0, 3}$ və ${3, 4}$ palindrom olmalıdır. Burada $3$ -cü, $0$ -cı və $4$ -cü simvolların hamısı $T$ olmalıdır. Lakin bu, ardıcıl yerləşən $3$ -cü və $4$ -cü simvolların dəyişməsini tələb edir ki, bu da icazə verilmir.

Nümunə 1