시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 63 7 6 21.429%

문제

신해빈이 운영하는 영화관은 8개의 좌석이 R줄 만큼 있다. 어떤 좌석은 이미 예약되있으며, 영화관에 들어오는 손님은 총 세 종류이다.

  • 예약하고 온 손님
  • 예약하지 않고 온 솔로
  • 예약하지 않고 온 커플 (너무 당연하지만, 커플은 같이 앉고 싶어한다)

예약하고 온 손님은 그냥 예약한 좌석에 앉으면 된다. 이제 신해빈은 솔로와 커플들을 적절한 좌석에 앉혀야 한다. 그런데 솔로와 커플은 모두 다른 사람의 옆이나 뒤에 앉기를 싫어한다. 이를 최대한 고려하여 각 손님의 좌석을 결정해준다면, 신해빈의 영화관은 매출이 늘어나 순살치킨을 더 많이 먹을 수 있다.

신해빈은 치킨을 먹느라 바빠서 우리가 이 문제를 해결해야한다. 문제의 조건으로 예약된 좌석들의 위치, 솔로의 수 S,  커플 쌍의 수 C가 주어진다.

이제 다음의 조건들 :

  • 솔로는 비예약석에만 앉는다.
  • 솔로는 같은 줄에 있는 어떤 사람 옆에도 앉기 싫다.
  • 솔로는 자신이 앉은 좌석 바로 앞 좌석에 어떤 사람이 앉아 있는게 싫다.
  • 커플은 같은 줄에 같이, 비예약석에 앉아야 한다.
  • 커플은 파트너를 제외하고는 같은 줄에 있는 어떤 사람 옆에도 앉기 싫다.
  • 커플은 자신들이 앉은 좌석 바로 앞 좌석에 어떤 사람이 앉아 있는게 싫다.
  • (바로 앞좌석이라 함은, 바로 앞 줄의 같은 열에 있는 좌석을 말한다.)

위의 조건을 모두 만족시키면서 솔로와 커플을 앉힐 수 있는지 판단해야 한다.

유의 : "어떤 사람"은 예약 손님, 솔로, 커플을 모두 포함한다.

유의 : 예약하고 온 손님은 관대해서 위의 조건들을 안 따진다.

입력

첫째 줄에 테스트 케이스의 수 T (T ≤ 20)가 주어진다.

각 테스트 케이스마다 첫째 줄에 세 정수 R, S, C(1 ≤ R ≤ 20, 0 ≤ S ≤ 30, 0 ≤ C ≤ 30)가 주어지고, 그 다음 R개의 줄은 영화관 가장 앞쪽에 있는 좌석줄부터 시작하여 가장 뒤쪽에 있는 좌석줄과 대응된다. 각 줄은 길이 8의 바이너리 문자열인데, 0은 비예약석을 1은 예약석을 의미한다.

출력

각 테스트 케이스마다 명시한 조건들을 모두 만족시킬 수 있으면 "YES" 아니면 "NO"를 출력한다.

예제 입력

3
3 5 1
00000000
01111100
00000000
2 4 1
00000000
10011000
2 5 1
00000000
10011000

예제 출력

YES
YES
NO

힌트