예산안

예산안은 행이 서로 다른 지출 항목을, 열이 서로 다른 지점(사이트)을 나타내는 표(행렬)이다.

우리는 이미 두 가지를 알고 있다. 각 지출 항목의 합계(각 행의 합)와 각 지점의 합계(각 열의 합)이다. 여기에 더해 개별 칸에 대한 추가 제약이 주어질 수 있다. 예를 들어 어떤 지점은 식비로 최소 2000크로나가 필요하고, 다른 지점은 클립 구입에 100크로나를 넘게 쓰지 않는다는 식이다.

음이 아닌 정수만 사용하면서 모든 행의 합과 열의 합을 정확히 맞추고, 모든 추가 제약을 만족하는 예산안(행렬)이 존재하는지 판정하여라.

첫째 줄에 테스트 케이스의 수 $N$이 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 두 정수 $m$과 $n$이 주어진다 ($m \le 200$, $n \le 20$). 각각 행의 수와 열의 수이다.
• 둘째 줄에 행렬의 각 행의 합을 나타내는 $m$개의 정수가 주어진다.
• 셋째 줄에 행렬의 각 열의 합을 나타내는 $n$개의 정수가 주어진다.
• 넷째 줄에 제약의 수 $c$가 주어진다.
• 다음 $c$개의 줄에 각각 하나의 제약이 주어진다.

제약은 r c op v 형태로 주어진다. 정수 $r$과 $c$는 행렬의 칸(또는 여러 칸)을 가리킨다. 왼쪽 위 칸이 1 1이며, 0은 전체를 뜻한다. 즉 4 0은 넷째 행의 모든 칸을, 0 0은 행렬 전체를 가리킨다. op는 <, =, > 중 하나이고 $v$는 정수이다. 예를 들어 1 2 > 5는 1행 2열의 값이 $5$보다 커야 함을, 4 0 = 3은 넷째 행의 모든 값이 $3$이어야 함을 의미한다.

각 테스트 케이스에 대하여, 모든 행의 합과 열의 합, 그리고 모든 제약을 만족하는 음이 아닌 정수 행렬이 존재하면 POSSIBLE을, 존재하지 않으면 IMPOSSIBLE을 한 줄에 하나씩 출력하여라.