#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define inc(i,l,r) for(int i=l;i<=r;i++)

#define dec(i,r,l) for(int i=r;i>=l;i--)

const int N=(<<)+;

const int mod=1e9+;

int n,m;

LL ans[+];

LL cnt[N],dp[N];

int main()

{

    int _; scanf("%d",&_);

    while(_--) {

        scanf("%d%d",&n,&m);

        int task=(<<)-;

        inc(i,,task) cnt[i]=__builtin_popcount(i); // i二进制有多少1

        mem(dp,); dp[]=1LL;

        while(m--) {

            char s[]; int u,v;

            scanf("%s%d%d",s,&u,&v);

            u--, v--;

            int now=(<<u)|(<<v);

            if(s[]=='+') {

                inc(i,,task) if((i&now)==)

                    dp[i|now]=(dp[i|now]+dp[i])%mod;

            } else {

                inc(i,,task) if((i&now)==)

                    dp[i|now]=(dp[i|now]-dp[i]+mod)%mod;

            }

            mem(ans,);

            inc(i,,task)

                ans[cnt[i]]=(ans[cnt[i]]+dp[i])%mod;

            inc(i,,n) {

                printf("%lld",ans[i]);

                if(i==n) printf("\n");

                else printf(" ");

                i++;

            } // 边集为1对应2个点 2对应4个点 3对应6个点

        }

    }

    return ;

}