QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352077#8238. Dreamy PutataJohnAlfnovAC ✓2004ms264592kbC++2010.6kb2024-03-12 20:21:192024-03-12 20:21:19

Judging History

你现在查看的是最新测评结果

  • [2024-03-12 20:21:19]
  • 评测
  • 测评结果:AC
  • 用时:2004ms
  • 内存:264592kb
  • [2024-03-12 20:21:19]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m;
int L[100005][6],R[100005][6],U[100005][6],D[100005][6];
int powdv(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int sm[270005][11][11],ms[270005][11][11];
void zheng(int x,int o){
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)sm[o][i][j]=0;
	sm[o][0][0]=1;
	for(int i=m+1;i<=2*m;++i)sm[o][i][i-m]=1;
	for(int i=1;i<=m;++i){
		int ny=powdv(R[(x+n-2)%n+1][i]);
		int l=L[(x+n-2)%n+1][i],u=U[(x+n-2)%n+1][i],d=D[(x+n-2)%n+1][i];
		sm[o][0][i+m]=mod-100ll*ny%mod;sm[o][i+m][i+m]=100ll*ny%mod;
		sm[o][i][i+m]=mod-1ll*l*ny%mod;
		sm[o][(i+m-2)%m+1+m][i+m]=mod-1ll*u*ny%mod;
		sm[o][i%m+1+m][i+m]=mod-1ll*d*ny%mod;
	}
}
void fan(int x,int o){
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)ms[o][i][j]=0;
	ms[o][0][0]=1;
	for(int i=m+1;i<=2*m;++i)ms[o][i-m][i]=1;
	for(int i=1;i<=m;++i){
		int ny=powdv(L[x%n+1][i]);
		int r=R[x%n+1][i],u=U[x%n+1][i],d=D[x%n+1][i];
		ms[o][0][i]=mod-100ll*ny%mod;ms[o][i][i]=100ll*ny%mod;
		ms[o][i+m][i]=mod-1ll*r*ny%mod;
		ms[o][(i+m-2)%m+1][i]=mod-1ll*u*ny%mod;
		ms[o][i%m+1][i]=mod-1ll*d*ny%mod;
	}
}
void build(int l,int r,int o){
	if(l==r){
		zheng(l,o);fan(l,o);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)
		sm[o][i][j]=ms[o][i][j]=0;
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(sm[o<<1][i][j])
		for(int k=0;k<=2*m;++k)if(sm[o<<1|1][j][k]){
			sm[o][i][k]=(sm[o][i][k]+1ll*sm[o<<1][i][j]*sm[o<<1|1][j][k])%mod;
		}
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(ms[o<<1|1][i][j])
		for(int k=0;k<=2*m;++k)if(ms[o<<1][j][k]){
			ms[o][i][k]=(ms[o][i][k]+1ll*ms[o<<1|1][i][j]*ms[o<<1][j][k])%mod;
		}
}
void add1(int l,int r,int o,int u){
	if(l==r){
		zheng(l,o);
		return;
	}
	int mid=(l+r)>>1;
	if(u<=mid)add1(l,mid,o<<1,u);
	else add1(mid+1,r,o<<1|1,u);
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)
		sm[o][i][j]=0;
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(sm[o<<1][i][j])
		for(int k=0;k<=2*m;++k)if(sm[o<<1|1][j][k]){
			sm[o][i][k]=(sm[o][i][k]+1ll*sm[o<<1][i][j]*sm[o<<1|1][j][k])%mod;
		}
}
void add2(int l,int r,int o,int u){
	if(l==r){
		fan(l,o);
		return;
	}
	int mid=(l+r)>>1;
	if(u<=mid)add2(l,mid,o<<1,u);
	else add2(mid+1,r,o<<1|1,u);
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)
		ms[o][i][j]=0;
	for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(ms[o<<1|1][i][j])
		for(int k=0;k<=2*m;++k)if(ms[o<<1][j][k]){
			ms[o][i][k]=(ms[o][i][k]+1ll*ms[o<<1|1][i][j]*ms[o<<1][j][k])%mod;
		}
}
int a1[11][11],a11[11][11],a2[11][11],a22[11][11];
void query1(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(a1[i][j]){
			for(int k=0;k<=2*m;++k)if(sm[o][j][k]){
				a11[i][k]=(a11[i][k]+1ll*a1[i][j]*sm[o][j][k])%mod;
			}
		}
		for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
			a1[i][j]=a11[i][j],a11[i][j]=0;
		}
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll)query1(l,mid,o<<1,ll,rr);
	if(mid<rr)query1(mid+1,r,o<<1|1,ll,rr);
}
void query2(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j)if(a2[i][j]){
			for(int k=0;k<=2*m;++k)if(ms[o][j][k]){
				a22[i][k]=(a22[i][k]+1ll*a2[i][j]*ms[o][j][k])%mod;
			}
		}
		for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
			a2[i][j]=a22[i][j],a22[i][j]=0;
		}
		return;
	}
	int mid=(l+r)>>1;
	if(mid<rr)query2(mid+1,r,o<<1|1,ll,rr);
	if(mid>=ll)query2(l,mid,o<<1,ll,rr);
}
int e[100005][6];
int a[16][17],aa[16];
void gauss(int n){
	for(int i=1;i<=n;++i){
		if(!a[i][i]){
			for(int j=i+1;j<=n;++j)if(a[j][i]){
				for(int k=1;k<=n+1;++k)swap(a[i][k],a[j][k]);
				break;
			}
		}
		assert(a[i][i]);
		int ny=powdv(a[i][i]);
		for(int j=i+1;j<=n;++j)if(a[j][i]){
			int zz=mod-1ll*ny*a[j][i]%mod;
			for(int k=i;k<=n+1;++k)a[j][k]=(a[j][k]+1ll*a[i][k]*zz)%mod;
		}
	}
	for(int i=n;i>=1;--i){
		aa[i]=a[i][n+1];
		for(int j=i+1;j<=n;++j)aa[i]=(aa[i]-1ll*aa[j]*a[i][j]%mod+mod)%mod;
		aa[i]=1ll*aa[i]*powdv(a[i][i])%mod;
	}
}
int bn=powdv(100);
#define LL(x,y) (1ll*L[x][y]*bn%mod)
#define RR(x,y) (1ll*R[x][y]*bn%mod)
#define UU(x,y) (1ll*U[x][y]*bn%mod)
#define DD(x,y) (1ll*D[x][y]*bn%mod)
int main(){;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&U[i][j]);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&D[i][j]);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&L[i][j]);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&R[i][j]);
	build(1,n,1);
	int q;
	scanf("%d",&q);
	while(q--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x,y;
			scanf("%d%d",&x,&y);
			++x,++y;
			scanf("%d%d%d%d",&U[x][y],&D[x][y],&L[x][y],&R[x][y]);
			add1(1,n,1,x%n+1);add2(1,n,1,(x+n-2)%n+1);
		}else{
			int sx,sy,tx,ty;
			scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
			++sx,++sy,++tx,++ty;
			if(tx<n){
				for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
					a1[i][j]=(i==j),a11[i][j]=0;
				}
				if(tx<n-1)query1(1,n,1,tx+2,n);
			}
			if(tx>1){
				for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
					a2[i][j]=(i==j),a22[i][j]=0;
				}
				if(tx>2)query2(1,n,1,1,tx-2);
			}
			if(tx==1){
				for(int i=1;i<=2*m;++i)for(int j=1;j<=2*m+1;++j)
					a[i][j]=0;
				for(int i=1;i<=m;++i){
					a[i][2*m+1]=mod-1;a[i][i]=mod-1;
					a[i][(i+m-2)%m+1]=UU(1,i);
					a[i][i%m+1]=DD(1,i);
					a[i][i+m]=RR(1,i);
					for(int j=1;j<=2*m;++j)a[i][j]=(a[i][j]+1ll*LL(1,i)*a1[j][i+m])%mod;
					a[i][2*m+1]=(a[i][2*m+1]-1ll*LL(1,i)*a1[0][i+m])%mod;
					a[i][2*m+1]=(a[i][2*m+1]+mod)%mod;
				}
				for(int i=1;i<=m;++i){
					a[i+m][2*m+1]=mod-1;a[i+m][i]=RR(n,i);
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*(mod-1)*a1[j][i+m])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*(mod-1)*a1[0][i+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*UU(n,i)*a1[j][(i+m-2)%m+1+m])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*UU(n,i)*a1[0][(i+m-2)%m+1+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*DD(n,i)*a1[j][i%m+1+m])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*DD(n,i)*a1[0][i%m+1+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*LL(n,i)*a1[j][i])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*LL(n,i)*a1[0][i])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]+mod)%mod;
				}
				for(int i=1;i<=2*m+1;++i)a[ty][i]=(i==ty);
				gauss(2*m);
				for(int i=1;i<=m;++i)e[tx][i]=aa[i],e[tx+1][i]=aa[i+m];
			}else if(tx==n){
				for(int i=1;i<=2*m;++i)for(int j=1;j<=2*m+1;++j)
					a[i][j]=0;
				for(int i=1;i<=m;++i){
					a[i][2*m+1]=mod-1;a[i][i+m]=mod-1;
					a[i][(i+m-2)%m+1+m]=UU(n,i);
					a[i][i%m+1+m]=DD(n,i);
					a[i][i]=LL(n,i);
					for(int j=1;j<=2*m;++j)a[i][j]=(a[i][j]+1ll*RR(n,i)*a2[j][i])%mod;
					a[i][2*m+1]=(a[i][2*m+1]-1ll*RR(n,i)*a2[0][i])%mod;
					a[i][2*m+1]=(a[i][2*m+1]+mod)%mod;
				}
				for(int i=1;i<=m;++i){
					a[i+m][2*m+1]=mod-1;a[i+m][i+m]=LL(1,i);
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*(mod-1)*a2[j][i])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*(mod-1)*a2[0][i])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*UU(1,i)*a2[j][(i+m-2)%m+1])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*UU(1,i)*a2[0][(i+m-2)%m+1])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*DD(1,i)*a2[j][i%m+1])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*DD(1,i)*a2[0][i%m+1])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*RR(1,i)*a2[j][i+m])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]-1ll*RR(1,i)*a2[0][i+m])%mod;
					a[i+m][2*m+1]=(a[i+m][2*m+1]+mod)%mod;
				}
				for(int i=1;i<=2*m+1;++i)a[ty][i]=(i==ty+m);
				gauss(2*m);
				for(int i=1;i<=m;++i)e[tx-1][i]=aa[i],e[tx][i]=aa[i+m];
			}else{
				for(int i=1;i<=3*m;++i)for(int j=1;j<=3*m+1;++j)
					a[i][j]=0;
				for(int i=1;i<=m;++i){
					a[i][3*m+1]=mod-1;a[i][i+m]=mod-1;
					a[i][(i+m-2)%m+1+m]=UU(tx,i);
					a[i][i%m+1+m]=DD(tx,i);
					a[i][i]=LL(tx,i);
					a[i][i+2*m]=RR(tx,i);
					a[i][3*m+1]=(a[i][3*m+1]+mod)%mod;
				}
				for(int i=1;i<=m;++i){
					a[i+m][3*m+1]=mod-1;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*(mod-1)*a2[j][i])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]-1ll*(mod-1)*a2[0][i])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*UU(1,i)*a2[j][(i+m-2)%m+1])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]-1ll*UU(1,i)*a2[0][(i+m-2)%m+1])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*DD(1,i)*a2[j][i%m+1])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]-1ll*DD(1,i)*a2[0][i%m+1])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j]=(a[i+m][j]+1ll*RR(1,i)*a2[j][i+m])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]-1ll*RR(1,i)*a2[0][i+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+m][j+m]=(a[i+m][j+m]+1ll*LL(1,i)*a1[j][i+m])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]-1ll*LL(1,i)*a1[0][i+m])%mod;
					a[i+m][3*m+1]=(a[i+m][3*m+1]+mod)%mod;
				}
				for(int i=1;i<=m;++i){
					a[i+2*m][3*m+1]=mod-1;
					for(int j=1;j<=2*m;++j)a[i+2*m][j+m]=(a[i+2*m][j+m]+1ll*(mod-1)*a1[j][i+m])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]-1ll*(mod-1)*a1[0][i+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+2*m][j+m]=(a[i+2*m][j+m]+1ll*UU(n,i)*a1[j][(i+m-2)%m+1+m])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]-1ll*UU(n,i)*a1[0][(i+m-2)%m+1+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+2*m][j+m]=(a[i+2*m][j+m]+1ll*DD(n,i)*a1[j][i%m+1+m])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]-1ll*DD(n,i)*a1[0][i%m+1+m])%mod;
					for(int j=1;j<=2*m;++j)a[i+2*m][j+m]=(a[i+2*m][j+m]+1ll*LL(n,i)*a1[j][i])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]-1ll*LL(n,i)*a1[0][i])%mod;
					for(int j=1;j<=2*m;++j)a[i+2*m][j]=(a[i+2*m][j]+1ll*RR(n,i)*a2[j][i])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]-1ll*RR(n,i)*a2[0][i])%mod;
					a[i+2*m][3*m+1]=(a[i+2*m][3*m+1]+mod)%mod;
				}
				for(int i=1;i<=3*m+1;++i)a[ty][i]=(i==ty+m);
				gauss(3*m);
				for(int i=1;i<=m;++i)e[tx-1][i]=aa[i],e[tx][i]=aa[i+m],e[tx+1][i]=aa[i+2*m];
			}
			if(sx==tx||sx==tx-1||sx==tx+1){
				printf("%d\n",(e[sx][sy]+mod)%mod);
				continue;
			}
			if(sx<tx-1){
				for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
					a2[i][j]=(i==j),a22[i][j]=0;
				}
				query2(1,n,1,sx,tx-2);
				int ans=a2[0][sy];
				for(int i=1;i<=m;++i)ans=(ans+1ll*e[tx-1][i]*a2[i][sy])%mod;
				for(int i=1;i<=m;++i)ans=(ans+1ll*e[tx][i]*a2[i+m][sy])%mod;
				printf("%d\n",(ans+mod)%mod);
			}else{
				for(int i=0;i<=2*m;++i)for(int j=0;j<=2*m;++j){
					a1[i][j]=(i==j),a11[i][j]=0;
				}
				query1(1,n,1,tx+2,sx);
				int ans=a1[0][sy+m];
				for(int i=1;i<=m;++i)ans=(ans+1ll*e[tx][i]*a1[i][sy+m])%mod;
				for(int i=1;i<=m;++i)ans=(ans+1ll*e[tx+1][i]*a1[i+m][sy+m])%mod;
				printf("%d\n",(ans+mod)%mod);
			}
		}
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10096kb

input:

4 3
1 2 3
4 5 6
7 8 9
10 11 12
23 24 25
26 27 28
29 30 31
32 33 34
10 11 12
13 14 15
16 17 18
19 20 21
66 63 60
57 54 51
48 45 42
39 36 33
4
2 0 1 1 1
2 0 0 3 2
1 1 1 25 25 25 25
2 0 0 3 2

output:

76426175
344136684
555192113

result:

ok 3 number(s): "76426175 344136684 555192113"

Test #2:

score: 0
Accepted
time: 76ms
memory: 10156kb

input:

3 3
95 62 24
70 74 23
53 63 36
2 25 20
13 2 4
16 22 40
2 2 14
11 1 67
17 6 20
1 11 42
6 23 6
14 9 4
30000
2 2 2 0 2
2 2 0 0 0
2 1 0 0 0
1 0 1 28 36 4 32
1 1 1 55 32 12 1
2 2 1 1 0
2 1 2 0 0
1 0 2 89 2 3 6
1 2 0 53 29 8 10
2 2 2 0 1
2 2 0 1 0
1 2 1 83 15 1 1
2 2 1 1 2
1 2 2 54 41 2 3
2 2 0 1 2
1 0 1 ...

output:

794352047
445720561
950211149
433211214
322045805
617604648
966924565
819436272
601016121
500019039
427833008
54797408
789868594
569035765
757433456
254373638
982293964
982293964
853196341
504864820
764730651
545590959
586948249
843898620
592509932
508256498
954689273
713397189
518777787
988654370
9...

result:

ok 15144 numbers

Test #3:

score: 0
Accepted
time: 102ms
memory: 10092kb

input:

3 4
71 12 51 12
85 83 41 85
20 19 3 75
25 25 1 60
12 7 11 10
72 65 13 1
1 44 16 5
1 1 32 3
3 14 69 5
3 19 32 23
2 9 16 2
5 2 15 19
30000
2 2 3 1 3
2 2 0 0 2
2 1 1 0 1
1 2 1 64 29 1 6
1 2 3 20 70 2 8
2 1 3 0 3
1 1 1 87 7 5 1
2 2 1 0 0
2 2 1 0 3
2 2 1 0 1
1 2 3 64 25 4 7
2 2 2 1 3
2 2 0 1 0
2 2 2 1 1
...

output:

354672429
912592651
205898503
454595712
326527558
244765319
546555335
503022787
150107622
215140594
135585822
236524624
320026574
56673681
280529820
593236671
485177445
743045702
401830954
263027327
262401428
875715418
150860374
179088742
530926216
923964115
667195812
555355389
571319510
737826815
2...

result:

ok 15095 numbers

Test #4:

score: 0
Accepted
time: 126ms
memory: 10132kb

input:

3 5
30 59 44 6 16
12 30 11 83 86
58 49 65 50 44
68 24 2 31 34
24 11 74 12 3
32 23 4 2 17
1 15 29 59 5
19 31 6 4 6
6 15 8 5 34
1 2 25 4 45
45 28 9 1 5
4 13 23 43 5
30000
2 2 0 0 3
2 1 2 0 2
1 1 4 75 7 5 13
2 1 3 0 3
2 1 2 0 4
1 0 1 29 4 53 14
1 0 4 88 10 1 1
2 2 4 1 3
2 2 4 1 3
1 1 2 79 14 3 4
2 2 4 ...

output:

518130880
192901969
549392638
587807011
692872396
692872396
17980668
639677814
546570041
285563686
899784603
294224899
300472120
850053405
384430261
300472120
427268842
269195383
688402844
326045142
856426869
371304714
239555499
858574611
249782581
367550595
813603991
235110041
400091873
781877964
3...

result:

ok 15101 numbers

Test #5:

score: 0
Accepted
time: 85ms
memory: 10092kb

input:

4 3
88 61 8
25 67 82
16 72 5
71 24 3
4 31 51
66 17 4
31 26 63
1 8 11
5 7 21
4 4 6
11 1 31
15 11 50
3 1 20
5 12 8
42 1 1
13 57 36
30000
2 2 1 1 0
1 0 1 15 57 26 2
2 2 1 1 2
2 2 2 0 2
2 2 0 0 0
1 0 1 54 22 8 16
1 2 2 75 12 5 8
1 2 2 67 4 11 18
2 3 2 1 2
2 1 1 0 0
1 0 0 10 70 2 18
1 2 1 35 45 1 19
2 1 ...

output:

932295932
233938741
962914267
815912722
593921746
511030278
628154532
228176878
914256121
677597027
882198995
674345936
857722782
760168451
592843949
808131481
511414300
772346610
433759393
630381295
280392804
171039969
661778948
70945073
35883397
783291216
850970394
64550544
976645462
954726136
157...

