QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#445292	#8809. Telephone Plans	Crysfly	11	72ms	77656kb	C++17	2.6kb	2024-06-16 00:55:03	2024-06-16 00:55:03

Judging History

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

[2024-06-16 00:55:03]
评测

测评结果：11
用时：72ms
内存：77656kb

查看

[2024-06-16 00:55:03]
提交

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 500005
#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);
	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()) 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());
	
	++idx;
	for(int x:s[1]) fa[x]=idx,c[fu].erase(x),c[idx].insert(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),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: 74224kb

input:

output:

result:

ok 147 lines

Test #2:

score: 0

Accepted

time: 7ms

memory: 75376kb

input:

output:

result:

ok 8 lines

Test #3:

score: 0

Accepted

time: 7ms

memory: 74660kb

input:

output:

result:

ok 92 lines

Test #4:

score: 0

Accepted

time: 4ms

memory: 75568kb

input:

output:

result:

ok 92 lines

Test #5:

score: 0

Accepted

time: 7ms

memory: 74872kb

input:

output:

result:

ok 92 lines

Test #6:

score: 0

Accepted

time: 7ms

memory: 74544kb

input:

output:

result:

ok 92 lines

Test #7:

score: 0

Accepted

time: 7ms

memory: 76068kb

input:

output:

result:

ok 92 lines

Test #8:

score: 0

Accepted

time: 9ms

memory: 75960kb

input:

output:

result:

ok 92 lines

Test #9:

score: 0

Accepted

time: 11ms

memory: 75112kb

input:

output:

result:

ok 92 lines

Test #10:

score: 0

Accepted

time: 7ms

memory: 74324kb

input:

output:

result:

ok 92 lines

Test #11:

score: 0

Accepted

time: 11ms

memory: 75632kb

input:

output:

result:

ok 92 lines

Test #12:

score: 0

Accepted

time: 3ms

memory: 74948kb

input:

output:

result:

ok 92 lines

Test #13:

score: 0

Accepted

time: 7ms

memory: 75672kb

input:

output:

result:

ok 92 lines

Test #14:

score: 0

Accepted

time: 7ms

memory: 75372kb

input:

output:

result:

ok 92 lines

Test #15:

score: 0

Accepted

time: 7ms

memory: 75224kb

input:

output:

result:

ok 92 lines

Test #16:

score: 0

Accepted

time: 15ms

memory: 75492kb

input:

output:

result:

ok 92 lines

Test #17:

score: 0

Accepted

time: 9ms

memory: 75664kb

input:

output:

result:

ok 92 lines

Test #18:

score: 0

Accepted

time: 7ms

memory: 75172kb

input:

output:

result:

ok 92 lines

Test #19:

score: 0

Accepted

time: 4ms

memory: 75720kb

input:

output:

result:

ok 92 lines

Test #20:

score: 0

Accepted

time: 12ms

memory: 75192kb

input:

output:

result:

ok 92 lines

Test #21:

score: 0

Accepted

time: 4ms

memory: 74992kb

input:

output:

result:

ok 94 lines

Test #22:

score: 0

Accepted

time: 10ms

memory: 73976kb

input:

output:

result:

ok 93 lines

Test #23:

score: 0

Accepted

time: 8ms

memory: 74816kb

input:

output:

result:

ok 92 lines

Test #24:

score: 0

Accepted

time: 8ms

memory: 75656kb

input:

output:

result:

ok 92 lines

Test #25:

score: 0

Accepted

time: 7ms

memory: 74808kb

input:

output:

result:

ok 92 lines

Test #26:

score: 0

Accepted

time: 18ms

memory: 74312kb

input:

output:

result:

ok 92 lines

Test #27:

score: 0

Accepted

time: 3ms

memory: 74272kb

input:

output:

result:

ok 139 lines

Test #28:

score: 0

Accepted

time: 15ms

memory: 74232kb

input:

output:

result:

ok 149 lines

Subtask #2:

score: 2

Accepted

Test #29:

score: 2

Accepted

time: 15ms

memory: 73968kb

input:

output:

result:

ok 147 lines

Test #30:

score: 0

Accepted

time: 15ms

memory: 75432kb

input:

output:

result:

ok 8 lines

Test #31:

score: 0

Accepted

time: 11ms

memory: 75732kb

input:

output:

result:

ok 92 lines

Test #32:

score: 0

Accepted

time: 4ms

memory: 74360kb

input:

output:

result:

ok 92 lines

Test #33:

score: 0

Accepted

time: 11ms

memory: 74504kb

input:

output:

result:

ok 92 lines

Test #34:

score: 0

Accepted

time: 7ms

memory: 75148kb

input:

output:

result:

ok 92 lines

Test #35:

score: 0

Accepted

time: 11ms

memory: 74560kb

input:

output:

result:

ok 92 lines

Test #36:

score: 0

Accepted

time: 15ms

memory: 74800kb

input:

output:

result:

ok 92 lines

Test #37:

score: 0

Accepted

time: 9ms

memory: 74864kb

input:

output:

result:

ok 92 lines

Test #38:

score: 0

