QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#931660	#10179. 입자 가속기	WuMin4	100 ✓	357ms	49472kb	C++20	1.9kb	2025-03-11 15:40:56	2025-03-11 15:40:57

Judging History

This is the latest submission verdict.

[2025-03-11 15:40:57]
Judged

Verdict: 100
Time: 357ms
Memory: 49472kb

Show

[2025-03-11 15:40:56]
Submitted

answer

#include <bits/stdc++.h>
#define ls (u<<1)
#define rs ((u<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
int n,in[400005],out[400005],to[400005],f[400005],cnt,nw;
int c[1600005],lz[1600005],cc[400005];
vector<int> t[400005];
void add(int x,int v){
	while(x<=2*n) cc[x]+=v,x+=(x&-x);
}
int _qu(int x){
	int res=0;
	while(x) res+=cc[x],x-=(x&-x);
	return res;
}
int qu(int x,int y){
	return _qu(y)-_qu(x-1);
}
void push_up(int u){
	c[u]=max(c[ls],c[rs]);
}
void push_down(int u){
	if(lz[u])
		lz[ls]=max(lz[ls],lz[u]),lz[rs]=max(lz[rs],lz[u]),c[ls]=max(c[ls],lz[u]),c[rs]=max(c[rs],lz[u]),lz[u]=0;
}
void build(int u,int l,int r){
	if(l==r){
		c[u]=1;
		return;
	} 
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void upd(int u,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y){
		c[u]=max(c[u],v);
		lz[u]=max(lz[u],v);
		return;
	}
	push_down(u);
	if(x<=mid)
		upd(ls,l,mid,x,y,v);
	if(mid<y)
		upd(rs,mid+1,r,x,y,v);
	push_up(u);
}
int qur(int u,int l,int r,int x){
	if(l==r)
		return c[u];
	push_down(u);
	if(x<=mid)
		return qur(ls,l,mid,x);
	else
		return qur(rs,mid+1,r,x);
}
void dfs(int x,int fa){
	in[x]=++cnt,to[cnt]=x,f[x]=fa;
	for(int v:t[x])
		if(v!=fa) dfs(v,x);
	out[x]=++cnt,to[cnt]=x;
}
void initialize(int N,vector<int>A,vector<int>B){
	n=N;
	build(1,1,2*n);
	for(int i=0;i<N-1;i++){
		t[A[i]+1].push_back(B[i]+1);
		t[B[i]+1].push_back(A[i]+1);
	}
	dfs(1,0);
}
int generate(int v,bool result){
	v++;
	int rt=to[qur(1,1,2*n,in[v])];
	if(result){
		nw-=qu(in[rt],out[rt]-1)/2;
		add(in[v],1),add(out[rt],-1);
		nw+=qu(in[rt],out[rt]-1)/2;
	}
	else{
		nw-=qu(in[rt],out[rt]-1)/2;
		for(int u:t[v]){
			if(u!=f[v]){
				add(out[rt],qu(in[u],out[u]-1));
				add(out[u],-qu(in[u],out[u]-1));
				upd(1,1,2*n,in[u],out[u],in[u]);
				nw+=qu(in[u],out[u]-1)/2;
			}
		}
		nw+=qu(in[rt],out[rt]-1)/2;
	}
	return nw;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9

Accepted

Test #1:

score: 9

Accepted

time: 0ms

memory: 10064kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1

result:

ok 3 lines

Test #2:

score: 9

Accepted

time: 1ms

memory: 10064kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
0
1
1

result:

ok 6 lines

Test #3:

score: 9

Accepted

time: 3ms

memory: 10608kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
26
27
27
28
28
29
29
29
30
30
31
31
32
32
32
33
33
34
34
35
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
43
44
44
...

result:

ok 5001 lines

Test #4:

score: 9

Accepted

time: 4ms

memory: 12656kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
1
1
1
1
1
2
2
2
3
3
3
3
3
4
4
4
4
5
5
5
5
5
5
5
6
6
7
7
7
7
8
8
8
8
9
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40...

result:

ok 5001 lines

Test #5:

score: 9

Accepted

time: 2ms

memory: 10440kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40...

result:

ok 5001 lines

Test #6:

score: 9

Accepted

time: 4ms

memory: 10616kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
7
8
8
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
1...

result:

ok 5001 lines

Test #7:

score: 9

Accepted

time: 3ms

memory: 10564kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
1
1
1
1
1
2
2
2
2
2
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
5
6
6
6
6
6
7
7
7
8
8
8
8
9
9
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
1...

result:

ok 5001 lines

Test #8:

score: 9

Accepted

time: 5ms

memory: 10588kb

input:

5000 5000
254 2905
254 3692
254 530
2905 3302
254 3965
3692 359
359 1575
530 2521
2521 4332
3302 139
359 2744
2521 4758
359 2648
1575 422
2905 1946
1575 3295
254 4103
3965 2870
2648 260
139 1274
2521 702
4332 1751
2744 4696
3302 3492
2870 261
2521 3483
4696 4380
530 3239
4332 2957
2870 315
2521 1199...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6...

result:

ok 5001 lines

Test #9:

score: 9

Accepted

time: 5ms

memory: 12564kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
14
14
15
15
15
16
16
17
17
18
18
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
31
32
32
33
33
33
33
34
34
35
35
36
36
36
36
37
37
38
38
39
39
40
40
40
41
41
42
42
4...

result:

ok 5001 lines

Test #10:

score: 9

Accepted

time: 3ms

memory: 10584kb

input:

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
1
2
2
3
3
3
3
4
4
4
4
4
5
5
5
5
5
6
6
6
6
7
7
7
7
7
7
8
8
8
8
9
9
9
9
9
9
10
10
10
10
11
11
11
11
11
12
12
12
13
13
13
13
14
14
14
14
15
15
15
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
22
22
22
23
23
23
24
24
24
24
24
25
25
25
26
26
26
27
27
27
28
28
...

result:

ok 5001 lines

Test #11:

score: 9

Accepted

time: 2ms

memory: 12524kb

input:

5000 5000
4578 81
4578 4163
81 4207
4163 442
4578 2090
4578 950
950 4490
442 750
4207 2755
442 831
950 2408
4578 2891
750 3636
750 1203
831 714
831 1011
2755 1949
750 2349
2755 4820
1203 2406
2349 2359
4578 1092
4820 4935
4163 2293
3636 3361
1011 2701
2755 3668
1203 1511
2891 1289
2701 2173
714 3853...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
5
5
5...

result:

ok 5001 lines

Subtask #2:

score: 16

Accepted

Test #12:

score: 16

Accepted

time: 124ms

memory: 45396kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
2
2
3
3
4
4
5
5
6
6
6
7
7
8
7
7
7
7
8
9
9
10
10
10
11
11
11
12
12
12
13
14
14
14
14
14
14
15
15
16
16
17
17
17
18
19
19
19
20
21
22
22
23
23
24
24
24
24
25
25
26
26
27
27
27
28
28
29
29
30
30
31
31
31
31
32
32
33
34
34
34
34
35
35
35
35
36
37
37
37
37
3...

result:

ok 200001 lines

Test #13:

score: 16

Accepted

time: 147ms

memory: 45124kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
2
3
2
2
2
2
2
3
4
4
4
5
6
6
6
6
7
7
7
7
7
7
8
9
9
9
10
10
10
11
12
13
13
14
14
14
15
16
16
17
17
17
17
18
19
20
20
20
21
22
22
22
23
24
24
25
25
25
25
26
26
26
27
27
28
29
30
31
31
31
32
32
32
33
34
35
36
36
36
36
37
37
38
38
3...

result:

ok 200001 lines

Test #14:

score: 16

Accepted

time: 101ms

memory: 45572kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
2
3
3
4
4
4
5
5
5
5
5
6
7
8
8
9
9
10
10
10
10
10
10
10
11
12
13
13
13
13
14
15
15
16
16
17
18
18
19
20
20
21
21
21
21
22
23
23
23
23
24
24
24
25
26
26
26
27
27
28
28
29
29
30
31
31
32
32
33
33
34
35
36
36
...

result:

ok 200001 lines

Test #15:

score: 16

Accepted

time: 78ms

memory: 42784kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #16:

score: 16

Accepted

time: 78ms

memory: 44108kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #17:

score: 16

Accepted

time: 326ms

memory: 49424kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
3
3
4
4
5
6
6
7
7
8
7
7
7
8
8
9
8
8
8
8
8
8
8
8
8
7
7
7
7
6
6
6
6
6
5
5
5
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2...

result:

ok 200001 lines

Test #18:

score: 16

Accepted

time: 332ms

memory: 47180kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
0
0
1
1
1
1
1
0
0
0
0
0
1
2
3
3
3
3
3
3
3
4
4
5
5
5
6
7
7
7
7
7
8
7
8
8
7
7
7
7
7
7
7
7
7
6
6
5
5
5
5
5
5
5
5
5
5
5
5
5
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3...

result:

ok 200001 lines

Test #19:

score: 16

Accepted

time: 296ms

memory: 48248kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #20:

score: 16

Accepted

time: 151ms

memory: 46744kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #21:

score: 16

Accepted

time: 145ms

memory: 46900kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #22:

score: 16

Accepted

time: 195ms

memory: 49472kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
2
3
3
3
3
4
4
4
5
6
6
7
7
8
8
9
9
10
9
10
10
11
11
12
13
14
14
14
15
16
16
16
17
17
18
19
19
19
19
20
20
20
20
21
21
21
22
22
23
23
24
24
24
25
26
26
26
27
27
27
28
29
29
30
31
32
32
33
33
33
33
33
33
34
35
35
35
36
37
37
38
38
38
39
39
39
40
40
40
40
4...

result:

ok 200001 lines

Test #23:

score: 16

Accepted

time: 221ms

memory: 47624kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
1
1
1
1
1
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
5
4
4
4
4
4
5
6
7
7
6
7
8
8
8
8
8
8
8
8
8
9
8
8
9
9
10
10
11
10
10
10
10
10
10
11
10
10
10
10
10
10
10
10
11
11
12
13
14
14
14
14
14
15
16
17
17
17
17
17
18
18
18
17
17
17
17
18
18
19
19
20
21
22
22
22
22
22
22
23
23
...

result:

ok 200001 lines

Test #24:

score: 16

Accepted

time: 189ms

memory: 47788kb

input:

200000 200000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Subtask #3:

score: 20

Accepted

Test #25:

score: 20

Accepted

time: 110ms

memory: 31316kb

input:

200000 200000
155284 18435
18435 57260
57260 88628
88628 170108
57260 126961
170108 72596
72596 46044
170108 28914
46044 177699
155284 143087
18435 161808
177699 107693
18435 74517
28914 77075
126961 116303
177699 26806
74517 43330
77075 188898
126961 45168
57260 93201
93201 198698
77075 36077
57260...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #26:

score: 20

Accepted

time: 115ms

memory: 42252kb

input:

200000 200000
20214 166890
166890 39782
39782 160973
160973 71809
71809 84135
84135 193485
193485 191907
191907 73443
73443 172846
172846 62828
62828 30539
30539 148834
148834 105784
105784 31379
31379 169920
169920 104347
104347 46092
46092 84919
84919 105144
105144 181794
181794 12834
12834 103965...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #27:

score: 20

Accepted

time: 99ms

memory: 33072kb

input:

200000 200000
13661 52989
13661 191413
13661 183385
13661 180760
13661 45914
13661 154223
13661 92602
13661 143465
13661 115429
13661 35411
13661 110883
13661 100122
13661 103685
13661 173658
13661 44682
13661 142827
13661 182193
13661 191182
13661 101940
13661 117063
13661 92502
13661 128744
13661 ...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #28:

score: 20

Accepted

time: 115ms

memory: 33396kb

input:

200000 200000
59493 126128
59493 29185
29185 51986
126128 194222
194222 36489
29185 13257
59493 88509
29185 5290
88509 117426
88509 9059
117426 14322
88509 79181
14322 145100
59493 177676
36489 59023
14322 107337
107337 91882
59023 62581
88509 79723
62581 111878
88509 99587
107337 50973
107337 72208...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
8
9
9
10
10
10
11
11
11
12
12
13
13
14
14
14
15
15
16
16
17
17
17
18
18
19
19
19
19
20
20
21
21
21
22
22
23
23
24
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
4...

result:

ok 200001 lines

Test #29:

score: 20

Accepted

time: 109ms

memory: 32932kb

input:

200000 200000
50649 125693
125693 177021
50649 129661
125693 177646
50649 153735
177021 17725
177646 38191
177646 131228
131228 188459
17725 87195
131228 65228
188459 149799
131228 49249
177021 58334
149799 72746
177021 100560
17725 56967
153735 9760
87195 143112
56967 58239
56967 52551
72746 94572
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
1
1
1
1
1
1
1
2
2
2
2
3
3
4
4
4
5
5
5
5
5
5
5
5
5
5
6
6
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40...

result:

ok 200001 lines

Test #30:

score: 20

Accepted

time: 115ms

memory: 31520kb

input:

200000 200000
137632 127467
127467 5653
127467 197110
5653 81441
137632 85612
127467 43502
5653 169404
169404 24353
24353 106517
81441 144676
169404 74287
137632 116267
81441 67278
43502 132495
197110 88474
144676 119375
132495 192477
119375 150584
144676 194589
85612 161691
43502 61970
116267 12035...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40...

result:

ok 200001 lines

Test #31:

score: 20

Accepted

time: 121ms

memory: 46944kb

input:

200000 200000
193163 161978
161978 107021
107021 156836
156836 141327
141327 46033
46033 13410
13410 156870
156870 113251
113251 123238
123238 159270
159270 9025
9025 77335
77335 161412
161412 53833
53833 38675
38675 3617
3617 160334
160334 24651
24651 52629
52629 89954
89954 26069
26069 160133
1601...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
12
12
13
13
13
14
14
15
15
16
16
16
17
18
18
18
19
18
19
19
20
20
21
21
21
22
23
23
23
24
25
25
26
26
26
27
27
28
28
29
29
30
30
30
31
31
32
32
33
33
34
34
35
36
36
37
37
38
38
39
39
40
41
42
42
43
43
44
44
44
44...

result:

ok 200001 lines

Test #32:

score: 20

Accepted

time: 115ms

memory: 42372kb

input:

200000 200000
54298 136701
136701 112193
112193 47141
47141 147159
147159 8741
8741 57318
57318 132905
132905 166419
166419 3716
3716 132730
132730 190970
190970 158330
158330 172256
172256 105190
105190 79961
79961 53628
53628 20171
20171 194146
194146 162753
162753 82550
82550 187910
187910 155308...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
0
0
0
1
1
2
2
1
1
2
2
2
3
3
4
4
5
5
5
5
6
6
6
6
7
7
7
7
7
7
7
7
7
8
9
9
9
9
9
9
10
10
10
10
11
11
12
13
14
14
15
16
16
16
16
16
16
16
17
17
18
18
18
19
19
20
20
21
21
22
22
23
23
24
25
25
26
26
27
28
28
28
29
29
29
30
30
31
31
31
32
32
33
33
33
34
35
36
37
37...

result:

ok 200001 lines

Test #33:

score: 20

Accepted

time: 177ms

memory: 41968kb

input:

200000 200000
82045 122275
122275 14122
14122 96764
96764 1042
1042 185589
185589 178282
178282 30232
30232 184846
184846 44122
44122 40830
40830 164819
164819 191178
191178 79970
79970 186031
186031 6564
6564 171025
171025 16761
16761 107519
107519 52617
52617 184251
184251 136421
136421 95834
9583...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
3
3
4
4
4
5
5
6
6
6
7
7
7
7
8
8
9
9
10
10
11
11
12
13
13
13
13
13
14
15
16
17
17
18
19
19
19
20
21
22
22
22
22
23
23
24
24
25
26
26
26
26
27
27
28
28
29
30
31
31
31
32
32
32
33
33
34
34
35
35
36
37
38
39
39
...

result:

ok 200001 lines

Test #34:

score: 20

Accepted

time: 111ms

memory: 31972kb

input:

200000 200000
9300 141962
9300 74037
9300 171352
9300 69828
9300 31149
9300 163110
9300 51311
9300 175754
9300 53863
9300 196326
9300 79356
9300 152196
9300 35221
9300 140191
9300 166005
9300 37195
9300 15191
9300 177944
9300 38965
9300 88716
9300 193524
9300 65556
9300 166955
9300 133598
9300 18447...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
1
1
2
2
3
3
4
4
5
5
5
6
6
7
7
8
8
9
9
10
10
11
11
11
12
12
12
13
13
14
14
14
15
15
15
16
16
16
17
17
17
17
17
18
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
26
27
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
...

result:

ok 200001 lines

Test #35:

score: 20

Accepted

time: 97ms

memory: 33620kb

input:

200000 200000
55095 66903
55095 74853
55095 157386
55095 103529
55095 36321
55095 29867
55095 22904
55095 23422
55095 40249
55095 98190
55095 95688
55095 182008
55095 179919
55095 195415
55095 128984
55095 191659
55095 166868
55095 126279
55095 126087
55095 187890
55095 161121
55095 9103
55095 24960...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
1
1
2
2
2
2
2
2
3
3
3
4
4
4
5
5
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40...

result:

ok 200001 lines

Test #36:

score: 20

Accepted

time: 107ms

memory: 33856kb

input:

200000 200000
46111 33352
46111 11834
46111 118619
46111 179895
46111 56636
46111 149637
46111 119569
46111 107962
46111 110220
46111 139911
46111 33162
46111 146736
46111 137101
46111 177259
46111 73282
46111 16493
46111 182145
46111 95400
46111 119830
46111 188083
46111 39896
46111 94147
46111 378...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40...

result:

ok 200001 lines

Subtask #4:

score: 23

Accepted

Test #37:

score: 23

Accepted

time: 212ms

memory: 36548kb

input:

200000 200000
124028 117993
117993 64181
124028 176900
64181 197782
124028 153477
153477 179542
64181 191368
197782 55523
64181 36078
153477 108486
117993 169125
179542 68449
124028 153826
124028 142937
36078 65258
36078 28508
68449 114673
191368 17655
197782 90991
176900 48570
191368 6324
153826 18...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #38:

score: 23

Accepted

time: 349ms

memory: 41136kb

input:

200000 200000
131866 18043
18043 57193
57193 60655
60655 35995
35995 28070
28070 67968
67968 105408
105408 156686
156686 106458
106458 29522
29522 122097
122097 74460
74460 184393
184393 103127
103127 66034
66034 143537
143537 21725
21725 50976
50976 176162
176162 105552
105552 55780
55780 62169
621...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #39:

score: 23

Accepted

time: 168ms

memory: 36108kb

input:

200000 200000
151691 17854
151691 146833
151691 26054
151691 187921
151691 87998
151691 15359
151691 105393
151691 139556
151691 144598
151691 19426
151691 72223
151691 81216
151691 4463
151691 198983
151691 82874
151691 131724
151691 76749
151691 167757
151691 4589
151691 60837
151691 117757
151691...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #40:

score: 23

Accepted

time: 210ms

memory: 37104kb

input:

200000 200000
57103 151863
57103 65099
65099 131631
131631 104062
131631 193083
104062 5074
65099 80436
80436 44079
57103 40438
193083 5819
5074 88154
65099 77383
77383 82202
193083 96604
104062 174500
80436 76033
80436 152882
104062 196890
88154 128462
193083 78716
96604 167178
65099 52255
128462 1...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
1...

result:

ok 200001 lines

Test #41:

score: 23

Accepted

time: 272ms

memory: 35360kb

input:

200000 200000
89494 182333
182333 56926
182333 58254
89494 81056
81056 48573
58254 16161
182333 132854
182333 11767
89494 165398
58254 63917
132854 7594
48573 77124
11767 63758
132854 499
7594 35605
499 60637
35605 82629
35605 193537
7594 28488
77124 58231
58254 104417
104417 105692
82629 146853
284...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
1
1
1
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
6
6
7
7
8
8
8
9
9
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
...

result:

ok 200001 lines

Test #42:

score: 23

Accepted

time: 223ms

memory: 35248kb

input:

200000 200000
198744 171839
171839 96336
171839 84982
198744 72866
72866 65285
96336 119065
65285 195480
72866 10813
171839 54689
84982 167042
119065 189784
195480 98624
84982 122612
54689 150357
84982 10562
119065 112708
119065 8167
119065 135976
150357 73987
189784 137557
189784 7450
135976 138950...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
6
6
6...

result:

ok 200001 lines

Test #43:

score: 23

Accepted

time: 268ms

memory: 43972kb

input:

200000 200000
32572 118598
118598 132801
132801 156122
156122 188935
188935 111884
111884 72952
72952 66645
66645 86122
86122 73092
73092 162868
162868 81386
81386 19496
19496 66232
66232 134316
134316 43589
43589 188163
188163 187596
187596 55838
55838 163954
163954 125220
125220 114296
114296 1213...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
9
9
9
9
9
9
9
8
8
8
7
7
6
6
6
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3...

result:

ok 200001 lines

Test #44:

score: 23

Accepted

time: 264ms

memory: 43732kb

input:

200000 200000
56612 89655
89655 54489
54489 53220
53220 68726
68726 147206
147206 190958
190958 46701
46701 75405
75405 119226
119226 176873
176873 175328
175328 114541
114541 155577
155577 104877
104877 158873
158873 110342
110342 1255
1255 169454
169454 137805
137805 109417
109417 117061
117061 43...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
1
1
2
1
1
2
2
2
2
3
3
4
4
3
3
4
4
4
4
3
3
3
3
3
3
3
4
4
4
4
4
5
5
5
6
6
7
7
8
9
8
8
7
7
7
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4...

result:

ok 200001 lines

Test #45:

score: 23

Accepted

time: 357ms

memory: 45588kb

input:

200000 200000
190180 86212
86212 83118
83118 6556
6556 197239
197239 178423
178423 185777
185777 70277
70277 182867
182867 59341
59341 78666
78666 123751
123751 165916
165916 117788
117788 55220
55220 110537
110537 135432
135432 34205
34205 53267
53267 43805
43805 188021
188021 189193
189193 173617
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #46:

score: 23

Accepted

time: 209ms

memory: 35840kb

input:

200000 200000
136630 196715
136630 143295
136630 93713
136630 82595
136630 156404
136630 136007
136630 116102
136630 167408
136630 88406
136630 95990
136630 71025
136630 53269
136630 31260
136630 8846
136630 169255
136630 63909
136630 4801
136630 121020
136630 62563
136630 194788
136630 130930
13663...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
1
2
2
3
3
4
4
4
4
5
5
6
6
7
7
8
8
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
...

result:

ok 200001 lines

Test #47:

score: 23

Accepted

time: 198ms

memory: 37176kb

input:

200000 200000
28805 125171
28805 190194
28805 141776
28805 146209
28805 185271
28805 77491
28805 198714
28805 171091
28805 44032
28805 174598
28805 18422
28805 185816
28805 196696
28805 43484
28805 136566
28805 139490
28805 60725
28805 183920
28805 11636
28805 53946
28805 188042
28805 84241
28805 10...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
1
1
2
2
2
2
2
3
3
3
4
4
4
4
4
4
5
5
5
6
6
6
6
6
7
7
8
8
9
9
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
1...

result:

ok 200001 lines

Test #48:

score: 23

Accepted

time: 155ms

memory: 38112kb

input:

200000 200000
37088 104058
37088 97836
37088 109638
37088 24780
37088 81012
37088 193141
37088 182696
37088 60140
37088 129604
37088 162906
37088 192574
37088 30483
37088 149302
37088 18094
37088 105753
37088 100088
37088 95543
37088 195048
37088 58496
37088 138450
37088 7103
37088 142290
37088 1555...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5...

result:

ok 200001 lines

Test #49:

score: 23

Accepted

time: 49ms

memory: 30464kb

input:

199997 50010
0 1
1 2
0 3
3 4
0 5
5 6
0 7
7 8
0 9
9 10
0 11
11 12
0 13
13 14
0 15
15 16
0 17
17 18
0 19
19 20
0 21
21 22
0 23
23 24
0 25
25 26
0 27
27 28
0 29
29 30
0 31
31 32
0 33
33 34
0 35
35 36
0 37
37 38
0 39
39 40
0 41
41 42
0 43
43 44
0 45
45 46
0 47
47 48
0 49
49 50
0 51
51 52
0 53
53 54
0 55...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 50011 lines

Test #50:

score: 23

Accepted

time: 98ms

memory: 30796kb

input:

199997 50010
145095 116126
116126 107326
145095 173391
173391 5505
145095 103699
103699 171745
145095 69906
69906 192278
145095 176236
176236 153983
145095 112713
112713 185089
145095 101806
101806 163168
145095 127146
127146 36978
145095 120836
120836 2033
145095 192582
192582 191541
145095 197658
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 50011 lines

Subtask #5:

score: 32

Accepted

Test #51:

score: 32

Accepted

time: 195ms

memory: 37580kb

input:

200000 200000
75490 97148
75490 176817
75490 80168
75490 73425
97148 38334
80168 199950
73425 5116
5116 154439
80168 90246
154439 5305
154439 101118
101118 28211
90246 91284
75490 103069
80168 85099
176817 55430
38334 31693
55430 28292
80168 163565
163565 196782
28211 194198
28292 163487
73425 30097...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #52:

score: 32

Accepted

time: 243ms

memory: 35532kb

input:

200000 200000
8015 98823
98823 7276
8015 21449
7276 143252
143252 64348
7276 33746
8015 26461
7276 132054
64348 91287
132054 51413
64348 174096
33746 21438
51413 59412
21438 135457
26461 97934
51413 129071
21438 198010
7276 10682
64348 105282
21449 156482
135457 80599
80599 154745
33746 134051
21449...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
5
6
6
6
7
7
8
8
9
9
10
10
11
11
12
12
12
12
13
13
14
14
15
15
16
16
17
17
18
18
18
19
19
20
20
21
21
21
22
22
23
23
24
24
24
25
25
25
26
26
26
27
27
28
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42...

result:

ok 200001 lines

Test #53:

score: 32

Accepted

time: 174ms

memory: 36576kb

input:

200000 200000
52197 124383
52197 31618
124383 3645
31618 59457
52197 16500
3645 151858
151858 130239
59457 23642
16500 141681
23642 161914
151858 188043
141681 140868
130239 9029
31618 96816
151858 61565
124383 89789
31618 104502
188043 67086
23642 138788
31618 193349
3645 183222
67086 3031
3031 177...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
1
1
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
5
5
5
5
5
5
6
6
7
7
7
7
8
8
8
9
9
9
9
10
10
11
11
11
11
11
11
12
12
12
12
12
12
12
12
12
12
13
13
14
14
14
15
15
15
15
16
16
16
16
16
17
17
18
18
18
18
19
19
19
20
20
21
21
21
22
22
22
22
23
23
23
24
24
24
24
24
24
25
2...

result:

ok 200001 lines

Test #54:

score: 32

Accepted

time: 178ms

memory: 35844kb

input:

200000 200000
31752 56157
31752 72032
72032 179436
179436 93861
31752 114198
72032 6862
179436 113827
113827 158117
6862 72903
114198 143451
6862 103300
103300 192212
179436 46687
93861 92075
46687 178733
158117 18592
143451 73064
56157 189221
113827 90567
56157 11148
103300 185899
18592 172610
1114...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5...

result:

ok 200001 lines

Test #55:

score: 32

Accepted

time: 300ms

memory: 35248kb

input:

200000 200000
182605 100168
182605 150821
100168 74710
150821 20550
20550 167113
100168 17696
17696 25040
25040 111697
20550 109417
167113 74202
182605 57306
150821 96382
167113 86110
100168 49244
182605 89081
57306 182281
49244 98662
100168 126232
126232 31618
49244 144375
182605 16771
16771 143953...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #56:

score: 32

Accepted

time: 201ms

memory: 45180kb

input:

200000 200000
13556 98226
98226 182272
182272 115498
115498 133063
133063 90232
90232 8911
8911 173430
173430 44981
44981 195989
195989 131940
131940 177152
177152 169347
169347 117674
117674 69448
69448 99130
99130 31342
31342 119863
119863 29543
29543 74506
74506 52799
52799 60580
60580 48801
4880...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #57:

score: 32

Accepted

time: 196ms

memory: 45752kb

input:

200000 200000
4193 19717
19717 4837
4837 185949
185949 85401
85401 35093
35093 198727
198727 194265
194265 120482
120482 114909
114909 135596
135596 78416
78416 7800
7800 153239
153239 64478
64478 140882
140882 149514
149514 43910
43910 96576
96576 42462
42462 197912
197912 118477
118477 29843
29843...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
13
14
14
14
14
14
14
15
15
15
15
16
16
17
18
18
19
19
19
20
21
22
23
24
24
24
24
25
26
26
27
27
26
26
26
27
28
27
27
28
29
29
29
30
31
31
31
31
32
32
32
33
33
34
34
34
35
35
35
36
37
37
37
37
37
...

result:

ok 200001 lines

Test #58:

score: 32

Accepted

time: 288ms

memory: 41892kb

input:

200000 200000
191307 76239
76239 65252
65252 131928
131928 163671
163671 166660
166660 195625
195625 104592
104592 164766
164766 91885
91885 130646
130646 139059
139059 81760
81760 161326
161326 26142
26142 67352
67352 110121
110121 193330
193330 57667
57667 154314
154314 176081
176081 18568
18568 1...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
3
3
3
3
4
4
4
4
5
5
5
5
5
6
6
7
7
7
7
7
7
7
8
9
9
9
9
9
9
9
10
10
10
11
11
11
11
12
12
11
11
11
11
11
10
11
12
12
12
12
12
12
12
12
12
12
12
13
12
13
13
13
13
14
14
14
14
14
14
15
15
15
15
15
15
15
15
16
16
16
16
16
1...

result:

ok 200001 lines

Test #59:

score: 32

Accepted

time: 196ms

memory: 45660kb

input:

200000 200000
91544 33834
33834 85344
85344 103162
103162 83480
83480 79249
79249 170464
170464 32922
32922 101654
101654 77773
77773 142133
142133 79852
79852 189932
189932 104030
104030 74244
74244 187125
187125 170275
170275 13045
13045 80931
80931 107592
107592 147318
147318 115531
115531 21496
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

result:

ok 200001 lines

Test #60:

score: 32

Accepted

time: 191ms

memory: 45220kb

input:

200000 200000
153585 24715
24715 198798
198798 111420
111420 33987
33987 123974
123974 195195
195195 124200
124200 156626
156626 114414
114414 65953
65953 136830
136830 100278
100278 53616
53616 114372
114372 20630
20630 62102
62102 135201
135201 157830
157830 75360
75360 50514
50514 175438
175438 7...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #61:

score: 32

Accepted

time: 113ms

memory: 38124kb

input:

200000 200000
25035 110456
25035 53877
25035 32564
25035 157671
25035 41410
25035 122629
25035 6806
25035 131153
25035 98395
25035 103747
25035 170195
25035 29549
25035 192122
25035 161554
25035 182327
25035 42540
25035 57779
25035 18220
25035 19391
25035 113860
25035 39076
25035 164045
25035 80973
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
...

result:

ok 200001 lines

Test #62:

score: 32

Accepted

time: 147ms

memory: 37716kb

input:

200000 200000
162456 75679
162456 88820
162456 128245
162456 22707
162456 146850
162456 86592
162456 98638
162456 111864
162456 58005
162456 105063
162456 152612
162456 154863
162456 86698
162456 193499
162456 70726
162456 131912
162456 125500
162456 183948
162456 154370
162456 77076
162456 14072
16...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
31
31
31
32
32
33
33
34
34
34
35
35
35
36
36
37
37
38
38
39
39
39
40
40
41
41
42
42
42
42
...

result:

ok 200001 lines

Test #63:

score: 32

Accepted

time: 107ms

memory: 34104kb

input:

200000 200000
104219 183893
104219 169445
104219 18410
104219 10318
104219 13468
104219 138803
104219 106747
104219 33342
104219 107690
104219 67370
104219 140903
104219 49548
104219 3466
104219 89504
104219 116415
104219 5068
104219 140819
104219 143896
104219 178819
104219 165734
104219 197984
104...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
1
1
1
2
2
2
2
2
2
2
3
3
3
4
4
5
5
5
5
6
6
6
7
7
7
7
7
7
7
8
8
8
9
9
9
9
9
10
10
10
10
10
10
11
11
11
11
12
12
13
13
13
14
14
14
15
15
15
16
16
17
17
18
18
18
18
18
19
19
20
20
20
21
21
21
22
22
22
23
23
23
23
23
23
23
23
24
24
24
24
24
25
25
25
25
25
25
25
25...

result:

ok 200001 lines

Test #64:

score: 32

Accepted

time: 107ms

memory: 33396kb

input:

200000 200000
22372 163335
22372 73325
22372 90124
22372 199769
22372 145530
22372 86043
22372 48775
22372 159613
22372 21184
22372 86175
22372 109713
22372 87672
22372 188037
22372 12122
22372 14294
22372 155561
22372 5836
22372 146375
22372 58001
22372 169840
22372 102196
22372 128107
22372 33004
...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6...

result:

ok 200001 lines

Test #65:

score: 32

Accepted

time: 116ms

memory: 35964kb

input:

200000 200000
58389 91704
58389 140162
58389 122362
58389 140894
58389 69691
58389 104863
58389 66594
58389 14299
58389 19227
58389 173280
58389 19685
58389 181557
58389 55999
58389 150589
58389 149726
58389 86053
58389 142759
58389 15350
58389 43228
58389 77447
58389 178482
58389 165000
58389 70870...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 200001 lines

Test #66:

score: 32

Accepted

time: 96ms

memory: 34420kb

input:

199997 199997
0 1
1 2
0 3
3 4
0 5
5 6
0 7
7 8
0 9
9 10
0 11
11 12
0 13
13 14
0 15
15 16
0 17
17 18
0 19
19 20
0 21
21 22
0 23
23 24
0 25
25 26
0 27
27 28
0 29
29 30
0 31
31 32
0 33
33 34
0 35
35 36
0 37
37 38
0 39
39 40
0 41
41 42
0 43
43 44
0 45
45 46
0 47
47 48
0 49
49 50
0 51
51 52
0 53
53 54
0 5...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 199998 lines

Test #67:

score: 32

Accepted

time: 177ms

memory: 35820kb

input:

199997 199997
69479 150023
150023 192848
69479 107851
107851 107537
69479 167805
167805 107412
69479 37215
37215 149001
69479 89878
89878 19093
69479 166588
166588 47936
69479 84828
84828 117078
69479 51330
51330 170191
69479 85911
85911 89222
69479 41955
41955 185821
69479 21212
21212 122880
69479 ...

output:

b74500f8-4e8b-4d58-879e-82e9596bfa16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 199998 lines