Budget

A budget proposal is a table (matrix) in which the rows represent different kinds of expenses and the columns represent different sites.

Two things are already known: the total for each kind of expense (the sum of each row) and the total for each site (the sum of each column). In addition, there may be extra constraints on individual entries — for example, that one site needs at least 2000 kronor for food, or that another site will spend no more than 100 kronor on paperclips.

Your task is to determine whether a budget proposal exists that uses only non-negative integer amounts, matches every row total and column total exactly, and satisfies all of the extra constraints.

The first line contains an integer $N$, the number of test cases.

Each test case is given as follows:

• The first line contains two integers $m$ and $n$ ($m \le 200$, $n \le 20$), the number of rows and the number of columns.
• The second line contains $m$ integers: the row sums of the matrix.
• The third line contains $n$ integers: the column sums of the matrix.
• The fourth line contains an integer $c$, the number of constraints.
• Each of the next $c$ lines contains one constraint.

A constraint is written as r c op v. The integers $r$ and $c$ select an entry (or a set of entries) of the matrix: the upper-left corner is 1 1, and 0 means all, so 4 0 means every entry in the fourth row and 0 0 means the entire matrix. op is one of <, =, >, and $v$ is an integer. For example, 1 2 > 5 means the entry in row 1, column 2 must be strictly greater than $5$, and 4 0 = 3 means every entry in the fourth row must equal $3$.

For each test case, print POSSIBLE if there exists a matrix of non-negative integers that satisfies all row sums, all column sums, and every constraint; otherwise print IMPOSSIBLE. Print each answer on its own line.