result:

ok 15053 numbers

Test #6:

score: 0
Accepted
time: 112ms
memory: 10148kb

input:

4 4
64 11 70 2
77 89 4 59
6 25 27 5
63 4 18 2
2 50 16 37
21 5 64 27
80 35 52 91
32 84 58 39
9 31 4 21
1 5 19 6
12 6 17 3
4 7 7 48
25 8 10 40
1 1 13 8
2 34 4 1
1 5 17 11
30000
2 3 3 0 2
2 3 3 2 0
2 1 0 0 2
2 2 2 0 3
2 3 2 0 0
1 1 0 23 67 3 7
1 1 2 35 55 4 6
2 3 3 2 0
1 3 0 43 45 2 10
2 2 2 1 2
1 2 1 ...

output:

334801426
881562250
651785364
269029145
797504056
802317525
440410805
53552375
677589332
658093753
982712164
788895880
961111614
469915277
451427917
456274210
40639936
749247016
771008350
950381441
457182636
209481283
480115371
761237802
49182981
367217021
640094262
160525935
294564634
429528898
122...

result:

ok 15241 numbers

Test #7:

score: 0
Accepted
time: 150ms
memory: 10020kb

input:

4 5
23 58 1 58 70
53 28 81 87 92
30 77 67 56 70
88 69 21 93 36
70 2 67 16 18
3 61 17 2 6
55 5 10 39 14
9 1 16 3 35
3 13 23 7 7
11 5 1 5 1
8 15 1 4 13
2 20 60 3 26
4 27 9 19 5
33 6 1 6 1
7 3 22 1 3
1 10 3 1 3
30000
2 2 3 0 4
2 3 4 2 1
1 1 4 67 20 7 6
2 1 4 0 0
2 3 2 0 4
2 2 0 1 0
1 1 0 70 17 2 11
2 1...

output:

773395519
202993618
363831331
26600683
628490409
965293227
988464346
254121301
37657552
240517728
959914287
429450563
627759885
77881676
628640396
532755563
789153435
734943549
768356171
155599128
586898868
974688108
332913835
782091995
938757871
25868446
879373433
781809249
970823879
749935361
7024...

result:

ok 15156 numbers

Test #8:

score: 0
Accepted
time: 89ms
memory: 10156kb

input:

5 3
45 41 80
78 24 25
14 64 88
77 13 48
78 19 44
38 13 9
12 57 47
20 8 5
19 15 8
9 26 1
7 5 4
7 4 26
59 8 2
2 3 43
2 36 44
10 41 7
3 15 2
7 20 5
2 69 1
11 19 11
30000
2 4 2 2 1
1 3 0 79 7 4 10
1 3 1 25 28 42 5
1 4 1 66 19 12 3
2 4 2 0 1
2 4 2 3 0
1 4 2 81 2 2 15
2 2 2 0 0
2 4 0 0 1
1 0 1 92 5 1 2
2 ...

output:

424703237
74093968
190343982
962559774
102755459
671175664
701973110
602834246
516593273
331066997
859528771
49139165
970030107
394559031
237142618
869135259
952444644
324920125
954118145
742091927
407449341
550194093
802575663
95826696
690734073
36175815
772030766
568903915
533320284
698003803
8396...

result:

ok 15052 numbers

Test #9:

score: 0
Accepted
time: 126ms
memory: 10060kb

input:

5 4
57 88 72 54
52 68 2 33
72 47 16 85
48 71 26 31
13 24 1 36
21 8 11 31
5 1 87 27
7 47 61 7
20 9 59 19
24 36 92 49
8 1 10 11
34 20 5 9
8 2 2 1
21 13 2 27
56 11 1 9
14 3 7 4
9 11 6 31
13 4 21 7
11 7 13 23
7 29 6 6
30000
2 4 0 0 1
2 4 1 3 0
2 4 3 3 0
1 0 1 10 50 15 25
2 3 0 2 3
2 4 1 3 0
2 4 2 2 3
2 ...