Accepted

time: 7ms

memory: 75268kb

input:

output:

result:

ok 92 lines

Test #39:

score: 0

Accepted

time: 15ms

memory: 75560kb

input:

output:

result:

ok 92 lines

Test #40:

score: 0

Accepted

time: 11ms

memory: 75940kb

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: 9ms

memory: 74384kb

input:

output:

result:

ok 92 lines

Test #42:

score: 0

Accepted

time: 11ms

memory: 75232kb

input:

output:

result:

ok 92 lines

Test #43:

score: 0

Accepted

time: 7ms

memory: 74836kb

input:

output:

result:

ok 92 lines

Test #44:

score: 0

Accepted

time: 11ms

memory: 74720kb

input:

output:

result:

ok 92 lines

Test #45:

score: 0

Accepted

time: 11ms

memory: 74440kb

input:

output:

result:

ok 92 lines

Test #46:

score: 0

Accepted

time: 4ms

memory: 74728kb

input:

output:

result:

ok 92 lines

Test #47:

score: 0

Accepted

time: 11ms

memory: 75444kb

input:

output:

result:

ok 92 lines

Test #48:

score: 0

Accepted

time: 7ms

memory: 74216kb

input:

output:

result:

ok 92 lines

Test #49:

score: 0

Accepted

time: 7ms

memory: 74980kb

input:

output:

result:

ok 94 lines

Test #50:

score: 0

Accepted

time: 9ms

memory: 76056kb

input:

output:

result:

ok 93 lines

Test #51:

score: 0

Accepted

time: 3ms

memory: 74364kb

input:

output:

result:

ok 92 lines

Test #52:

score: 0

Accepted

time: 15ms

memory: 74512kb

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: 11ms

memory: 74724kb

input:

output:

result:

ok 92 lines

Test #54:

score: 0

Accepted

time: 11ms

memory: 74544kb

input:

output:

result:

ok 92 lines

Test #55:

score: 0

Accepted

time: 14ms

memory: 75752kb

input:

output:

result:

ok 139 lines

Test #56:

score: 0

Accepted

time: 11ms

memory: 73896kb

input:

output:

result:

ok 149 lines

Subtask #3:

score: 4

Accepted

Dependency #1:

100%

Accepted

Test #57:

score: 4

Accepted

time: 72ms

memory: 76524kb

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: 63ms

memory: 74584kb

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: 14ms

memory: 75656kb

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: 69ms

memory: 75612kb

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: 67ms

memory: 75056kb

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: 8ms

memory: 74496kb

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: 70ms

memory: 75244kb

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: 69ms

memory: 75508kb

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: 18ms

memory: 74872kb

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: 66ms

memory: 74656kb

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: 63ms

memory: 74768kb

input:

output:

result:

ok 2002 lines

Test #68:

score: 0

Accepted

time: 63ms

memory: 75680kb

input:

output:

result:

ok 2002 lines

Test #69:

score: 0

Accepted

time: 64ms

memory: 76384kb

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: 63ms

memory: 74416kb

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: 13ms

memory: 74808kb

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: 62ms

memory: 75024kb

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: 68ms

memory: 74612kb

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: 67ms

memory: 76380kb

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: 71ms

memory: 75428kb

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: 7ms

memory: 74176kb

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: 13ms

memory: 77656kb

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: 12ms

memory: 76076kb

input:

output:

result:

ok 6000 lines

Test #79:

score: 0

Accepted

time: 10ms

memory: 77260kb

input:

output:

result:

ok 6000 lines

Subtask #4:

score: 2

Accepted

Dependency #2:

100%

Accepted

Test #80:

score: 2

Accepted

time: 63ms

memory: 75148kb

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: 66ms

memory: 77164kb

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: 12ms

memory: 75228kb

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: 68ms

memory: 75020kb

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: 72ms

memory: 74776kb

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: 14ms

memory: 75196kb

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: 64ms

memory: 76112kb

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: 67ms

memory: 74508kb

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: 10ms

memory: 74680kb

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: 72ms

memory: 75680kb

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: 70ms

memory: 75328kb

input:

output:

result:

ok 2002 lines

Test #91:

score: 0

Accepted

time: 59ms

memory: 75204kb

input:

output:

result:

ok 2002 lines

Test #92:

score: 0

Accepted

time: 62ms

memory: 74600kb

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: 72ms

memory: 76180kb

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: 25ms

memory: 75056kb

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: 68ms

memory: 75356kb

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: 63ms

memory: 75884kb

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: 70ms

memory: 74728kb

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: 72ms

memory: 74760kb

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: 4ms

memory: 75824kb

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: 8ms

memory: 75728kb

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: 10ms

memory: 74504kb

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: 7ms

memory: 75864kb

input:

output:

result:

ok 5999 lines

Subtask #5:

score: 0

Time Limit Exceeded

Dependency #3:

100%

Accepted

Test #103:

score: 0

Time Limit Exceeded

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:

Subtask #6:

score: 0

Time Limit Exceeded

Dependency #4:

100%

Accepted

Test #126:

score: 0

Time Limit Exceeded

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: