QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687515#8584. 바이러스Estelle_N100 ✓836ms327320kbC++142.9kb2024-10-29 19:27:532024-10-29 19:27:55

Judging History

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

  • [2024-10-29 19:27:55]
  • 评测
  • 测评结果:100
  • 用时:836ms
  • 内存:327320kb
  • [2024-10-29 19:27:53]
  • 提交

answer

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;
const int M = 5000005;

int n, m, cnt, val[N], vis[M];
long long dis[M];

vector <int> e[N];
vector < pair <int, int> > E[M], t[N];
priority_queue < pair <long long, int> > q;

void dijkstra()
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    q.push(make_pair(dis[1] = 0, 1));
    
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u] = 1;
        for(auto [v, w] : E[u])
            if(dis[v] > dis[u] + w)
                dis[v] = dis[u] + w, q.push({- dis[v], v});
    }
}

int rt, sum, MinId, MaxDep, siz[N], Max[N], dep[N], p[N][2];

void find(int u, int fa)
{
    siz[u] = 1;
    Max[u] = 0;
    for(int v : e[u])
    {
        if(v == fa || vis[v])
            continue;
        find(v, u);
        siz[u] += siz[v];
        Max[u] = max(Max[u], siz[v]);
    }
    Max[u] = max(Max[u], sum - siz[u]);
    rt = Max[u] < Max[rt] ? u : rt;
}

void getDis(int u, int fa)
{
    MaxDep = max(MaxDep, dep[u]);
    if(p[dep[u]][0] <= MinId)
    {
        p[dep[u]][0] = ++ cnt;
        if(dep[u] > 0)
            E[cnt].push_back({p[dep[u] - 1][0], 0});
        p[dep[u]][1] = ++ cnt;
        if(dep[u] > 0)
            E[p[dep[u] - 1][1]].push_back({cnt, 0});
    }
    E[p[dep[u]][0]].push_back({u + m, val[u]});
    E[u + m].push_back({p[dep[u]][1], 0});
    for(int v : e[u])
        if(!vis[v] && v != fa)
            dep[v] = dep[u] + 1, getDis(v, u);
}

void getEdge(int u, int fa)
{
    for(auto [x, y] : t[u])
    {
        if(y >= dep[u])
        {
            E[x].push_back({p[min(MaxDep, y - dep[u])][0], 0});
            E[p[min(MaxDep, y - dep[u])][1]].push_back({x, 0});
        }
    }
    for(int v : e[u])
        if(!vis[v] && v != fa)
            getEdge(v, u);
}

void solve(int u)
{
    MinId = cnt;
    dep[u] = MaxDep = 0;
    getDis(u, 0);
    getEdge(u, 0);
}

void division(int u)
{
    vis[u] = 1;
    solve(u);
    for(int v : e[u])
        if(!vis[v])
            sum = Max[rt = 0] = siz[v], find(v, u), division(rt);
}

vector <long long> ans;

vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C)
{
    n = N;
    m = M;
    for(int i = 0; i < N - 1; ++ i)
    {
        e[A[i] + 1].push_back(B[i] + 1);
        e[B[i] + 1].push_back(A[i] + 1);
    }
    for(int i = 0; i < M; ++ i)
        t[P[i] + 1].push_back({i + 1, D[i]}), E[P[i] + 1 + M].push_back({i + 1, 0});
    for(int i = 0; i < N; ++ i)
        val[i + 1] = C[i];

    cnt = n + m;
    sum = Max[rt = 0] = N;
    find(1, 0);
    division(rt);

    dijkstra();

    for(int i = 1; i <= M; ++ i)
        ans.push_back(dis[i] == dis[0] ? -1 : dis[i]);
    return ans;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 28ms
memory: 185484kb

input:

8 5
0 1
1 2
2 3
3 4
4 5
5 6
6 7
2 2
5 0
7 0
1 1
4 1
40 5 5 16 32 8 1 10

output:

0
24
-1
5
16

result:

ok 5 lines

Test #2:

score: 5
Accepted
time: 7ms
memory: 184352kb

input:

1 2
0 0
0 0
1000000000

output:

0
1000000000

result:

ok 2 lines

Test #3:

score: 5
Accepted
time: 24ms
memory: 184048kb

input:

1 1
0 0
1

output:

0

result:

ok single line: '0'

Test #4:

score: 5
Accepted
time: 20ms
memory: 184268kb

input:

5 5
0 1
1 2
2 3
3 4
4 4
3 4
3 4
4 4
3 3
205776802 419505279 604355565 320588676 267287300

output:

0
205776802
205776802
205776802
205776802

result:

ok 5 lines

Test #5:

score: 5
Accepted
time: 20ms
memory: 184048kb

input:

5 5
0 1
1 2
2 3
3 4
0 1
2 4
3 2
2 2
0 3
798595430 17544794 263282020 749935522 265537216

output:

0
17544794
17544794
17544794
17544794

result:

ok 5 lines

Test #6:

score: 5
Accepted
time: 16ms
memory: 184048kb

input:

5 5
0 1
1 2
2 3
3 4
4 0
3 0
0 0
1 1
1 0
805814316 68727170 931548944 955566578 268585692

output:

0
-1
-1
-1
-1

result:

ok 5 lines

Test #7:

score: 5
Accepted
time: 34ms
memory: 184052kb

input:

5 5
0 1
1 2
2 3
3 4
3 4
0 4
2 4
2 4
2 4
140258399 508694682 846494800 923720900 238592045

output:

0
140258399
140258399
140258399
140258399

result:

ok 5 lines

Test #8:

score: 5
Accepted
time: 23ms
memory: 184272kb

input:

10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 7
3 7
9 8
0 5
5 7
4 3
2 9
6 9
7 8
4 8
998183090 584072254 887174893 11448861 742483923 59447072 545713676 980826811 811598242 35544321

output:

0
11448861
11448861
11448861
11448861
11448861
11448861
11448861
11448861
11448861

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 15ms
memory: 184052kb

input:

10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
2 5
5 4
9 5
2 9
5 2
6 4
2 4
8 4
9 7
2 0
911698130 382043019 90722009 440968421 571375991 137522383 377189267 211855539 341720684 687999451

output:

0
90722009
137522383
90722009
137522383
90722009
90722009
137522383
90722009
90722009

result:

ok 10 lines

Test #10:

score: 5
Accepted
time: 8ms
memory: 184280kb

input:

10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
3 3
2 5
0 4
3 2
5 1
1 0
4 2
8 0
3 2
3 0
892608355 903586083 572266475 47500884 6301829 729660024 455211808 942317353 131889193 801254776

output:

0
6301829
6301829
6301829
6301829
903586083
6301829
-1
6301829
47500884

result:

ok 10 lines

Test #11:

score: 5
Accepted
time: 16ms
memory: 184156kb

input:

10 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
0 9
9 9
4 9
0 9
7 9
8 9
0 9
6 9
5 9
4 9
95389682 395000358 484533614 652845161 327306317 799690376 871884048 751786316 693371321 784309957

output:

0
95389682
95389682
95389682
95389682
95389682
95389682
95389682
95389682
95389682

result:

ok 10 lines

Test #12:

score: 5
Accepted
time: 19ms
memory: 184100kb

input:

20 20
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
2 12
0 12
5 17
7 14
6 16
1 19
13 18
6 14
4 9
0 18
18 18
6 11
0 13
15 17
1 8
6 18
9 9
13 16
6 19
2 15
436523225 735146636 641656461 569341995 381628222 450451359 605334108 99712125 988489106 717299297...

output:

0
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125
99712125

result:

ok 20 lines

Test #13:

score: 5
Accepted
time: 23ms
memory: 184316kb

input:

20 20
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
13 3
6 4
16 1
19 19
19 17
5 2
5 7
12 7
6 18
12 11
18 11
11 5
13 13
15 19
19 3
9 7
16 7
16 6
5 7
8 9
999021218 83246177 270836731 525612430 672541663 476653247 839288054 764153704 941216586 648134044 ...

output:

0
348015639
499890278
77178908
77178908
553832155
160425085
77178908
77178908
77178908
77178908
77178908
77178908
77178908
300536180
77178908
77178908
77178908
160425085
77178908

result:

ok 20 lines

Test #14:

score: 5
Accepted
time: 23ms
memory: 184056kb

input:

20 20
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
12 8
12 4
19 3
8 0
12 0
16 0
4 0
12 1
3 3
9 6
11 5
6 7
14 9
8 5
15 2
8 5
8 2
0 2
18 3
16 7
346014551 491695164 57622712 97722771 993912839 996909253 733512353 277580504 195751201 438876633 523544328 ...

output:

0
195751201
519350473
195751201
377943706
519350473
993912839
377943706
253373913
195751201
195751201
195751201
195751201
195751201
519350473
195751201
195751201
253373913
519350473
377943706

result:

ok 20 lines

Test #15:

score: 5
Accepted
time: 11ms
memory: 184160kb

input:

20 20
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
7 19
5 19
8 19
17 19
14 19
19 19
15 19
14 19
12 19
15 19
9 19
1 19
0 19
2 19
8 19
8 19
4 19
8 19
13 19
1 19
69882800 452312168 666117339 829711627 782632700 231822906 990022913 818955019 160583703 53...

output:

0
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683
2957683

result:

ok 20 lines

Test #16:

score: 5
Accepted
time: 27ms
memory: 184812kb

input:

500 500
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
51 52...

output:

0
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
15461593
5660055
9594340
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
5660055
18867951
5660055
...

result:

ok 500 lines

Test #17:

score: 5
Accepted
time: 23ms
memory: 184720kb

input:

500 500
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
51 52...

output:

0
1835541
39136776
9642798
1835541
1835541
3122805
3122805
1835541
1835541
1835541
1835541
1835541
1835541
1835541
75659436
1835541
3122805
1835541
1835541
1835541
1835541
3122805
1835541
1835541
1835541
3122805
3122805
3122805
3122805
1835541
3122805
1835541
1835541
3122805
1835541
1835541
1835541
...

result:

ok 500 lines

Test #18:

score: 5
Accepted
time: 20ms
memory: 184488kb

input:

500 500
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
51 52...

output:

0
15059089
6799303
6799303
6799303
7283744
6799303
11520777
6799303
6799303
40534885
14863038
6799303
7283744
6799303
11520777
7840730
6799303
7283744
6799303
51471677
11520777
7283744
40534885
7840730
7283744
6799303
6799303
7283744
6799303
6799303
40515088
40534885
6799303
6799303
40515088
1486303...

result:

ok 500 lines

Test #19:

score: 5
Accepted
time: 20ms
memory: 184760kb

input:

500 500
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
51 52...

output:

0
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
296569
2965...

result:

ok 500 lines

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #20:

score: 8
Accepted
time: 31ms
memory: 189524kb

input:

5000 5000
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
51 ...

output:

0
357202
357202
357202
357202
357202
357202
357202
357202
357202
357202
357202
357202
357202
357202
471014
357202
357202
357202
357202
471014
357202
357202
357202
357202
357202
357202
357202
357202
357202
471014
357202
357202
471014
357202
357202
357202
471014
357202
471014
471014
357202
471014
3572...

result:

ok 5000 lines

Test #21:

score: 8
Accepted
time: 47ms
memory: 189576kb

input:

5000 5000
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
51 ...

output:

0
318116
318116
2453747
318116
1295185
318116
318116
318116
318116
318116
318116
318116
318116
318116
2662212
318116
318116
318116
318116
4116663
318116
318116
318116
965483
318116
318116
318116
318116
318116
318116
318116
318116
2453747
965483
318116
318116
318116
318116
318116
318116
318116
318116...

result:

ok 5000 lines

Test #22:

score: 8
Accepted
time: 39ms
memory: 189404kb

input:

5000 5000
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
51 ...

output:

0
108835
718123
711556
108835
854767
108835
5013848
2626157
718123
2184570
108835
108835
711556
1696752
854767
711556
711556
854767
108835
3053622
108835
108835
711556
108835
108835
108835
711556
3227850
108835
108835
108835
711556
108835
711556
108835
1696752
108835
711556
711556
108835
2133476
227...

result:

ok 5000 lines

Test #23:

score: 8
Accepted
time: 40ms
memory: 189528kb

input:

5000 5000
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
51 ...

output:

0
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
66133
6613...

result:

ok 5000 lines

Test #24:

score: 8
Accepted
time: 39ms
memory: 188804kb

input:

5000 5000
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
51 ...

output:

0
1377425856
1028983153
9485538478
3452534969
1804173843
1634860890
8708348252
1821421203
3133671853
1287774037
6419727383
3031362618
7166669022
7916465186
4455509207
1513813067
5511961737
2693040650
2560474501
2695762132
6020924333
2031936144
6081836278
729039375
8758966485
3991251425
5683032929
24...

result:

ok 5000 lines

Subtask #3:

score: 27
Accepted

Dependency #2:

100%
Accepted

Test #25:

score: 27
Accepted
time: 734ms
memory: 327020kb

input:

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

0
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
12921
1292...

result:

ok 100000 lines

Test #26:

score: 27
Accepted
time: 783ms
memory: 324640kb

input:

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

0
92505
92505
156629
42862
7540
7540
9697
7540
7540
7540
7540
7540
9697
9697
7540
7540
7540
7540
92505
92505
26245
9697
7540
7540
7540
7540
9697
9697
9697
9697
7540
7540
9697
92505
69397
7540
7540
7540
7540
7540
9697
7540
76707
7540
7540
7540
7540
9697
92505
26245
7540
9697
7540
9697
7540
7540
92505...

result:

ok 100000 lines

Test #27:

score: 27
Accepted
time: 767ms
memory: 321896kb

input:

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

0
54379
43355
39510
384625
39510
54379
39510
39510
39510
39510
53419
54379
39510
39510
39510
53419
39510
54379
53419
148362
53419
66006
53419
66006
39510
53419
178861
53419
53419
39510
53139
54379
43355
39510
39510
39510
53419
53419
53419
66006
39510
39510
39510
53419
152856
66006
53419
53419
39510
...

result:

ok 100000 lines

Test #28:

score: 27
Accepted
time: 698ms
memory: 327320kb

input:

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

0
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
11837
1183...

result:

ok 100000 lines

Test #29:

score: 27
Accepted
time: 594ms
memory: 306560kb

input:

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

0
34598917
37859045
327465835
16892301
3821590
32482320
46899329
78855855
31357855
81275826
22362679
319613462
26109068
64023551
5916527
23122893
23235714
8313305
43345571
24320703
26215530
16892301
18055830
7658846
76316730
14873846
38637760
12246801
45359471
79901745
79511766
13915610
10871963
165...

result:

ok 100000 lines

Test #30:

score: 27
Accepted
time: 432ms
memory: 297816kb

input:

90000 96036
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
5...

output:

0
45553908
45334898
45174475
45018542
45553908
45293764
45247893
45503569
45011484
44910795
45121416
45381426
45392900
44910795
45121416
45066049
45449457
45503569
46486693
45368357
45174475
45392900
45174475
45018542
45293764
45503569
45018542
45392900
45247893
45174475
45066049
45511683
45018542
4...

result:

ok 96036 lines

Test #31:

score: 27
Accepted
time: 388ms
memory: 283156kb

input:

90000 90016
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
5...

output:

0
72180407457
37322422758
88490146510
98728324034
23338409025
31703853041
80467049510
96341120740
40169894739
12708301336
6557026439
44046713322
5377578441
32562651429
59883478467
11711351997
14209688746
50750758344
67908060122
50626027568
3422931225
74270676085
39883369800
60974419131
45351595199
7...

result:

ok 90016 lines

Test #32:

score: 27
Accepted
time: 407ms
memory: 288008kb

input:

90000 90128
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
5...

output:

0
1880804470
3897762496
2527241536
2978002325
2945563348
884620776
1994287256
3802999091
3736292003
4676478935
3281882524
2986913132
1131617379
1174379406
477233277
4388045811
4857867129
672277985
303518232
3909473738
3894761137
970036335
2569294214
1310172876
4948314617
4115450288
954678852
3113829...

result:

ok 90128 lines

Test #33:

score: 27
Accepted
time: 428ms
memory: 294892kb

input:

90000 90942
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
5...

output:

0
568182122
578932103
593462011
573866470
572868751
592362933
569820304
573777243
569820304
583269415
575836469
574137356
593369001
593392246
592875459
570054769
579728421
592362933
593392246
571786356
577943553
572917190
583800215
583009616
819583110
573764581
592479143
592479143
590445574
59287545...

result:

ok 90942 lines

Subtask #4:

score: 5
Accepted

Test #34:

score: 5
Accepted
time: 19ms
memory: 184120kb

input:

8 5
0 1
1 2
2 3
3 4
4 5
3 6
3 7
2 2
5 0
7 0
1 1
4 1
40 5 5 16 32 8 1 10

output:

0
24
10
5
16

result:

ok 5 lines

Test #35:

score: 5
Accepted
time: 15ms
memory: 184348kb

input:

10 10
9 3
0 6
1 8
5 1
3 2
8 7
0 4
6 5
0 9
9 0
7 2
1 0
8 1
6 3
1 2
4 6
7 2
5 1
5 4
10 12 5 9 8 21 20 6 13 5

output:

0
11
17
11
5
11
5
11
17
5

result:

ok 10 lines

Test #36:

score: 5
Accepted
time: 16ms
memory: 184316kb

input:

20 20
16 11
13 10
17 6
13 18
13 16
13 0
2 5
14 7
5 17
15 1
18 19
7 15
6 4
13 2
1 8
0 14
13 12
13 9
9 3
10 9
5 16
8 18
0 19
17 16
7 11
2 7
15 13
18 18
19 11
2 18
16 7
11 17
16 19
14 15
5 15
13 19
5 8
7 15
17 15
201842345 959136634 799276472 790823713 190419998 931723392 553266463 967187391 208167145 ...

output:

0
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910
134949910

result:

ok 20 lines

Test #37:

score: 5
Accepted
time: 15ms
memory: 184060kb

input:

20 20
11 17
13 8
6 4
18 13
15 12
5 15
16 7
8 10
3 18
16 3
16 19
16 1
2 9
1 11
14 2
0 14
10 5
16 0
17 6
0 1
17 5
1 14
16 6
1 5
4 3
4 4
18 4
12 8
7 8
0 12
3 12
4 13
11 5
2 0
10 9
18 1
18 17
15 19
11 4
392505795 598245226 676917494 520541066 400541959 961423871 653272803 503778194 808079532 53571674 86...

output:

0
392505795
392505795
392505795
392505795
793047754
793047754
392505795
395420842
392505795
392505795
392505795
392505795
392505795
1069423289
392505795
395420842
392505795
392505795
392505795

result:

ok 20 lines

Test #38:

score: 5
Accepted
time: 28ms
memory: 184156kb

input:

20 20
1 13
3 12
0 8
2 4
8 5
10 17
10 0
10 11
13 16
19 9
6 18
10 14
10 2
7 1
5 6
4 15
11 3
9 7
10 19
4 4
7 2
1 0
9 1
3 1
10 15
18 0
6 3
19 8
15 0
16 5
15 5
4 10
0 0
14 1
9 10
17 11
17 0
12 4
13 6
32588836 700122468 935315183 460144664 72259535 979008218 991710456 656707652 436761227 637241986 4232798...

output:

0
362671255
732711304
537602043
176293815
32588836
516986682
32588836
32588836
149603530
362671255
32588836
32588836
32588836
219213726
32588836
32588836
378798728
32588836
32588836

result:

ok 20 lines

Test #39:

score: 5
Accepted
time: 31ms
memory: 184120kb

input:

20 20
17 7
12 3
15 0
17 6
7 12
10 16
2 15
17 1
17 4
14 19
17 5
0 9
17 2
18 14
4 10
19 13
9 18
3 11
11 8
3 19
13 19
4 19
6 19
4 19
9 19
2 19
15 19
3 19
15 19
13 19
9 19
4 19
11 19
10 19
3 19
12 19
17 19
7 19
15 19
601569352 457345748 950690477 940932136 419713541 265386030 296609107 328433361 2843618...

output:

0
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849
71625849

result:

ok 20 lines

Test #40:

score: 5
Accepted
time: 11ms
memory: 184556kb

input:

500 500
61 206
219 174
496 451
386 483
285 100
385 54
98 441
455 305
40 443
496 139
88 374
462 27
426 92
259 245
155 262
205 223
29 190
496 33
54 120
93 182
167 350
23 211
147 429
463 41
372 354
31 465
461 258
117 433
149 21
27 322
240 387
498 202
261 279
233 315
485 68
389 390
256 82
91 405
350 370...

output:

0
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
770946
7709...

result:

ok 500 lines

Test #41:

score: 5
Accepted
time: 20ms
memory: 184548kb

input:

500 500
411 418
150 393
315 115
204 312
270 177
232 356
167 235
314 443
125 65
169 456
102 483
269 55
317 62
124 132
173 271
150 22
257 198
331 71
26 361
171 476
182 289
149 11
460 208
287 134
116 43
135 376
148 408
324 167
295 118
300 50
150 368
422 185
400 475
375 409
428 390
377 294
290 218
256 1...

output:

0
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
6449391
64...

result:

ok 500 lines

Test #42:

score: 5
Accepted
time: 23ms
memory: 184396kb

input:

500 500
191 230
92 212
99 452
123 269
259 301
156 121
195 231
429 5
240 327
243 66
402 436
460 55
9 16
251 290
417 156
334 245
112 406
162 186
371 294
108 275
18 119
397 235
50 333
25 278
254 300
456 185
433 49
172 495
94 334
147 240
398 441
498 268
306 135
35 448
25 18
327 391
95 372
421 232
42 386...

output:

0
3197154
3197154
3197154
3197154
14362633
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
3197154
65618143
3197154
3197154
3197154
3197154
3197154
3197154
43588673
3197154
3197154...

result:

ok 500 lines

Test #43:

score: 5
Accepted
time: 16ms
memory: 184328kb

input:

500 500
372 50
64 368
71 283
194 472
261 189
129 131
87 243
332 46
191 163
136 458
36 220
161 313
6 490
331 359
391 214
48 422
337 144
397 40
475 425
416 333
51 437
343 318
66 56
49 5
241 402
231 252
83 486
53 411
347 388
468 241
353 124
275 168
486 377
137 108
278 137
28 286
181 416
443 48
366 371
...

output:

0
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
244238527
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
1401277
...

result:

ok 500 lines

Test #44:

score: 5
Accepted
time: 27ms
memory: 184400kb

input:

500 500
243 313
464 344
352 116
215 310
460 330
181 193
85 95
373 382
185 91
227 62
70 138
342 103
284 101
143 445
88 163
339 139
69 472
262 247
188 267
429 73
129 422
225 25
275 389
276 364
166 184
293 148
417 23
332 90
219 76
120 48
101 199
137 100
55 72
207 214
365 370
83 4
204 18
342 146
216 357...

output:

0
2185120
2185120
97049678
16788183
705908158
2185120
2185120
42725473
2185120
2185120
2185120
97049678
108699201
2185120
2185120
2185120
362023472
2185120
2185120
2185120
2185120
2185120
11181490
32623158
2185120
2185120
2185120
2185120
21435748
2185120
2185120
2185120
7221891
2185120
21435748
2185...

result:

ok 500 lines

Test #45:

score: 5
Accepted
time: 15ms
memory: 184328kb

input:

500 500
350 403
403 289
88 400
310 62
150 122
454 111
244 358
76 307
124 285
10 266
184 75
126 421
439 127
265 409
400 70
79 86
232 367
138 345
404 207
249 313
140 188
228 333
492 203
490 452
186 461
246 492
173 28
364 23
497 154
204 316
269 429
329 198
319 306
281 430
71 448
123 14
334 155
385 123
...

output:

0
1623578
1623578
1623578
1623578
1623578
1623578
1623578
1623578
1623578
58121494
1623578
1623578
1623578
1623578
1623578
1623578
1623578
1623578
12712309
1623578
45586847
1623578
1623578
12712309
1623578
1623578
55828524
1623578
5437637
1623578
1623578
1623578
1623578
1623578
1623578
1623578
16235...

result:

ok 500 lines

Test #46:

score: 5
Accepted
time: 21ms
memory: 184544kb

input:

500 500
204 252
121 383
17 289
23 184
185 53
140 235
153 172
180 276
149 360
165 275
155 210
108 19
410 29
366 78
113 217
245 477
421 30
262 69
313 13
157 84
445 324
197 491
14 299
317 463
448 395
346 147
285 270
187 415
269 273
296 264
317 16
317 72
273 308
62 340
317 167
399 468
65 334
15 363
217 ...

output:

0
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
320391
3203...

result:

ok 500 lines

Test #47:

score: 5
Accepted
time: 32ms
memory: 184552kb

input:

500 500
80 439
397 302
494 6
286 440
87 284
162 134
165 458
435 457
205 298
433 242
37 247
196 308
280 105
136 61
118 49
284 53
495 487
63 337
409 18
225 234
55 141
459 128
480 148
203 496
246 245
266 174
398 367
91 116
367 37
103 296
237 222
271 90
476 82
135 195
306 107
342 232
216 449
231 366
456...

output:

0
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
626982
6269...

result:

ok 500 lines

Test #48:

score: 5
Accepted
time: 11ms
memory: 184336kb

input:

500 500
151 54
116 9
420 190
389 13
463 185
492 41
153 275
58 401
348 418
308 236
286 264
273 279
405 439
434 409
310 455
227 443
65 472
136 22
314 226
425 463
436 177
122 304
53 183
97 386
123 235
288 193
379 14
154 435
168 58
186 442
67 87
270 464
278 436
264 239
459 194
330 107
238 36
391 295
327...

output:

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
537913710
-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
...

result:

ok 500 lines

Test #49:

score: 5
Accepted
time: 19ms
memory: 184356kb

input:

500 500
281 87
80 344
406 57
240 106
431 207
144 338
256 211
387 421
288 307
333 497
4 396
344 449
442 53
32 8
312 441
453 200
40 271
400 88
267 114
78 25
407 245
56 104
360 153
289 377
144 312
62 20
410 155
422 443
144 189
457 495
100 349
203 241
182 220
166 256
144 122
396 368
23 259
26 174
345 28...

output:

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
-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 500 lines

Test #50:

score: 5
Accepted
time: 26ms
memory: 184124kb

input:

10 10
6 1
0 8
4 5
3 6
1 7
6 4
8 9
6 2
4 0
7 9
3 9
5 9
1 8
1 9
0 9
7 8
5 9
7 9
7 8
862356160 788992052 555344928 988358675 544571805 367930488 930965978 113006487 106980354 685457319

output:

0
106980354
106980354
106980354
106980354
106980354
106980354
106980354
106980354
106980354

result:

ok 10 lines

Test #51:

score: 5
Accepted
time: 23ms
memory: 184352kb

input:

10 10
4 5
7 2
0 8
2 9
8 4
7 0
4 3
0 1
8 6
7 4
3 6
2 2
3 5
7 1
6 9
3 9
4 4
9 6
9 2
624978489 419987641 360310630 109893809 16066306 444018075 314952966 440336058 617035212 664392432

output:

0
16066306
360310630
16066306
360310630
16066306
16066306
16066306
16066306
360310630

result:

ok 10 lines

Test #52:

score: 5
Accepted
time: 15ms
memory: 184156kb

input:

10 10
6 1
9 3
6 4
3 7
9 6
9 8
4 2
3 5
8 0
7 0
0 0
4 0
4 0
7 1
3 2
6 0
6 2
0 0
9 0
544668059 868121497 137406315 985565984 254857299 953292287 628906847 593822079 116451169 899911402

output:

0
-1
965130547
965130547
593822079
593822079
1222728926
710273248
-1
1493733481

result:

ok 10 lines

Test #53:

score: 5
Accepted
time: 27ms
memory: 184064kb

input:

20 20
5 13
16 8
12 9
4 14
2 6
2 3
10 18
7 10
7 0
4 5
17 11
7 12
4 7
5 17
18 19
16 4
16 2
7 1
8 15
10 16
8 19
15 19
6 19
9 16
10 19
6 19
16 18
5 17
13 18
1 16
5 19
18 18
19 19
11 19
6 17
12 17
14 19
12 19
6 19
184442386 954719942 433105203 178727138 438058180 26474227 787306104 14303762 213175066 544...

output:

0
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762
14303762

result:

ok 20 lines

Test #54:

score: 5
Accepted
time: 32ms
memory: 184280kb

input:

20 20
16 11
13 8
3 4
17 3
0 1
4 2
2 15
17 9
15 10
10 14
18 12
3 0
0 5
10 19
9 7
1 6
17 18
9 16
17 13
15 10
17 14
9 19
10 18
13 5
10 9
10 8
17 11
16 19
7 10
6 2
7 4
18 6
19 16
0 15
11 8
3 16
3 16
5 6
3 3
532432368 943572232 97392659 978981748 614404856 404652376 622219746 729818019 869681613 49505053...

output:

0
40773966
40773966
40773966
96561909
40773966
40773966
40773966
40773966
40773966
532432368
96561909
71217874
40773966
40773966
71217874
40773966
40773966
71217874
96561909

result:

ok 20 lines

Test #55:

score: 5
Accepted
time: 27ms
memory: 184280kb

input:

20 20
10 4
14 2
18 12
15 10
10 17
4 7
10 6
9 16
15 18
10 13
18 1
5 11
1 5
15 14
12 8
6 19
15 3
13 0
10 9
10 1
11 2
15 6
19 2
1 0
0 1
17 0
8 0
8 1
16 0
12 4
10 3
8 1
19 0
11 2
18 1
18 0
5 3
10 1
6 1
226902765 485478584 417306587 421702108 780333789 564315858 733926612 813892447 44879036 293367019 989...

output:

0
476423630
18831
612774245
485497415
18831
924100561
44897867
44897867
268363451
18831
18831
44897867
612774245
476423630
485497415
785182171
476423630
18831
612774245

result:

ok 20 lines

Test #56:

score: 5
Accepted
time: 32ms
memory: 184432kb

input:

500 500
258 364
231 276
95 376
274 1
12 37
231 2
34 221
266 315
155 284
424 342
196 289
145 97
409 207
348 283
386 120
255 287
401 295
266 49
66 485
59 301
117 48
429 491
133 358
371 294
256 406
338 24
436 111
481 83
397 15
266 435
266 173
354 35
314 482
410 441
465 456
230 347
192 134
112 353
236 1...

output:

0
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
603514
6035...

result:

ok 500 lines

Test #57:

score: 5
Accepted
time: 19ms
memory: 184332kb

input:

500 500
19 294
302 243
469 257
292 411
231 80
242 234
134 326
352 319
99 222
169 114
405 142
107 288
232 343
458 169
127 315
499 431
481 367
135 82
91 99
57 311
364 226
495 426
466 135
362 304
137 225
273 90
406 499
108 468
214 329
256 478
426 350
83 421
220 155
139 110
286 183
305 211
340 495
462 2...

output:

0
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
2368015
23...

result:

ok 500 lines

Test #58:

score: 5
Accepted
time: 19ms
memory: 184372kb

input:

500 500
149 444
334 30
170 18
344 196
286 25
433 88
105 310
445 31
72 411
112 241
221 64
244 441
407 205
0 468
39 284
138 74
19 395
222 313
365 324
60 267
99 41
251 141
137 70
257 63
279 220
24 269
130 218
374 84
396 231
176 301
195 396
155 447
240 182
181 442
7 430
285 233
109 335
334 91
272 473
25...

output:

0
5027619
5027619
5027619
5027619
732635566
5027619
5027619
66535878
5027619
9498498
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
5027619
74675479
5027619
5027619
5027619
5027619
9498498
5027619
5027619
5027619
5027619
5027619
502761...

result:

ok 500 lines

Test #59:

score: 5
Accepted
time: 16ms
memory: 184116kb

input:

5 5
1 4
0 1
0 2
1 3
0 4
3 4
3 3
3 4
4 4
356251622 244999661 599988275 914391300 963118056

output:

0
244999661
244999661
244999661
244999661

result:

ok 5 lines

Test #60:

score: 5
Accepted
time: 19ms
memory: 184120kb

input:

5 5
1 4
0 2
1 3
0 1
0 0
2 4
2 3
3 1
0 1
848600690 447099829 211804374 961820332 915051568

output:

0
848600690
848600690
1295700519
848600690

result:

ok 5 lines

Test #61:

score: 5
Accepted
time: 27ms
memory: 184048kb

input:

5 5
1 4
1 3
0 1
0 2
4 0
2 0
2 0
3 0
1 0
524427741 999411104 392621073 946301528 925732979

output:

0
-1
-1
-1
-1

result:

ok 5 lines

Test #62:

score: 5
Accepted
time: 36ms
memory: 184124kb

input:

10 10
4 9
2 5
0 1
2 6
1 3
3 8
1 4
0 2
3 7
8 5
4 6
1 5
9 6
9 6
5 6
7 6
4 6
2 4
7 6
741580620 234238988 485524663 335068921 30719219 982130970 259229780 111263847 906072058 295277236

output:

0
30719219
30719219
30719219
30719219
30719219
30719219
30719219
30719219
30719219

result:

ok 10 lines

Test #63:

score: 5
Accepted
time: 20ms
memory: 184092kb

input:

10 10
3 8
2 5
2 6
4 9
1 4
3 7
0 1
1 3
0 2
2 2
0 4
3 6
8 3
9 4
5 1
2 0
2 6
4 1
5 3
604510802 168223925 295654236 978000401 592767703 585283724 797821113 489121673 768487991 157072253

output:

0
168223925
168223925
168223925
168223925
295654236
295654236
168223925
168223925
168223925

result:

ok 10 lines

Test #64:

score: 5
Accepted
time: 30ms
memory: 184052kb

input:

10 10
2 5
0 2
0 1
3 7
1 3
3 8
4 9
1 4
2 6
5 0
0 0
1 0
0 0
9 0
6 1
4 0
3 0
6 0
8 0
542436999 588230248 779623364 83056795 901010660 198291041 965280026 462459787 659169979 15996895

output:

0
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 10 lines

Test #65:

score: 5
Accepted
time: 19ms
memory: 184052kb

input:

20 20
6 14
4 10
7 16
8 18
9 19
0 1
7 15
6 13
5 12
3 7
4 9
1 4
0 2
1 3
8 17
2 5
3 8
5 11
2 6
12 8
11 8
14 8
9 8
2 8
10 8
8 8
17 8
10 8
4 6
3 7
8 8
18 8
12 6
6 8
1 8
18 8
16 8
10 8
16 6
387698750 570432818 297569620 276137658 724453895 760946638 770833490 165973525 93544734 690933720 927284728 9203493...

output:

0
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734
93544734

result:

ok 20 lines

Test #66:

score: 5
Accepted
time: 36ms
memory: 184124kb

input:

20 20
5 12
4 10
8 17
7 15
6 13
5 11
8 18
4 9
0 1
1 3
0 2
2 5
2 6
7 16
6 14
9 19
3 7
1 4
3 8
18 7
13 4
5 5
9 2
6 8
8 5
16 4
6 4
15 0
9 6
13 6
8 8
6 8
19 0
5 1
1 2
12 1
19 2
11 1
3 8
872220622 193272299 730444521 18658514 693706168 869758470 711222143 847858150 819299744 2841546 493333146 848461327 83...

output:

0
193272299
2841546
2841546
2841546
2841546
18658514
18658514
38199713
2841546
2841546
2841546
2841546
990118919
730444521
2841546
836596786
2841546
848461327
2841546

result:

ok 20 lines

Test #67:

score: 5
Accepted
time: 15ms
memory: 184060kb

input:

20 20
8 18
7 16
2 5
7 15
9 19
5 12
4 9
2 6
3 8
1 3
6 14
8 17
6 13
0 1
1 4
0 2
3 7
4 10
5 11
0 0
6 0
7 0
5 0
15 0
13 0
14 0
4 0
9 0
4 0
2 0
10 1
14 0
11 0
15 0
16 1
2 0
8 1
14 0
8 1
396119312 796103047 43136967 857699803 696795723 719829249 854844550 114365970 350167633 360778181 952614697 992813896 ...

output:

0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 20 lines

Test #68:

score: 5
Accepted
time: 16ms
memory: 184456kb

input:

500 500
18 37
206 414
177 356
98 197
44 90
223 447
157 316
106 214
174 349
71 143
75 151
15 31
11 24
210 421
111 224
123 247
175 351
5 12
213 427
221 443
12 25
187 376
106 213
178 358
42 86
209 420
12 26
7 16
67 136
40 81
184 370
66 133
152 306
212 426
211 423
207 415
43 88
77 156
70 142
185 372
46 ...

output:

0
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
124841
1248...

result:

ok 500 lines

Test #69:

score: 5
Accepted
time: 43ms
memory: 184372kb

input:

500 500
226 453
209 419
53 107
159 319
190 382
182 365
186 374
23 47
93 187
30 61
45 91
16 33
142 285
104 209
155 311
134 270
110 221
54 109
215 432
191 383
139 280
144 289
88 177
140 282
75 151
52 106
136 273
56 114
65 132
117 236
228 458
158 318
46 94
24 49
226 454
98 197
175 352
228 457
187 375
9...

output:

0
215463128
24422616
24422616
99861002
24422616
24422616
24422616
157972325
913883736
432317663
220803689
212510154
30012003
24422616
24422616
99861002
329960862
30012003
24422616
27722054
409688944
128127146
38620212
432317663
24422616
24422616
432317663
24422616
157972325
24422616
24422616
6720110...

result:

ok 500 lines

Test #70:

score: 5
Accepted
time: 20ms
memory: 184404kb

input:

500 500
158 317
159 320
42 86
199 400
97 196
176 353
205 412
146 294
31 63
70 142
78 158
128 258
7 16
111 224
182 365
220 441
189 380
106 213
60 122
219 439
130 261
176 354
96 194
243 487
242 485
53 108
231 463
24 50
121 243
102 205
78 157
18 37
114 229
128 257
28 58
29 59
145 292
50 102
79 159
196 ...

output:

0
426929973
1229769403
438445005
1218560456
1557464610
1075532131
1106699971
602624866
689899491
2097888996
-1
816524750
869998882
463598310
169557843
1235334603
557276084
302515262
214418749
1619544610
196794437
796503145
-1
-1
512647503
603000484
298423585
435627769
1218560456
193261302
973866043
...

result:

ok 500 lines

Subtask #5:

score: 8
Accepted

Dependency #4:

100%
Accepted

Test #71:

score: 8
Accepted
time: 39ms
memory: 187088kb

input:

5000 5000
4426 3689
1019 3640
630 1680
975 778
57 2376
3988 1652
4740 247
2839 905
1009 2080
4524 1040
74 3498
1593 4186
512 4455
1831 3775
4097 1433
4884 2311
2817 819
4340 3361
1572 1720
3650 2253
912 2286
18 1673
3862 1527
3725 2883
1820 3941
1152 3236
422 4883
2088 2684
2262 395
3982 4770
2432 8...

output:

0
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
1058524
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67772
67...

result:

ok 5000 lines

Test #72:

score: 8
Accepted
time: 35ms
memory: 187136kb

input:

5000 5000
1593 2245
970 1672
1100 4412
1788 4990
4518 1037
2340 1876
794 4663
2241 1039
2722 922
3084 1356
3754 4003
1459 842
3625 478
4220 921
758 4133
2708 2570
558 4686
1545 1104
2012 3623
3854 369
253 2448
3239 2151
308 1072
4307 198
567 4265
4993 3568
4835 1014
3446 3100
72 2181
4240 2452
2620 ...

output:

0
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
817005
8170...

result:

ok 5000 lines

Test #73:

score: 8
Accepted
time: 37ms
memory: 187024kb

input:

5000 5000
1359 471
2483 2148
3872 4382
99 661
1616 1020
174 408
1440 584
315 150
2754 2311
857 2036
264 2952
8 4497
2979 3052
1266 2899
4936 724
1799 1354
52 660
913 1224
2334 877
1623 4742
813 982
4725 3648
3234 586
3189 132
4582 1526
2015 4581
4075 3760
1747 3338
2074 3392
3207 4096
4364 1974
3678...

output:

0
40511
40511
40511
40511
40511
40511
40511
44152623
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
3458255
11202454
33114607
40511
11202454
40511
18769680
40511
4922773
40511
40511
167336660
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511
40511...

result:

ok 5000 lines

Test #74:

score: 8
Accepted
time: 36ms
memory: 187116kb

input:

5000 5000
4658 754
247 1196
3466 981
3866 4484
498 1208
1497 2111
120 2426
4152 2979
3048 1724
364 3330
3621 4431
762 4112
518 3041
2147 2535
266 2684
1389 1436
3971 2890
171 265
3812 2318
280 3676
158 1474
3554 4731
4093 3683
1881 2586
4993 1383
3445 342
4630 1254
2474 237
2688 57
1663 4169
3715 21...

output:

0
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
102361
1023...

result:

ok 5000 lines

Test #75:

score: 8
Accepted
time: 35ms
memory: 187212kb

input:

5000 5000
356 3764
1880 1366
250 1020
3193 2918
4503 2594
502 1696
997 842
3735 3940
4629 568
2854 2540
3258 2753
3155 2298
203 2363
111 2352
1271 3093
786 3886
1864 1245
3359 2261
1559 2751
4440 2627
1685 2709
1762 4631
4488 441
1253 1827
651 1376
1165 3084
2531 4339
4217 2955
3111 1219
2489 4423
4...

output:

0
37847403
37847403
37847403
37847403
61954337
37847403
39033146
51364293
37847403
37847403
85367550
83961375
39033146
37847403
37847403
39444770
66555121
118350906
37847403
37847403
37847403
71540692
38984249
39033146
62434690
37847403
134639940
37847403
50566418
45048826
37847403
37847403
50490980...

result:

ok 5000 lines

Test #76:

score: 8
Accepted
time: 23ms
memory: 187044kb

input:

5000 5000
3938 789
3173 2683
3909 778
2153 3870
4297 319
2961 480
2479 298
2121 1877
3101 3768
2480 2887
4735 4923
4068 4516
821 1869
3940 825
4852 916
3309 2801
625 4284
694 2446
1546 225
1691 2596
814 1272
2017 1925
2275 4955
4948 2078
2513 4422
858 1710
3048 2538
1471 365
2155 82
3891 795
4280 16...

output:

0
197674
197674
197674
197674
197674
19574262
1406993
197674
197674
197674
197674
638000
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
197674
573739
197674
197674
539993
245942137
19767...

result:

ok 5000 lines

Test #77:

score: 8
Accepted
time: 35ms
memory: 187108kb

input:

5000 5000
2440 1442
339 2962
3325 4327
2147 217
21 674
4402 3282
1820 3172
1307 3627
3927 3898
4742 531
606 259
3376 4381
3391 383
3497 1427
2908 589
4094 187
1531 362
2746 652
2467 4490
3423 3152
4796 1988
1103 2619
1708 1931
261 3188
1234 1114
226 2810
1844 3613
4448 974
4229 2957
2588 4125
1805 8...

output:

0
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
161893
1618...

result:

ok 5000 lines

Test #78:

score: 8
Accepted
time: 24ms
memory: 187096kb

input:

5000 5000
2832 3084
3033 2813
781 2619
4325 3485
364 1560
2131 1040
3465 613
3569 4186
3206 69
127 878
4080 117
2325 339
1498 2408
2094 4426
3720 340
4463 2428
580 312
1515 922
3452 4110
3952 1145
2534 1362
3566 2107
3581 21
3086 1966
526 3153
2460 2707
1410 4018
2503 2734
3913 1707
667 4347
2003 11...

output:

0
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
220541
2205...

result:

ok 5000 lines

Test #79:

score: 8
Accepted
time: 31ms
memory: 186572kb

input:

5000 5000
2895 3836
4306 4802
2057 2253
3764 2434
4175 1333
3708 810
4726 2417
3082 1408
3607 3099
586 3234
3386 3829
1238 4621
1635 4253
3798 2604
4341 1382
3730 4043
2901 2500
3453 3757
4487 887
749 2721
3782 754
2231 1942
1784 3052
1841 2137
4378 4329
2791 4829
4068 4875
4945 2966
2483 4441
3857 ...

output:

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
-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 5000 lines

Test #80:

score: 8
Accepted
time: 23ms
memory: 186672kb

input:

5000 5000
1855 3916
1422 2648
316 2296
3994 2702
3883 272
689 1718
181 1078
1880 1948
2600 31
4785 67
3543 2128
1564 1995
3277 3911
4636 381
4033 4970
3721 3954
4346 2046
588 4467
15 4440
1629 4646
4000 4715
2454 2132
2777 3964
1273 4016
731 3836
746 1361
4425 2603
4830 57
3293 1244
2786 2755
3815 3...

output:

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
1574349129
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1420750584
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1422956260
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 5000 lines

Test #81:

score: 8
Accepted
time: 36ms
memory: 187172kb

input:

5000 5000
3052 3992
2333 1544
3298 3108
3579 4896
4641 1280
972 504
2414 520
4058 1513
2952 3873
4105 4046
2159 3003
3767 4702
993 2457
1084 2959
2062 162
1488 4615
1729 2723
2886 4921
3197 3538
1516 3597
463 1658
4283 4569
3101 153
719 1002
3848 4097
1123 2578
2631 835
3284 2413
1380 404
4401 1380
...

output:

0
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
107759
1077...

result:

ok 5000 lines

Test #82:

score: 8
Accepted
time: 40ms
memory: 186928kb

input:

5000 5000
1650 1032
1403 1294
679 3282
3714 2756
2937 4341
1964 372
3428 4661
2531 2908
4474 2307
188 2322
2556 1357
4190 378
2779 3539
4185 1387
4531 4390
2164 2375
1365 2408
649 2726
2428 1699
4323 465
1567 473
2959 935
4421 2531
3300 3379
2942 4885
1170 4182
685 643
4616 3400
1613 2079
2707 2067
...

output:

0
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
20733
2073...

result:

ok 5000 lines

Test #83:

score: 8
Accepted
time: 32ms
memory: 187096kb

input:

5000 5000
766 1686
3818 170
3499 876
4137 485
390 1222
2050 4740
881 1907
2214 2196
1868 2163
2681 1337
4047 3193
3892 2382
1758 1034
302 4601
3375 2745
1773 672
341 484
4414 1808
1339 1841
4389 1073
1450 3172
300 434
3113 3322
3381 1448
972 3323
1203 2051
4492 971
3331 1428
1494 3051
3665 3937
1011...

output:

0
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
182711764
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
215750
308569
215750
41867822
215750
215750
215750...

result:

ok 5000 lines

Test #84:

score: 8
Accepted
time: 38ms
memory: 187936kb

input:

5000 5000
2136 4274
983 1968
768 1538
1209 2420
530 1062
1474 2950
904 1810
1845 3692
1368 2737
1854 3710
1492 2986
876 1753
2371 4743
326 654
1235 2472
442 885
1029 2060
2042 4086
731 1464
1342 2685
1732 3466
1636 3274
2020 4042
304 609
1149 2299
747 1496
419 839
460 921
1615 3231
329 660
1680 3362...

output:

0
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
84289
1464912
84289
84289
84289
84289
387847
84289
84289
530658
84289
84289
84289
84289
84289
84289
272868
84289
84289
84289
84289
84289
84289
84289
387847
84289
84289
84289
84289
272868
84289
272868
84...

result:

ok 5000 lines

Test #85:

score: 8
Accepted
time: 28ms
memory: 187760kb

input:

5000 5000
2251 4504
526 1054
1305 2612
2143 4288
1360 2721
66 134
663 1327
1361 2724
45 92
231 463
1922 3845
1572 3146
2435 4872
1159 2319
338 678
315 632
497 996
621 1243
886 1774
1752 3506
1869 3739
1020 2042
371 743
960 1921
1235 2471
699 1399
921 1843
974 1949
1810 3621
317 635
2253 4508
1325 26...

output:

0
2622074
1279840
33646807
2048706
1279840
1279840
506238229
1279840
2048706
124495835
27361297
2048706
1279840
7701786
2145543
2048706
41362003
1279840
360982180
170290069
1279840
203875531
5281186
17199558
3117202
458788329
368053579
10541830
1279840
1279840
1279840
5036461
1279840
31707193
528118...

result:

ok 5000 lines

Test #86:

score: 8
Accepted
time: 27ms
memory: 186984kb

input:

5000 5000
228 457
941 1884
2229 4460
1765 3532
404 809
2066 4134
1336 2674
2305 4611
1318 2637
2380 4761
2306 4614
1834 3669
1115 2231
2459 4919
895 1792
1725 3451
676 1353
1973 3948
2350 4702
2287 4576
677 1356
188 378
411 823
433 867
1527 3056
1928 3857
1211 2423
727 1456
2102 4206
1319 2640
1623 ...

output:

0
27889434
277798772
83848920
21606661
846491500
90412294
101780008
159598347
126549548
348842966
358433748
509613620
272506689
351048327
165286971
500821457
246925990
566893751
103283839
721576889
818737917
356147232
243069023
517335544
256833593
50113349
461477083
123218104
242531831
191436858
100...

result:

ok 5000 lines

Subtask #6:

score: 47
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #87:

score: 47
Accepted
time: 533ms
memory: 263104kb

input:

100000 100000
48246 3261
13942 41714
70510 87011
7899 48057
89181 48916
79627 34784
65317 53515
14210 31443
71651 97258
38408 69813
6473 8328
71059 18744
60724 85784
56350 13265
35782 67488
27959 68801
50678 3998
60150 62362
37603 67643
5187 80108
74151 73085
68067 49481
7747 37918
24191 76501
70142...

output:

0
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
35189
3518...

result:

ok 100000 lines

Test #88:

score: 47
Accepted
time: 554ms
memory: 263156kb

input:

100000 100000
53125 54096
51681 41789
29209 79345
31749 60714
74822 53246
64952 70818
93553 82780
91951 42299
13400 79731
12249 8756
63158 90127
48498 39703
90080 81889
68222 55515
72787 78191
14608 19512
98527 69900
67472 24155
38859 8300
32239 77434
66535 99862
77872 49072
6881 34024
62832 68727
1...

output:

0
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
7154
715...

result:

ok 100000 lines

Test #89:

score: 47
Accepted
time: 531ms
memory: 262028kb

input:

100000 100000
26052 18308
95839 56864
19263 54858
24397 12951
82314 38068
49527 95088
36820 71937
14849 9119
57093 50323
88570 37227
8032 32161
46137 31200
43066 66058
25246 77935
14119 74218
46289 26561
3252 54582
26022 68938
83659 91520
8903 60705
14382 58571
45807 1754
79220 25299
29350 50454
239...

output:

0
8435
8435
8435
96811046
40843311
8435
8435
8435
8435
13688387
2993890
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
88816
8435
8435
8435
6469187
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8435
8422050
8435
8435
8435
8...

result:

ok 100000 lines

Test #90:

score: 47
Accepted
time: 541ms
memory: 262772kb

input:

100000 100000
54491 50034
96323 40434
39778 92371
24116 86024
36992 68206
92414 80910
34901 42519
56106 16067
54056 70251
73239 14097
76853 42047
30989 13743
46782 37871
92080 68361
3386 25258
76947 71616
93956 29139
35010 90507
28675 68936
48854 22001
15922 25824
40762 21801
67140 48027
14569 98099...

output:

0
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
1299342
5998
5998
9104
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
5998
...

result:

ok 100000 lines

Test #91:

score: 47
Accepted
time: 535ms
memory: 262340kb

input:

100000 100000
26298 35452
31322 41214
12962 89091
2399 87430
96860 29016
72476 59176
71125 53640
29884 63753
91686 52247
8699 2877
9976 69353
45231 3067
51898 18522
60374 78506
4995 38291
6095 82820
97301 12260
55471 39278
267 23368
95685 59007
28011 74353
10517 41913
81361 48431
22059 10318
36763 8...

output:

0
11845
2997
2997
2997
56097999
2997
45177
2997
2997
50370647
2593769
2997
2997
2997
11845
26392
2997
26392
2997
2997
550568
2997
1173339
6273237
11845
54485235
8210223
8945946
136837
11845
2264811
2997
11845
2997
11845
2997
2997
2997
2997
2997
2997
45177
2997
2997
2997
11845
26392
26392
11845
2997
...

result:

ok 100000 lines

Test #92:

score: 47
Accepted
time: 569ms
memory: 263356kb

input:

100000 100000
52455 41434
69954 51288
54448 19482
77032 71710
28198 93400
82448 10675
80031 83716
62755 63718
66689 27198
60217 26896
47503 25845
54931 25758
20544 65203
37588 34861
22816 45480
39096 12213
31683 83459
43702 56449
28323 41397
37312 70284
39150 46182
52258 69973
39967 39009
65165 6403...

output:

0
6188
15613241
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188
6188...

result:

ok 100000 lines

Test #93:

score: 47
Accepted
time: 536ms
memory: 262648kb

input:

100000 100000
26295 47477
74632 32935
81472 38967
79566 30364
46868 5666
80187 74441
8364 60469
97163 13356
3709 27947
11191 81
39462 87377
8682 34572
19395 17740
46609 35283
40177 89128
25424 88452
46734 69925
3632 75212
80187 39951
74063 95093
44461 25937
6781 7937
44308 58002
31521 86319
4503 427...

output:

0
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
17672
1767...

result:

ok 100000 lines

Test #94:

score: 47
Accepted
time: 523ms
memory: 262668kb

input:

100000 100000
9514 34045
64213 12631
74799 67823
75129 45149
29495 7739
61938 48452
17307 66329
89982 38910
65453 42187
87100 79861
35333 59782
72189 72814
38757 16752
24782 32639
43214 60294
27084 55255
24945 48650
58292 918
35960 5929
70538 98997
55360 57564
45147 72647
61232 78860
20251 71784
238...

output:

0
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
13455
1345...

result:

ok 100000 lines

Test #95:

score: 47
Accepted
time: 277ms
memory: 244084kb

input:

100000 100000
88366 7223
40658 73815
55052 15935
80715 80310
71840 65527
54054 839
73336 28748
91317 36179
86168 54061
28980 49764
90103 53865
72383 72446
4348 39024
97603 15908
87170 13918
3994 9819
71046 63695
92977 2159
89636 7410
14809 85905
47788 26570
43768 10215
88121 56650
16438 1866
17741 6...

output:

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
-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 100000 lines

Test #96:

score: 47
Accepted
time: 511ms
memory: 250740kb

input:

100000 100000
82371 83871
5498 52157
30752 60585
53063 9218
72218 39064
48339 80104
94269 85200
3469 37564
39344 87388
27684 66396
1494 31866
22467 4230
4061 63015
70757 81548
11030 4397
43188 10481
28657 86608
89429 50070
24703 75651
38676 3690
28626 27707
1853 24818
46045 39816
14685 53540
34279 7...

output:

0
172323129
115401130
107595060
471376550
109613986
198595612
906712247
123163415
491699127
323251259
171053520
150350262
165622676
202045341
107186134
274348769
184987961
117242690
112946725
256597645
141980519
118511773
90886912
120367972
273987643
89550465
205342894
93786773
120758315
110039495
1...

result:

ok 100000 lines

Test #97:

score: 47
Accepted
time: 563ms
memory: 245444kb

input:

100000 100000
74116 58605
99519 78064
94321 77492
35040 71469
27084 20212
849 41016
52805 25368
13636 84764
85642 62989
20224 82595
5306 23545
49051 42060
17150 76111
71449 95103
9576 16707
65923 65688
69646 33129
15912 66141
61399 48689
59816 83317
16300 8795
45396 82607
55518 79497
57392 69656
587...

output:

0
57438610
92496770
172007336
137513211
57196293
244557066
68103307
57205866
65076387
59556021
351894611
262443821
170334987
113081575
599702666
57205866
84936369
57185035
60362479
294084846
68874103
112350826
57185035
435989737
566961613
57196293
65058757
59161024
377575550
60290305
505226836
62087...

result:

ok 100000 lines

Test #98:

score: 47
Accepted
time: 580ms
memory: 257540kb

input:

100000 100000
77630 26549
26779 88393
65009 55256
99891 30439
47485 52025
83619 21519
151 56604
63457 93202
4364 89130
54007 89273
65671 5853
77744 96818
92707 65994
43083 35758
43923 14083
59375 11340
23476 90270
26138 31890
42014 38371
67835 50898
40146 96506
16095 47790
86195 37770
53073 9427
265...

output:

0
31232
31232
31232
31232
31232
31232
32184
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
97654
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
31232
3123...

result:

ok 100000 lines

Test #99:

score: 47
Accepted
time: 615ms
memory: 257996kb

input:

100000 100000
44884 39900
57639 5221
53977 16048
23300 24563
93977 81427
91642 44905
86495 82692
86931 83827
79434 2011
40776 5713
42283 75840
47551 39970
93761 92820
40555 65156
70123 18422
30469 55945
69080 38959
544 48432
88237 11184
86124 39320
65476 38857
8358 45469
39652 32544
46153 53852
9863...

output:

0
5239
5239
49596
5239
5239
1380392
49596
49596
49596
88266
49596
5630
254126989
5239
49596
21060
21060
5239
49596
5239
5239
5239
5630
21060
49596
5239
52937
164179
49596
21060
295829403
21060
103240
49596
21060
477914
5239
5239
1358450
5239
5239
367021
25009493
464381
5239
5239
36970139
5239
52937
...

result:

ok 100000 lines

Test #100:

score: 47
Accepted
time: 587ms
memory: 261340kb

input:

100000 100000
6136 57362
69350 78918
28780 31856
51279 62240
49013 94185
84260 84302
50905 59786
99348 36377
72464 42922
42543 95266
86458 12684
75463 64202
28051 15776
39447 38544
77817 41040
49829 79706
16737 31154
28594 32903
30699 57476
31656 57400
43183 16363
84087 97743
30120 91371
65768 42049...

output:

0
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
11123
1112...

result:

ok 100000 lines

Test #101:

score: 47
Accepted
time: 463ms
memory: 252484kb

input:

100000 100000
20438 58638
9172 95867
10159 52593
98551 12364
19363 87096
4402 59800
49731 6991
1349 67353
58236 81117
73670 31087
37419 83855
49435 5553
96421 41906
98678 65524
4954 54158
53120 23193
30205 19131
43972 93487
98716 66997
85077 4691
1395 48256
985 58265
16461 22767
19692 1441
79011 784...

output:

0
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
9233
923...

result:

ok 100000 lines

Test #102:

score: 47
Accepted
time: 480ms
memory: 252680kb

input:

100000 100000
63730 82909
20090 70089
56839 10736
57230 86986
87216 91569
57464 76206
2425 58294
97532 2468
54640 34916
95186 31496
8301 64951
6355 67183
35716 36406
3583 24315
35895 46597
31144 50367
11595 79163
51564 11369
5501 15986
90380 27797
33454 26376
80906 56226
52982 15724
31152 22315
1202...

output:

0
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
9387
938...

result:

ok 100000 lines

Test #103:

score: 47
Accepted
time: 483ms
memory: 252756kb

input:

100000 100000
38571 64171
40576 22460
74321 85175
58690 596
49934 28715
81011 90484
10538 99647
86465 44811
35672 65217
8704 62667
3245 31836
56414 33668
19854 6043
26261 35879
69297 84716
44126 84194
2044 37632
30827 34363
32236 17742
21184 74106
2753 57874
51258 73421
62059 56072
95989 5606
98850 ...

output:

0
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
5145
514...

result:

ok 100000 lines

Test #104:

score: 47
Accepted
time: 460ms
memory: 278636kb

input:

100000 100000
16403 32807
46127 92256
33491 66983
43992 87986
34457 68916
25069 50140
42202 84405
6872 13745
9732 19465
47060 94122
4132 8266
32928 65858
19563 39127
26856 53714
28770 57542
37755 75512
21980 43962
43905 87812
928 1858
40735 81472
40615 81232
18878 37758
27861 55723
11144 22289
24809...

output:

0
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
26308
3742
3742
3742
3742
299990
3742
3742
3742
3742
3742
3742
3742
60094
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
158225
3742
77545
3742
3742
3742
3742
3742
3742
77545
3742
3742
3742
3742
...

result:

ok 100000 lines

Test #105:

score: 47
Accepted
time: 470ms
memory: 271888kb

input:

100000 100000
41781 83563
9312 18626
27463 54927
35251 70504
40107 80216
6149 12299
2850 5701
17788 35578
45825 91652
10377 20755
15744 31489
15673 31348
48824 97650
39690 79381
24848 49697
43119 86240
27991 55983
12936 25874
16524 33050
8184 16370
42945 85891
44392 88785
45622 91245
39298 78597
475...

output:

0
337734050
356052451
334627646
531777131
334853020
334614517
334614517
334614517
334614517
334614517
334627646
783495200
334993535
334614517
335390377
334808300
334614517
334627646
339595557
336360273
433310138
338544319
334616383
342969747
334800724
334627646
337507232
341468543
338014723
33480072...

result:

ok 100000 lines

Test #106:

score: 47
Accepted
time: 441ms
memory: 253808kb

input:

100000 100000
39605 79212
41333 82667
11645 23291
653 1308
28465 56932
37386 74773
8557 17115
23191 46384
17308 34618
32020 64042
6694 13389
46738 93478
5428 10857
39536 79073
16636 33273
29069 58139
16238 32478
9369 18740
7721 15444
49079 98160
11543 23088
22027 44056
23860 47721
41705 83411
9252 1...

output:

0
616710629
552446812
1211633849
709459067
555541381
674030594
635462632
765615457
797636900
1308159646
567392884
1235881617
688934538
693397842
1123235383
771654981
919123559
666283205
601393430
536850221
610963880
814068179
939511297
583443811
530607974
536436717
797021701
737807167
529879875
5360...

result:

ok 100000 lines

Test #107:

score: 47
Accepted
time: 757ms
memory: 309876kb

input:

100000 100000
68038 68039
82659 82660
20328 20329
70679 70680
34378 34379
50104 50105
23942 23943
59345 59346
79787 79788
58362 58363
16188 16189
70908 70909
29915 29916
45009 45010
4663 4664
75459 75460
89596 89597
97899 97900
83637 83638
10828 10829
60675 60676
15072 15073
30822 30823
31173 31174
...

output:

0
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
3742
374...

result:

ok 100000 lines

Test #108:

score: 47
Accepted
time: 819ms
memory: 311360kb

input:

100000 100000
66849 66850
52449 52450
62849 62850
71870 71871
19152 19153
55042 55043
10068 10069
32202 32203
98667 98668
46577 46578
51420 51421
48740 48741
29134 29135
84746 84747
54387 54388
66536 66537
20851 20852
74708 74709
86883 86884
77016 77017
46194 46195
80651 80652
94833 94834
96376 9637...

output:

0
8140
368159
8140
8140
8140
8140
8140
542550
8140
8140
11611
8140
8140
112058
8140
8140
8140
397246
130391
8297350
57558
8140
223875
8140
53549
8140
58428
8140
8140
8140
57558
8140
70050
630076
73566
8140
8140
221432
8140
8140
630076
58428
795630
8140
76174
8140
8140
8140
8140
8140
8140
2834864
814...

result:

ok 100000 lines

Test #109:

score: 47
Accepted
time: 836ms
memory: 301408kb

input:

100000 100000
54459 54460
43547 43548
56075 56076
81751 81752
96835 96836
59254 59255
90574 90575
4758 4759
19434 19435
13361 13362
81046 81047
36258 36259
96852 96853
27850 27851
51407 51408
48548 48549
68037 68038
98984 98985
57022 57023
5143 5144
46757 46758
93469 93470
32229 32230
31771 31772
28...

output:

0
147136
126053
1565825
173320
10667817
280252
7132699
8668922
3442529
104910
771981
4531599
78086488
2075883
4130424
1228533
333704
243796
3357301
771981
560109
1228533
233614
392373
2411548
280252
1643624
116032
652943
138626
138626
333704
704262
2727397
116032
243796
866992
3275573
3879471
104910...

result:

ok 100000 lines

Test #110:

score: 47
Accepted
time: 129ms
memory: 222792kb

input:

10000 100000
1816 1817
769 770
9562 9574
7325 7341
3970 3971
4623 4624
177 178
9299 9329
8600 8630
1900 1901
754 755
3109 3110
257 258
7526 7533
7949 7959
9139 9148
6614 6618
9504 9529
4997 4998
7532 7544
7613 7637
8246 8273
2624 2625
4782 8780
3767 3768
1324 1325
4766 4767
512 513
9901 9902
7253 72...

output:

0
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
29765
2976...

result:

ok 100000 lines

Test #111:

score: 47
Accepted
time: 121ms
memory: 223112kb

input:

10000 100000
3349 3350
7315 7320
5940 5970
542 543
5373 5397
2900 2901
6419 6438
2831 2832
7113 7127
6281 6303
8220 8221
9146 9162
2777 2778
8252 8284
1794 1795
691 692
6842 6865
3275 3276
4007 4008
4576 4577
6902 6914
3153 3154
3250 3251
2272 2273
2893 2894
1441 1442
5943 5976
7118 7137
1981 1982
2...

output:

0
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
192088
1920...

result:

ok 100000 lines

Test #112:

score: 47
Accepted
time: 125ms
memory: 222836kb

input:

10000 100000
7660 7661
966 967
7400 7420
9435 9460
8784 8788
94 95
8024 8039
8593 8616
1838 1839
5522 5555
8870 8891
3035 3036
902 903
6283 6307
3747 3748
88 89
6084 6119
2423 2424
9846 9863
371 372
3447 3448
654 655
710 711
2903 2904
2808 2809
4388 4389
4315 7380
3440 3441
6902 6915
182 183
1970 19...

output:

0
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
34995
3499...

result:

ok 100000 lines

Test #113:

score: 47
Accepted
time: 126ms
memory: 223104kb

input:

10000 100000
6895 6900
4510 4511
9073 9087
2141 2142
9836 9842
2467 2468
3494 3495
1096 1097
6120 6121
5644 5659
1636 1637
5098 5126
6274 6288
38 39
4921 4922
9140 9150
6356 6383
7464 7478
9846 9863
150 151
3161 3162
8645 8651
9981 9992
9353 9366
1464 1465
6432 6464
1302 1303
2800 2801
5454 5488
790...

output:

0
12376
12376
12376
12376
1831743
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
1142110
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
12376
3323108
12376
12376
12376
1237...

result:

ok 100000 lines

Test #114:

score: 47
Accepted
time: 151ms
memory: 221472kb

input:

10000 100000
5491 5492
5926 5943
7267 7295
160 161
6565 6591
7823 7847
6079 6108
3604 3605
9631 9642
680 681
7875 7881
2791 2792
2493 2494
6978 6997
6610 6611
2934 2935
9904 9909
1426 1427
1420 1421
356 357
123 124
7254 7268
3649 3650
2442 2443
2191 2192
2429 2430
2588 2589
7950 7960
8870 8891
8182 ...

output:

0
45790
1792610
45790
1024990
264033
45790
45790
554171
45790
45790
264033
45790
1129430
45790
1050401
45790
45790
1024990
45790
3735207
45790
45790
45790
264033
45790
1024990
45790
45790
45790
3201898
45790
264033
45790
2308263
45790
1024990
1314629
45790
45790
45790
45790
9390182
45790
45790
45790...

result:

ok 100000 lines

Test #115:

score: 47
Accepted
time: 140ms
memory: 221832kb

input:

10000 100000
461 462
5171 5203
9280 9290
9715 9741
2116 2117
2826 2827
3384 3385
6560 6581
7245 7251
425 426
1071 1072
1267 1268
6831 6843
9352 9364
8871 8893
5369 5388
985 986
1248 1249
6356 6383
7125 7151
6405 6411
4298 4299
3749 3750
3167 3168
2101 2102
8454 8478
1924 1925
1211 1212
3762 3763
781...

output:

0
2257314
64217
64217
64217
64217
1088128
64217
685218
64217
64217
64217
685218
2916279
246456
64217
64217
246456
64217
2257314
685218
64217
64217
702957
64217
64217
64217
1326378
64217
64217
685218
64217
64217
7413237
64217
724185
64217
64217
64217
64217
64217
246456
246456
64217
64217
64217
685218...

result:

ok 100000 lines

Test #116:

score: 47
Accepted
time: 107ms
memory: 213384kb

input:

10000 100000
3829 9550
8223 8226
2296 2297
1115 1116
7262 7284
5103 5136
6845 6870
9291 9312
6625 6641
8721 8732
6286 6312
4904 4905
1960 1961
2830 2831
3560 3561
5571 5583
7402 7425
1706 1707
8601 8632
3323 3324
8870 8890
3406 3407
1541 1542
7602 7614
4920 4921
693 694
192 193
8460 8490
7828 7856
4...

output:

0
2917115
3946656
10141594
4683587
5925129
26065998
4617923
23070330
1775222
309411
16340485
71924295
1775222
2318736
5925129
499965
-1
4164238
76194590
1638071
829
829
240483
39146405
7610827
6954834
3946656
490165
3946656
18933431
240483
37714990
16577353
6945299
829
16524100
24969963
2318736
5585...

result:

ok 100000 lines

Test #117:

score: 47
Accepted
time: 125ms
memory: 214096kb

input:

10000 100000
7553 7587
8036 8062
871 872
6751 6752
975 976
6827 6834
5306 5332
1112 1113
5427 5434
384 385
8883 8917
3745 3746
3796 3797
290 291
6285 6311
217 218
5077 5084
4667 4668
6541 6542
5842 5844
3100 3101
9717 9744
9491 9503
3726 3727
2570 2571
3789 3790
1415 1416
6433 6466
9066 9072
7688 77...

output:

0
9971565
19320722
25268655
10933573
9786192
93144340
57429937
12468184
16156340
-1
44803262
15455605
16507115
16503478
10053349
14069212
26210212
55383307
14090942
91785351
10108292
10636956
16503478
10636956
13033105
14758870
18420587
24890089
18420587
10528389
14758870
13942081
108392270
18040844...

result:

ok 100000 lines

Test #118:

score: 47
Accepted
time: 293ms
memory: 255540kb

input:

50000 100000
12401 12402
36230 36242
10185 10186
31321 31323
21134 21135
31978 32004
21547 21548
18890 18891
9330 9331
8751 8752
27261 27311
37683 37726
10395 10396
36416 36456
30740 30792
30111 30166
16426 16427
23380 23381
33758 33826
40809 40819
12185 12186
35004 35054
40860 40921
28077 28152
170...

output:

0
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
3770
377...

result:

ok 100000 lines

Test #119:

score: 47
Accepted
time: 305ms
memory: 255272kb

input:

50000 100000
33228 33241
25976 26004
18513 18514
22130 22131
26759 26780
7864 7865
10588 10589
11420 11421
46360 46390
40518 40553
5677 5678
30124 30193
2258 2259
34480 34481
2227 2228
36406 36436
38807 38868
44921 44935
47318 47358
13933 13934
8754 8755
42751 42807
18011 18012
29142 29176
22088 220...

output:

0
29089
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
29089
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
14787
29089
14787
14787
14787
14787
14787
14787
14787
14787
1478...

result:

ok 100000 lines

Test #120:

score: 47
Accepted
time: 299ms
memory: 255328kb

input:

50000 100000
4312 4313
40558 40633
30292 30370
13915 13916
46999 47037
43077 43143
34061 34117
27431 27492
29440 29456
40339 40352
3948 3949
29742 29744
41458 41485
3984 3985
24022 24023
47959 48008
5405 5406
13996 13997
23658 23659
9154 9155
37970 37985
18037 18038
33860 33872
45419 45456
18075 180...

output:

0
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
16107
1610...

result:

ok 100000 lines

Test #121:

score: 47
Accepted
time: 288ms
memory: 255440kb

input:

50000 100000
13325 13326
40519 40554
3584 3585
48113 48158
47952 47994
47337 47397
14491 14492
18770 18771
643 644
14360 14361
10946 10947
4069 4070
28549 28622
6424 6425
18357 18358
49491 49493
503 504
28845 28898
42104 42145
29976 30054
23905 23906
23916 23917
43815 43828
22429 22430
10344 10345
1...

output:

0
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
159112
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
39760
397...

result:

ok 100000 lines

Test #122:

score: 47
Accepted
time: 367ms
memory: 253736kb

input:

50000 100000
32905 32910
15349 15350
42290 42358
41657 41725
49072 49128
19884 19885
18452 18453
9646 9647
43549 43613
5282 5283
29170 29232
3536 3537
10968 10969
44811 44873
14974 14975
2785 2786
23046 23047
31527 31576
47788 47824
26 27
11222 11223
18771 18772
47976 48043
5428 5429
22120 22121
186...

output:

0
185728
185728
185728
225982
185728
185728
185728
210480
185728
192545
185728
185728
192545
185728
185728
185728
925138
185728
185728
185728
185728
185728
315377
192545
207044
185728
210480
185728
185728
185728
305862
185728
185728
185728
450426
185728
315377
192545
925138
207044
185728
192545
1857...

result:

ok 100000 lines

Test #123:

score: 47
Accepted
time: 367ms
memory: 253500kb

input:

50000 100000
29929 29961
37173 37181
45718 45739
34714 34791
21346 21347
14133 14134
29969 30040
37325 37326
10412 10413
37972 37989
41598 41607
17162 17163
47611 47628
16419 16420
32951 33003
25024 25048
5198 5199
7994 7995
12459 12460
31058 31113
47770 47788
36545 36556
13453 13454
24018 24019
721...

output:

0
49043
25269
49043
25269
25269
49043
49043
25269
25269
122647
49043
49043
49043
49043
49043
49043
25269
49043
49043
25269
859642
25269
25269
49043
907211
25269
49043
49043
176348
49043
49043
25269
49043
49043
25269
25269
25269
25269
49043
54748
54748
54748
49043
25269
49043
25269
54748
25269
49043
...

result:

ok 100000 lines

Test #124:

score: 47
Accepted
time: 328ms
memory: 248288kb

input:

50000 100000
1125 1126
2058 2059
20088 20089
8765 8766
25860 25930
21880 21881
36577 36621
27448 27526
44973 45038
6962 6963
45862 45868
49724 49801
11599 11600
35112 35113
43541 43596
24002 24003
37715 37790
45911 45967
25975 26003
9468 9469
19957 19958
32013 32074
9967 9968
46712 46779
23314 23315...

output:

0
5291030
4193382
4852178
6384452
6937758
4070858
4329421
4115798
4509512
206958090
4070858
7203305
10712735
4080683
6831260
5391428
4115798
-1
4115798
4080683
5188305
4661000
4070858
14423519
4661000
4897140
9815482
-1
4852178
4813489
4159781
4070858
4115798
4771187
4115798
6831260
4080683
5877791
...

result:

ok 100000 lines

Test #125:

score: 47
Accepted
time: 358ms
memory: 248272kb

input:

50000 100000
11509 11510
9002 9003
15353 15354
37982 38008
25334 25353
2077 2078
11256 11257
15250 15251
21403 21404
42586 42635
23272 23273
7894 7895
42116 42169
44489 44545
616 617
21187 21188
24137 24138
39861 39870
16089 16090
10947 10948
29472 29520
19139 19140
12242 12243
21457 21458
42720 427...

output:

0
2856322
3092375
4033919
2576952
4169421
3429957
2856322
2407466
2407466
2477307
2856339
2943266
2338907
2810624
2407466
4033919
-1
5538492
6620297
2856322
3155510
4011131
2576952
3855303
2856322
4033919
4033919
5538492
3583434
2410211
2856339
4705349
3177979
4384595
2477307
2407466
4033919
7465169...

result:

ok 100000 lines

Test #126:

score: 47
Accepted
time: 578ms
memory: 297600kb

input:

100000 100000
40547 40548
61849 61880
28657 28658
52719 52763
28796 28797
75005 75035
93313 93364
10561 10562
18024 18025
55146 55163
10360 10361
43285 43286
69221 69264
198 199
23381 23382
71516 71624
81695 81724
91971 92018
95274 95279
93090 93141
81237 81254
99529 99553
40344 40345
76780 76800
51...

output:

0
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
22359
2235...

result:

ok 100000 lines

Test #127:

score: 47
Accepted
time: 613ms
memory: 297692kb

input:

100000 100000
50519 50593
49359 49360
60324 60390
27488 27489
57844 57884
55362 55373
28787 28788
29113 29114
43200 43201
5023 5024
28221 28222
86437 86526
67709 67802
2946 2947
81001 81006
41414 41415
3768 3769
88136 88139
81913 81938
58928 58936
57658 57735
8459 8460
37313 37314
98272 98377
50736 ...

output:

0
73841
6052
6052
6052
6052
83997
6052
6052
6052
6052
73841
83997
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
73841
6052
6052
6052
6052
6052
6052
29190
6052
29190
6052
6052
6052
6052
6052
6052
6052
29190
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
6052
...

result:

ok 100000 lines

Test #128:

score: 47
Accepted
time: 587ms
memory: 297904kb

input:

100000 100000
79530 79625
68779 68827
1966 1967
71412 71417
71425 71443
78186 78275
56275 56307
29557 29558
46183 46184
39684 39685
4166 4167
48595 48596
60315 60372
38282 38283
14197 14198
89792 89890
54283 54329
8161 8162
25810 25811
70376 70460
36507 36508
59251 59360
25342 25343
68792 68853
5434...

output:

0
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
6108
610...

result:

ok 100000 lines

Test #129:

score: 47
Accepted
time: 571ms
memory: 298068kb

input:

100000 100000
58750 58804
53433 53521
25959 25960
56570 56673
31669 31670
25609 25610
96620 96633
86422 86495
36885 36886
2014 2015
50483 50521
27756 27757
40319 40320
53438 53532
81506 81570
20675 20676
18190 18191
24592 24593
63464 63548
270 271
86424 86500
43245 43246
79741 79824
86840 86885
9381...

output:

0
3998
3998
3998
3998
3998
3998
23024
3998
3998
3998
46689
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
101594
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998...

result:

ok 100000 lines

Test #130:

score: 47
Accepted
time: 576ms
memory: 295920kb

input:

100000 100000
79904 79927
22796 22797
99133 99206
99336 99389
34145 34146
95370 95471
34057 34058
40542 40543
95108 95170
38617 38618
99287 99292
4217 4218
71207 71230
51148 51182
94645 94691
47763 91255
72626 72730
84198 84278
23308 23309
12557 12558
75448 75475
14665 14666
21233 21234
14895 14896
...

output:

0
82183
58771
58771
58771
83293
135912
102654
82183
58771
207311
102654
58771
83293
58771
817082
58771
58771
73847
182557
58771
58771
1842962
58771
102654
58771
58771
58771
58771
58771
113154
83293
58771
58771
58771
434912
58771
58771
651458
58771
82183
102654
58771
58771
58771
58771
83293
58771
821...

result:

ok 100000 lines

Test #131:

score: 47
Accepted
time: 606ms
memory: 295664kb

input:

100000 100000
57015 57117
61408 61444
74314 74321
866 867
62525 62562
37447 37448
71889 71924
66594 66687
1034 1035
98477 98564
48117 48118
24834 24835
62560 62633
52040 52073
50317 50411
69936 70025
30244 30245
81480 81517
6238 6239
97811 97901
13068 13069
58330 58410
25281 25282
63676 63750
27494 ...

output:

0
6105
143254
6105
6105
6105
27135
6105
6105
6105
6105
6105
6105
6105
6105
37300
18738
6105
6105
6105
27135
21501
6105
6105
84196
18738
2290973
6105
6105
37300
6105
6105
6105
6105
6105
6105
6105
37300
6105
288677
6105
6105
27135
18738
6105
27135
18738
6105
390502
2138744
27135
37300
6105
6105
6105
6...

result:

ok 100000 lines

Test #132:

score: 47
Accepted
time: 552ms
memory: 290100kb

input:

100000 100000
97993 98041
85236 85238
28660 28661
76200 76309
96610 96614
1661 1662
83033 83063
10113 10114
68619 68729
86209 86293
95943 95949
92202 92258
71710 71790
21243 21244
16067 16068
29736 29737
42688 42689
94029 94127
94708 94816
59377 59388
73483 73552
80574 80597
79993 80104
98436 98481
...

output:

0
887268
3442354
887268
992679
1793072
1216672
1256062
902734
5510228
836611
1022294
1029155
1022294
767946
836611
836611
1747123
1029155
902734
1555026
1029155
1110025
767946
767946
1307132
1051771
1022294
4756252
992679
992679
1307132
1413351
1555026
1793072
1688908
789132
1413351
836611
6268567
1...

result:

ok 100000 lines

Test #133:

score: 47
Accepted
time: 560ms
memory: 289736kb

input:

100000 100000
38240 38241
25091 25092
40976 40977
76549 76561
61646 61696
97750 97779
81942 81995
97812 97903
35076 35077
19290 19291
29419 29420
60747 60791
96878 96927
59464 59562
73435 73455
12193 12194
14474 14475
14977 14978
38492 38493
44802 44803
54266 54295
84442 84542
72810 72875
6245 6246
...

output:

0
990357
1186244
457712
207244
430065
922510
1698103
489604
677342
990357
556948
549513
207244
549513
448411
430065
1698103
2850324
286003
448411
853750
280231
292060
135049161
232031
1107785
292060
1417921
1171132
1353786
2112291
2160940
379603
286003
570360
292060
624414
280231
280231
990357
96485...

result:

ok 100000 lines