Паліндромна ДНК
A
G
T
C
A
Послідовність ДНК складається з чотирьох можливих нуклеобаз: аденіну, гуаніну, тиміну та цитозину. Ми будемо позначати кожну з цих баз їхньою початковою літерою. Для наших цілей нуклеобази мають асоційований циклічний "порядок": після A йде G, за яким слідує T, потім C, і знову A. Сучасні дослідження в геноміці виявили, що багато хвороб викликані певними підпослідовностями баз, які не утворюють паліндромну послідовність! Ваше завдання як провідного дослідника в лабораторіях ICPC полягає в тому, щоб взяти рядок ДНК S та серію підмножин P_1,..., P_t індексів до символів (нуклеобаз) у S, і перетворити S так, щоб кожне з обмежень отриманого рядка до P_1,..., P_t було паліндромним. (Обмеження S до підмножини P = {i_1, i_2,..., i_k} індексів, де 0 ≤ i_1 < i_2 <...< i_k < | S|, є рядок S_i1S_i2...S_ik). Можна змінити будь-яку базу S за бажанням, але лише три перетворення можуть бути застосовані до бази:
Залишити її незмінною.
Збільшити її на 1 у циклічному порядку нуклеобаз (наприклад, перетворити C на A).
Зменшити її на 1 (наприклад, перетворити T на G).
Крім того, через обмеження сучасної технології неможливо змінити дві бази на послідовних позиціях у послідовності. Чи досяжна наша мета?
AGTAT
GG
GG
GTG
Наприклад, розглянемо послідовність ДНК. Нумеруйте позиції, починаючи з 0, і припустимо, що у нас є три підмножини P_1 = {1, 4}, P_2 = {0, 1} та P_3 = {0, 2, 4}. Одне з рішень - збільшити перший символ і зменшити останній, отримавши S' = GGTAG. Обмеження S' до P_1, P_2 та P_3 є , і , відповідно; всі вони є паліндромними.
CATGC
T
Один випадок, коли рішення неможливе, це коли рядок є , і ми вимагаємо, щоб підпослідовності, визначені позиціями {0, 3} та {3, 4}, були паліндромними. Тут символи 3, 0 і 4 повинні всі стати . Але це передбачає зміну послідовних символів 3 і 4, що не дозволено.
Вхідні дані
ACGT
Перший рядок кожного тестового випадку містить два цілі числа N та T (1 ≤ N ≤ 10 000, 1 ≤ T ≤ 6 000), довжину послідовності та кількість підмножин для розгляду. Наступний рядок містить послідовність ДНК довжини N, всі символи якої є в . Підмножини описуються наступними T рядками. Кожен рядок починається з "L:", де L (0 ≤ L ≤ N) - це кількість позицій у підмножині, і за ним слідують T різних цілих чисел між 0 та N-1 у зростаючому порядку. Підмножини можуть частково або повністю перекриватися.
Порожній рядок розділяє різні тестові випадки. Вхідний файл завершується рядком, що містить '0 0'.
Вихідні дані
В одному рядку на тестовий випадок надрукуйте 'YES', якщо завдання можна виконати, і 'NO' в іншому випадку.