QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#445311	#8809. Telephone Plans	Crysfly	20	995ms	246920kb	C++17	2.7kb	2024-06-16 01:04:58	2024-06-16 01:04:58

Judging History

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

[2024-06-16 01:04:58]
评测

测评结果：20
用时：995ms
内存：246920kb

查看

[2024-06-16 01:04:58]
提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline ll read()
{
    char c=getchar();ll x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int O,n,q;

set<int>e[maxn],c[maxn*2];
struct node{
	int u,pa;
	set<int>::iterator it;
};

ll res1[maxn*3],res2[maxn*3];
int fa[maxn*2],idx;

ll add(int u,int v){
//	cout<<"add "<<u<<" "<<v<<"\n";
	e[u].insert(v),e[v].insert(u);
	int fu=fa[u],fv=fa[v];
	if(c[fu].size()<c[fv].size()) swap(u,v),swap(fu,fv);
	
	ll ans=1ll*c[fu].size()*c[fv].size();
	for(int x:c[fv]) c[fu].insert(x),fa[x]=fu;
	c[fv].clear();
//	cout<<"ans "<<ans<<"\n";
	return ans;
}

ll del(int u,int v){
	e[u].erase(v),e[v].erase(u);
	
	queue<node>q[2];
	set<int>s[2];
	s[0].insert(u),s[1].insert(v);
	if(e[u].size()) q[0].push((node){u,0,e[u].begin()});
	if(e[v].size()) q[1].push((node){v,0,e[v].begin()});
	
	while(q[0].size() && q[1].size()) {
		int o=(s[1].size()<s[0].size());
		auto [u,pa,it]=q[o].front(); q[o].pop();
		int v=*it;
		if(v!=pa && !s[o].count(v)){
			s[o].insert(v);
			if(e[v].size()) q[o].push({v,u,e[v].begin()});
		}
		++it;
		if(it==e[u].end()) continue;
		if(*it==pa) ++it;
		if(it==e[u].end()) continue;
		q[o].push({u,pa,it});
	}
	if(!q[0].size() && (q[1].size() || s[0].size()<s[1].size())) swap(u,v),swap(s[0],s[1]);
	
	int fu=fa[u];
	ll ans=1ll*s[1].size()*(c[fu].size()-s[1].size());
	assert(s[1].size()*2<=c[fu].size());
	
	++idx;
	swap(c[idx],s[1]);
	for(int x:c[idx]) fa[x]=idx,c[fu].erase(x);
	
	return ans;
}

signed main()
{
//	freopen("my.out","w",stdout);
	O=read(),n=read(),q=read(); idx=n;
	For(i,1,n) c[i].insert(i);
	For(i,1,n*2) fa[i]=i;
	ll lst=0;
	For(i,1,q){
		int op=read();
		res1[i]=res1[i-1],res2[i]=res2[i-1];
		if(op==1){
			int u=read(),v=read();
			if(O)u^=lst,v^=lst;
			res1[i]+=add(u,v);
		}
		if(op==2){
			int u=read(),v=read();
			if(O)u^=lst,v^=lst;
			res2[i]+=del(u,v);
		}
		if(op==3){
			ll t=read();
			if(O)t^=lst;
			lst=res1[i]-res2[i-t];
			cout<<lst<<"\n";
		}
	}
	return 0;
}
/*
*/

源文件, 语言: C++17

详细

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 7ms

memory: 144196kb

input:

output:

result:

ok 147 lines

Test #2:

score: 0

Accepted

time: 21ms

memory: 144784kb

input:

output:

result:

ok 8 lines

Test #3:

score: 0

Accepted

time: 23ms

memory: 145096kb

input:

output:

result:

ok 92 lines

Test #4:

score: 0

Accepted

time: 17ms

memory: 146236kb

input:

output:

result:

ok 92 lines

Test #5:

score: 0

Accepted

time: 11ms

memory: 144512kb

input:

output:

result:

ok 92 lines

Test #6:

score: 0

Accepted

time: 8ms

memory: 144960kb

input:

output:

result:

ok 92 lines

Test #7:

score: 0

Accepted

time: 15ms

memory: 145220kb

input:

output:

result:

ok 92 lines

Test #8:

score: 0

Accepted

time: 8ms

memory: 144740kb

input:

output:

result:

ok 92 lines

Test #9:

score: 0

Accepted

time: 23ms

memory: 144856kb

input:

output:

result:

ok 92 lines

Test #10:

score: 0

Accepted

time: 15ms

memory: 144608kb

input:

output:

result:

ok 92 lines

Test #11:

score: 0

Accepted

time: 21ms

memory: 145996kb

input:

output:

result:

ok 92 lines

Test #12:

score: 0

Accepted

time: 19ms

memory: 145720kb

input:

output:

result:

ok 92 lines

Test #13:

score: 0

Accepted

time: 15ms

memory: 145392kb

input:

output:

result:

ok 92 lines

Test #14:

score: 0

Accepted

time: 19ms

memory: 145236kb

input:

output:

result:

ok 92 lines

Test #15:

score: 0

Accepted

time: 21ms

memory: 145892kb

input:

output:

result:

ok 92 lines

Test #16:

score: 0

Accepted

time: 12ms

memory: 146120kb

input:

output:

result:

ok 92 lines

Test #17:

score: 0

Accepted

time: 18ms

memory: 145696kb

input:

output:

result:

ok 92 lines

Test #18:

score: 0

Accepted

time: 7ms

memory: 144780kb

input:

output:

result:

ok 92 lines

Test #19:

score: 0

Accepted

time: 8ms

memory: 145104kb

input:

output:

result:

ok 92 lines

Test #20:

score: 0

Accepted

time: 11ms

memory: 145944kb

input:

output:

result:

ok 92 lines

Test #21:

score: 0

Accepted

time: 11ms

memory: 145840kb

input:

output:

result:

ok 94 lines

Test #22:

score: 0

Accepted

time: 11ms

memory: 145340kb

input:

output:

result:

ok 93 lines

Test #23:

score: 0

Accepted

time: 11ms

memory: 145608kb

input:

output:

result:

ok 92 lines

Test #24:

score: 0

Accepted

time: 11ms

memory: 145988kb

input:

output:

result:

ok 92 lines

Test #25:

score: 0

Accepted

time: 16ms

memory: 144976kb

input:

output:

result:

ok 92 lines

Test #26:

score: 0

Accepted

time: 19ms

memory: 145192kb

input:

output:

result:

ok 92 lines

Test #27:

score: 0

Accepted

time: 30ms

memory: 145680kb

input:

output:

result:

ok 139 lines

Test #28:

score: 0

Accepted

time: 12ms

memory: 145204kb

input:

output:

result:

ok 149 lines

Subtask #2:

score: 2

Accepted

Test #29:

score: 2

Accepted

time: 20ms

memory: 144920kb

input:

output:

result:

ok 147 lines

Test #30:

score: 0

Accepted

time: 7ms

memory: 146172kb

input:

output:

result:

ok 8 lines

Test #31:

score: 0

Accepted

time: 17ms

memory: 145176kb

input:

output:

result:

ok 92 lines

Test #32:

score: 0

Accepted

time: 15ms

memory: 145784kb

input:

output:

result:

ok 92 lines

Test #33:

score: 0

Accepted

time: 16ms

memory: 144324kb

input:

output:

result:

ok 92 lines

Test #34:

score: 0

Accepted

time: 22ms

memory: 145944kb

input:

output:

result:

ok 92 lines

Test #35:

score: 0

Accepted

time: 15ms

memory: 146252kb

input:

output:

result:

ok 92 lines

Test #36:

score: 0

Accepted

time: 12ms

memory: 146064kb

input:

output:

result:

ok 92 lines

Test #37:

score: 0

Accepted

time: 15ms

memory: 145600kb

input:

output:

result:

ok 92 lines

Test #38:

score: 0

Accepted

time: 25ms

memory: 144452kb

input:

output:

result:

ok 92 lines

Test #39:

score: 0

Accepted

time: 18ms

memory: 145652kb

input:

output:

result:

ok 92 lines

Test #40:

score: 0

Accepted

time: 21ms

memory: 144960kb

input:

1
30 150
1 23 18
3 1
3 0
1 22 12
3 5
3 0
1 16 20
3 4
3 1
3 14
1 17 5
3 1
3 6
1 5 29
3 14
1 4 29
1 29 23
3 5
3 14
3 12
1 22 14
3 8
1 40 54
1 54 42
1 38 41
3 41
1 79 83
3 79
3 84
3 82
1 67 79
3 73
3 83
1 86 95
3 122
3 117
1 112 100
3 106
3 109
3 105
1 107 101
3 120
3 175
3 135
1 155 150
3 138
1 140 13...

output:

result:

ok 92 lines

Test #41:

score: 0

Accepted

time: 15ms

memory: 144708kb

input:

output:

result:

ok 92 lines

Test #42:

score: 0

Accepted

time: 19ms

memory: 144620kb

input:

output:

result:

ok 92 lines

Test #43:

score: 0

Accepted

time: 10ms

memory: 145036kb

input:

output:

result:

ok 92 lines

Test #44:

score: 0

Accepted

time: 7ms

memory: 144968kb

input:

output:

result:

ok 92 lines

Test #45:

score: 0

Accepted

time: 15ms

memory: 146104kb

input:

output:

result:

ok 92 lines

Test #46:

score: 0

Accepted

time: 11ms

memory: 145840kb

input:

output:

result:

ok 92 lines

Test #47:

score: 0

Accepted

time: 7ms

memory: 145176kb

input:

output:

result:

ok 92 lines

Test #48:

score: 0

Accepted

time: 11ms

memory: 144344kb

input:

output:

result:

ok 92 lines

Test #49:

score: 0

Accepted

time: 11ms

memory: 145728kb

input:

output:

result:

ok 94 lines

Test #50:

score: 0

Accepted

time: 16ms

memory: 145176kb

input:

output:

result:

ok 93 lines

Test #51:

score: 0

Accepted

time: 12ms

memory: 144652kb

input:

output:

result:

ok 92 lines

Test #52:

score: 0

Accepted

time: 11ms

memory: 145968kb

input:

1
30 150
1 1 16
1 16 30
3 2
1 18 2
3 1
1 22 20
3 2
1 1 26
3 2
1 8 29
1 3 29
1 17 27
3 6
3 37
3 33
3 38
1 45 35
3 34
3 46
1 33 39
3 33
3 50
3 60
1 62 33
3 33
3 70
3 78
3 65
1 64 69
3 74
1 74 90
3 66
1 77 64
3 122
3 123
1 109 116
3 75
3 98
3 126
1 122 111
3 93
1 138 142
3 154
1 143 133
3 146
1 188 178...

output:

result:

ok 92 lines

Test #53:

score: 0

Accepted

time: 19ms

memory: 146212kb

input:

output:

result:

ok 92 lines

Test #54:

score: 0

Accepted

time: 16ms

memory: 144828kb

input:

output:

result:

ok 92 lines

Test #55:

score: 0

Accepted

time: 11ms

memory: 145636kb

input:

output:

result:

ok 139 lines

Test #56:

score: 0

Accepted

time: 12ms

memory: 146264kb

input:

output:

result:

ok 149 lines

Subtask #3:

score: 4

Accepted

Dependency #1:

100%

Accepted

Test #57:

score: 4

Accepted

time: 15ms

memory: 145856kb

input:

0
2000 6000
1 1455 291
1 291 432
1 1253 432
3 1
3 2
1 1458 1253
1 1458 689
3 7
1 597 689
1 597 1759
1 143 1759
1 1655 143
1 1655 878
1 878 817
1 817 871
3 15
3 6
1 871 1188
3 7
1 1188 815
1 815 1414
1 1414 1304
3 22
1 1257 1304
3 19
1 1257 493
1 1654 493
1 1654 327
1 327 240
1 240 1873
1 1873 1717
3...

output:

result:

ok 2002 lines

Test #58:

score: 0

Accepted

time: 27ms

memory: 145488kb

input:

0
2000 6000
1 203 393
1 1271 393
1 1271 1708
3 3
3 1
1 1708 311
1 458 311
1 458 271
1 835 271
3 4
1 37 835
3 8
3 5
1 37 1647
3 4
1 845 1647
1 1097 845
1 1835 1097
1 554 1835
1 1141 554
1 1141 1619
1 1619 1046
3 14
1 1046 1112
3 7
3 11
1 1112 13
3 8
3 7
1 246 13
3 2
1 246 1582
3 29
1 1582 183
3 23
1 ...

output:

result:

ok 2002 lines

Test #59:

score: 0

Accepted

time: 24ms

memory: 145152kb

input:

0
2000 6000
1 30 1101
1 327 480
1 535 666
1 718 1543
1 1945 1388
1 452 143
3 6
1 633 162
1 1555 1503
3 9
1 1790 508
3 1
1 1819 191
1 1599 1322
1 464 571
3 9
1 164 1069
1 149 1911
1 205 1889
1 84 1336
3 18
3 3
3 8
1 1931 1058
3 13
3 0
3 1
1 1099 294
1 1423 427
1 778 525
3 26
1 1268 540
1 1654 1749
1 ...

output:

result:

ok 2002 lines

Test #60:

score: 0

Accepted

time: 7ms

memory: 146504kb

input:

0
2000 6000
1 2000 1575
3 1
1 1575 1079
3 2
3 4
1 236 2000
3 4
3 2
1 837 2000
1 1765 1079
3 6
1 1079 1120
1 15 236
1 236 828
3 1
1 837 454
1 954 837
1 1471 1765
1 86 1765
3 10
1 2 1120
1 1204 1120
3 10
1 15 415
1 367 15
1 1499 828
3 13
1 1330 828
1 454 487
1 454 234
3 30
1 954 1528
1 954 596
1 943 1...

output:

result:

ok 2002 lines

Test #61:

score: 0

Accepted

time: 17ms

memory: 145488kb

input:

0
2000 6000
1 1740 751
3 0
1 369 751
3 3
1 1740 85
1 437 1740
3 2
1 385 369
3 1
1 1859 369
1 85 981
3 7
1 85 552
3 6
1 437 73
1 437 1741
3 11
1 385 1614
1 1887 385
1 1859 904
1 1859 756
3 21
1 1833 981
1 771 981
3 22
1 552 1974
1 552 1462
3 10
3 20
1 73 1680
3 22
3 26
1 1081 73
1 263 1741
1 1741 180...

output:

result:

ok 2002 lines

Test #62:

score: 0

Accepted

time: 22ms

memory: 147964kb

input:

0
2000 6000
3 0
1 774 1866
1 317 1083
3 1
3 2
1 553 1192
1 278 37
1 365 1201
3 5
1 1519 219
1 1669 386
1 208 205
1 530 571
1 1629 222
3 7
3 7
1 478 1627
1 16 1884
1 73 632
1 1841 212
3 20
1 1978 227
3 19
3 14
1 1673 582
1 750 982
1 1165 1853
1 1758 1148
1 1818 1286
1 1726 1935
3 4
3 31
1 1735 1316
1...

output:

result:

ok 2002 lines

Test #63:

score: 0

Accepted

time: 23ms

memory: 145916kb

input:

0
2000 6000
1 803 12
1 12 1370
3 0
1 12 516
3 4
1 12 672
1 12 1639
1 773 803
1 632 803
1 1354 803
3 2
1 803 1580
1 803 1691
1 729 1370
1 1370 1553
1 816 1370
1 1370 1364
3 7
3 11
1 1987 1370
3 19
1 641 516
1 588 516
3 11
1 1725 516
1 516 1554
1 516 1442
3 26
3 9
1 672 1766
3 13
1 672 188
3 13
3 15
1...

output:

result:

ok 2002 lines

Test #64:

score: 0

Accepted

time: 20ms

memory: 144792kb

input:

0
2000 6000
1 370 898
1 898 1052
1 244 898
1 898 1930
1 504 898
1 370 866
1 370 1266
3 5
1 1630 370
1 915 370
3 4
1 603 370
3 10
1 1866 1052
3 10
1 429 1052
3 1
1 1052 804
1 1052 325
1 35 1052
1 70 244
1 244 1796
3 19
1 244 238
1 244 414
1 1954 244
3 16
1 1930 874
3 22
1 1930 646
3 13
3 20
3 11
1 19...

output:

result:

ok 2002 lines

Test #65:

score: 0

Accepted

time: 11ms

memory: 146228kb

input:

0
2000 6000
3 0
1 367 962
1 26 1974
1 1570 1132
1 1050 1612
1 132 1746
1 1855 1903
1 371 1689
3 8
3 1
1 262 312
1 392 1030
1 869 1920
1 1101 23
3 14
3 10
3 11
1 176 652
3 9
3 3
3 2
1 1837 40
1 1249 849
1 1888 1820
3 10
3 24
3 16
1 1289 1454
1 1698 1295
1 49 1286
1 1954 176
3 31
3 30
1 1672 564
3 2
3...

output:

result:

ok 2002 lines

Test #66:

score: 0

Accepted

time: 20ms

memory: 144796kb

input:

0
2000 6000
1 1761 851
1 1761 543
1 1761 638
3 3
1 1761 615
3 4
3 1
1 1761 1629
3 3
1 1761 922
3 5
3 9
1 1495 1761
1 1321 1761
1 1761 1185
1 30 1761
3 9
1 426 1761
3 14
1 1761 941
1 295 1761
1 1761 905
1 1650 1761
3 4
1 659 1761
3 24
1 274 1761
1 46 1761
1 1761 1636
1 1348 1761
3 0
1 1761 1385
3 21
...

output:

result:

ok 2002 lines

Test #67:

score: 0

Accepted

time: 11ms

memory: 145680kb

input:

output:

result:

ok 2002 lines

Test #68:

score: 0

Accepted

time: 20ms

memory: 147624kb

input:

output:

result:

ok 2002 lines

Test #69:

score: 0

Accepted

time: 14ms

memory: 145312kb

input:

0
2000 6000
1 928 1128
1 1128 836
3 2
1 1743 1128
3 3
1 1128 309
1 1128 1361
1 1977 1128
1 95 1128
3 8
1 1128 93
1 1128 1804
1 1037 1128
3 0
1 1128 1282
1 1128 1887
1 1954 1128
3 6
1 1810 1128
1 1128 447
3 1
3 2
1 1128 12
1 1128 905
3 18
1 152 1128
1 1128 1576
1 396 1128
3 22
3 21
1 414 928
1 928 92...

output:

result:

ok 2002 lines

Test #70:

score: 0

Accepted

time: 16ms

memory: 145084kb

input:

0
2000 6000
1 1734 1244
1 55 1734
1 1734 1406
1 1734 1778
3 1
1 823 1734
3 6
1 1734 239
1 1951 1734
3 4
1 1795 1734
1 102 1734
3 7
3 7
1 1734 374
3 10
3 1
1 1239 1734
3 13
1 1103 1734
1 1734 373
1 1734 213
1 1734 1086
1 1734 1892
1 1969 1734
3 1
1 1734 1678
3 7
3 10
1 1857 1734
3 11
1 1911 1734
3 15...

output:

result:

ok 2002 lines

Test #71:

score: 0

Accepted

time: 15ms

memory: 146676kb

input:

0
2000 6000
3 0
1 1919 1490
1 1545 272
3 2
3 0
1 1699 1355
3 3
3 2
3 6
3 3
1 669 1969
3 2
3 6
1 1116 818
1 336 1584
1 1774 137
1 799 1168
3 14
1 645 729
1 837 876
3 4
1 1034 43
1 389 1869
1 966 872
1 2000 791
1 355 754
1 1065 1359
3 26
3 13
1 267 425
1 22 734
3 20
3 31
3 22
3 8
1 1770 1631
3 22
3 17...

output:

result:

ok 2002 lines

Test #72:

score: 0

Accepted

time: 12ms

memory: 145260kb

input:

0
1999 6000
1 1774 429
1 429 1860
3 2
1 1860 676
3 4
1 206 676
1 206 1533
3 2
3 7
1 1533 848
3 6
1 84 848
1 690 84
1 1757 690
1 593 1757
3 15
1 561 593
1 991 561
3 4
3 17
1 991 1411
3 11
1 1411 81
3 6
1 1673 81
3 10
1 888 1673
1 1651 888
3 20
1 1763 1651
3 26
1 1352 1763
1 259 1352
3 12
3 34
1 159 2...

output:

result:

ok 2004 lines

Test #73:

score: 0

Accepted

time: 17ms

memory: 145480kb

input:

0
1999 5999
1 732 101
1 101 377
3 2
3 2
1 1425 732
3 0
1 72 732
1 1697 377
3 3
3 7
1 1399 377
1 1425 1606
1 67 1425
3 4
1 72 1306
3 10
1 72 900
3 16
1 1613 1697
1 1697 1433
3 19
3 6
1 394 1399
3 10
1 1399 43
1 1821 1606
1 1606 1411
1 67 804
1 1317 67
3 10
3 15
1 823 1306
1 1306 654
1 1816 900
3 11
3...

output:

result:

ok 2003 lines

Test #74:

score: 0

Accepted

time: 15ms

memory: 145920kb

input:

0
2000 6000
1 1993 265
1 1767 265
1 265 712
1 1767 1266
3 0
3 1
1 517 1266
1 1496 517
1 517 1321
1 1767 435
1 435 527
1 834 517
3 7
1 517 485
1 517 1161
3 1
1 1161 552
1 485 1477
3 4
3 5
1 527 721
1 552 1912
1 1767 519
3 0
1 18 1767
3 22
1 435 244
1 449 1912
3 19
1 1912 922
3 7
1 1067 922
3 21
1 244...

output:

result:

ok 2002 lines

Test #75:

score: 0

Accepted

time: 26ms

memory: 146252kb

input:

0
2000 6000
1 559 1394
1 1394 1989
1 1843 1989
3 3
1 1843 301
1 301 1621
1 841 301
1 301 1178
1 841 1356
1 1178 1976
1 1669 841
3 3
1 1669 1562
3 7
1 1178 659
1 1976 1644
3 16
1 1501 659
3 16
3 19
1 1356 1197
1 1356 311
3 10
1 311 435
1 311 540
3 14
1 1989 1032
3 15
1 1356 172
1 1197 449
3 0
1 1987 ...

output:

result:

ok 2002 lines

Test #76:

score: 0

Accepted

time: 16ms

memory: 145620kb

input:

0
2000 6000
1 1023 824
3 0
3 2
1 889 21
1 1483 426
1 24 626
1 1393 1500
1 663 1284
1 858 1082
1 1254 272
1 557 517
1 1635 309
1 1486 1373
1 1980 978
1 1063 1459
1 2000 1225
1 608 116
1 785 1310
1 300 1362
3 5
3 14
3 19
3 18
3 18
1 805 1686
1 1760 523
1 816 1350
1 1691 591
1 376 892
1 482 729
3 0
3 9...

output:

result:

ok 2002 lines

Test #77:

score: 0

Accepted

time: 20ms

memory: 145656kb

input:

0
2000 6000
1 1836 1295
1 1270 1323
3 2
1 1207 790
3 1
3 4
1 1264 886
3 0
1 773 1387
1 216 1519
1 1566 1204
1 953 1308
3 9
1 215 1251
1 1233 162
3 1
1 1514 1111
1 445 530
1 475 1181
1 166 1969
3 3
3 14
3 19
3 5
3 1
1 1464 215
3 8
1 1908 1456
3 5
3 4
1 1046 980
1 789 1426
1 750 1508
3 8
3 14
3 22
1 1...

output:

result:

ok 2002 lines

Test #78:

score: 0

Accepted

time: 22ms

memory: 145828kb

input:

output:

result:

ok 6000 lines

Test #79:

score: 0

Accepted

time: 15ms

memory: 145908kb

input:

output:

result:

ok 6000 lines

Subtask #4:

score: 2

Accepted

Dependency #2:

100%

Accepted

Test #80:

score: 2

Accepted

time: 21ms

memory: 145912kb

input:

1
2000 6000
1 122 748
3 1
1 29 123
3 0
1 31 835
1 835 277
1 1395 277
3 7
1 1407 320
1 320 1690
1 1059 1690
3 10
1 113 1032
1 113 1880
1 1504 1880
1 1624 1504
1 1828 1624
3 38
1 251 1883
1 251 640
1 879 640
3 79
1 80 956
3 158
1 65 1297
1 1267 1297
1 1267 962
3 138
3 214
3 199
3 211
3 210
1 905 530
3...

output:

result:

ok 2002 lines

Test #81:

score: 0

Accepted

time: 24ms

memory: 146012kb

input:

1
2000 6000
1 1852 193
1 1852 428
1 1656 428
3 0
1 1662 1510
3 6
1 1514 1144
3 12
1 1259 1149
1 193 1259
3 5
1 820 210
1 1103 820
1 582 1103
1 1156 582
1 1156 429
1 429 818
1 707 818
1 707 940
3 27
1 134 968
1 338 134
1 338 1316
1 1333 1316
1 1665 1333
3 107
1 1781 1579
1 53 1781
3 206
1 1564 26
1 1...

output:

result:

ok 2002 lines

Test #82:

score: 0

Accepted

time: 11ms

memory: 146608kb

input:

1
2000 6000
3 0
3 0
1 538 1450
3 0
3 3
1 371 277
1 1292 996
1 846 423
1 327 166
1 708 1178
1 406 23
1 175 217
3 9
1 1293 1353
1 481 503
1 146 354
1 862 1857
1 1269 781
1 1676 193
1 220 1292
3 9
3 8
1 1126 907
1 759 26
1 1479 1644
1 220 1650
3 13
1 1011 1556
3 26
3 4
1 984 117
3 20
3 16
1 571 472
1 1...

output:

result:

ok 2002 lines

Test #83:

score: 0

Accepted

time: 7ms

memory: 144752kb

input:

1
2000 6000
1 237 1698
3 1
3 3
1 1078 236
1 1416 1699
3 3
1 978 1700
1 1073 1823
1 1052 1073
1 979 1423
1 1423 290
3 4
1 1599 1008
3 37
3 33
1 1579 1017
3 45
1 1838 150
1 1838 569
1 1069 1018
3 59
1 1089 997
1 910 204
3 78
1 1770 941
1 1881 348
3 115
3 143
1 1289 445
3 131
1 1712 821
3 164
1 1937 17...

output:

result:

ok 2002 lines

Test #84:

score: 0

Accepted

time: 21ms

memory: 147624kb

input:

1
2000 6000
1 1872 557
1 1872 197
1 557 627
3 2
1 555 654
1 195 1185
1 195 74
3 6
3 18
1 614 1466
1 497 614
3 30
1 1428 684
3 34
1 677 276
3 45
1 1876 1168
3 53
3 80
1 1412 1253
3 76
1 1078 2
1 2 715
3 75
1 842 1478
1 1842 1478
3 112
3 152
1 1351 364
1 364 193
1 590 1336
3 149
1 877 1294
1 197 391
1...

output:

result:

ok 2002 lines

Test #85:

score: 0

Accepted

time: 35ms

memory: 145000kb

input:

1
2000 6000
3 0
1 2000 63
1 1297 592
1 651 1184
1 949 476
3 0
1 1399 1451
1 627 1486
3 12
1 1633 760
1 728 1722
1 1612 677
3 10
1 1642 1890
3 11
3 5
1 1075 875
3 1
1 1457 815
1 695 511
1 1201 503
1 187 1233
1 607 1434
1 919 1957
1 809 6
1 897 77
3 1
1 1952 853
1 601 832
3 9
1 1206 1522
3 12
3 21
3 6...

output:

result:

ok 2002 lines

Test #86:

score: 0

Accepted

time: 28ms

memory: 145568kb

input:

1
2000 6000
1 1818 696
1 1818 1960
1 560 1818
1 1818 1900
1 1818 939
1 696 1760
3 4
3 23
1 1930 685
3 23
1 676 803
3 20
1 338 668
3 35
3 36
1 631 661
3 44
1 1951 1001
1 846 1951
3 51
3 93
1 547 2022
1 2022 690
1 270 2022
1 795 638
3 89
3 144
1 751 696
1 321 696
1 696 1300
3 137
1 412 654
1 2002 1110...

output:

result:

ok 2002 lines

Test #87:

score: 0

Accepted

time: 16ms

memory: 146612kb

input:

1
2000 6000
1 297 1312
3 1
1 386 296
1 296 746
1 457 296
1 296 1185
1 396 1313
1 1313 445
3 1
3 27
3 20
1 1340 884
3 31
1 1284 1201
1 1284 134
3 38
1 436 1686
3 63
1 449 149
3 72
1 461 830
3 64
3 92
1 551 472
1 1557 472
1 331 688
1 266 688
3 92
1 626 1079
1 626 1587
3 144
1 314 597
1 374 1696
1 1413...

output:

result:

ok 2002 lines

Test #88:

score: 0

Accepted

time: 16ms

memory: 145540kb

input:

1
2000 6000
3 0
3 1
3 1
1 591 1379
3 0
1 703 535
1 1018 863
3 3
3 2
1 1360 1900
1 179 887
1 475 1780
3 11
1 1863 138
3 13
1 169 50
1 1325 1423
1 1014 651
1 1047 936
1 1940 439
3 2
3 31
1 178 62
3 27
1 1799 302
1 1839 876
1 887 851
1 308 921
1 1965 551
3 0
1 262 1479
1 497 556
1 1681 281
1 293 1362
1...

output:

result:

ok 2002 lines

Test #89:

score: 0

Accepted

time: 16ms

memory: 146300kb

input:

1
2000 6000
1 1217 743
1 217 1217
1 40 1217
3 1
3 6
1 1223 1247
1 778 1223
1 1223 469
1 1094 1223
1 1778 1223
1 1550 1223
1 653 1223
1 1223 1072
3 0
1 1155 941
3 75
3 75
3 95
1 904 1167
3 67
1 1178 736
3 94
1 1192 1175
1 783 1192
3 99
1 1097 257
1 613 1097
3 143
1 145 1130
1 1130 936
1 906 1130
1 11...

output:

result:

ok 2002 lines

Test #90:

score: 0

Accepted

time: 20ms

memory: 145728kb

input:

output:

result:

ok 2002 lines

Test #91:

score: 0

Accepted

time: 7ms

memory: 145288kb

input:

output:

result:

ok 2002 lines

Test #92:

score: 0

Accepted

time: 20ms

memory: 144720kb

input:

1
2000 6000
1 76 1149
1 76 1087
3 2
3 1
1 79 1564
1 84 79
3 2
1 1147 70
3 8
1 1726 67
3 10
1 918 89
3 29
1 1069 80
1 80 723
3 31
1 97 891
1 97 971
1 1526 97
3 46
1 2 900
3 76
3 86
1 262 23
1 1099 23
1 1035 23
3 90
1 196 1422
1 196 1974
1 271 196
3 155
1 153 242
1 1219 1469
1 1219 1619
3 174
1 1152 9...

output:

result:

ok 2002 lines

Test #93:

score: 0

Accepted

time: 20ms

memory: 146380kb

input:

1
2000 6000
1 854 1405
1 1603 854
3 2
1 853 1067
3 7
1 1182 848
3 7
3 8
1 860 1605
3 10
1 857 356
1 563 857
1 857 1261
1 206 857
1 901 857
1 857 1609
1 857 607
1 857 1053
1 857 973
1 193 857
3 13
1 1705 814
1 407 814
3 111
3 153
1 975 2020
3 137
1 1357 1021
1 764 1021
1 1494 961
3 172
1 1434 1081
3 ...

output:

result:

ok 2002 lines

Test #94:

score: 0

Accepted

time: 18ms

memory: 146156kb

input:

1
2000 6000
3 0
3 0
1 406 304
3 1
1 1812 1549
1 1226 151
3 7
3 1
1 1953 1790
1 1304 1179
1 478 1304
1 307 1140
3 8
3 5
1 1267 1215
1 256 1336
3 10
1 1200 1762
3 12
1 1354 698
3 8
3 28
1 1662 702
1 16 120
1 1967 843
1 1770 1562
3 14
1 821 1379
1 1635 827
1 1555 1876
1 213 386
3 15
3 17
1 1101 646
1 1...

output:

result:

ok 2002 lines

Test #95:

score: 0

Accepted

time: 16ms

memory: 146208kb

input:

1
1999 6000
1 321 396
3 1
1 1753 397
1 1753 144
1 144 1241
1 1241 454
3 2
3 8
3 11
1 833 456
1 1232 833
1 429 1232
1 897 429
1 897 969
3 12
1 1143 1009
3 59
1 1026 1846
3 67
1 320 1850
1 320 831
1 1 831
3 72
1 399 55
1 399 678
3 105
1 170 583
3 140
1 1644 152
1 136 1644
1 136 533
3 160
1 601 270
3 2...

output:

result:

ok 2004 lines

Test #96:

score: 0

Accepted

time: 15ms

memory: 147580kb

input:

1
1999 5999
1 862 892
1 1004 892
3 1
3 0
1 861 848
3 2
1 256 856
1 1002 1101
3 2
1 995 961
1 1843 860
1 920 860
3 14
1 1255 290
1 919 290
3 39
3 39
1 1148 887
1 963 1148
1 1017 1692
3 62
3 75
1 917 903
1 1895 130
3 94
1 1860 2033
1 1007 39
1 1007 2045
3 120
1 2039 1128
1 1128 696
1 1278 792
1 252 79...

output:

result:

ok 2003 lines

Test #97:

score: 0

Accepted

time: 11ms

memory: 145168kb

input:

1
2000 6000
1 609 259
3 0
1 608 641
3 2
1 643 221
1 1127 221
1 256 613
3 0
3 10
1 409 617
1 209 1221
1 409 515
3 12
1 578 1266
1 1464 434
3 40
1 417 388
3 57
3 76
1 590 1180
3 72
1 1181 1168
3 76
1 1479 1660
3 86
1 474 1591
3 98
1 459 1858
1 1290 494
3 119
3 132
1 1955 445
3 137
1 1147 1144
1 151 17...

output:

result:

ok 2002 lines

Test #98:

score: 0

Accepted

time: 21ms

memory: 146236kb

input:

1
2000 6000
1 1088 841
3 1
3 3
1 840 764
1 1516 764
1 184 1516
3 5
3 12
1 698 759
1 759 310
1 179 1203
1 1203 175
1 175 1797
1 1174 1203
1 698 1810
1 1797 1178
1 794 1511
1 1843 175
3 8
1 1273 1077
3 96
1 1256 706
1 1192 1060
1 522 1192
1 302 1060
3 107
3 177
1 1070 1611
1 1058 1230
1 1611 646
3 171...

output:

result:

ok 2002 lines

Test #99:

score: 0

Accepted

time: 7ms

memory: 146428kb

input:

1
2000 6000
1 80 1939
1 121 1631
3 1
3 1
3 1
3 0
1 546 1609
1 1663 904
1 311 1360
1 410 1985
1 390 1767
3 10
1 368 721
1 1590 62
1 1176 515
1 95 1682
1 98 530
1 75 578
1 361 956
1 1051 244
1 2 71
3 1
1 1610 450
1 399 1298
3 0
1 1546 1882
1 487 1378
1 1039 1228
1 1513 1862
3 16
1 35 1139
3 21
1 1746 ...

output:

result:

ok 2002 lines

Test #100:

score: 0

Accepted

time: 15ms

memory: 145308kb

input:

1
2000 6000
3 0
1 838 577
1 953 369
3 0
1 1030 247
1 191 1389
1 1990 1730
1 355 199
1 1990 517
3 11
1 1789 216
1 391 319
1 1286 188
3 11
3 1
1 687 875
1 1093 1089
1 1062 1034
3 4
1 1558 824
1 1752 355
1 1759 1033
3 1
1 1145 101
3 7
1 1630 707
1 1191 781
3 24
3 4
1 1115 622
1 1406 1419
3 15
1 1353 97...

output:

result:

ok 2002 lines

Test #101:

score: 0

Accepted

time: 15ms

memory: 145484kb

input:

1
2000 6000
1 428 1670
3 1
1 661 429
1 1999 1671
3 0
1 1992 68
3 6
1 1481 72
3 14
1 266 667
3 5
3 22
1 272 151
1 1980 87
3 21
1 496 1933
3 42
3 33
1 175 559
1 111 611
3 43
1 295 0
3 71
1 122 299
3 66
1 429 533
1 318 703
3 90
3 99
3 100
1 398 187
1 250 517
1 1627 250
1 1195 76
3 107
3 187
1 475 1404
...

output:

result:

ok 5799 lines

Test #102:

score: 0

Accepted

time: 11ms

memory: 146308kb

input:

output:

result:

ok 5999 lines

Subtask #5:

score: 4

Accepted

Dependency #3:

100%

Accepted

Test #103:

score: 4

Accepted

time: 126ms

memory: 165576kb

input:

0
100000 300000
1 72195 62466
1 62466 62453
1 86364 62453
1 51654 86364
1 43288 51654
1 43288 16339
1 16339 787
1 787 92480
3 7
1 6912 92480
3 2
1 33178 6912
3 11
1 33178 67163
1 53048 67163
3 4
1 80720 53048
1 5642 80720
1 5642 84104
3 9
3 16
1 13753 84104
1 97278 13753
3 20
1 9284 97278
1 54758 92...

output:

result:

ok 100002 lines

Test #104:

score: 0

Accepted

time: 124ms

memory: 168272kb

input:

0
100000 300000
1 11870 97470
3 0
1 60002 11870
1 61666 60002
3 4
1 61666 25652
1 25652 13707
1 13707 2473
1 53160 2473
1 53160 45334
1 45334 66111
3 7
1 8288 66111
3 7
1 89745 8288
1 89745 3852
1 64527 3852
3 5
3 2
3 18
3 20
1 65152 64527
1 65152 50492
3 22
1 50492 1662
3 9
1 1662 33947
1 5953 3394...

output:

result:

ok 100002 lines

Test #105:

score: 0

Accepted

time: 99ms

memory: 164728kb

input:

0
100000 300000
3 0
1 445 42657
1 90268 18417
3 3
3 4
3 5
1 54366 42709
1 46347 22032
1 1991 72714
3 2
1 65651 75593
1 93754 22278
1 2570 51242
3 3
1 58694 48713
3 6
1 40757 18965
1 11154 14248
3 9
1 74760 34938
3 2
1 60059 72444
1 65817 52131
1 4793 65455
3 12
1 12455 22385
1 53103 71160
3 26
3 21
...

output:

result:

ok 100002 lines

Test #106:

score: 0

Accepted

time: 130ms

memory: 167924kb

input:

0
100000 300000
1 79124 60591
3 1
1 60591 33308
1 99848 79124
1 15484 79124
3 1
3 1
1 67345 33308
1 33308 63899
3 7
1 99848 51598
1 57766 99848
1 15484 15981
1 15484 99822
1 5033 67345
3 13
1 39274 67345
1 63899 113
3 1
1 63899 29708
1 51598 82494
3 20
1 51920 51598
1 57766 32553
3 15
1 57766 55141
...

output:

result:

ok 100002 lines

Test #107:

score: 0

Accepted

time: 482ms

memory: 168928kb

input:

0
100000 300000
1 34920 94436
3 0
1 34920 79412
1 47623 94436
1 67893 94436
3 4
1 79412 88298
3 5
1 75095 79412
1 65281 47623
1 47623 44673
1 16510 67893
1 96935 67893
1 88298 40672
3 5
1 88298 60535
3 5
1 78916 75095
3 9
1 75095 33325
1 15591 65281
3 21
1 18050 65281
3 7
1 44673 2284
1 41794 44673
...

output:

result:

ok 100002 lines

Test #108:

score: 0

Accepted

time: 122ms

memory: 164680kb

input:

0
100000 300000
1 43634 61890
3 1
1 2885 53168
1 59059 65822
1 17093 95967
1 76807 61886
1 50218 18376
1 8459 73477
1 87433 31277
1 9372 28733
1 6823 58840
1 63131 2967
1 30329 86055
1 22587 58582
1 9354 66972
1 64175 74737
3 14
1 49160 78305
3 7
1 11193 24661
1 59539 5125
1 8861 35993
1 91433 83716...

output:

result:

ok 100002 lines

Test #109:

score: 0

Accepted

time: 131ms

memory: 167952kb

input:

0
100000 300000
1 62627 43009
1 15136 62627
1 89805 62627
3 1
1 56054 43009
1 38460 43009
3 2
3 5
1 29007 43009
1 54981 15136
1 15136 67471
3 3
3 10
1 15136 48523
1 5726 89805
1 89805 1851
3 5
3 0
1 89805 14880
3 13
1 67713 56054
1 28935 56054
1 9841 56054
1 38460 16943
3 22
3 19
1 68714 38460
3 24
...

output:

result:

ok 100002 lines

Test #110:

score: 0

Accepted

time: 455ms

memory: 171960kb

input:

0
100000 300000
1 2984 28134
3 0
1 7700 2984
1 2984 8636
3 2
1 43994 28134
3 0
1 28134 93496
3 7
1 28134 81009
3 2
3 10
1 7700 59394
1 95760 7700
1 69198 7700
1 8636 27687
1 8636 13241
1 97986 8636
1 43994 7427
1 39108 43994
3 17
1 88476 43994
3 0
3 6
3 12
1 93496 39398
3 13
3 24
1 1253 93496
1 1946...

output:

result:

ok 100002 lines

Test #111:

score: 0

Accepted

time: 123ms

memory: 165044kb

input:

0
100000 300000
1 74091 88079
1 8548 69001
3 0
1 77641 86477
1 19229 58507
1 57286 72793
3 3
3 5
3 7
3 1
1 55572 42735
1 66049 87066
3 3
1 69673 75611
3 10
3 1
3 3
1 39369 3726
1 46715 10718
1 19482 14246
1 44173 55751
3 11
1 38150 61009
1 15868 98898
3 21
3 14
1 27867 34566
1 289 77427
1 18660 3520...

output:

result:

ok 100002 lines

Test #112:

score: 0

Accepted

time: 156ms

memory: 169076kb

input:

0
100000 300000
1 59572 68591
1 68591 4254
1 68591 84502
1 35835 68591
3 1
1 68591 47266
3 1
3 0
1 586 68591
3 9
1 68591 72215
3 11
1 88078 68591
1 87706 68591
3 11
1 41466 68591
1 17371 68591
3 13
1 68591 9772
1 68591 62922
1 91786 68591
1 68591 51603
3 21
1 68591 40629
3 22
1 90139 68591
3 24
3 17...

output:

result:

ok 100002 lines

Test #113:

score: 0

Accepted

time: 147ms

memory: 168140kb

input:

0
100000 300000
1 37764 40010
1 37764 68671
1 37764 15539
3 2
1 98913 37764
1 89679 37764
3 6
1 73501 37764
1 33044 37764
3 9
3 6
1 61405 37764
1 37764 81109
1 34707 37764
3 8
3 13
1 99431 37764
1 37764 69411
1 37764 8630
1 10893 37764
3 20
1 37764 30179
1 37764 21219
1 37764 54825
3 18
3 0
1 39456 ...

output:

result:

ok 100002 lines

Test #114:

score: 0

Accepted

time: 161ms

memory: 161800kb

input:

0
100000 300000
1 6047 21195
1 6047 8377
3 1
3 3
3 2
1 81691 6047
3 0
1 69789 6047
3 0
3 2
1 79256 6047
1 34880 6047
1 88038 6047
1 64166 6047
1 6047 16633
3 14
1 89485 6047
1 39994 6047
3 2
1 6047 71580
1 6047 59334
1 6047 25195
1 70188 6047
1 82596 6047
1 6047 24636
1 20417 6047
1 6047 33865
3 4
1...

output:

result:

ok 100002 lines

Test #115:

score: 0

Accepted

time: 137ms

memory: 165416kb

input:

0
100000 300000
1 26294 39353
1 26294 92612
3 2
1 92365 26294
1 26294 97204
1 31460 26294
3 4
1 26294 7889
3 1
1 44650 26294
1 81305 26294
1 26294 56319
3 8
1 77115 26294
1 29657 26294
1 26294 15454
3 12
1 95514 26294
1 2876 26294
1 26294 38831
1 26294 87562
3 18
1 26294 15741
1 87495 26294
1 64846 ...

output:

result:

ok 100002 lines

Test #116:

score: 0

Accepted

time: 166ms

memory: 168140kb

input:

0
100000 300000
1 60333 58346
1 60333 77468
1 60333 65305
1 60333 91740
3 1
1 60333 18091
3 0
1 60333 35286
1 1506 60333
1 98645 60333
1 60333 35023
3 4
1 60333 50978
1 50968 60333
1 60333 86478
3 5
1 60333 72268
3 8
1 60333 97423
1 31251 60333
1 73838 60333
3 18
1 60333 23317
3 15
3 18
1 402 60333
...

output:

result:

ok 100002 lines

Test #117:

score: 0

Accepted

time: 187ms

memory: 162136kb

input:

0
100000 300000
1 42647 94988
1 44631 8022
3 2
1 21549 30952
1 70306 52833
1 74983 89688
1 32977 4860
1 6250 94762
3 0
1 13151 69445
1 60398 2629
3 11
1 25890 85312
1 22376 81350
1 30352 41499
1 34718 70586
1 89100 87969
1 46227 84340
3 4
1 6043 95381
1 98931 86111
3 18
3 20
3 20
1 94654 65362
3 23
...

output:

result:

ok 100002 lines

Test #118:

score: 0

Accepted

time: 119ms

memory: 166116kb

input:

0
99999 300000
1 5780 34189
3 0
1 78013 34189
3 2
3 4
1 78013 21274
1 21274 45121
3 4
1 45121 33204
1 36762 33204
1 64889 36762
1 64889 196
3 12
3 1
1 196 43874
3 10
1 43874 32298
3 4
3 15
1 32298 58522
3 1
1 93023 58522
3 14
1 93023 18892
3 10
1 18892 70202
3 9
1 70202 78990
1 40195 78990
3 5
1 902...

output:

result:

ok 100004 lines

Test #119:

score: 0

Accepted

time: 496ms

memory: 172092kb

input:

0
99999 299999
1 57447 57519
3 0
1 57519 46429
1 1510 57447
1 57447 92671
1 46429 6530
1 12917 46429
1 29884 1510
3 2
1 78588 1510
1 92671 10407
3 9
1 92671 42980
1 15098 6530
1 68642 6530
1 81140 12917
1 52863 12917
1 62007 29884
1 42160 29884
1 78588 63160
3 3
3 13
3 22
1 73547 78588
1 10407 61680...

output:

result:

ok 100003 lines

Test #120:

score: 0

Accepted

time: 132ms

memory: 166408kb

input:

0
100000 300000
1 39740 35267
3 0
3 1
1 79605 39740
1 18089 39740
3 5
3 6
1 58475 39740
1 35061 18089
3 3
1 13033 58475
1 98714 13033
3 5
1 83122 98714
3 14
3 5
1 39247 35267
1 17331 35267
3 0
1 85216 83122
3 16
3 3
1 83122 10976
1 25428 79605
1 85216 81251
1 98714 80970
3 26
3 24
1 19094 85216
3 20...

output:

result:

ok 100002 lines

Test #121:

score: 0

Accepted

time: 412ms

memory: 169020kb

input:

0
100000 300000
1 77151 52807
1 77151 29457
1 54237 29457
1 29457 80060
3 2
1 80060 21959
3 4
1 80060 58831
1 46058 21959
3 8
1 46058 40013
1 6578 40013
1 29457 59932
3 5
1 6578 62071
1 43151 40013
3 5
1 43151 13640
3 9
3 1
3 15
1 58831 47735
3 13
1 29457 74380
3 19
1 74380 10656
3 3
1 43151 81761
3...

output:

result:

ok 100002 lines

Test #122:

score: 0

Accepted

time: 132ms

memory: 164852kb

input:

0
100000 300000
3 0
1 84210 30735
1 13643 40929
1 58925 40322
1 34555 64301
3 4
1 83500 53489
3 1
3 4
1 84397 61660
1 64164 27283
3 7
1 9890 37846
1 54909 94741
3 6
1 57103 43230
1 35299 67388
1 34307 25723
1 29056 54029
1 72922 61543
1 37964 16178
1 32304 32324
1 27473 38919
3 17
1 88544 52448
1 20...

output:

result:

ok 100002 lines

Test #123:

score: 0

Accepted

time: 131ms

memory: 165112kb

input:

0
100000 300000
1 6579 81506
1 18573 7685
1 46988 59688
1 78053 87676
3 4
1 14327 27680
1 57831 34949
3 6
3 1
3 2
1 82920 47589
1 36916 26278
1 41061 68190
1 35552 10053
3 11
3 3
1 89333 55923
1 66493 35063
1 3859 24185
1 6365 48050
1 3671 65998
1 12982 22246
3 17
1 50663 47565
1 85704 3309
3 11
1 1...

output:

result:

ok 100002 lines

Test #124:

score: 0

Accepted

time: 42ms

memory: 159016kb

input:

0
100000 300000
1 95226 76253
1 12545 95226
3 1
3 2
3 0
1 79193 12545
1 98963 95226
3 0
3 8
3 6
1 79193 8967
3 9
1 12545 55431
3 2
1 97726 8967
3 8
3 6
3 17
1 74052 55431
3 4
1 75782 55431
3 9
1 97365 12545
3 5
3 21
1 21035 97365
3 7
3 1
1 21035 43806
1 68481 21035
3 2
1 66380 21035
3 8
3 3
1 63556 ...

output:

result:

ok 299499 lines

Test #125:

score: 0

Accepted

time: 39ms

memory: 159428kb

input:

0
100000 300000
1 13104 26689
3 1
3 2
3 3
3 4
3 0
3 2
3 5
3 3
3 4
3 9
3 9
3 10
3 13
3 3
3 15
3 7
3 5
3 16
3 6
3 20
3 13
3 15
3 22
3 4
3 19
3 13
3 3
3 1
3 11
3 30
3 15
3 6
3 5
3 26
3 17
3 13
3 19
3 3
3 31
3 5
3 40
3 33
3 23
3 1
3 28
3 11
3 41
3 11
3 1
3 37
3 38
3 49
3 3
3 50
3 20
3 13
3 9
3 21
3 58
3...

output:

result:

ok 299999 lines

Subtask #6:

score: 5

Accepted

Dependency #4:

100%

Accepted

Test #126:

score: 5

Accepted

time: 127ms

memory: 167788kb

input:

1
100000 300000
1 99914 44637
1 54949 99914
1 30005 54949
1 30005 37908
1 82810 37908
3 3
1 82805 17647
1 81097 17647
3 14
1 81114 98590
3 20
1 98598 53663
1 8457 53663
1 12730 8457
3 36
1 21896 12764
1 21896 3379
1 54909 3379
3 76
3 97
1 54870 81162
1 81162 35892
1 35892 4762
3 126
1 4714 94599
1 9...

output:

result:

ok 100002 lines

Test #127:

score: 0

Accepted

time: 142ms

memory: 169008kb

input:

1
100000 300000
1 53751 11147
1 53034 53751
3 0
1 16314 53033
1 58774 16314
1 2799 58774
1 66417 2799
3 1
1 66407 44576
3 17
3 30
1 60919 44585
3 26
3 36
1 60879 48033
3 35
3 36
1 48040 72297
1 72297 19367
1 19367 44403
3 33
3 72
1 44304 67678
1 67678 63302
3 71
1 81342 63329
3 107
1 83300 81327
1 3...

output:

result:

ok 100002 lines

Test #128:

score: 0

Accepted

time: 116ms

memory: 164380kb

input:

1
100000 300000
1 33582 19533
1 47258 18382
1 22696 31850
1 94086 52377
3 3
1 86300 33706
1 47702 50164
1 3397 8500
1 50074 52765
1 45739 50765
1 92053 59741
1 83384 9304
1 72405 63932
3 4
1 61823 80383
3 10
1 15403 49828
1 19426 264
1 35081 99722
1 91422 14865
3 14
1 99621 37245
1 82078 54400
3 17
...

output:

result:

ok 100002 lines

Test #129:

score: 0

Accepted

time: 135ms

memory: 168084kb

input:

1
100000 300000
1 42346 68174
3 1
1 68175 46184
3 3
1 8807 42345
1 42345 98391
3 1
3 12
1 46179 44109
1 62557 46179
3 13
3 31
1 60425 8817
1 8817 57102
3 19
1 13370 98416
1 75804 98416
1 44131 1631
3 43
1 44037 91611
3 69
3 71
1 62489 52051
1 78769 62489
3 95
1 26172 60533
3 108
1 61192 60516
3 105
...

output:

result:

ok 100002 lines

Test #130:

score: 0

Accepted

time: 522ms

memory: 171588kb

input:

1
100000 300000
1 98712 91965
3 0
1 91964 21121
1 32324 98713
1 57450 98713
1 21121 16704
1 21121 85983
3 3
1 32336 40507
1 67603 32336
1 57470 18281
1 11067 57470
1 19764 16724
3 20
1 83349 16643
3 75
1 8488 85904
1 60883 85904
3 74
1 40519 9757
1 40519 31174
1 67695 89092
3 122
1 46642 67743
1 184...

output:

result:

ok 100002 lines

Test #131:

score: 0

Accepted

time: 142ms

memory: 164652kb

input:

1
100000 300000
1 65856 44769
1 33767 38882
1 45713 41739
3 1
1 34142 48384
3 1
3 2
3 6
3 5
1 43218 37203
3 0
1 24742 37318
1 39651 24106
1 86053 82059
3 1
3 7
3 10
3 6
1 17622 13174
1 88494 46204
1 85206 68675
3 3
1 36805 10327
1 84252 53232
1 38051 17993
3 19
1 69695 66449
1 979 73475
1 54152 2040...

output:

result:

ok 100002 lines

Test #132:

score: 0

Accepted

time: 139ms

memory: 168056kb

input:

1
100000 300000
1 77346 9535
3 1
1 67737 77347
3 3
1 29323 77345
1 62228 9532
1 9532 6805
1 9532 37746
3 0
1 67725 39180
1 8931 67725
1 23473 67725
3 21
1 29349 61806
1 29349 75812
1 37228 29349
3 45
1 36056 62297
3 73
1 1636 62284
1 62284 93121
1 6861 67680
1 6861 55530
3 94
1 6671 24486
3 139
1 30...

output:

result:

ok 100002 lines

Test #133:

score: 0

Accepted

time: 479ms

memory: 172536kb

input:

1
100000 300000
1 36375 83502
1 36375 71554
3 2
1 89283 36372
1 17767 83501
1 83501 67967
3 7
3 14
1 83489 11543
1 71565 8539
3 9
1 71582 3885
1 71582 6563
1 10714 89308
1 89308 48448
1 8081 89308
1 17784 71523
1 17784 70502
3 25
1 17677 32269
1 87911 67861
1 75677 67861
3 123
1 68069 69161
1 11649 ...

output:

result:

ok 100002 lines

Test #134:

score: 0

Accepted

time: 136ms

memory: 164840kb

input:

1
100000 300000
1 75001 64209
1 65078 87964
3 0
1 78084 7553
1 95881 21250
1 98188 34660
1 47763 49253
1 62160 1377
1 44730 28097
3 11
1 3359 65484
3 14
1 33124 25222
1 44698 37439
1 60348 91394
1 42191 62765
3 0
3 8
1 53245 18567
1 39160 68669
3 0
3 14
1 63959 18141
3 4
1 59168 44845
1 82443 65324
...

output:

result:

ok 100002 lines

Test #135:

score: 0

Accepted

time: 165ms

memory: 168324kb

input:

1
100000 300000
1 38620 95673
1 95673 40400
1 95673 29255
3 3
3 5
1 82515 95679
3 6
1 85030 95667
3 10
1 95670 3551
3 10
1 353 95660
1 44429 95660
1 95660 31629
1 95660 647
1 95660 32812
1 6745 95660
1 95660 84951
3 17
1 95714 53686
1 3186 95714
1 42456 95714
1 13958 95714
1 5058 95714
3 85
3 169
1 ...

output:

result:

ok 100002 lines

Test #136:

score: 0

Accepted

time: 169ms

memory: 169460kb

input:

1
100000 300000
1 67257 84745
1 78895 84745
1 38587 84745
3 0
1 84751 36895
3 6
1 84739 84007
1 79965 84739
3 13
1 84764 79386
1 84764 45458
3 31
1 80160 84781
1 83360 84781
3 33
1 84798 53640
3 48
1 65307 84811
3 79
1 56677 84807
1 84807 56586
1 84807 37808
3 92
1 84849 11858
3 118
3 159
1 56821 84...

output:

result:

ok 100002 lines

Test #137:

score: 0

Accepted

time: 159ms

memory: 164480kb

input:

1
100000 300000
1 16646 61601
3 1
3 1
3 1
3 1
1 40099 16647
1 39360 16647
3 1
3 2
1 16640 65842
3 7
3 15
1 99264 16652
1 70488 16652
1 34354 16652
3 9
3 16
1 16666 66271
1 39157 16666
1 16666 22235
3 31
1 16689 79600
3 62
1 16708 54804
1 16708 83419
1 8936 16708
1 49463 16708
1 63326 16708
1 16708 6...

output:

result:

ok 100002 lines

Test #138:

score: 0

Accepted

time: 137ms

memory: 168196kb

input:

1
100000 300000
1 92784 91105
1 92784 67883
1 92784 82125
1 81498 92784
1 92784 21745
1 39089 92784
1 86562 92784
3 3
3 31
3 30
1 92780 40871
3 30
1 48702 92756
3 36
3 40
3 32
1 72171 92765
1 92765 73534
1 80887 92765
1 93645 92765
1 45320 92765
1 92765 21359
1 92765 16817
1 5946 92765
1 21003 92765...

output:

result:

ok 100002 lines

Test #139:

score: 0

Accepted

time: 188ms

memory: 165852kb

input:

1
100000 300000
1 29294 49155
1 29294 105
1 44462 29294
1 51229 29294
1 56226 29294
1 83137 29294
1 29294 59373
3 3
3 26
3 21
1 29298 33174
1 2060 29298
1 29298 56946
3 23
1 29273 39718
1 41900 29273
1 29273 92968
3 59
1 52266 29237
3 86
1 29191 52544
1 29191 26831
1 96856 29191
3 126
3 158
1 29431 ...

output:

result:

ok 100002 lines

Test #140:

score: 0

Accepted

time: 201ms

memory: 164864kb

input:

1
100000 300000
1 76626 38193
3 0
3 0
1 67688 34462
1 84588 72007
1 42560 89029
3 5
3 2
1 45086 72626
3 6
1 88575 6166
3 12
1 99336 49243
3 14
3 6
3 1
1 31765 68181
1 58231 87459
1 92091 6102
3 0
1 69460 46964
3 24
1 2285 17385
1 36572 15073
1 42570 4480
3 4
1 40294 70049
1 66106 43544
3 1
1 88705 6...

output:

result:

ok 100002 lines

Test #141:

score: 0

Accepted

time: 132ms

memory: 169348kb

input:

1
99999 300000
1 70670 38693
3 1
3 3
3 3
3 2
1 9361 38692
1 3806 9361
1 3806 54206
3 3
3 14
1 54197 82459
1 82459 70072
3 8
1 37107 70055
1 37107 44343
1 4332 44343
3 27
3 46
1 91917 4308
1 12492 91917
1 67176 12492
1 67176 92312
3 63
3 93
3 72
1 43062 92398
1 19371 43062
1 51457 19371
3 79
1 51666 ...

output:

result:

ok 100004 lines

Test #142:

score: 0

Accepted

time: 523ms

memory: 172740kb

input:

1
99999 299999
1 27181 85267
1 13084 85267
1 27181 27345
1 27181 97390
1 13084 99184
1 20089 13084
1 27345 81674
1 27345 27813
1 97390 86294
1 58470 97390
3 8
1 99143 29623
1 63651 99143
3 63
1 20023 45905
1 20023 82207
3 76
1 81763 50643
1 81763 18800
1 27852 47482
1 27852 43011
1 86399 29431
1 775...

output:

result:

ok 100003 lines

Test #143:

score: 0

Accepted

time: 147ms

memory: 165368kb

input:

1
100000 300000
1 21514 12289
1 57603 21514
3 0
1 12290 62084
3 0
1 33652 62081
1 22251 57605
3 7
1 62088 48060
1 75799 33661
1 12302 64935
3 10
1 33622 85578
1 95837 62115
1 22217 98139
1 57639 94720
1 45541 48023
1 8140 94720
1 94720 27484
1 48023 63754
1 86259 27484
3 43
1 95968 37373
3 138
1 140...

output:

result:

ok 100002 lines

Test #144:

score: 0

Accepted

time: 402ms

memory: 170520kb

input:

1
100000 300000
1 90689 74241
1 90689 96076
3 0
1 33476 96079
3 0
1 33473 83595
1 98825 83595
3 3
1 74254 19616
1 98816 59700
1 83586 70929
1 19616 56593
1 33480 31235
1 31235 47902
1 33480 79207
3 3
1 42648 19681
1 85132 56656
1 47967 3907
1 79142 21018
1 37741 47967
3 75
3 138
1 96213 31469
3 145
...

output:

result:

ok 100002 lines

Test #145:

score: 0

Accepted

time: 139ms

memory: 161888kb

input:

1
100000 300000
1 65301 7528
1 87743 32248
3 1
1 79621 89781
3 3
3 0
3 0
1 76576 60411
3 6
1 64444 32845
1 77099 45808
1 35328 62931
3 14
1 6352 59945
1 91746 75816
1 85117 95765
1 56399 82790
3 10
1 41801 48452
1 17281 44459
1 76338 38234
1 87340 51387
3 15
1 10702 83365
1 11424 15951
1 84357 84662...

output:

result:

ok 100002 lines

Test #146:

score: 0

Accepted

time: 121ms

memory: 165484kb

input:

1
100000 300000
1 43435 97607
1 18572 48297
3 1
1 43469 57721
3 3
1 28096 26197
1 63261 86381
3 5
1 96716 25444
1 52334 91377
1 98687 16833
1 78885 55491
1 64685 59675
1 86204 57495
3 9
3 15
1 79045 42158
1 49268 32013
3 13
1 92181 87677
3 13
1 20089 80005
1 92583 95575
3 25
1 4585 15777
1 40397 640...

output:

result:

ok 100002 lines

Test #147:

score: 0

Accepted

time: 47ms

memory: 156300kb

input:

1
100000 300000
1 24481 84896
3 1
3 1
3 0
3 3
3 5
1 60869 84897
3 2
1 80358 60871
3 11
3 14
1 67283 80355
3 15
1 89498 80367
3 15
1 89503 69949
3 7
1 86876 69927
3 16
3 25
1 67273 62768
3 29
1 86893 93314
3 36
1 61129 89533
3 56
1 60915 84118
3 33
3 83
3 95
1 3748 80295
1 86795 58093
1 58093 85147
3...

output:

result:

ok 298999 lines

Test #148:

score: 0

Accepted

time: 43ms

memory: 157920kb

input:

1
100000 300000
1 98578 7949
3 0
3 1
3 3
3 3
3 4
3 7
3 0
3 9
3 4
3 9
3 11
3 6
3 7
3 15
3 2
3 8
3 10
3 2
3 0
3 5
3 4
3 1
3 20
3 19
3 17
3 9
3 23
3 21
3 15
3 0
3 1
3 1
3 0
3 29
3 9
3 19
3 33
3 9
3 37
3 31
3 23
3 39
3 5
3 27
3 25
3 12
3 17
3 34
3 48
3 14
3 11
3 50
3 41
3 40
3 23
3 2
3 8
3 51
3 30
3 53
...

output:

result:

ok 299999 lines

Subtask #7:

score: 0

Time Limit Exceeded

Dependency #6:

100%

Accepted

Test #149:

score: 5

Accepted

time: 942ms

memory: 245872kb

input:

1
500000 1500000
1 158685 390702
1 158685 259150
1 130956 259150
3 1
1 130954 474967
1 420812 474967
1 420812 219823
1 144097 219823
3 4
1 144123 60874
3 24
1 60914 308739
1 308739 458068
1 211634 458068
1 17155 211634
3 41
3 72
1 411007 17257
3 73
1 410986 230782
1 407170 230782
1 407170 372711
3 9...

output:

result:

ok 500002 lines

Test #150:

score: 0

Accepted

time: 995ms

memory: 246920kb

input:

1
500000 1500000
1 200108 224824
1 391043 224824
1 391043 467048
3 1
1 295129 467054
1 295129 406620
3 0
1 450821 406613
1 450821 377522
3 13
1 247357 377505
1 88385 247357
1 76954 88385
1 76954 260492
3 21
3 71
1 260562 428123
3 83
1 7015 428119
3 92
1 170386 7026
1 170386 266962
1 161663 266962
1 ...

output:

result:

ok 500002 lines

Test #151:

score: 0

Accepted

time: 752ms

memory: 227068kb

input:

1
500000 1500000
1 152139 71935
1 60623 244730
1 131546 106631
3 3
1 63236 342130
3 7
3 1
3 0
3 1
1 38633 329551
3 13
1 165797 388387
1 34106 129407
3 8
1 133906 286223
3 1
1 179634 443372
1 411121 77985
1 429810 278198
1 422220 105372
1 120289 422185
3 27
3 30
1 365219 151153
3 15
1 121340 95762
1 ...

output:

result:

ok 500002 lines

Test #152:

score: 0

Accepted

time: 921ms

memory: 244856kb

input:

1
500000 1500000
1 16388 198577
3 0
3 1
1 16389 361128
1 394949 198576
1 198576 350790
1 361128 279027
3 3
1 220419 361126
3 7
1 115947 394961
3 20
3 25
1 394968 133160
1 458556 350811
1 445822 350811
3 12
1 121281 278981
3 62
1 212640 278960
3 82
3 64
1 310335 220482
3 92
1 220503 187866
1 115877 3...

output:

result:

ok 500002 lines

Test #153:

score: -5

Time Limit Exceeded

input:

1
500000 1500000
1 492928 334787
1 492928 257389
1 334787 405750
3 1
1 17399 334789
1 63401 257387
1 151621 257387
1 320703 405744
3 1
1 405738 194723
1 17389 356147
3 30
1 17372 18586
1 63362 381673
1 63362 290474
1 151662 405490
1 151662 413297
3 37
1 320720 443038
3 102
3 114
1 320705 230391
1 23...

output: