Palindromik DNT
A
G
T
C
A
DNT ardıcıllığı dörd mümkün nukleobazadan ibarətdir: Adenin, Guanin, Timin və Sitozin. Bu bazalara onların ilk hərfi ilə müraciət edəcəyik. Məqsədimiz üçün nukleobazaların müəyyən bir dövri "sırası" var: A-dan sonra G, sonra T, sonra C və yenidən A gəlir. Genomika sahəsində aparılan son tədqiqatlar göstərir ki, bir çox xəstəliklər müəyyən bazaların alt ardıcıllıqlarının palindromik olmaması səbəbindən yaranır. ICPC laboratoriyalarında aparıcı tədqiqatçı olaraq sizin vəzifəniz DNT sətiri S və S-dəki simvolların (nukleobazaların) indekslərinin P_1,..., P_t alt qruplarını götürmək və S-i elə çevirməkdir ki, nəticə sətirinin P_1,..., P_t məhdudiyyətləri palindromik olsun. (İndekslərin P = {i_1, i_2,..., i_k} alt qrupuna S məhdudiyyəti, burada 0 ≤ i_1 < i_2 <...< i_k < | S|, S_i1S_i2...S_ik sətiridir). İstənilən vaxt S-in istənilən bazasını yoxlamaq mümkündür, lakin baza üzərində yalnız üç çevrilmə tətbiq edilə bilər:
Onu dəyişməz buraxın.
Nukleobazaların dövri sırasını 1 artırın (məsələn,
C
-ni
A
-ya çevirin).
Onu 1 azaldın (məsələn,
T
-ni
G
-yə çevirin).
Bundan əlavə, mövcud texnologiyanın məhdudiyyətləri səbəbindən ardıcıllığın ardıcıl mövqelərindəki iki bazanı dəyişdirmək mümkün deyil. Məqsədimizə nail olmaq mümkündürmü?
AGTAT
GG
GG
GTG
Məsələn, DNT ardıcıllığını nəzərdən keçirin. Mövqeləri 0-dan başlayaraq nömrələyin və üç alt qrupun P_1 = {1, 4}, P_2 = {0, 1} və P_3 = {0, 2, 4} olduğunu fərz edin. Bir həll ilk simvolu artırmaq və sonuncunu azaltmaqdır, nəticədə S' = GGTAG alınır. S'-in P_1, P_2 və P_3-ə məhdudiyyətləri müvafiq olaraq , və -dir; onların hamısı palindromikdir.
CATGC
T
Hər hansı bir həllin mümkün olmadığı bir hal, sətir olduğu və mövqelər {0, 3} və {3, 4} tərəfindən müəyyən edilmiş alt ardıcıllıqların palindromik olmasını tələb etdiyimiz zamandır. Burada 3, 0 və 4 simvollarının hamısı olmalıdır. Lakin bu, ardıcıl 3 və 4 simvollarını dəyişdirməyi tələb edir ki, bu da icazə verilmir.
Giriş verilənləri
ACGT
Hər test halının ilk sətri iki tam ədəd N və T (1 ≤ N ≤ 10 000, 1 ≤ T ≤ 6 000), ardıcıllığın uzunluğu və nəzərə alınacaq alt qrupların sayını ehtiva edir. Növbəti sətir uzunluğu N olan DNT ardıcıllığını ehtiva edir, bütün simvollar . Alt qruplar növbəti T sətirlə təsvir olunur. Hər sətir "L:" ilə başlayır, burada L (0 ≤ L ≤ N) alt qrupdakı mövqelərin sayıdır və artan sırada 0 və N-1 arasında T fərqli tam ədədlə davam edir. Alt qruplar qismən və ya tamamilə üst-üstə düşə bilər.
Fərqli test hallarını boş sətir ayırır. Giriş faylı '0 0' sətiri ilə tamamlanır.
Çıxış verilənləri
Hər test halı üçün bir sətirdə tapşırığın həll edilə biləcəyi halda 'YES' və əks halda 'NO' yazın.