#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<string.h>
#include<set>
using namespace std;
char in[100], out[100];
int n, A[300100];
int ans[10100]; 
int q;
int id[40000], ids=1;
pair<int, int> query[10100];
pair<pair<int, int>,int> order[10100];
int SQRT_N = 550;
string S[10100], ss;
vector<int> V[40000], ans1[10100];
set<string> SET;
void go_query(pair<int, int> pr, pair<int, int> now){
    int i, j;
    int l1 = pr.first;
    int r1 = pr.second;
    int l2 = now.first;
    int r2 = now.second;
    for(i = l1; i<l2; i++){
        if(i>0) id[A[i]+ids]--;
    }
    for(i = r1; i>r2; i--){
        if(i>0) id[A[i]+ids]--;
    }
    for(i = l1-1; i>=l2; i--){
        id[A[i]+ids]++;
    }
    for(i = r1+1; i<=r2; i++){
        id[A[i]+ids]++;
    }
    for(i=ids-1;i>0;i--){
        if(id[i*2]>id[i*2+1]){
            id[i]=id[i*2];
            V[i].clear();
            for(j=0;j<V[i*2].size();j++)V[i].push_back(V[i*2][j]);
        }else if(id[i*2]==id[i*2+1]){
            id[i]=id[i*2+1];
            V[i].clear();
            for(j=0;j<V[i*2].size();j++)V[i].push_back(V[i*2][j]);
            for(j=0;j<V[i*2+1].size();j++)V[i].push_back(V[i*2+1][j]);
        }else{
        	id[i]=id[i*2+1];
        	V[i].clear();
            for(j=0;j<V[i*2+1].size();j++)V[i].push_back(V[i*2+1][j]);
		}
    }
}
int main(){
	int I;
	for(I=11;I<21;I++){
		sprintf(in,".%d.in",I);
        freopen(in,"w",stdout);
		int i, j, a[10100], b[10100], k, t;
		memset(A,0,sizeof(A));
		memset(ans,0,sizeof(ans));
		ids = 1;
		memset(id,0,sizeof(id));
		SET.clear();
		for(i=0;i<10100;i++){
			query[i] ={0,0};
			order[i] ={{0,0},0};
		}
		for(i=0;i<40000;i++) V[i].clear();
		for(i=0;i<10100;i++) ans1[i].clear();
		
	    //scanf("%d %d %d",&n, &k, &q);
	    //cin >> n >> k >> q;
	    n = (I-10)*10;
	    k = (I-10)*10;
	    q = (I-10)*10;
	    cout << n <<" "<<k<<" "<<q<<"\n";
		while(ids<=k)ids*=2;
	    for(i=ids+1;i<= k+ids;i++) V[i].push_back(i-ids);
	    for(i=1;i<n;i++){
	    	A[i] = rand()%k+1;
	    	cout << A[i] << " ";
		}
		A[i] = rand()%2+1;
	    cout << A[i] << "\n";
	    
	    for(i=1;i<=k;i++){
	    	t = rand()%10+1;
	    	ss = "";
	    	for(j=0;j<t;j++){
	    		char cc;
	    		cc = rand()%26+'A';
	    		cc += 32 * rand()%2;
	    		ss += cc;
			}
			if(SET.count(ss)==1) i--;
			else{
				cout<<ss<<"\n";
				SET.insert(ss);
				S[i]=ss;
			}
		}
		//for(i=1;i<=n;i++) cin>>A[i]; //scanf("%d",A+i);
	    //for(i=1;i<=k;i++) cin>>S[i]; //scanf("%s",S[i]);
	
	    for(i=1;i<=q;i++){
	        //cin >> a[i] >> b[i] ; //scanf("%d %d", a+i, b+i);
	        a[i] = rand()%n+1;
	        b[i] = rand()%n+1;
	        if(a[i]>b[i]) swap(a[i],b[i]);
	        cout << a[i] <<" "<<b[i]<<"\n";
	        query[i]={a[i],b[i]};
	        order[i].first = {query[i].first/SQRT_N, query[i].second};
	        order[i].second = i;
	    }
	    sort(order+1,order+q+1);
	    for(i=1;i<=q;i++){
	        go_query(query[order[i-1].second],query[order[i].second]);
	        ans[order[i].second] = id[1];
	        for(j=0;j<V[1].size();j++) ans1[order[i].second].push_back(V[1][j]);
	        sort(ans1[order[i].second].begin(),ans1[order[i].second].end());
	    }
	    sprintf(in,".%d.out",I);
        freopen(in,"w",stdout);
	    for(i=1;i<=q;i++){
	    	cout << ans[i] <<" ";  //printf("%d ",ans[i]);
	    	for(j=0;j<ans1[i].size()-1;j++) cout<<S[ans1[i][j]] <<" ";//printf("%s%c",S[ans1[i][j]],(j==ans1[i].size()-1)?'\n':' ');
	    	cout<<S[ans1[i][j]] <<"\n";
	    }
	}
    return 0;
}