[CSP-J 2024] 接龙

#include<bits/stdc++.h>
#define int long long
#define N 100010
#define M 200010
#define R 110
#define DEBUG if(debug)
using namespace std;
const bool debug=0;
int n,k,q,dp[R][M],len[N],sum[R][M];
vector<pair<int,int>>voc[N];

void aha()
{
	memset(dp,0,sizeof dp);
	memset(sum,0,sizeof sum);
	
	scanf("%lld%lld%lld",&n,&k,&q);
	
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&len[i]);
		voc[i].clear();
		for(int j=1;j<=len[i];j++)
		{
			int tmp;
			scanf("%lld",&tmp);
			voc[i].push_back({tmp,++tot});		
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(auto tmp:voc[i])
		{
			int num=tmp.first,idx=tmp.second;
			
			if(cnt>0)
			{
				dp[1][idx]++;
				sum[1][num]+=dp[1][idx];
			}
			if(num==1)
			{
				cnt=k;
			}
			cnt--;
			
		}
	}
	
	for(int i=2;i<=R-10;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int cnt=0;
			
			for(int l=0;l<min(len[j],k);l++)
			{
				
				int num=voc[j][l].first,idx=voc[j][l].second;
				
				dp[i][idx]+=cnt;
				sum[i][num]+=dp[i][idx];
				
				cnt+=(sum[i-1][num]-dp[i-1][idx]);
			}
			
			for(int l=k;l<len[j];l++)
			{
				
				int num=voc[j][l-k].first,idx=voc[j][l-k].second;
				
				cnt-=(sum[i-1][num]-dp[i-1][idx]);
				
				
				num=voc[j][l].first,idx=voc[j][l].second;
				
				dp[i][idx]+=cnt;
				sum[i][num]+=dp[i][idx];
				
				cnt+=(sum[i-1][num]-dp[i-1][idx]);
				
			}
		}
	}
	
	int r,c;
	while(q--)
	{
		scanf("%lld%lld",&r,&c);
		DEBUG printf("ANS: ");
		if(sum[r][c])
		{
			printf("1");
		}
		else
		{
			printf("0");
		}
		
		DEBUG printf("%lld",sum[r][c]);
		printf("\n");
	}
	return;
}

signed main()
{
	
	//freopen("chain.in","r",stdin);
	//freopen("chain.out","w",stdout);
	int T;
	scanf("%lld",&T);
	while(T--) aha();
	
	return 0;
}