output:

50910996
216377646
573900831
94488786
398129185
72553576
227714101
439263073
864769360
737633649
315953214
971053832
297538736
612444954
155336683
149698059
307519489
277288455
434987247
690011402
580947251
261583247
24280548
473637822
957506150
659358847
304584321
805231430
355763909
371671194
3563...

result:

ok 15229 numbers

Test #10:

score: 0
Accepted
time: 166ms
memory: 10060kb

input:

5 5
16 38 3 13 63
94 53 55 11 36
89 60 70 27 78
36 15 75 89 65
69 44 67 66 92
4 3 48 80 31
1 40 31 72 13
7 15 14 17 19
19 50 9 6 4
27 21 24 26 3
9 13 36 2 2
4 4 11 7 44
3 13 13 51 2
30 9 2 1 1
2 8 5 5 4
71 46 13 5 4
1 3 3 10 7
1 12 3 5 1
15 26 14 4 30
2 27 4 3 1
30000
2 3 3 0 4
2 3 3 2 2
1 0 0 34 34...

output:

157640412
687387050
837923934
844421869
274018362
895430369
443299523
382623443
850399991
931489969
759234940
192352559
611861383
387013782
842447071
496743050
623398591
561396284
479647208
336852340
777717261
191482727
633322383
287868764
74768141
632861696
784428747
218665333
627277702
333573501
8...

result:

ok 15144 numbers

Test #11:

score: 0
Accepted
time: 37ms
memory: 10048kb

input:

10 3
81 66 37
60 28 14
78 86 86
48 85 80
35 38 80
6 24 92
42 39 22
51 19 17
24 90 75
84 97 58
8 6 58
15 52 16
4 10 8
30 7 3
51 30 15
62 4 5
50 18 11
38 39 50
72 8 17
10 1 40
2 10 1
16 6 13
14 1 1
21 1 7
2 25 3
26 20 2
4 13 7
7 41 1
1 1 7
4 1 1
9 18 4
9 14 57
4 3 5
1 7 10
12 7 2
6 52 1
4 30 60
4 1 32...

output:

228427104
803896245
264833563
753064087
301119297
725047338
241342719
686145017
602098062
293499112
249785324
771050358
774679486
964267877
470137845
52315848
785143210
282403387
517877956
785226997
445689512
232849844
615681766
129948283
123199230
605814309
15398995
490612360
46486523
376156864
929...

result:

ok 6539 numbers

Test #12:

score: 0
Accepted
time: 69ms
memory: 10156kb

input:

15 4
19 30 58 23
95 35 56 12
73 23 82 3
24 36 64 33
35 83 67 28
79 1 36 24
45 83 39 70
49 21 10 16
11 8 66 75
86 89 44 82
33 84 74 46
91 63 8 4
68 41 30 94
37 29 26 41
73 5 55 14
66 42 25 21
1 7 19 17
16 43 2 69
26 39 10 48
31 14 10 65
5 75 17 43
45 13 25 22
40 66 55 34
44 73 11 17
8 7 26 13
61 5 5 ...

output:

817241723
982734749
482199175
119378443
893638291
979342465
264556338
92052934
958824466
851266810
683720751
872806324
787928882
851735609
807816096
141792886
967921253
692672934
559586634
163827114
976156746
592647529
549317880
658406488
218852213
808431177
539401099
850609482
1883073
656868643
114...

result:

ok 6484 numbers

Test #13:

score: 0
Accepted
time: 107ms
memory: 10088kb

input:

20 5
74 46 89 8 37
52 88 26 44 20
60 50 15 11 39
60 42 90 42 17
54 79 34 49 25
47 34 97 67 66
33 32 57 63 57
54 32 95 41 77
20 30 10 61 75
43 68 59 81 66
50 40 42 26 28
7 72 31 77 76
81 92 31 27 7
10 67 68 71 52
58 42 12 69 35
73 88 66 38 47
71 23 56 66 2
27 49 57 59 90
41 58 71 75 91
8 67 52 65 26
...

output:

639778417
364226267
647053368
883426672
42223536
418385936
943273737
122622223
109902690
422993489
189755364
885103191
233768416
16323535
133413893
368728303
429746539
146564917
232762353
447281254
52315190
375639139
419899498
635167879
757822657
952255724
152964536
238218545
147952347
886296437
428...

result:

ok 6491 numbers

Test #14:

score: 0
Accepted
time: 744ms
memory: 264000kb

input:

