Паліндромна ДНК#1823

Паліндромна ДНК

10 секунд

256 мегабайтів

Легка

ДНК-послідовність складається з чотирьох можливих нуклеобаз: аденіну, гуаніну, тиміну та цитозину. Кожна база позначається першою літерою своєї назви. У цій задачі нуклеобази мають циклічний порядок: $A$ змінюється на $G$ , потім $T$ , потім $C$ , а далі знову $A$ .

Останні дослідження в геномиці показали, що багато хвороб викликаються тим, що деякі підпослідовності баз не утворюють паліндром. Як провідному досліднику лабораторії ICPC, вам надано ДНК-рядок $S$ та низку підмножин $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t, кожна з яких містить індекси (нуклеобаз) у $S$ . Ваше завдання — перетворити $S$ так, щоб для кожної з цих підмножин обмеження $S$ до $P_{1}, \dots, P_{t}$ P_1, \ldots, P_t було паліндромом. (Обмеження $S$ на підмножину $P = {i_{1}, i_{2}, \dots, i_{k}}$ P = \{i_1, i_2, \ldots, i_k\}, де $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$ , проте дозволено лише три операції над базою:

Залишити її незмінною.
Збільшити її на $1$ у циклічному порядку нуклеобаз (наприклад, $C$ змінити на $A$ ).
Зменшити її на $1$ у циклічному порядку (наприклад, $T$ змінити на $G$ ).

Крім того, через технологічні обмеження не можна змінювати дві бази із сусідніми позиціями в послідовності. Чи можна досягти мети?

Вхідні дані

У першому рядку кожного тесту записано два цілих числа $N$ і $T$ ( $1 \leq N \leq 10000$ 1 \leq N \leq 10\,000, $1 \leq T \leq 6000$ 1 \leq T \leq 6\,000) — довжина послідовності та кількість підмножин. У наступному рядку міститься ДНК-рядок довжини $N$ , який складається лише з літер $A$ , $C$ , $G$ , $T$ .

Далі йдуть $T$ рядків із описами підмножин. Кожен рядок починається з $L :$ , де $L$ ( $0 \leq L \leq N$ 0 \leq L \leq N) — кількість позицій у підмножині, далі йдуть $L$ різних цілих чисел від $0$ до $N - 1$ N - 1 у зростаючому порядку. Підмножини можуть частково або повністю перетинатися.

Порожній рядок відділяє окремі тести. Вхідні дані завершуються рядком 0 0.

Вихідні дані

Для кожного тесту в одному рядку виведіть YES, якщо рішення існує, інакше — NO.

Приклади

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

Один із способів — збільшити перший символ і зменшити останній, отримавши $S^{'} =$ S' = GGTAG. Обмеження $S^{'}$ S' на $P_{1}, P_{2}, P_{3}$ P_1, P_2, P_3 дорівнюють GG, GG, GTG відповідно; усі вони є паліндромами.

Випадок, коли рішення неможливе: $S =$ CATGC і потрібно, щоб підпослідовності на позиціях ${0, 3}$ і ${3, 4}$ були паліндромами. Тут символи $3$ , $0$ і $4$ мають стати $T$ . Але це вимагає змінювати символи $3$ і $4$ , які розташовані підряд, що заборонено.

Приклад 1