学步园

#include<stdio.h>
#include<string.h>
#define maxn 504
#define maxm 100003
#define inf 1000000000

int min(int a, int b)
{
    return a < b ? a : b;
}
int max(int a, int b)
{
    return a > b ? a : b;
}

struct E
{
    int v, next, c;
}edge[maxm];

int head[maxn], tot;
int n, m;
int S, T;
int s, t;

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
}

void add(int s, int t, int c)
{
    edge[tot].v = t;
    edge[tot].c = c;
    edge[tot].next = head[s];
    head[s] = tot++;
    edge[tot].v = s;
    edge[tot].c = 0;
    edge[tot].next = head[t];
    head[t] = tot++;
}

int gap[maxn], dis[maxn], cur[maxn], pre[maxn];
int sap(int s, int t, int vs)
{
    int i;
    for(i = 0; i <= vs; i++)
    {
        dis[i] = gap[i] = 0;
        cur[i] = head[i];
    }
    gap[0] = vs;
    int u = pre[s] = s, maxf = 0, aug = inf, v;
    while(dis[s] < vs)
    {
loop:    for(i = cur[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[u] == dis[v] + 1)
             {
                 aug = min(aug, edge[i].c);
                 pre[v] = u;
                 cur[u] = i;
                 u = v;
                 if(u == t)
                 {
                     while(u != s)
                     {
                         u = pre[u];
                         edge[cur[u]].c -= aug;
                         edge[cur[u]^1].c += aug;
                     }
                     maxf += aug;
                     aug = inf;
                 }
                 goto loop;
             }
         }
         int min_d = vs;
         for(i = head[u]; i != -1; i = edge[i].next)
         {
             v = edge[i].v;
             if(edge[i].c > 0 && dis[v] < min_d)
             {
                 min_d = dis[v];
                 cur[u] = i;
             }
         }
         if(!(--gap[dis[u]])) break;
         ++gap[dis[u] = min_d + 1];
         u = pre[u];
    }
    return maxf;
}

int low[maxn][maxn], high[maxn][maxn];
int in[maxn];
bool judge()
{
    int i, j;
    for(i = head[S]; i != -1; i = edge[i].next)
    {
        if(edge[i].c && i % 2 == 0)
            return 0;
    }
    return 1;
}

int ans[maxn][maxn];
void solve()
{
    int i, j;
    for(i = 1; i <= n; i++)
        for(j = head[i]; j != -1; j = edge[j].next)
        {
            int v = edge[j].v;
            ans[i][v-n] = edge[j^1].c += low[i][v-n];
        }
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j < m; j++)
            printf("%d ", ans[i][j]);
        printf("%d\n", ans[i][j]);
    }
}


int main()
{
    int i, j, cas;
    int x, y, z;
    char buf[11];
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d%d", &n, &m);
        for(i = 0; i <= n; i++)
            for(j = 0; j <= m; j++)
                low[i][j] = 0, high[i][j] = inf;
        init();
        s = 0; t = n+m+1; S = t+1; T = S+1;
        memset(in, 0, sizeof(in));
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &z);
            in[i] += z;
            in[s] -= z;
            add(s, i, 0);
        }
        for(i = 1; i <= m; i++)
        {
            scanf("%d", &z);
            in[i+n] -= z;
            in[t] += z;
            add(i+n, t, 0);
        }
        int w;
        scanf("%d", &w);
        bool flag = 1;
        while(w--)
        {
            scanf("%d%d%s%d", &x, &y, buf, &z);
            if(!flag) continue;
            int a, b, aa, bb;
            a = aa = x;
            b = bb = y;
            if(!x) a = 1, aa = n; 
            if(!y) b = 1, bb = m;
            if(buf[0] == '=')
                for(i = a; i <= aa; i++)
                    for(j = b; j <= bb; j++)
                    {
                        if(low[i][j] <= z && high[i][j] >= z)
                            low[i][j] = high[i][j] = z;
                        else flag = 0;
                    }
            if(buf[0] == '>')
            {
                if(z < 0) continue;
                for(i = a; i <= aa; i++)
                    for(j = b; j <= bb; j++)
                    {
                        low[i][j] = max(low[i][j], z+1);
                        if(low[i][j] > high[i][j])
                            flag = 0;
                    }
            }
            if(buf[0] == '<')
            {
                if(z <= 0) flag = 0;
                for(i = a; i <= aa; i++)
                    for(j = b; j <= bb; j++)
                    {
                        high[i][j] = min(high[i][j], z-1);
                        if(low[i][j] > high[i][j])
                            flag  = 0;
                    }
            }
        }
        if(!flag) { printf("IMPOSSIBLE\n"); continue;}
        add(t, s, inf);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
            {
                in[j+n] += low[i][j];
                in[i] -= low[i][j];
                add(i, j+n, high[i][j] - low[i][j]);
            }
        for(i = 0; i <= n+m+1; i++)
        {
            if(in[i] < 0) add(i, T, -in[i]);
            if(in[i] > 0) add(S, i, in[i]);
        }
        sap(S, T, T+1);
        if(!judge())
            printf("IMPOSSIBLE\n");
        else solve();
        if(cas) puts("");
    }
    return 0;
}