A plane partition is a two-dimensional array of nonnegative integers a
i,j (0<=i<n, 0<=j<m) that satisfies
1. 0<=a
i,j<=p
2. a
i,j>=a
i,j+13. a
i,j>=a
i+1,jIn this problem, we add some additional constrains in the following form:
Given x, y, z, there exists some integer k (may be negative) such that a
x+k,y+k=z+k.
Note: For i and j do not satisfy 0<=i<n and 0<=j<m, a
i,j does not exist.
Count how many valid plane partitions are there.
First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.
T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It's possible that there is no valid plane partitions.
T lines. Each line is answer to the corresponding test case.