100000 3
1 73 64
52 63 95
30 77 54
84 82 88
42 49 85
50 78 67
58 19 58
35 18 15
5 7 1
1 36 93
68 26 2
86 92 53
81 60 61
16 64 23
85 48 19
36 93 13
69 28 55
64 12 55
5 17 48
96 39 96
36 70 90
38 96 5
2 16 89
20 60 23
77 95 60
26 31 9
44 11 49
96 9 26
58 53 55
2 6 15
6 36 28
69 87 57
37 24 9
75 40 75
...

output:

284120907
924649627
863561154
124580633
327461480
880541069
354216083
344425981
869290322
726162864
852401987
901164811
737248442
713336732
116936699
93725609
571036745
555110281
98123687
360768289
548752652
135342301
113187378
854007521
456474003
405207785
568222544
273119944
23105323
959342696
470...

result:

ok 5549 numbers

Test #15:

score: 0
Accepted
time: 1278ms
memory: 263868kb

input:

100000 4
43 84 94 9
51 53 43 92
80 85 84 74
28 60 14 37
92 35 80 41
81 74 93 81
18 64 73 44
1 63 6 43
8 19 36 10
47 46 56 63
81 34 51 34
15 5 31 66
40 67 37 78
69 95 77 92
49 87 88 44
59 56 36 96
2 25 93 6
54 16 4 89
97 76 21 72
13 24 79 87
88 41 66 41
31 53 91 66
83 39 28 54
9 39 8 79
39 28 83 22
8...

output:

970083585
468439101
702708882
361058188
286356617
216643969
789090532
745804812
760332031
510418319
89227262
36071722
66406269
348122580
495905506
780300006
103263448
817779478
706395495
778878502
870194500
741118561
870781768
148436812
830347059
417656361
985758040
964132171
889163823
78517671
5364...

result:

ok 8118 numbers

Test #16:

score: 0
Accepted
time: 728ms
memory: 263488kb

input:

100000 3
32 44 5
68 85 73
54 73 84
94 40 65
11 68 78
85 11 49
75 70 68
31 30 36
44 70 10
77 48 92
31 37 68
23 70 76
45 76 40
16 40 33
36 76 3
58 48 89
89 45 14
68 44 36
79 86 81
67 58 23
34 43 67
5 92 17
3 21 81
23 59 73
76 77 89
54 17 48
10 77 49
86 54 30
14 37 45
45 68 44
66 1 59
21 72 54
46 25 61...

output:

657821239
557832902
526733891
405455461
512327394
774740622
451722300
971503418
89575344
409160388
26513920
406848935
585908802
956036971
92428741
797757545
406723554
654954849
254898574
73821667
438908231
632644781
497029378
10049486
855950702
600584181
546853474
460107062
256959150
153078927
61518...

result:

ok 13353 numbers

Test #17:

score: 0
Accepted
time: 1242ms
memory: 264592kb

input:

100000 4
1 34 43 58
33 75 88 53
85 73 77 32
96 79 20 15
71 61 73 32
72 42 68 8
93 48 84 45
64 74 21 85
90 29 95 34
74 27 80 37
55 9 20 70
77 77 78 4
53 26 84 66
30 13 56 88
94 97 79 10
9 94 46 23
76 19 96 57
59 77 27 41
68 80 80 3
43 12 88 57
5 72 63 54
74 94 97 95
87 10 88 59
90 79 34 81
30 22 87 6...

output:

158184626
46438465
139960011
600876180
44697286
126543896
236850831
180061456
407651901
953701763
619394894
252320009
77702526
257557368
438333439
656982968
183063460
941107963
13589692
521891566
428345882
979513834
203561651
261654229
3204573
31758119
746462743
436951916
175846782
453983916
8032578...

result:

ok 15724 numbers

Test #18:

score: 0
Accepted
time: 2004ms
memory: 263824kb

input:

100000 5
73 65 54 33 54
81 65 3 4 8
59 58 69 11 10
3 55 48 5 27
78 12 79 2 7
48 35 8 74 14
78 24 10 93 2
75 97 90 35 92
60 54 32 52 9
1 93 26 6 53
71 8 91 2 65
78 72 11 60 7
24 10 3 44 51
75 17 35 54 20
90 68 1 52 6
69 21 62 80 47
68 63 85 20 70
44 74 3 46 17
70 72 12 34 39
66 55 24 69 26
6 32 86 5 ...

output:

178851296
162115154
489843274
831874389
520384272
430534929
414601775
171889539
119979929
411670828
615705704
218029567
897060176
700748744
963244040
215172933
995792279
428831608
882734035
660462378
389767553
668275909
540133375
807319711
105670166
606575962
508412606
226324747
533640807
60093347
1...

result:

ok 6817 numbers

Test #19:

score: 0
Accepted
time: 1985ms
memory: 264044kb

input:

100000 5
32 74 16 46 75
80 68 8 15 33
39 97 41 71 59
89 47 18 30 1
66 45 30 89 5
2 85 32 36 50
42 23 76 32 69
95 35 4 46 77
78 96 27 40 76
70 8 70 54 66
4 31 84 92 14
53 2 15 51 72
43 29 53 52 25
85 79 20 35 78
41 76 33 65 58
61 13 61 54 37
58 29 60 72 87
52 79 7 91 25
19 21 42 80 69
43 52 46 18 25
...

output:

725955759
710046583
427576398
993651674
731931091
895785668
523961085
902666201
220828866
518078508
17424232
973201828
399984922
228839424
165140208
53143549
422567786
858181780
431701211
863933380
512985273
689088374
977027776
119748381
256956731
206376383
577241188
390637555
145428164
292073801
96...

result:

ok 9323 numbers

Test #20:

score: 0
Accepted
time: 1944ms
memory: 263496kb

input:

100000 5
30 94 3 3 45
68 30 61 45 22
52 16 57 66 96
78 96 12 96 80
42 77 90 26 83
94 90 53 58 25
31 39 92 86 27
20 27 54 94 48
17 11 63 53 17
29 42 79 81 92
47 94 52 17 43
12 20 21 68 8
72 83 65 67 62
25 54 52 6 64
86 91 42 56 21
35 51 15 55 18
65 59 82 78 95
68 80 85 50 86
5 77 14 30 30
69 80 71 11...

output:

605478808
5119144
445403182
21221335
142846095
588934996
46642807
204397690
5327551
831209476
654072485
334603179
534192008
545420302
825459264
205507704
597130365
521617449
646736700
754643199
103216781
929143067
791350967
891598837
971964043
448295138
262849669
882574577
695805194
380449124
205567...

result:

ok 14589 numbers

Test #21:

score: 0
Accepted
time: 1909ms
memory: 263568kb

input:

100000 5
52 41 62 61 57
23 60 66 56 83
67 55 47 29 13
33 88 79 23 26
74 30 85 51 81
83 44 76 2 61
92 3 26 25 15
40 45 3 70 51
35 9 75 76 85
45 73 9 32 8
16 54 27 89 71
84 46 25 59 91
28 5 19 92 37
34 3 36 40 8
3 1 39 87 91
71 43 49 64 8
20 60 57 15 15
58 85 36 60 94
60 88 61 93 42
81 77 57 4 29
6 44...

output:

185419912
768439949
374112631
745995763
826719432
822261079
588286700
576996967
490423215
614980501
7363742
813130672
42154188
47457075
917341787
115212408
940601676
795487859
590309669
589505982
982552899
207763921
367654465
954049447
209198384
273700729
197431340
365762925
267443836
361350246
8152...

result:

ok 17103 numbers

Test #22:

score: 0
Accepted
time: 1874ms
memory: 263992kb

input:

100000 5
85 26 49 17 71
46 13 85 86 9
80 54 10 86 67
57 75 2 89 8
49 97 48 50 61
78 83 54 24 36
64 81 24 96 51
63 19 70 21 22
89 3 14 10 79
5 54 18 94 52
76 20 14 93 48
7 64 49 59 28
22 59 75 29 74
53 57 6 10 28
12 16 48 96 19
64 81 83 64 85
62 28 17 56 76
11 24 17 54 57
47 65 95 26 38
53 87 82 16 8...

output:

615620508
127890517
476618930
64594793
682823828
252420790
552704013
614011083
331767096
251221155
278485650
142740174
340485180
960775912
761449259
540111993
201059179
558751054
680254505
902536986
787407723
521352466
23980633
652024083
613297227
949509131
389192631
156230012
171984172
953613464
41...

result:

ok 22188 numbers

Test #23:

score: 0
Accepted
time: 1861ms
memory: 263824kb

input:

100000 5
66 63 70 9 42
34 10 41 37 33
93 52 26 46 6
63 78 57 23 52
25 49 11 83 24
37 9 66 89 55
53 62 41 26 44
85 73 58 70 90
90 77 5 84 19
8 88 27 94 78
92 21 79 53 78
89 82 20 42 61
95 78 17 9 76
90 68 19 43 49
40 93 41 87 78
56 4 37 65 48
69 76 74 80 49
9 25 25 48 74
33 24 13 38 62
79 80 10 71 67...

output:

687281850
811218241
305501864
908513812
554542182
98535565
295873110
920639325
861717882
942340257
267684501
861694329
722030650
501829583
282662385
599250933
601193772
885782513
199996974
320025605
558708045
923843030
971980520
638459532
715776608
812453283
208159853
401865772
671523982
612371114
9...

result:

ok 27400 numbers

Extra Test:

score: 0
Extra Test Passed