#include <bits/stdc++.h>
using namespace std;
char infile[100], outfile[100];

long long int A1[200100],A2[200100], ans[2], C1[500100], C2[500100], B[500100][2],s[2],aa[200100][2];
vector <long long int> V[500100];
void f(long long int a, long long int b,long long int c,long long int d,long long int e, long long int g){
	if(V[a].size()==d){
		if(e==1){
			if(c%2==1){
				B[b][g]--;
				ans[g] = ans[g] + B[b][g];
			}else{
				B[b][g]--;
				ans[g] = ans[g] - B[b][g];
			}
		}else{
			if(c%2==1){
				ans[g] = ans[g] - B[b][g];
				B[b][g]++;
			}else{
				ans[g] = ans[g] + B[b][g];
				B[b][g]++;
			}
		}
		return;
	} 
	f(a,b,c,d+1,e,g);
	f(a,b*V[a][d],c+1,d+1,e,g);
}


int main(){
	long long int I, n, m, i,a,j;
	
	for(i=1;i<500001;i++){
		if(V[i].size()<2){
			for(j=i;j<=500001;j=j+i){
				V[j].push_back(i);
			}
		}
	}
	for(I=31;I<=50;I++){
		sprintf(infile, ".%d.in", I);
	    freopen(infile, "w", stdout);
	    //scanf("%lld %lld",&n, &m);
	    n = 200000;
	    m = 200000;
	    printf("%lld %lld\n",n, m);
	    for(i=1;i<=n;i++){
	    	//A1[i] = (rand()*1000+rand())%100+1;
	    	A1[i] = (rand()*1000+rand())%500000+1;
	    	printf("%lld ",A1[i]);
	    	//scanf("%lld",A1+i);
		} 
		printf("\n");
		for(i=1;i<=n;i++){
			//A2[i] = (rand()*1000+rand())%100+1;
			A2[i] = (rand()*1000+rand())%500000+1;
			printf("%lld ",A2[i]);
			//scanf("%lld",A2+i);
		} 
		printf("\n");
		for(i=0;i<500100;i++) B[i][0]=B[i][1]=C1[i]=C2[i]=0;
		ans[0]=ans[1]=s[0]=s[1]=0;
		for(i=0;i<m;i++){
			//scanf("%lld",&a);
			a = (rand()*1000+rand())%n+1;
			printf("%lld\n",a);
			f(A1[a],1,0,1,C1[a],0);
			C1[a] = !C1[a];
			f(A2[a],1,0,1,C2[a],1);
			C2[a] = !C2[a];
			aa[i][0]=ans[0];
			aa[i][1]=ans[1];
			//printf("%lld %lld\n",ans[0],ans[1]);
			s[0]+=ans[0];
			s[1]+=ans[1];
		}
		sprintf(infile, ".%d.out", I);
	    freopen(infile, "w", stdout);
	    for(i=0;i<m;i++) printf("%lld %lld\n",aa[i][0],aa[i][1]);
		printf("%lld %lld\n",s[0],s[1]);
	}
}
/*
5 6
1 2 3 4 6
2 1 2 3 5
1
2
3
4
5
1
*/