Театр
Вам предстоит помочь владельцу театра в Бангкоке. В театре R рядов, и в каждом ряду по 8 мест. Некоторые из этих мест уже зарезервированы заранее. Теперь у вас есть несколько клиентов, которые хотят посмотреть фильм. Существует два типа клиентов: одиночные и пары. Пары, естественно, хотят сидеть рядом друг с другом. Также, если возможно, одиночные и пары не хотят сидеть рядом или позади других людей. Клиенты будут очень довольны, если эти ограничения будут соблюдены.
Ваша задача — определить, возможно ли это. Вам даны места, которые уже зарезервированы, количество одиночных S и количество пар C. Необходимо выяснить, можно ли их разместить так, чтобы все следующие условия были выполнены для всех одиночных и пар:
Одиночный может сидеть только на незарезервированном месте.
Одиночный не сидит рядом с каким-либо человеком в том же ряду.
Одиночный не сидит прямо позади какого-либо человека в соседнем ряду перед ним/ней.
Пара может сидеть только на двух соседних незарезервированных местах в том же ряду.
Пара не сидит рядом с каким-либо человеком в том же ряду, кроме своего партнера.
Пара не сидит прямо позади какого-либо человека в соседнем ряду перед ним/ней.
Примечание: человек определяется как другой одиночный, другая пара или зарезервированное место, так как там будет кто-то сидеть.
Зарезервированные места не должны удовлетворять ни одному из этих ограничений, так как клиент, который зарезервировал места, доволен сидеть там независимо.
Входные данные
Первая строка ввода — это количество тестовых случаев T ≤ 20.
Каждый тестовый случай начинается с строки, содержащей три числа: R, S, C (1 ≤ R ≤ 20, 0 ≤ S ≤ 30, 0 ≤ C ≤ 30). Следующие R строк представляют ряды в театре, начиная с самого переднего ряда до самого заднего. Каждая строка — это двоичная строка длиной 8, где 0 указывает, что место незарезервировано, а 1 указывает, что место зарезервировано.
Выходные данные
Для каждого тестового случая выведите YES, если возможно удовлетворить все требования. В противном случае выведите NO.
Объяснение: Возможное размещение для ввода 1, которое удовлетворяет всем требованиям, это (s обозначает одиночного, c обозначает пару).
Возможное размещение для ввода 2 это:
Нет возможного размещения, чтобы удовлетворить все ограничения для ввода 3.