레고 벽돌 벽 쌓기

당신은 블록 모형 회사의 설명서 제작 팀에 막 합류했습니다. 선임 디자이너들은 새롭고 흥미로운 블록 모형을 설계하지만, 모든 세부 사항을 직접 확인할 시간은 없습니다. 당신이 할 일은 그들이 만든 부분 모형이 주어진 블록 집합만으로 완전히 조립될 수 있는지 확인하는 것입니다.

가장 흔한 작업은 평평한 직사각형 벽을 만드는 것입니다. 이 작업이 워낙 자주 등장하기 때문에, 확인 과정을 자동화하는 프로그램을 작성할 가치가 있습니다. 프로그램은 폭이 각각 1, 2, 3 단위인 세 종류의 블록 R1, R2, R3만으로 직사각형 벽을 만들 수 있는지 판정해야 합니다.

벽은 블록 규칙을 지켜야 합니다. 즉, 서로 인접한 두 행에서 블록 사이의 세로 이음매가 절대로 같은 위치에 놓이면 안 됩니다. 아래 그림에는 각각 R1 블록 2개와 R2 블록 2개로 만든 2행 3열(행 × 열) 벽 두 개가 있습니다. 왼쪽 벽은 블록 규칙을 지키지만, 오른쪽 벽은 지키지 않습니다(타원이 규칙을 어긴 세로 정렬을 표시합니다).

만들어야 하는 각 벽에 대해, 벽의 크기(블록 단위의 행 수와 열 수)와 디자이너가 이미 고정해 둔 몇몇 블록의 위치가 주어집니다(이 블록들은 벽이 모형의 다른 부분과 연결되는 지점에서 생깁니다). 벽이 넓을 때(열이 10개보다 많을 때) 디자이너는 보통 맨 윗행의 블록 대부분을 고정해 둡니다. 또한 벽을 만드는 데 사용할 수 있는 블록 집합도 함께 주어집니다.

참고: 집합에 있는 블록을 모두 사용할 필요는 없으며, 미리 고정된 블록은 이 집합에서 가져오지 않습니다.

예를 들어, 행 2·열 3에 R1 블록이 고정되어 있는 3행 5열 벽을, R1 5개·R2 5개·R3 5개로 이루어진 집합으로 만든다고 합시다. 한 가지 올바른 해법은 아래 그림처럼 R1 4개, R2 2개, R3 2개를 사용합니다.

입력은 여러 개의 벽을 설명합니다. 각 벽은 행의 수와 열의 수가 적힌 줄로 시작하며, 두 값 모두 1 이상 30 이하입니다. 0 0이 적힌 줄은 입력의 끝을 뜻합니다.

각 벽의 둘째 줄에는 세 개의 수가 있습니다. 각각 사용할 수 있는 R1의 개수, R2의 개수, R3의 개수입니다.

셋째 줄에는 미리 고정된 블록의 개수 N이 있습니다(N은 0일 수 있습니다). 이어서 N개의 줄이 나오며, 각 줄은 세 수 S, R, C로 하나의 고정 블록을 나타냅니다. S는 블록의 크기(1, 2, 또는 3), R과 C는 그 블록의 행과 가장 왼쪽 열입니다. 벽의 왼쪽 위 모서리는 행 1, 열 1입니다.

각 벽마다 한 줄을 출력합니다. 벽을 만들 수 있으면 Yes, 그렇지 않으면 No를 출력합니다.