借鉴文章：http://blog.csdn.net/houserabbit/article/details/40429907 、http://sd-invol.github.io/2014/10/22/Anshan-2014-G/

很多最小割问题的核心在于如何建立数学模型。表示智商是硬伤。。唉。。。

最终的决策是种二分模型，用最小割求出最小代价的割边，所以图中的边均表示为扩增路径中代价。

#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <cmath>
using namespace std;
#ifdef __GNUC__
typedef long long LL;
#define opt64(a) printf("%lld",a);
#else
typedef __int64 LL;
#define opt64(a) printf("%I64d",a);
#endif // __GNUC__
//acm.hdu.edu.cn/showproblem.php?pid=5076
const int MAXN = 1<<10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
int n, m;
int thrd[MAXN], u[MAXN];
int LE[MAXN], LEid[MAXN], S[MAXN], Sid[MAXN];
int head[MAXN], cnt;
struct _edge
{
    int v, nxt, w;
    _edge(int vv, int ww, int nnxt):v(vv),w(ww),nxt(nnxt){}
    _edge(){}
}ee[MAXN*1000];
void add(int u, int v, int w)
{
    ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++;
    ee[cnt] = _edge(u,0,head[v]); head[v] = cnt++;
}
int cal(int x)
{
    int res = 0;
    while (x)
    {
        x &= x-1;
        ++res;
    }
    return res;
}
int dis[MAXN], qq[MAXN];
int start, eend;
bool bfs() {
    int l, r, u, v, i;
    memset(dis, -1, sizeof(dis));
    dis[start] = 0;
    qq[0] = start;
    l = 0;
    r = 1;
    while (l < r) {
        u = qq[l++];
        for (i = head[u]; ~i; i = ee[i].nxt) {
            v = ee[i].v;
            if (dis[v] < 0 && ee[i].w > 0) {
                dis[v] = dis[u] + 1;
                if (v == eend)
                    return true;
                qq[r++] = v;
            }
        }
    }
    return false;
}

int dfs(int u, int nowflow) {
    if (u == eend)
        return nowflow;
    int i, v, tmp, res = 0;
    for (i = head[u]; ~i; i = ee[i].nxt) {
        v = ee[i].v;
        if (dis[v] == dis[u] + 1 && ee[i].w > 0) {
            tmp = dfs(v, min(nowflow, ee[i].w));
            nowflow -= tmp;
            ee[i].w -= tmp;
            ee[i ^ 1].w += tmp;
            res += tmp;
            if (!nowflow)
                break;
        }
    }
    if (!nowflow)
        dis[u] = -1;
    return res;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int T, s, t;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        n = 1<<n; m = 1<<m;
        memset(head, -1, sizeof head);
        cnt = 0;
        for (int i = 0; i< n; ++i) scanf("%d", thrd+i);
        for (int i = 0; i< n; ++i) scanf("%d", u+i);
        for (int i = 0; i< n; ++i)
        {
            LE[i] = -1, S[i] = -1;
            for (int j = 0; j< m; ++j)
            {
                int w;
                scanf("%d", &w);
                w += 2333;
                if (j >= thrd[i])
                {
                    if (LE[i] < w) LE[i]=w, LEid[i]=j;
                }
                else
                {
                    if (S[i] < w) S[i] = w, Sid[i] = j;
                }
            }
        }
        s = 2*n, t = s+1;
        start = s; eend = t;
        for (int i = 0; i< n; ++i)
        {
            int k = cal(i);
            if (k & 1)
                add(s, i, S[i]), add(i+n, t, LE[i]);
            else
                add(s, i, LE[i]), add(i+n, t, S[i]);
            add(i, i+n, inf);
            for (int j = i+1; j< n; ++j)
            {
                if (cal(i^j) == 1)
                {
                    if (k & 1)
                        add(i, j+n, u[i]^u[j]);
                    else
                        add(j, i+n, u[i]^u[j]);
                }
            }
        }
        while (bfs())
            dfs(s, inf);
        for (int i = 0; i < n; i++)
        {
            if (i)
                printf(" ");
            int aa = cal(i);
            if (aa & 1) {
                if (dis[i] != -1)
                    printf("%d", Sid[i]);
                else
                    printf("%d", LEid[i]);
            } else {
                if (dis[i] != -1)
                    printf("%d", LEid[i]);
                else
                    printf("%d", Sid[i]);
            }
        }
        printf("\n");
    }
    return 0;
}