Театр#6578

Театр

20 секунд

64 мегабайти

Складна

У цьому завданні вам потрібно допомогти власнику театру в Бангкоку. Театр має $R$ рядів, і кожен ряд містить $8$ місць. Деякі з цих місць вже зарезервовані заздалегідь. Тепер у вас є кілька клієнтів, які хочуть подивитися фільм. Існує два типи клієнтів. Перший тип - це ті, хто приходить сам. Інший тип - це ті, хто приходить парою. Природно, пара хоче сидіти поруч один з одним. Також, якщо можливо, кожен одинак і кожна пара не хочуть сидіти поруч або позаду іншої людини. Клієнти будуть дуже раді, якщо ці обмеження можуть бути виконані.

Ваше завдання в цій задачі - визначити, чи це можливо. Зокрема, вам надано місця, які вже зарезервовані, кількість одинаків $S$ та кількість пар $C$ , ви повинні визначити, чи можливо їх розмістити так, щоб усі наступні умови були виконані для всіх одинаків і пар:

Одинак може сидіти лише на незарезервованому місці.
Одинак не сидить поруч з будь-якою особою в тому ж ряду.
Одинак не сидить безпосередньо позаду будь-якої особи в сусідньому ряду перед ним/нею.
Пара може сидіти лише на двох сусідніх незарезервованих місцях в одному ряду.
Пара не сидить поруч з будь-якою особою в тому ж ряду, крім свого партнера.
Пара не сидить безпосередньо позаду будь-якої особи в сусідньому ряду перед ним/нею.

Примітка: особа визначається як інший одинак, інша пара або зарезервоване місце, оскільки там буде хтось сидіти.

Зарезервовані місця не повинні задовольняти жодне з цих обмежень, оскільки клієнт, який зарезервував місця, задоволений сидіти там незалежно від умов.

Вхідні дані

Перша строка введення - це кількість тестових випадків $T \leq 20$ T \leq 20.

Кожен тестовий випадок починається з рядка, що містить три числа, $R$ , $S$ , $C$ ( $1 \leq R \leq 20$ 1 \leq R \leq 20, $0 \leq S \leq 30$ 0 \leq S \leq 30, $0 \leq C \leq 30$ 0 \leq C \leq 30). Наступні $R$ рядків представляють ряди в театрі, починаючи з переднього ряду до заднього. Кожен рядок - це бінарний рядок довжиною $8$ , де $0$ вказує, що місце незарезервоване, а $1$ вказує, що місце зарезервоване.

Вихідні дані

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

Пояснення: можливе розміщення для введення $1$ , яке задовольняє всі вимоги, це (s позначає одинака, c позначає пару)

Можливе розміщення для введення $2$ це:

Немає можливого розміщення, щоб задовольнити всі обмеження для введення $3$ .

Приклади

Приклад 1