#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define int long long

using namespace std;

const int MAXN=5e5+5;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

int t,s,k,n,a[MAXN],sum[MAXN];

struct node{

	int l,r;

	friend bool operator < (node x,node y){

		return x.l==y.l?x.r<y.r:x.l<y.l;

	}

}lim[MAXN];

int tot=0;

signed main(){

	//freopen("test.in","r",stdin);

	//freopen("vio.out","w",stdout);

	t=read();

	while(t--){

		s=read(),k=read(),n=read();

		sum[0]=tot=0;

		bool flag=0;

		for(int i=1;i<=n;++i){

			a[i]=read();

			sum[i]=sum[i-1]+a[i];

			if(i%2==0) continue;

			if(a[i]>=k) flag=1;

			int p=(sum[i-1]+1)%k;

			int q=sum[i]%k;

			if(a[i]-1==q-p){

				lim[++tot]=(node){p,q};

			}

			else{

				lim[++tot]=(node){p,k-1};

				lim[++tot]=(node){0,q};

			}

		}

		if(flag){

			puts("NIE");

			continue;

		}

		sort(lim+1,lim+tot+1);

		int mn=0x7fffffffffffff,mx=0;

		for(int i=1;i<=tot;++i){

			//cout<<lim[i].l<<' '<<lim[i].r<<endl;

			mn=min(mn,lim[i].l);

			mx=max(mx,lim[i].r);

		}

		lim[++tot]=(node){k,k};

		flag=0;

		int i=1;

		int l=0,r=0;

		while(i<=tot){

			while(i<=tot&&l<=lim[i].l&&lim[i].l<=r){

				r=max(r,lim[i].r);

				++i;

			}

			if(lim[i].l-r-1>=s){

				flag=1;

				break;

			}else{

				l=lim[i].l,r=lim[i].r;

				++i;

			}

		}

		if(mn+k-mx-1>=s) flag=1;

		if(s>k) flag=0;

		if(flag) puts("TAK");

		else puts("NIE");

	}

	return 0;

}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN=4e5+5;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

int n,m,a[MAXN],b[MAXN],ans[MAXN],id[MAXN];

int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;

void add(int u,int v){

	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

}

int root[MAXN],tot=0;

struct node{

	int ls,rs,mx,id;

}tr[MAXN*40];

int update(int k){

	if(tr[tr[k].ls].mx>=tr[tr[k].rs].mx) tr[k].mx=tr[tr[k].ls].mx,tr[k].id=tr[tr[k].ls].id;

	else tr[k].mx=tr[tr[k].rs].mx,tr[k].id=tr[tr[k].rs].id;

}

void insert(int &k,int l,int r,int pos,int val){

	if(!k) k=++tot;

	if(l==r){

		tr[k].mx=val;

		tr[k].id=pos;

		return ;

	}

	int mid=(l+r)>>1;

	if(pos<=mid) insert(tr[k].ls,l,mid,pos,val);

	else insert(tr[k].rs,mid+1,r,pos,val);

	update(k);

}

int merge(int x,int y,int l,int r){

	if(!x||!y) return x+y;

	if(l==r){

		tr[x].mx+=tr[y].mx;

		return x;

	}

	int mid=(l+r)>>1;

	tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);

	tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);

	update(x);

	return x;

}

void dfs(int x,int fa){

	for(int i=pre[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa) continue;

		dfs(y,x);

		root[x]=merge(root[x],root[y],1,m);

	}

}

int main(){

	n=read(),m=read();

	for(int i=1,u,v;i<n;++i){

		u=read(),v=read();

		add(u,v),add(v,u);

	}

	for(int i=1;i<=n;++i){

		scanf("%d%d",&a[i],&b[i]);

		insert(root[i],1,m,a[i],b[i]);

	}

	dfs(1,0);

	for(int i=1;i<=n;++i){

		printf("%d %d\n",tr[root[i]].id,tr[root[i]].mx);

	}

	return 0;

}