QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267571#7869. 建设终末树275307894a100 ✓1306ms181148kbC++144.1kb2023-11-27 14:39:302023-11-27 14:39:31

Judging History

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

  • [2023-11-27 14:39:31]
  • 评测
  • 测评结果:100
  • 用时:1306ms
  • 内存:181148kb
  • [2023-11-27 14:39:30]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e3+5,M=N*N+5,K=(1<<25)+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,q,x,y,z,id[N][N],Ct;vector<int> S[N];
struct yyy{int to,z;};struct ljb{int head,h[N*N];yyy f[N*N*4];void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;/*cerr<<x<<' '<<y<<'\n';*/}}s;
int fa[N],d[N],tp[N],siz[N],son[N],is[N],df[N],ih;
int g[N];
int ans[N][N],vis[N][N];
void dfs1(int v,int La,int is){
	for(int i:S[v]) if(i^La) dfs1(i,v,is),g[v]+=g[i];
	if(!g[v]) ans[is][v]=1;
	else if(g[v]==x&&v^1) ans[is][v]=0;
	// else cerr<<v<<' '<<g[v]<<'\n';
}
int f[N][N];
int GF(int x,int *fa){return fa[x]^x?fa[x]=GF(fa[x],fa):x;}
vector<int> scs;
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	int fa[N*4][N];
	void build(int l=1,int r=n,int v=1){
		iota(fa[v]+1,fa[v]+m+1,1);if(l==r) return;
		int m=l+r>>1;build(l,m,ls);build(m+1,r,rs);
	}
	void add(int x,int y,int l=1,int r=n,int v=1){
		// cerr<<x<<' '<<y<<' '<<z1<<' '<<z2<<'\n';
		if(x<=l&&r<=y) {scs.emplace_back(v);return;}
		int m=l+r>>1;x<=m&&(add(x,y,l,m,ls),0);y>m&&(add(x,y,m+1,r,rs),0);
	}
	void push(int l=1,int r=n,int v=1){
		if(l==r) {Mc(f[df[l]],fa[v]);return;}
		for(int i=1;i<=m;i++) if(GF(i,fa[v])^i){
			fa[ls][GF(i,fa[ls])]=GF(fa[v][i],fa[ls]);
			fa[rs][GF(i,fa[rs])]=GF(fa[v][i],fa[rs]);
		}
		int m=l+r>>1;push(l,m,ls);push(m+1,r,rs);
	}
	void merge(int v,int z1,int z2){fa[v][GF(z1,fa[v])]=GF(z2,fa[v]);}
}
void make1(int x,int La){
	fa[x]=La;d[x]=d[La]+1;siz[x]=1;
	for(int i:S[x]) if(i^La) make1(i,x),siz[x]+=siz[i],siz[i]>siz[son[x]]&&(son[x]=i);
}
void make2(int x,int La){
	tp[x]=La;is[x]=++ih;df[ih]=x;if(son[x]) make2(son[x],La);
	for(int i:S[x]) if(i^fa[x]&&i^son[x]) make2(i,i);
}
int LCA(int x,int y){
	while(tp[x]^tp[y]) d[tp[x]]<d[tp[y]]&&(swap(x,y),0),x=fa[tp[x]];
	return d[x]<d[y]?x:y;
}
void merge(int x,int y){
	// cerr<<z1<<' '<<z2<<' '<<x<<' '<<y<<'\n';
	while(tp[x]^tp[y]) Tree::add(is[tp[y]],is[y]),y=fa[tp[y]];
	if(x^y) Tree::add(is[x]+1,is[y]);
}
void tarjan(int x,int y,int w){
	// cerr<<x<<' '<<y<<' '<<w<<'\n';
	if(~ans[x][y]&&ans[x][y]^w){puts("-1");exit(0);}
	if(vis[x][y]) return;vis[x][y]=1;ans[x][y]=w;
	for(int j=s.h[id[x][y]],i=s.f[j].to;j;j=s.f[j].z,i=s.f[j].to) tarjan(i,y,w);
	if(w){
		for(int i:S[y]) if(i^fa[y]) tarjan(x,i,1);
	}else{
		for(int i:S[fa[y]]) if(i^y) tarjan(x,i!=fa[fa[y]]?i:fa[y],i!=fa[fa[y]]);
	}
}
void Solve(){
	int i,j;scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		S[x].emplace_back(y);S[y].emplace_back(x);
	}
	for(i=1;i<=m;i++) for(j=1;j<=n;j++) id[i][j]=++Ct,ans[i][j]=-1;
	for(i=1;i<=m;i++){
		Me(g,0);scanf("%d",&x);
		for(j=1;j<=x;j++) scanf("%d",&y),g[y]++;
		dfs1(1,0,i);
	}
	make1(1,0);make2(1,1);Tree::build();
	while(q--){
		scanf("%d",&x);vector<int> c1(x);for(i=0;i<x;i++) scanf("%d",&c1[i]);
		int Ls=c1.front();for(int i:c1) Ls=LCA(Ls,i);
		scs.clear();for(int i:c1) merge(Ls,i);
		scanf("%d",&x);int La=0;
		while(x--){
			int y;scanf("%d",&y);
			if(!La){La=y;continue;}
			for(int i:scs) Tree::merge(i,La,y); 
		}
	}
	Tree::push();
	for(i=2;i<=n;i++) for(j=1;j<=m;j++) if(GF(j,f[i])^j){
		// cerr<<j<<' '<<i<<' '<<GF(j,f[i])<<'\n';
		s.add(id[j][i],f[i][j]),s.add(id[f[i][j]][i],j);
	}
	for(i=1;i<=m;i++) for(j=2;j<=n;j++) if(~ans[i][j]) tarjan(i,j,ans[i][j]);
	for(i=1;i<=m;i++) for(j=2;j<=n;j++) if(ans[i][j]==-1) tarjan(i,j,1);
	for(i=1;i<=m;i++) {
		for(j=1;j<=n;j++) {
			int flag=0;for(int h:S[j]) flag|=ans[i][d[h]<d[j]?j:h]^(h!=fa[j]);
			if(!flag) printf("%d ",j);
			// cerr<<i<<' '<<j<<' '<<ans[i][j]<<' '<<flag<<'\n';
		}
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 694ms
memory: 174972kb

input:

1999 1998 27199
1368 233
233 617
233 388
233 1127
1905 233
907 233
233 40
233 1325
233 1940
1739 233
501 233
233 33
735 233
233 283
233 1427
1992 233
233 632
233 685
1188 233
648 233
233 344
233 1321
986 233
848 233
770 233
256 233
164 233
936 233
1206 233
53 233
1054 233
1430 233
1714 233
86 233
11...

output:

1294 1264 1662 1036 1036 1450 899 641 906 1005 1005 1683 1547 1547 878 1654 1630 1085 503 1338 1654 641 1388 1388 878 1904 1547 1036 1662 1388 906 906 1662 987 878 1683 467 815 1662 1909 1388 1654 899 9 1338 1450 1909 1610 1671 899 1671 181 1036 906 987 467 899 815 705 705 641 1547 899 1904 1662 154...

result:

ok Accepted.

Test #2:

score: 0
Accepted
time: 709ms
memory: 174760kb

input:

1998 2000 25224
1860 579
579 1400
720 579
579 1379
579 1628
579 69
579 400
1941 579
579 811
579 252
1816 579
579 1786
579 335
579 1467
1480 579
98 579
579 755
579 55
579 1059
650 579
579 1846
1437 579
579 861
338 579
1687 579
579 1248
579 1827
579 1169
1613 579
579 1494
579 1502
1090 579
612 579
579...

output:

219 942 158 865 295 1458 219 158 1855 906 557 295 1855 1545 422 557 1545 937 1855 906 634 872 872 1442 1458 1450 158 239 872 295 422 942 295 937 1689 1213 295 634 219 1183 1855 1213 443 1450 1458 872 1117 488 239 1577 698 865 422 219 1699 443 1823 1183 1689 634 488 1117 1545 323 1458 323 1458 443 90...

result:

ok Accepted.

Test #3:

score: 0
Accepted
time: 810ms
memory: 178860kb

input:

1999 1999 17845
621 466
466 254
1001 466
466 326
466 779
466 40
527 466
466 1130
466 504
466 1136
466 73
466 1156
963 466
466 1095
247 466
466 1146
1361 466
466 1340
774 466
466 422
466 1649
466 948
466 1803
466 1765
686 466
466 551
612 466
608 466
318 466
466 132
1215 466
466 310
1962 466
466 1999
...

output:

1046 842 80 647 1792 1241 1483 904 981 1483 1046 1732 904 80 647 544 1085 904 1399 1345 1792 647 904 647 1483 1345 594 1732 380 544 1792 1471 1792 586 1046 1120 544 1478 1399 1792 1732 380 1345 1190 1824 1046 594 647 647 904 1792 1732 380 1732 1478 1085 1120 1860 586 1013 1824 1471 981 1995 1190 147...

result:

ok Accepted.

Test #4:

score: 0
Accepted
time: 685ms
memory: 174600kb

input:

1999 1999 23606
1568 1784
784 1568
1253 1568
1568 869
1568 1404
1601 1568
262 1568
1661 1568
1568 335
1839 1568
1568 208
1154 1568
1568 400
1576 1568
1112 1568
187 1568
1568 1370
1568 1451
1568 293
1568 344
1037 1568
13 1568
1568 1240
518 1568
1568 1912
1121 1568
1005 1568
1568 887
1510 1568
1568 71...

output:

-1

result:

ok Accepted.

Test #5:

score: 0
Accepted
time: 787ms
memory: 178672kb

input:

1998 1998 17047
512 545
545 1651
497 545
545 1154
545 1847
545 1201
898 545
1304 545
545 915
495 545
545 71
1361 545
545 1508
1070 545
545 221
545 593
1612 545
545 1011
545 13
913 545
1659 545
545 1557
545 1425
545 1065
1673 545
545 170
1602 545
680 545
982 545
1600 545
545 1784
678 545
1484 545
191...

output:

-1

result:

ok Accepted.

Test #6:

score: 0
Accepted
time: 691ms
memory: 172704kb

input:

2000 1999 30204
1179 128
586 1179
1179 1556
1179 330
1412 1179
83 1179
147 1179
636 1179
1179 1584
1429 1179
212 1179
1179 1724
19 1179
1179 160
1179 1326
964 1179
1179 624
1179 1498
1137 1179
442 1179
1179 1027
1179 309
1179 1767
1179 721
198 1179
899 1179
211 1179
1179 1740
1746 1179
1179 828
568 ...

output:

1987 49 881 880 1837 47 627 89 49 1159 1896 49 1671 627 727 881 639 49 1837 737 49 1528 1671 1226 627 727 1837 608 1585 1933 737 737 1837 842 880 1755 47 28 1755 28 1671 880 28 1387 1528 608 608 1159 1755 1154 1249 639 1528 371 1987 47 881 1243 842 639 637 1154 1528 49 627 1243 1226 1528 637 1159 18...

result:

ok Accepted.

Test #7:

score: 0
Accepted
time: 545ms
memory: 168272kb

input:

1999 1998 32159
467 1459
467 522
467 1297
467 1095
1751 467
1347 467
1771 467
1939 467
467 589
467 782
467 1947
11 467
467 1008
1841 467
467 615
467 1837
467 999
467 1674
572 467
1204 467
926 467
659 467
1579 467
467 1663
533 467
467 491
996 467
467 1355
467 596
530 467
467 1205
642 467
676 467
1206...

output:

-1

result:

ok Accepted.

Subtask #2:

score: 15
Accepted

Test #8:

score: 15
Accepted
time: 0ms
memory: 14288kb

input:

10 10 8
4 2
2 9
6 9
8 7
4 10
7 2
5 2
2 1
5 3
3 10 7 2
2 10 2
2 4 10
2 10 4
2 8 2
2 4 10
1 8
2 2 10
1 1
1 10
2 10 9
3 10 3 4
2 7 1
3 10 6 3
2 4 8
2 3 2
4 2 9 4 6
2 5 7
2 3 9
2 2 1
4 10 6 8 5
4 10 6 1 2
2 1 4
2 7 5
2 5 3
2 8 3

output:

10 10 10 10 2 10 8 2 1 10 

result:

ok Accepted.

Test #9:

score: 0
Accepted
time: 1ms
memory: 14224kb

input:

10 10 9
9 10
3 5
2 3
9 2
2 6
1 3
8 5
1 7
6 4
1 7
1 8
2 10 2
4 8 5 1 2
2 10 9
2 2 7
1 8
4 1 8 5 2
2 10 6
4 9 2 4 3
2 3 10
2 5 3
2 8 3
2 8 5
2 5 3
2 6 5
2 5 9
2 9 3
2 9 8
2 1 8
3 7 1 6
2 2 8
2 10 2
3 8 1 4
2 9 5
3 1 6 8
3 9 4 3
2 1 7

output:

7 8 9 1 9 1 8 3 9 3 

result:

ok Accepted.

Test #10:

score: 0
Accepted
time: 0ms
memory: 14504kb

input:

10 10 8
7 1
3 2
6 1
2 1
3 5
10 8
4 7
9 2
6 10
1 9
2 3 5
2 10 8
3 9 1 5
1 9
2 1 8
1 10
4 2 7 9 3
3 9 3 6
3 1 9 3
3 3 1 2
3 8 2 9
2 1 9
2 8 9
2 4 2
3 2 8 9
3 4 9 6
3 7 3 6
2 7 10
2 5 8
2 5 9
2 1 5
3 9 7 1
2 9 4
3 8 3 7
3 7 6 3

output:

9 3 10 2 9 10 10 3 3 1 

result:

ok Accepted.

Test #11:

score: 0
Accepted
time: 2ms
memory: 14340kb

input:

10 10 6
8 1
3 10
6 1
9 2
8 5
3 7
9 7
6 4
6 3
2 1 6
3 6 10 3
1 8
4 10 1 4 3
3 3 1 6
3 1 4 10
2 9 2
2 9 2
3 6 1 4
2 7 10
3 3 2 9
3 3 4 6
5 4 8 10 5 9
5 5 6 4 9 1
2 5 9
4 2 6 5 10
3 7 3 8
3 1 9 2
3 2 8 9
2 10 2
4 10 5 3 2
3 6 2 10

output:

-1

result:

ok Accepted.

Test #12:

score: 0
Accepted
time: 2ms
memory: 14300kb

input:

10 10 9
1 7
7 5
7 8
3 7
7 10
4 7
7 9
6 7
2 7
3 6 3 9
3 8 2 4
6 2 7 5 3 6 8
3 4 5 10
4 6 4 10 9
7 5 10 4 6 9 8 1
6 8 9 4 10 5 2
3 4 5 1
7 7 8 5 1 10 9 6
2 8 7
2 3 7
2 6 2
2 3 6
3 3 9 2
2 10 1
2 8 1
2 8 5
2 9 5
2 7 3
2 5 3
3 2 10 8
2 5 8
2 1 3
2 8 4
3 4 5 6
2 9 2
2 10 9
3 3 8 9

output:

7 7 7 7 7 1 7 7 1 7 

result:

ok Accepted.

Test #13:

score: 0
Accepted
time: 0ms
memory: 14376kb

input:

10 10 6
4 9
8 4
4 7
3 4
5 4
2 4
4 6
1 4
10 4
9 8 1 6 4 9 10 5 3 2
5 4 2 10 7 3
2 4 6
2 6 4
8 2 6 10 5 3 9 1 8
8 7 9 10 6 5 3 2 1
8 7 8 10 5 2 1 9 3
8 5 10 7 6 2 9 8 3
9 10 5 7 1 8 9 3 2 6
6 3 2 6 10 5 7
3 5 2 4
2 10 4
4 10 6 8 2
3 10 5 2
4 3 1 8 5
2 6 9
3 7 4 10
6 8 9 7 3 6 1
4 3 8 7 2
3 5 10 2
2 5 ...

output:

1 4 4 4 1 1 1 4 1 4 

result:

ok Accepted.

Test #14:

score: 0
Accepted
time: 0ms
memory: 18352kb

input:

10 10 7
10 6
10 4
2 10
8 10
10 1
5 10
3 10
7 10
9 10
5 8 1 3 5 6
10 2 10 8 5 7 9 3 6 4 1
7 4 8 6 10 3 5 9
2 1 10
7 7 6 10 8 4 1 9
1 5
9 9 4 6 10 1 7 2 3 5
10 6 4 3 9 1 5 8 7 2 10
2 8 2
8 6 1 3 5 7 4 8 9
3 8 5 4
3 10 5 4
2 10 4
3 4 2 10
3 6 7 1
3 4 10 5
2 6 3
2 7 2
4 8 7 6 4
3 8 3 9
4 10 8 4 5
3 10 2...

output:

1 1 10 1 1 5 1 1 10 1 

result:

ok Accepted.

Test #15:

score: 0
Accepted
time: 2ms
memory: 14360kb

input:

10 10 9
8 7
5 3
1 8
7 6
10 4
3 6
1 2
5 9
9 4
5 7 6 9 1 10
3 10 5 9
2 9 6
2 3 4
5 10 6 5 4 3
3 9 3 8
4 3 8 2 10
3 8 4 2
5 3 9 10 8 2
1 5
2 5 7
2 7 4
2 10 7
2 7 9
2 6 5
2 8 1
2 8 1
2 3 5
2 3 10
4 5 8 3 7
3 2 4 5
2 7 5
3 5 1 2
2 1 6
2 2 10
2 8 4
2 2 8
2 7 1

output:

3 5 6 3 3 3 3 3 3 5 

result:

ok Accepted.

Test #16:

score: 0
Accepted
time: 0ms
memory: 14020kb

input:

10 10 9
2 7
1 8
2 5
9 4
5 3
10 7
4 6
10 8
6 1
2 7 5
4 1 4 10 9
2 1 2
5 10 9 4 2 7
3 1 9 4
2 8 9
4 6 8 3 2
2 8 1
3 2 1 9
4 5 8 9 4
2 9 10
2 1 7
2 10 8
2 7 8
2 3 10
2 7 6
2 8 6
2 5 10
2 6 2
2 5 10
3 5 9 8
2 4 10
2 1 5
2 2 9
2 5 7
3 3 10 1
3 8 4 5
3 5 10 9

output:

-1

result:

ok Accepted.

Test #17:

score: 0
Accepted
time: 0ms
memory: 14332kb

input:

10 10 6
8 10
3 5
4 1
9 6
7 10
7 9
2 8
3 1
4 6
1 1
2 10 9
3 3 6 2
2 8 10
2 10 7
2 8 7
5 9 4 3 10 5
3 8 9 10
1 7
2 2 10
3 4 1 5
3 10 9 5
3 1 9 10
3 6 4 10
5 9 6 1 2 8
4 4 2 5 3
2 4 7
3 9 2 4
3 7 1 3
4 5 8 2 4
4 3 10 1 9
3 10 8 3

output:

1 10 10 10 10 10 1 10 7 10 

result:

ok Accepted.

Test #18:

score: 0
Accepted
time: 2ms
memory: 16272kb

input:

10 10 8
3 4
2 8
1 4
1 9
7 5
7 6
5 8
6 10
10 9
2 10 2
3 10 1 2
4 8 5 7 1
2 10 2
1 10
4 1 9 8 5
6 4 8 6 5 2 9
2 1 9
4 7 1 9 2
6 10 2 4 3 9 8
2 9 4
3 1 4 2
2 7 4
3 6 8 7
2 7 8
2 10 7
3 7 3 1
3 2 9 1
3 10 1 3
2 4 1
3 8 5 6
2 4 9
2 8 1
2 9 2
3 3 6 2
3 6 7 8

output:

10 10 1 10 10 1 1 1 10 1 

result:

ok Accepted.

Subtask #3:

score: 20
Accepted

Test #19:

score: 20
Accepted
time: 20ms
memory: 40212kb

input:

500 498 5000
60 409
462 125
461 410
42 178
133 372
137 265
358 27
450 294
45 454
76 405
132 118
333 331
365 230
114 218
112 377
49 429
60 299
488 95
85 362
89 33
426 308
427 198
468 481
289 363
195 430
61 21
162 55
12 487
395 85
79 475
391 215
244 351
331 43
452 186
247 271
224 390
206 347
447 165
9...

output:

498 368 6 72 163 77 212 74 6 269 322 74 74 359 243 48 373 1 92 1 500 71 161 361 455 36 104 161 25 390 305 390 469 369 74 309 415 366 239 429 352 425 74 389 47 429 161 74 161 161 341 92 275 174 1 378 452 74 29 485 266 213 4 47 1 21 479 342 390 375 207 365 161 472 378 92 435 352 1 350 431 322 104 479 ...

result:

ok Accepted.

Test #20:

score: 0
Accepted
time: 20ms
memory: 40348kb

input:

500 500 5000
297 429
444 310
304 235
470 8
33 395
174 34
276 320
298 478
149 117
400 211
118 399
448 268
446 484
268 180
465 471
68 443
33 358
256 431
490 452
110 389
304 418
286 219
498 16
416 376
495 173
408 138
473 228
317 199
344 279
31 469
159 16
377 397
492 402
308 107
461 11
332 105
377 77
31...

output:

39 252 124 376 250 200 48 31 336 117 179 31 481 203 415 380 65 292 114 244 60 6 15 60 357 441 370 279 296 38 41 65 250 133 1 463 65 179 387 79 446 489 405 83 357 376 472 65 223 371 354 265 481 280 377 74 87 70 171 481 436 471 203 163 237 409 65 13 114 280 249 321 65 481 13 416 348 110 357 1 306 380 ...

result:

ok Accepted.

Test #21:

score: 0
Accepted
time: 22ms
memory: 40608kb

input:

499 498 5000
28 246
54 26
13 312
346 225
377 80
274 410
352 446
394 386
204 453
54 355
337 480
313 263
90 395
388 61
193 71
213 265
125 121
65 120
154 216
331 206
475 413
263 332
322 306
75 290
335 222
149 360
89 139
52 10
91 132
202 88
211 106
205 422
19 467
250 156
382 223
161 486
4 8
495 16
64 12...

output:

147 176 188 490 374 147 62 438 354 405 442 472 495 33 117 374 269 136 1 211 369 176 442 438 441 47 24 221 98 405 277 251 467 172 136 6 475 1 314 62 377 166 1 107 305 200 344 1 229 136 71 200 10 369 78 301 6 1 221 200 438 172 48 358 458 135 7 395 254 188 133 405 274 200 298 412 117 200 200 355 342 39...

result:

ok Accepted.

Test #22:

score: 0
Accepted
time: 21ms
memory: 40192kb

input:

499 500 5000
71 225
374 470
413 420
422 368
357 141
479 360
172 237
21 40
16 386
434 274
188 207
249 16
9 259
152 63
488 264
166 467
51 70
90 417
209 411
43 101
102 206
320 29
110 408
182 333
115 394
138 458
29 296
73 241
392 145
235 428
197 114
271 125
131 401
122 377
215 252
186 253
38 309
11 491
...

output:

66 299 264 133 346 22 322 2 378 141 4 497 29 2 133 378 2 2 29 378 108 4 108 421 378 4 390 421 29 346 323 2 322 497 141 312 295 421 2 66 21 497 422 2 497 390 422 497 108 497 264 422 378 22 390 295 467 93 29 113 497 2 22 422 312 264 312 497 22 21 322 93 21 299 29 21 4 22 312 2 322 497 22 29 93 141 93 ...

result:

ok Accepted.

Test #23:

score: 0
Accepted
time: 16ms
memory: 38724kb

input:

498 498 5000
181 300
371 226
361 224
82 101
233 476
366 273
212 240
90 169
488 477
22 374
164 369
276 390
350 61
101 165
331 274
72 325
371 190
472 404
250 449
179 451
64 153
447 267
97 24
495 168
139 170
203 407
493 225
413 216
29 490
306 332
257 309
43 279
189 94
294 287
297 319
289 406
221 338
74...

output:

178 489 439 71 71 326 44 448 270 71 274 8 63 145 8 71 96 326 274 178 109 437 491 391 437 326 96 140 63 343 270 437 439 489 274 224 178 491 324 185 448 270 391 8 251 489 437 274 491 97 473 124 8 97 343 491 8 44 473 124 491 63 391 178 489 97 448 343 489 324 448 185 185 439 489 489 489 178 437 391 71 2...

result:

ok Accepted.

Test #24:

score: 0
Accepted
time: 14ms
memory: 41932kb

input:

498 499 5000
49 110
380 351
80 59
60 4
378 224
383 28
95 381
220 227
287 440
251 493
278 388
157 339
489 377
98 308
122 403
267 47
109 207
140 31
461 264
210 481
130 216
31 410
383 9
141 13
343 448
45 324
297 449
371 149
474 214
41 154
185 138
299 34
412 411
492 327
277 229
33 494
237 12
97 420
6 18...

output:

187 412 483 390 412 483 93 483 412 483 483 390 412 483 483 412 483 93 412 93 187 412 187 483 431 93 187 483 390 187 93 483 390 390 390 93 187 390 483 187 93 187 93 390 187 187 187 187 412 483 187 483 187 483 187 483 483 390 187 93 483 412 412 187 483 412 483 187 412 390 483 390 483 187 412 390 93 41...

result:

ok Accepted.

Test #25:

score: 0
Accepted
time: 16ms
memory: 40732kb

input:

500 499 5000
368 181
285 335
445 454
267 331
22 212
294 281
454 121
19 31
57 14
101 152
130 284
329 396
406 500
446 115
337 61
421 68
203 119
352 238
313 450
16 259
167 307
326 255
173 256
77 42
203 270
249 402
153 135
146 450
172 73
185 149
398 15
426 213
407 368
351 124
159 356
371 418
319 156
304...

output:

355 210 461 415 461 210 210 415 355 461 461 19 461 487 487 461 19 355 415 461 415 487 355 487 487 487 415 487 355 487 210 487 210 210 355 355 487 461 487 355 19 355 355 487 210 487 487 415 355 461 210 355 487 415 487 487 487 487 19 355 19 461 461 487 461 19 224 210 210 210 461 355 19 461 210 461 210...

result:

ok Accepted.

Test #26:

score: 0
Accepted
time: 3ms
memory: 40932kb

input:

500 499 5000
350 140
294 337
407 172
180 28
139 287
2 413
498 218
4 449
245 412
45 247
397 482
427 165
202 490
53 323
178 209
247 341
253 485
478 203
34 305
306 173
111 14
188 64
213 9
278 59
347 454
83 448
356 336
148 239
378 272
145 402
457 189
299 209
291 368
96 110
187 270
218 304
358 217
6 455
...

output:

-1

result:

ok Accepted.

Test #27:

score: 0
Accepted
time: 11ms
memory: 39400kb

input:

499 499 5000
75 164
439 163
466 334
370 484
25 201
107 165
250 122
355 17
411 164
169 9
463 497
428 442
93 50
7 326
15 207
479 112
454 391
329 96
127 290
1 2
99 347
39 84
407 405
147 271
57 298
472 129
195 377
296 35
441 440
232 176
388 92
325 198
425 267
23 100
487 433
78 416
193 365
348 352
324 28...

output:

-1

result:

ok Accepted.

Subtask #4:

score: 20
Accepted

Dependency #2:

100%
Accepted

Test #28:

score: 20
Accepted
time: 27ms
memory: 37728kb

input:

499 499 265
20 482
382 88
211 434
122 198
238 180
411 104
462 291
28 215
220 69
192 172
493 52
25 455
162 29
405 278
161 339
316 212
443 257
419 262
411 458
331 93
106 144
422 264
488 248
86 165
62 411
426 236
443 30
140 260
499 37
295 372
315 237
15 67
403 366
467 235
42 262
61 300
312 362
469 202
...

output:

298 488 28 270 17 17 222 222 184 325 488 488 28 479 215 17 1 28 74 488 74 222 488 17 369 222 250 369 479 250 479 479 250 1 57 488 42 298 17 298 496 17 496 298 422 496 1 222 488 57 442 479 74 488 28 267 42 17 28 17 298 51 479 298 28 28 28 17 28 222 74 51 1 222 488 28 479 488 488 222 28 298 184 28 51 ...

result:

ok Accepted.

Test #29:

score: 0
Accepted
time: 32ms
memory: 42636kb

input:

500 498 275
323 261
41 144
117 22
223 61
412 79
403 191
166 56
401 274
42 204
439 277
439 175
475 382
320 164
179 397
143 302
68 276
11 9
252 25
421 419
109 353
451 165
63 461
28 241
7 91
302 420
60 284
283 113
418 176
443 177
64 412
144 497
493 14
483 209
287 375
287 100
298 376
298 193
188 321
288...

output:

156 491 491 11 339 168 11 420 144 157 420 208 193 76 157 157 160 208 76 339 208 76 11 229 193 157 491 191 193 56 191 1 491 420 157 157 420 11 156 144 420 156 76 160 160 1 76 193 420 420 302 156 11 420 156 193 193 156 11 420 1 420 11 156 11 237 68 160 11 156 1 156 11 420 11 11 157 420 491 237 160 193...

result:

ok Accepted.

Test #30:

score: 0
Accepted
time: 28ms
memory: 43584kb

input:

500 499 215
233 327
276 433
188 7
393 452
431 389
55 485
238 103
411 344
273 193
351 211
248 161
489 149
13 427
336 210
487 199
76 324
452 477
290 134
108 418
378 300
371 218
499 85
418 450
480 353
248 451
89 3
249 248
283 203
294 443
102 360
412 20
234 177
479 171
357 165
490 340
133 110
52 106
374...

output:

-1

result:

ok Accepted.

Test #31:

score: 0
Accepted
time: 26ms
memory: 39904kb

input:

499 499 260
157 101
80 132
333 13
206 419
136 233
322 168
48 362
32 485
426 214
493 349
179 181
245 284
332 366
234 63
407 254
429 337
32 217
469 130
18 129
147 42
223 473
9 310
330 6
242 483
233 228
154 498
31 351
171 377
455 328
497 301
343 244
355 144
386 489
437 247
307 493
134 316
185 256
199 2...

output:

-1

result:

ok Accepted.

Test #32:

score: 0
Accepted
time: 23ms
memory: 38240kb

input:

498 498 1951
289 275
304 352
50 441
95 466
432 162
324 216
367 399
413 154
163 345
290 127
450 195
437 41
326 421
236 299
248 449
60 233
31 183
278 228
184 444
384 448
135 462
39 486
215 123
136 120
12 200
182 416
475 292
180 40
381 334
324 310
113 429
177 398
393 447
67 350
112 46
133 23
205 218
33...

output:

136 381 206 255 416 173 137 39 416 137 100 136 44 416 136 151 262 173 185 173 402 44 151 137 311 137 154 198 151 136 416 133 44 185 11 198 327 475 416 416 334 136 402 262 255 100 475 44 100 475 151 107 39 381 1 1 173 173 173 173 262 11 416 39 136 173 398 446 255 475 260 100 416 137 152 262 311 352 1...

result:

ok Accepted.

Test #33:

score: 0
Accepted
time: 13ms
memory: 38508kb

input:

498 499 2728
88 127
472 81
109 272
124 323
459 371
316 200
321 29
306 46
458 36
95 143
148 205
207 308
252 440
39 74
131 100
237 277
298 341
16 473
349 492
83 461
98 382
17 13
295 198
65 83
165 426
127 412
413 327
237 268
183 211
207 255
221 41
128 433
100 217
40 9
151 64
426 360
189 322
209 26
290 ...

output:

-1

result:

ok Accepted.

Test #34:

score: 0
Accepted
time: 20ms
memory: 39936kb

input:

498 500 285
165 321
87 3
184 139
75 133
257 406
187 14
396 96
323 248
63 165
69 170
388 281
117 164
114 329
103 355
138 177
169 498
182 462
368 424
323 474
322 317
303 416
57 259
498 425
135 216
137 38
30 437
151 205
147 19
459 12
174 280
400 348
248 435
362 213
180 54
363 77
54 157
65 303
447 366
6...

output:

189 400 362 57 362 323 47 425 425 189 323 132 47 189 47 189 57 323 47 57 189 323 362 165 47 189 57 132 165 362 425 57 362 47 323 400 362 165 47 132 400 132 323 362 47 27 47 47 132 323 165 425 400 400 27 323 47 132 323 323 57 189 57 362 323 362 57 47 47 455 27 400 27 400 323 400 1 27 165 455 47 425 3...

result:

ok Accepted.

Test #35:

score: 0
Accepted
time: 21ms
memory: 39996kb

input:

499 500 371
4 44
100 459
299 107
478 284
421 197
56 90
381 198
305 237
137 260
451 188
381 435
230 458
354 76
100 157
431 198
133 394
181 340
221 198
180 15
269 386
287 330
378 152
198 129
274 318
139 38
150 385
11 352
114 428
408 154
248 44
206 76
264 56
35 222
457 194
196 272
494 443
96 453
439 43...

output:

222 294 157 1 294 76 294 222 76 44 76 294 157 381 294 381 428 294 76 76 381 222 157 381 157 381 294 428 222 381 381 157 294 44 76 76 157 76 76 428 157 428 294 44 294 157 157 76 381 157 428 157 157 157 76 157 44 428 381 157 428 44 428 76 157 381 157 157 157 381 381 76 1 294 44 354 381 157 381 428 381...

result:

ok Accepted.

Test #36:

score: 0
Accepted
time: 19ms
memory: 42148kb

input:

498 500 355
367 393
291 435
471 306
44 77
23 36
411 421
59 308
419 155
179 222
58 44
66 4
420 442
228 398
435 339
133 296
184 382
335 175
346 398
316 237
24 57
208 281
332 389
195 320
60 425
136 205
9 365
187 177
493 108
468 445
430 494
241 321
486 304
478 127
18 223
182 261
279 377
233 210
212 193
...

output:

-1

result:

ok Accepted.

Test #37:

score: 0
Accepted
time: 32ms
memory: 42508kb

input:

500 498 215
80 358
454 116
72 463
139 277
370 436
202 220
16 188
1 213
38 59
494 217
497 424
426 135
35 302
419 26
326 499
209 10
311 315
451 285
54 60
161 103
168 413
393 104
234 308
434 39
442 49
306 374
311 158
342 287
74 14
199 102
285 51
379 459
411 125
101 210
84 321
369 111
45 334
65 471
143 ...

output:

466 397 75 199 1 258 35 1 8 19 159 1 1 459 177 50 1 447 1 192 91 193 469 274 239 122 91 447 1 175 41 258 54 215 24 60 366 447 379 285 392 1 177 24 199 328 6 15 54 201 407 481 91 8 287 213 8 87 175 25 156 481 1 397 466 215 177 35 287 24 392 411 201 199 24 330 79 15 1 24 253 348 91 414 366 129 58 34 9...

result:

ok Accepted.

Test #38:

score: 0
Accepted
time: 20ms
memory: 39904kb

input:

499 498 307
333 446
460 222
39 378
485 52
81 34
75 195
334 424
457 84
460 367
255 166
223 160
310 85
437 87
61 238
108 430
264 487
122 6
319 428
119 154
258 304
133 36
276 326
235 383
327 146
375 340
206 98
157 414
241 47
63 479
307 81
308 335
91 390
121 108
463 492
487 146
361 371
9 311
199 265
297...

output:

12 442 224 224 336 224 12 79 378 1 442 336 432 1 487 1 442 224 79 126 378 34 79 12 336 442 1 487 435 1 487 487 435 378 1 1 224 435 224 224 12 224 435 442 224 432 378 12 1 1 336 12 378 224 336 1 435 39 39 12 224 491 442 487 224 1 378 224 435 1 12 79 12 487 224 378 487 1 34 1 224 378 378 1 79 12 435 4...

result:

ok Accepted.

Test #39:

score: 0
Accepted
time: 28ms
memory: 41728kb

input:

498 499 314
282 244
343 470
265 268
88 151
423 412
198 242
421 306
203 225
297 471
63 170
290 497
83 91
132 248
11 395
127 81
387 98
422 222
108 122
29 375
419 297
144 324
151 58
96 345
330 475
177 68
144 28
35 448
394 371
328 124
141 279
231 67
208 340
10 403
298 77
170 127
274 378
305 439
81 442
3...

output:

406 144 406 144 144 144 144 144 144 406 146 406 146 144 144 144 144 144 144 144 155 144 146 144 144 144 406 144 144 144 144 406 144 144 144 144 144 144 144 144 144 406 146 144 110 1 155 469 144 144 144 144 144 144 144 144 412 144 144 144 144 144 144 144 144 144 144 406 155 144 144 144 155 144 406 14...

result:

ok Accepted.

Test #40:

score: 0
Accepted
time: 16ms
memory: 40104kb

input:

499 500 5000
262 245
206 378
294 422
331 197
13 210
57 31
239 117
278 155
209 272
182 479
200 209
178 150
371 388
286 42
104 405
356 494
171 235
362 305
361 269
34 20
256 137
233 425
346 311
170 69
76 319
168 110
366 162
305 265
199 194
107 182
59 157
48 243
153 435
469 22
226 54
360 187
72 363
293 ...

output:

475 206 96 275 384 7 279 280 249 287 357 351 499 498 292 275 435 435 461 40 466 2 252 486 1 2 308 230 140 1 140 154 497 82 176 417 486 10 249 195 200 309 350 463 185 185 104 96 203 499 102 460 92 275 403 351 96 323 249 270 475 69 26 179 407 480 287 308 96 99 239 308 131 351 434 90 193 467 114 475 44...

result:

ok Accepted.

Test #41:

score: 0
Accepted
time: 20ms
memory: 40412kb

input:

498 500 5000
306 1
215 389
341 416
374 34
262 125
476 288
444 90
342 85
215 31
472 463
2 111
325 349
59 275
435 49
448 82
497 167
233 428
407 232
155 109
365 49
322 318
381 10
84 226
422 345
388 168
206 304
301 282
275 47
38 489
210 442
332 118
339 125
393 67
210 421
270 388
380 354
358 352
310 228
...

output:

243 36 34 465 414 441 359 350 355 379 438 434 189 27 482 88 243 96 372 307 348 93 1 167 498 469 131 457 348 453 298 400 1 394 93 73 449 243 356 4 193 374 372 221 27 127 416 410 70 416 31 187 1 143 189 348 364 113 355 439 419 8 31 304 379 283 446 387 94 187 225 457 245 179 263 387 217 127 235 368 440...

result:

ok Accepted.

Test #42:

score: 0
Accepted
time: 4ms
memory: 36996kb

input:

499 498 5000
395 382
498 86
410 99
157 411
263 304
133 323
163 150
111 220
38 124
305 157
398 491
269 82
9 376
91 239
285 185
370 362
121 456
414 63
306 140
454 183
206 60
417 483
34 482
138 412
358 173
75 346
477 324
429 59
10 486
202 412
426 246
360 267
200 439
394 363
77 348
320 187
442 428
120 5...

output:

-1

result:

ok Accepted.

Test #43:

score: 0
Accepted
time: 17ms
memory: 42356kb

input:

499 499 5000
56 232
281 262
375 216
390 313
244 105
298 227
349 160
115 400
455 98
147 463
25 371
97 131
255 345
187 342
93 207
207 432
330 216
301 346
415 377
166 265
399 495
94 276
354 139
74 50
230 385
42 480
276 457
419 239
264 97
413 157
436 401
154 203
284 425
414 389
358 93
60 308
285 259
144...

output:

147 421 181 74 329 94 291 94 85 194 329 431 109 1 293 91 112 298 358 33 313 431 294 296 204 204 448 313 293 358 161 329 313 43 85 161 298 206 169 293 291 431 293 283 343 303 336 493 348 147 423 348 112 33 226 448 236 277 236 109 293 378 182 85 109 194 109 348 493 313 431 28 182 456 293 313 493 1 373...

result:

ok Accepted.

Test #44:

score: 0
Accepted
time: 15ms
memory: 42708kb

input:

498 498 5000
466 442
188 316
306 215
336 277
11 225
2 23
426 316
396 299
463 201
280 428
288 440
104 398
238 363
341 6
289 106
142 49
192 481
4 195
323 278
185 213
461 475
465 317
324 465
68 187
434 491
222 268
141 334
72 108
61 360
321 471
498 18
166 206
396 377
96 127
5 91
213 456
29 286
191 224
2...

output:

448 226 341 237 376 351 457 376 435 482 374 414 457 377 71 405 401 482 416 91 67 373 137 376 236 91 482 44 416 265 329 101 359 265 184 405 448 351 461 341 385 329 416 101 405 461 373 107 414 156 184 176 416 341 150 70 150 384 416 70 46 265 46 137 236 114 226 377 376 91 137 384 341 439 482 176 482 46...

result:

ok Accepted.

Test #45:

score: 0
Accepted
time: 23ms
memory: 40204kb

input:

498 500 367
378 138
146 248
403 496
200 459
400 75
23 277
418 16
101 24
277 362
384 408
320 208
441 46
361 25
85 303
278 288
337 425
24 114
56 344
346 124
128 250
75 9
193 130
114 360
273 250
68 268
310 145
468 287
283 469
225 319
24 400
212 378
135 354
280 311
1 90
208 357
280 56
403 321
411 455
47...

output:

453 403 400 75 403 400 8 24 400 1 75 357 8 250 24 24 330 453 90 400 51 250 8 330 453 24 8 24 24 24 75 250 453 400 8 491 24 453 24 24 400 403 24 24 400 168 24 491 8 1 1 400 1 24 1 24 453 453 400 400 24 453 400 403 24 8 400 400 400 75 168 24 75 400 1 400 75 250 250 24 330 250 24 24 400 400 24 330 75 2...

result:

ok Accepted.

Test #46:

score: 0
Accepted
time: 33ms
memory: 42592kb

input:

498 498 294
286 177
26 389
64 73
369 155
345 299
409 106
94 9
286 191
199 354
43 307
107 441
258 222
264 129
456 23
462 275
344 156
193 445
401 360
215 267
33 442
209 465
170 1
257 189
418 15
324 377
175 120
486 498
303 353
30 172
104 43
344 76
126 325
264 455
445 310
47 12
420 381
394 331
391 233
1...

output:

416 238 471 28 179 365 471 28 365 238 238 28 498 371 416 371 416 28 76 471 177 177 28 286 416 170 471 365 76 238 371 1 76 177 76 371 365 365 238 76 76 238 76 177 371 471 286 371 471 383 179 76 177 177 371 28 371 498 498 286 286 498 416 498 471 177 179 177 177 286 498 286 498 416 416 383 28 365 286 3...

result:

ok Accepted.

Test #47:

score: 0
Accepted
time: 38ms
memory: 40096kb

input:

498 500 214
246 323
132 465
29 71
436 107
95 214
163 281
487 35
388 133
469 148
250 240
486 135
45 144
311 160
461 127
372 283
254 127
252 389
276 441
94 194
115 98
209 127
411 242
99 50
180 47
124 107
483 44
175 272
229 159
176 41
9 206
477 397
302 108
11 318
362 391
356 363
417 391
274 65
71 309
1...

output:

146 213 213 147 146 146 146 394 147 147 146 276 147 147 276 394 146 394 213 213 146 276 213 213 146 147 146 394 213 394 276 276 147 276 394 276 146 147 276 276 394 146 213 213 147 276 146 213 146 394 146 394 146 276 213 146 146 394 147 394 146 213 146 394 394 146 276 213 213 147 394 146 147 276 146 ...

result:

ok Accepted.

Subtask #5:

score: 25
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #48:

score: 25
Accepted
time: 358ms
memory: 131968kb

input:

1999 1999 16990
734 609
971 297
1864 1528
1995 858
1223 411
1800 580
451 1384
800 866
1709 422
740 1381
1402 431
614 526
249 531
406 228
1589 456
1357 1731
852 869
557 1681
1072 632
1695 358
1686 186
1706 313
189 1115
907 1051
1645 1854
1794 1639
1857 1859
496 660
1784 578
311 100
1430 765
330 1319
...

output:

1194 531 200 971 1592 54 901 869 1497 901 971 1196 919 824 311 311 919 1534 1759 531 579 1645 311 200 325 54 1196 869 1194 919 971 869 1196 901 1645 1668 1592 1990 1845 1695 1845 1527 1645 1527 639 54 325 1534 531 122 1196 1497 531 639 1534 54 311 1645 1194 1534 1527 1527 1534 531 824 325 971 1845 1...

result:

ok Accepted.

Test #49:

score: 0
Accepted
time: 370ms
memory: 137940kb

input:

2000 1998 12882
650 855
532 1114
1227 1437
104 109
599 1148
1400 1487
993 78
1127 1447
1961 1896
1683 170
403 327
1883 1974
1392 1111
1803 571
738 717
1088 1311
411 654
1268 444
919 859
741 954
893 1815
967 1079
1070 1257
1368 643
825 199
7 799
1752 377
1560 1870
1693 748
1834 707
277 411
1175 598
1...

output:

633 633 967 1946 967 1946 1590 967 1988 967 13 292 1114 1946 1020 1020 13 1593 1174 1824 967 506 1632 967 506 573 1824 1174 1632 1632 1174 220 1946 1824 1632 1824 1824 506 1824 1038 1447 1447 13 967 1824 119 967 633 1114 967 633 893 13 1988 13 506 1632 119 1020 1593 1227 1114 893 1824 1174 1020 633 ...

result:

ok Accepted.

Test #50:

score: 0
Accepted
time: 520ms
memory: 158308kb

input:

1999 1998 2748
1888 854
1797 419
1733 1121
1431 1009
622 1970
1348 1837
55 478
607 1747
1982 1626
1959 1099
1837 130
605 333
1805 1369
1202 35
1503 986
875 837
693 332
238 1200
41 222
314 925
5 194
1049 238
1493 1290
1206 374
1642 1107
363 1963
49 199
1440 687
75 1130
1131 985
1405 1814
219 953
1134...

output:

1052 984 1141 1496 789 1290 1405 1581 1141 385 1827 1141 1278 1257 1328 1827 1290 1052 1206 1290 1581 1496 1581 789 1278 1290 385 610 610 610 1257 789 1496 610 1830 1290 1141 385 1278 1141 789 1405 789 1052 610 1346 1257 85 238 1278 1278 299 1496 299 1278 1496 1052 1827 789 1257 1252 984 1141 1215 1...

result:

ok Accepted.

Test #51:

score: 0
Accepted
time: 542ms
memory: 162696kb

input:

1998 2000 2456
1687 1024
311 1248
1239 1331
606 1760
1677 1623
853 1920
1163 1877
1523 1818
74 35
1019 1313
232 284
1892 7
583 400
226 1630
1664 478
242 1805
1814 91
519 169
1406 242
1953 506
767 451
1631 1421
916 1717
461 1635
1177 1193
1138 235
486 411
255 809
1157 155
33 1668
295 1772
1529 1369
1...

output:

782 782 785 1652 1520 94 94 180 1697 606 180 685 94 180 1652 1 785 785 785 606 1840 782 1894 1746 1894 685 1520 685 1652 1349 1706 785 782 411 1652 1520 1349 1597 536 1772 1349 1697 782 1652 180 1706 785 1706 180 1597 1520 1652 1840 1746 785 180 1746 1923 536 411 1923 1772 606 1 1697 782 785 782 192...

result:

ok Accepted.

Test #52:

score: 0
Accepted
time: 361ms
memory: 162312kb

input:

1999 2000 2084
1907 1359
888 1314
963 598
1112 1636
1517 1034
1933 1578
813 973
972 78
1929 1119
1774 952
1471 1814
461 756
506 1085
803 1937
1220 18
38 1010
1375 1576
1800 1767
309 1072
382 888
739 1838
76 174
497 477
1600 1821
264 1359
1278 1546
445 520
968 501
1840 610
750 858
103 1112
1236 321
1...

output:

-1

result:

ok Accepted.

Test #53:

score: 0
Accepted
time: 382ms
memory: 160148kb

input:

1999 2000 2517
1460 515
265 141
171 1521
1148 1253
1131 949
1922 1829
619 920
848 802
158 312
587 1813
1899 796
1228 1431
1228 1768
1128 1975
58 734
1668 1656
1441 517
1623 234
1242 1238
1787 169
1808 256
217 1547
1295 1866
568 1573
1255 1350
124 520
1606 852
1754 1602
1085 1206
796 91
1905 745
1607...

output:

-1

result:

ok Accepted.

Test #54:

score: 0
Accepted
time: 510ms
memory: 158348kb

input:

1998 1998 2949
1605 573
1586 1754
1027 296
213 353
1981 396
535 1992
781 1237
1369 90
1255 400
1941 210
680 177
510 115
1303 285
403 244
55 1327
1605 1531
1968 1444
218 316
1502 689
1123 123
131 1558
1742 1730
1512 219
1647 1583
1653 1428
1132 65
549 462
406 584
1072 1879
716 1069
1860 543
351 1253
...

output:

860 1032 465 521 1 268 20 621 481 860 860 462 1578 307 532 621 645 1982 1559 799 831 1145 386 1482 636 1952 1559 1286 1394 307 256 268 983 1701 1983 488 462 1982 1952 1063 321 636 1701 1631 777 1309 1113 1631 860 1982 28 1309 1347 375 1390 256 1740 683 637 683 617 488 227 889 176 20 465 481 1993 306...

result:

ok Accepted.

Test #55:

score: 0
Accepted
time: 497ms
memory: 158440kb

input:

1999 1998 2979
1386 1126
766 166
651 245
803 925
1737 60
1606 460
619 835
921 1145
491 1518
1718 1176
1250 761
841 999
761 394
823 756
1926 1159
1976 1122
1536 1288
1963 429
1199 584
1232 928
1233 1188
1968 709
1109 964
37 1690
508 523
839 1033
613 190
656 1354
531 1910
1431 1859
1890 972
982 40
126...

output:

1511 1144 1144 1585 499 1628 1523 1523 1696 678 532 678 1978 452 26 1518 37 1077 1093 1077 1518 1554 1171 1286 1523 260 1488 260 450 468 260 1511 933 1182 1 1523 1817 1554 532 186 1286 1300 364 468 1182 532 678 364 295 364 1817 538 1171 1978 1978 1096 858 1518 678 186 1093 94 364 1523 1518 391 933 1...

result:

ok Accepted.

Test #56:

score: 0
Accepted
time: 534ms
memory: 160360kb

input:

1999 1999 2386
1948 1104
1966 963
1141 1282
1133 1069
455 517
1327 1603
1368 516
755 1717
1415 992
1786 1679
633 381
1545 1140
1277 1370
1219 285
1061 602
165 9
1144 387
952 1780
1953 578
968 799
183 598
1262 503
990 251
1786 814
1932 466
1869 1102
595 1338
1848 865
1425 362
647 21
1994 27
1377 716
...

output:

839 975 1791 1791 1791 839 982 1235 362 686 982 1429 970 975 1791 1861 1791 1861 1791 1061 970 940 970 1791 1061 1039 1791 1491 1107 1627 1791 1279 1061 1302 1491 1235 1279 975 940 1997 199 1997 672 1061 1791 992 982 1861 1245 166 975 734 1491 1207 940 199 1997 1485 604 1834 349 1070 992 362 982 179...

result:

ok Accepted.

Test #57:

score: 0
Accepted
time: 464ms
memory: 154400kb

input:

1998 1998 3943
1721 662
484 891
524 1161
483 1222
824 401
1039 1027
179 793
555 1800
61 1904
265 128
1830 82
1613 1795
1428 745
1120 1146
857 1776
230 75
763 1954
1111 1868
1014 215
110 536
783 399
267 433
1867 491
1713 595
903 833
865 1894
1001 593
1165 393
504 1208
1077 1202
855 635
1057 236
1776 ...

output:

1845 1149 1666 1683 1688 609 1440 1191 1870 1778 1847 1270 1404 745 120 1888 1343 1662 1319 131 126 702 355 1873 116 1904 607 1267 1390 824 1011 1023 1093 1928 1911 1334 86 374 870 197 1802 1363 555 1538 566 1521 1164 592 699 1423 1577 1521 1087 1917 425 1461 232 1496 1971 755 1954 824 1536 775 1477...

result:

ok Accepted.

Test #58:

score: 0
Accepted
time: 358ms
memory: 133876kb

input:

1999 1998 32642
1546 1931
1475 669
810 1758
114 471
1167 1223
297 932
1921 1720
1640 519
1709 1618
1547 1434
981 1433
1132 1773
1522 232
760 1827
51 484
1648 870
1257 594
9 1538
1840 1490
773 9
1385 1968
1215 1326
1228 58
1197 403
1258 1938
1879 775
46 1880
195 542
684 1362
511 1555
1210 340
1359 16...

output:

225 1113 1038 304 1045 304 265 1630 870 304 1572 334 1938 872 936 1753 1657 665 1326 304 292 902 1677 225 1657 1088 220 427 1682 225 9 79 799 1649 297 902 902 885 725 225 1657 225 885 725 885 425 1753 1195 1040 565 1649 695 707 1040 1630 1840 1162 1715 1677 1257 707 1162 1326 92 732 649 466 872 742 ...

result:

ok Accepted.

Test #59:

score: 0
Accepted
time: 404ms
memory: 177200kb

input:

1999 1998 50000
1244 222
642 583
279 699
1377 95
1321 1432
1030 1267
4 456
399 582
1867 304
121 745
65 424
1117 718
190 40
1172 807
535 725
169 1998
1712 1537
413 1600
313 496
7 1456
31 1977
1983 947
555 569
655 1195
617 955
68 1165
177 1479
262 1500
1533 1733
1507 927
1341 1587
1718 541
1839 362
18...

output:

558 558 976 132 1872 1571 752 1505 1601 444 1986 1553 1522 333 1754 1207 976 1154 1522 1446 325 792 938 746 486 276 1264 1043 1 592 505 665 540 558 1899 1230 558 803 509 1302 246 1516 1544 871 47 1659 697 609 276 944 1900 1372 158 569 765 132 1110 698 602 282 976 691 1028 1112 739 264 1423 1559 976 ...

result:

ok Accepted.

Test #60:

score: 0
Accepted
time: 406ms
memory: 177040kb

input:

1999 1998 50000
1481 1787
923 1228
245 1382
1097 1350
1585 563
1940 461
468 270
1534 291
1877 202
1738 924
160 1380
1665 1458
1859 1053
1685 1036
390 1385
1740 1719
1499 29
554 1258
1690 530
140 76
341 685
906 1383
1275 123
1933 1020
1892 1119
46 73
1400 1408
490 59
1205 1395
1551 83
1071 1457
505 2...

output:

164 616 131 809 757 65 1117 1130 1544 1209 1369 1645 959 602 761 156 714 247 161 247 1277 125 1090 25 1501 937 1463 701 52 288 1035 353 247 196 607 6 192 1090 475 1222 830 247 959 70 1481 1774 1742 1662 1542 1260 972 744 475 1559 1736 889 175 350 1226 1041 82 1952 1871 185 1269 628 63 1390 1990 800 ...

result:

ok Accepted.

Test #61:

score: 0
Accepted
time: 409ms
memory: 181144kb

input:

1998 1999 50000
129 669
1774 926
1477 254
527 377
1454 588
1541 1133
264 292
189 1686
898 1858
300 1737
238 647
1116 1906
647 1496
1595 1296
1212 177
656 1016
1366 233
956 1907
1344 1411
1629 863
1441 874
848 193
130 1396
791 1137
40 173
1560 523
1698 1181
1395 1749
1057 1427
288 742
546 1069
902 25...

output:

1685 1730 1537 1752 388 1206 1685 155 159 1384 772 772 1730 891 1114 159 643 1836 488 1581 1973 1447 43 1621 1114 1114 99 1730 1359 772 159 1470 1385 1761 388 388 1836 1973 1004 388 772 1206 353 1004 1384 1685 1886 1384 1384 772 1836 1910 643 1658 1752 1239 1239 1385 1621 1650 1650 1973 1239 1746 19...

result:

ok Accepted.

Test #62:

score: 0
Accepted
time: 411ms
memory: 179124kb

input:

2000 1999 50000
1946 632
1829 219
1133 1145
1239 328
781 650
935 558
1930 1633
1909 1093
1708 1914
27 44
1134 1309
699 273
1160 1567
817 253
1398 1633
964 647
341 250
764 1865
1404 1610
597 795
1082 202
1276 1705
1193 331
307 1697
1234 1386
491 267
765 1132
1580 1318
527 181
1152 1170
1504 637
714 2...

output:

1598 1196 1870 1742 1954 503 1365 1365 137 1759 464 503 1759 720 464 503 1820 715 1002 1477 137 1386 503 1459 1870 8 1039 1675 8 1002 661 456 1310 1882 1477 1675 1598 456 1196 1085 606 503 1459 1265 110 1446 1196 1759 1954 1365 715 8 1459 8 1365 456 994 1675 1039 1759 1265 1590 1446 1459 606 1358 12...

result:

ok Accepted.

Test #63:

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

input:

2000 1998 50000
853 34
127 1282
1878 301
235 947
1292 1642
1125 122
264 779
121 736
1417 1995
82 1846
305 380
1505 1954
1532 47
1022 633
117 178
521 735
1582 1016
352 256
1901 871
1115 1577
453 1133
1718 909
471 1376
990 1298
1075 282
1167 1018
903 191
1969 1851
1990 1443
1628 773
323 1829
1477 174
...

output:

-1

result:

ok Accepted.

Subtask #6:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #5:

100%
Accepted

Test #64:

score: 10
Accepted
time: 760ms
memory: 164524kb

input:

2000 1999 58321
444 202
1301 594
1824 45
1172 931
1071 1931
1891 654
66 1894
775 1506
1542 979
419 246
25 380
1118 813
1433 1691
572 346
1519 1626
1198 1332
352 1380
1031 1436
843 1428
994 1236
878 328
1337 1461
1717 1038
1096 1811
1191 1527
1426 629
1426 33
108 752
1587 304
367 934
944 621
330 574
...

output:

542 1071 1173 1173 1173 595 426 878 1842 330 878 595 159 595 595 330 1379 159 595 473 1063 1429 595 1885 1063 473 878 174 1885 259 473 542 174 878 1379 401 878 595 1368 1885 401 878 174 1173 401 473 330 174 878 878 1071 1429 1885 878 229 1820 1173 595 1379 427 1379 426 174 330 878 159 878 229 878 25...

result:

ok Accepted.

Test #65:

score: 0
Accepted
time: 618ms
memory: 152292kb

input:

1999 1999 120206
325 133
1513 265
1066 365
71 254
958 824
67 965
869 1570
1336 401
727 1032
578 691
1019 1324
628 297
1142 400
257 1762
824 275
483 1513
1487 236
1253 859
1742 1500
1567 1713
1513 50
1709 773
472 242
1878 958
106 92
168 1447
546 301
1816 1941
1721 1293
1611 169
1179 1240
604 1198
190...

output:

79 1434 86 1001 1893 1542 1703 1703 1542 958 86 1001 1515 847 1893 847 651 1332 931 1513 1066 958 958 1515 1066 870 958 702 702 1001 1703 847 79 1542 1513 958 1332 1332 1001 847 86 651 1332 137 1290 847 1747 958 870 870 1893 1354 1332 1513 702 79 1354 1703 1332 958 1549 1893 1066 1170 1515 958 1515 ...

result:

ok Accepted.

Test #66:

score: 0
Accepted
time: 1256ms
memory: 178824kb

input:

2000 1998 11568
789 1898
271 1158
841 1494
550 1984
849 947
168 1329
1197 1475
33 571
1630 1528
914 1244
1299 1366
517 1835
1072 1263
1093 169
83 1279
185 1646
276 516
1166 642
935 1544
1332 1129
1000 1183
1981 1751
1410 413
195 1361
1146 341
1431 1340
1507 1517
1031 1577
384 1945
1001 311
1955 466
...

output:

886 479 1840 947 1898 224 877 1961 1625 1544 1544 1840 1332 1389 1625 1898 1466 886 224 617 1404 1052 1629 43 1629 877 1898 43 1404 1961 1544 390 1389 196 947 947 540 886 43 1389 362 947 1347 1840 224 1840 589 947 1389 1898 1625 43 1629 877 1961 691 1389 1961 479 1898 1840 479 390 617 1898 1544 1031...

result:

ok Accepted.

Test #67:

score: 0
Accepted
time: 1110ms
memory: 178988kb

input:

1998 1999 16058
691 172
248 257
1915 1925
797 1761
1123 812
74 221
983 1425
1180 126
1019 294
1402 1603
1501 406
657 619
619 1232
989 1045
979 475
100 65
902 159
824 1058
120 1115
659 582
400 579
1151 327
213 1884
1860 1632
361 800
1300 1232
1691 1929
1253 1977
1710 590
1447 672
1571 1618
1829 1912
...

output:

1646 1737 610 834 181 1474 1474 619 849 505 1253 1253 619 741 1447 889 106 619 741 758 1198 619 1737 1447 1612 1737 373 1447 851 505 849 44 1547 800 181 373 834 322 373 1547 505 1554 758 619 949 849 979 741 1447 373 1737 322 466 44 1474 181 741 1547 949 466 1646 322 849 322 106 1646 1547 758 373 466...

result:

ok Accepted.

Test #68:

score: 0
Accepted
time: 1148ms
memory: 176636kb

input:

1999 2000 15762
727 1155
686 1728
592 1649
1843 1253
210 209
1302 1332
1597 736
783 47
208 1404
233 1678
1569 466
533 272
886 1008
1001 1080
1332 1998
1494 1653
1427 1005
1935 1615
1822 1861
1210 1264
889 1531
1981 228
1692 900
903 142
343 1148
1147 435
728 218
504 857
1931 568
1523 975
1422 1731
11...

output:

-1

result:

ok Accepted.

Test #69:

score: 0
Accepted
time: 1155ms
memory: 178720kb

input:

1998 1999 12015
1333 282
690 525
1915 571
1016 389
1491 1981
191 1379
1234 528
202 1277
1774 108
523 440
1918 1471
369 17
239 1883
269 291
901 1547
969 559
463 1086
589 493
570 1048
1308 916
1027 1948
1625 1183
111 52
957 1797
1068 1836
690 966
371 1313
1742 124
1948 1198
1669 1724
1719 1377
1377 59...

output:

-1

result:

ok Accepted.

Test #70:

score: 0
Accepted
time: 771ms
memory: 162484kb

input:

1999 1999 105090
1544 1617
1033 9
1969 1798
1975 547
1420 884
663 844
682 1913
1460 1861
1603 1269
281 1009
258 467
812 1431
954 1663
1960 126
227 326
1256 1689
1968 1028
970 433
192 63
75 88
1476 1589
1058 1716
1645 1554
1570 1185
774 100
179 1514
1491 973
1974 168
603 1019
528 16
1536 1943
332 183...

output:

1527 1289 1280 1280 9 341 181 341 341 1925 1365 442 9 1025 1552 458 1167 1803 36 740 740 119 762 1514 36 349 1453 1552 9 9 88 558 740 349 9 1365 781 106 349 9 1025 1589 36 106 9 181 1280 885 903 430 1167 539 621 1514 1381 1202 848 1381 1925 1365 1202 88 1985 430 442 458 1373 36 1638 430 9 341 816 45...

result:

ok Accepted.

Test #71:

score: 0
Accepted
time: 1180ms
memory: 178928kb

input:

1998 1999 17168
249 98
1150 612
1350 1389
1802 1090
1275 1619
1408 1318
632 1274
1187 1410
1775 721
1323 467
164 889
292 30
1188 964
803 763
438 1380
42 1492
1066 742
36 747
1369 1674
487 858
25 493
1460 1600
349 440
1876 1290
1276 81
897 1772
204 1797
1204 1302
211 903
1169 1890
910 736
759 1614
34...

output:

48 1312 1426 1556 1285 30 698 97 1115 1510 1566 889 97 1749 831 1749 463 207 463 1719 304 1791 619 1 1831 831 213 1749 411 1285 698 1285 1510 340 1306 1467 164 1513 1650 926 1513 530 111 889 583 1 1899 926 1509 908 1426 30 1510 926 1362 1306 889 1306 1873 1831 1899 1275 164 1077 1791 1080 530 1873 5...

result:

ok Accepted.

Test #72:

score: 0
Accepted
time: 1306ms
memory: 178904kb

input:

1998 1999 12493
1763 1335
1363 1440
653 651
1963 1814
1872 1827
1780 1295
900 1346
1103 935
931 767
1148 1329
1819 1980
13 961
1935 1110
1765 1809
631 815
1023 513
956 691
1223 576
906 505
974 1252
69 1051
1895 126
313 1159
320 954
382 911
998 1778
1206 414
201 1393
1243 1472
584 1854
1144 1988
1171...

output:

343 1312 414 1 885 792 1056 1056 1590 1179 16 1009 386 945 1081 1009 1636 718 1906 1549 1872 1590 718 670 386 36 1590 386 1582 832 945 16 386 945 399 386 1331 228 228 885 1986 1312 414 426 1906 817 1331 718 1009 426 853 753 1081 1906 885 1590 753 1590 1912 1986 414 1351 414 853 1582 1986 414 853 885...

result:

ok Accepted.

Test #73:

score: 0
Accepted
time: 1197ms
memory: 178860kb

input:

2000 2000 13003
801 1607
625 1129
1318 743
1391 1618
16 160
1132 116
1478 1274
1942 1886
1397 1163
101 738
1467 261
1328 1884
979 1528
224 600
789 3
1065 1989
809 1038
151 1703
982 660
1023 1314
1426 400
293 1003
1455 1752
580 889
1437 798
747 1388
837 788
350 387
1743 435
1027 791
1532 1242
1306 60...

output:

70 1117 1117 1532 70 1920 1267 153 919 1835 1243 1532 227 1243 1855 1914 1311 928 1855 1 1835 1074 1855 1835 1267 759 1267 153 43 81 247 1243 1532 1835 1128 1532 7 780 1855 780 979 1532 7 21 1536 1074 153 1532 823 43 1532 1128 1243 1001 7 247 928 1835 526 63 526 227 1532 1835 1536 247 526 1920 247 1...

result:

ok Accepted.

Test #74:

score: 0
Accepted
time: 1284ms
memory: 181116kb

input:

2000 2000 16786
1499 508
1291 200
970 1542
1250 838
951 302
951 380
1241 187
1038 1874
1248 152
1438 381
1056 1508
88 60
1468 694
529 1608
1014 573
1180 1960
1321 937
1764 497
1167 416
35 1925
430 1916
1753 613
1953 379
1774 1568
1542 1571
1235 1957
1206 1760
1972 26
257 1956
1475 317
770 72
511 188...

output:

1104 165 190 1885 1618 690 1035 1595 211 1634 1634 1593 1793 1694 376 177 1358 536 937 57 240 339 1506 1333 1042 1968 326 1385 758 1169 1944 804 151 1867 1168 1793 1421 915 1132 1203 1442 328 1164 900 769 1329 784 1990 941 57 1168 34 471 225 830 1181 1708 492 393 1766 1498 1114 1086 1114 1056 1781 1...

result:

ok Accepted.

Test #75:

score: 0
Accepted
time: 590ms
memory: 179232kb

input:

1999 2000 250000
1881 1788
312 997
172 834
1247 846
297 645
108 841
613 1160
1497 906
182 311
1257 694
1761 1188
1825 1841
1291 1815
1583 144
903 389
739 1046
278 1356
636 1878
1636 325
1298 186
1886 89
73 1470
1738 825
372 208
487 453
45 408
1990 818
1087 1122
116 1030
344 1448
55 1994
653 683
549 ...

output:

180 1861 1376 1170 684 292 984 1422 1826 380 910 870 1420 384 1845 1325 1107 1426 247 1884 1420 1563 1922 1900 1609 1032 1651 1772 1728 1095 265 1500 1128 1559 91 633 180 1469 284 1177 295 739 420 1427 1578 773 192 1506 1450 1206 632 1233 1596 1957 1509 700 241 539 966 1610 1170 45 1800 1897 1666 10...

result:

ok Accepted.

Test #76:

score: 0
Accepted
time: 599ms
memory: 181124kb

input:

1998 1999 250000
49 951
742 1017
1058 1368
1185 1635
233 1956
1201 1123
192 1233
990 833
1024 701
1266 490
1912 1146
1750 1977
859 1685
1180 255
1055 1494
917 1
698 750
359 90
1889 543
1030 383
1097 1130
257 1751
1502 177
934 1898
1752 594
1254 246
1224 899
458 491
583 527
1730 55
193 69
886 165
172...

output:

1454 875 109 1788 1903 811 126 652 1264 797 1931 868 1267 506 508 1 1596 540 381 376 1995 394 1858 1493 1319 457 1755 430 1274 635 406 91 1122 1316 376 822 1195 459 406 1460 1702 822 52 1428 546 944 1561 575 1428 458 975 1829 1340 1118 937 757 381 1232 1074 633 149 358 459 1517 1203 565 1580 1118 82...

result:

ok Accepted.

Test #77:

score: 0
Accepted
time: 578ms
memory: 181132kb

input:

1999 1998 250000
627 799
1306 397
1906 1040
1910 861
1909 334
570 219
1109 1213
1929 566
1636 992
1267 1914
981 123
228 1981
1406 1734
1624 59
1502 1042
480 1680
1281 916
663 1462
348 1159
77 36
1193 837
9 411
493 260
576 1763
218 222
1140 1625
1297 1140
1569 1334
835 118
1592 474
98 394
639 1940
27...

output:

83 1 1605 268 1131 1027 114 83 824 1632 592 1548 1324 1541 268 1832 268 1591 834 404 1548 592 1759 1761 1697 662 627 1605 404 1336 268 1835 41 1761 1423 952 1423 1027 529 1460 1591 1761 1835 1686 1761 1423 1460 1 824 435 1591 42 1759 1423 1954 1697 1697 114 435 63 1471 529 575 269 662 1886 1591 42 1...

result:

ok Accepted.

Test #78:

score: 0
Accepted
time: 569ms
memory: 181148kb

input:

1998 2000 250000
536 1392
532 1072
687 636
880 477
1342 244
1103 1982
1288 1852
1153 467
161 870
1872 1537
751 1627
1269 1313
755 181
1272 142
302 1879
1558 720
314 405
86 1641
579 1188
497 172
1080 1747
1148 651
339 630
1035 592
810 917
882 1665
1157 1598
960 35
1599 277
467 1351
887 759
1786 472
4...

output:

373 1677 863 727 1737 388 727 1428 863 1301 1959 610 1677 436 214 1464 998 171 998 1871 1373 1544 556 1677 695 727 1297 646 47 1544 1959 47 1785 373 1179 1961 1676 1228 373 138 343 556 1919 47 1871 47 1794 1493 550 1373 293 949 293 1434 47 949 343 214 556 368 138 214 1959 1544 1301 533 388 214 1664 ...

result:

ok Accepted.

Test #79:

score: 0
Accepted
time: 348ms
memory: 166340kb

input:

1998 1999 250000
1628 1326
1311 363
1754 463
1309 883
238 469
726 1768
840 350
824 1191
241 4
1671 312
223 540
1948 1430
1510 133
1920 1181
1454 279
1205 113
195 1887
1837 805
591 1050
321 57
1624 310
1086 136
680 1055
1398 605
1372 1370
62 1962
236 19
658 1448
411 1889
1147 1170
1707 1048
1316 1378...

output:

-1

result:

ok Accepted.