QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#725939	#8584. 바이러스	TheZone	100 ✓	1007ms	335616kb	C++20	5.7kb	2024-11-08 20:45:25	2024-11-08 20:45:25

Judging History

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

[2024-11-08 20:45:25]
评测

测评结果：100
用时：1007ms
内存：335616kb

查看

[2024-11-08 20:45:25]
提交

answer

#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define LL long long
#define eb emplace_back
#define PII pair <LL, int>
using namespace std;

const int N = 1e5 + 9;
int n, m, num, all, mn, rt;
int fa[N], in[N], out[N], C[N], sz[N], mxsz[N], vis[N];
vector <int> G[N], dis[N];

const int LogN = 20;
const int Pt = 2 * N * LogN;

vector <pair <int, int> > edge[Pt];
LL dist[Pt];
void cmax(int &a, int b) {a < b && (a = b);}

int ecnt;
void add_edge(int u, int v, int l) {
    ++ecnt;
    edge[u].eb(v, l);
}
void add_edge(int u, int v) {
    G[u].eb(v), G[v].eb(u);
}

void getsz(int u, int lst) {
    sz[u] = 1, mxsz[u] = 0;
    for (int v : G[u]) if (v != lst && !vis[v]) {
        getsz(v, u);
        cmax(mxsz[u], sz[v]);
        sz[u] += sz[v];
    }
    cmax(mxsz[u], all - sz[u]);
    if (mxsz[u] < mn) mn = mxsz[u], rt = u;
}

vector <int> vert_in[N], vert_out[N];
int cur;

void getdis(int u, int d, int lst) {
    add_edge(vert_in[cur][d], in[u], 0);
    add_edge(out[u], vert_out[cur][d], 0);
    dis[u].eb(d);
    for (int v : G[u]) if (v != lst && !vis[v]) {
        getdis(v, d + 1, u);
    }
}
void build(int u) {
    vis[u] = 1;
    getsz(u, -1);
    vert_in[u].resize(sz[u]);
    vert_out[u].resize(sz[u]);
    for (int &v : vert_in[u]) v = ++num;
    for (int &v : vert_out[u]) v = ++num;
    
    rep (i, 0, sz[u] - 2) {
        add_edge(vert_in[u][i + 1], vert_in[u][i], 0);
        add_edge(vert_out[u][i], vert_out[u][i + 1], 0);
    }

    cur = u;
    getdis(u, 0, -1);

    for (int v : G[u]) if (!vis[v]) {
        rt = -1, mn = 1e9, all = sz[v];
        getsz(v, u); fa[rt] = u;
        build(rt);
    }
}

int id[N];
priority_queue <PII, vector <PII>, greater<PII> > pq;

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, u, v; i < n - 1; ++i) {
        u = A[i], v = B[i];
        add_edge(u, v);
    }

    rep (i, 0, n - 1) in[i] = ++num, out[i] = ++num;

    rt = -1, mn = 1e9, all = n;
    getsz(0, -1);
    fa[rt] = -1;
    build(rt);
    rep (i, 0, m - 1) {
        int p, d; p = P[i], d= D[i];
        id[i] = ++num;
        for (int x = p, j = dis[p].size() - 1; ~x; x = fa[x], --j) {
            int dt = min(d - dis[p][j], sz[x] - 1);
            if (dt < 0) continue;
            add_edge(id[i], vert_in[x][dt], 0);
            add_edge(vert_out[x][dt], id[i], 0);
        }
    }

    rep (i, 0, n - 1) add_edge(in[i], out[i], C[i]);

    memset(dist, 0x3f, sizeof(dist));
    dist[id[0]] = 0; pq.push({dist[id[0]], id[0]});
    while (!pq.empty()) {
        PII top = pq.top(); pq.pop();
        if (dist[top.second] != top.first) continue;
        int u = top.second;
        for (auto [v, l] : edge[u]) {
            if (dist[u] + l < dist[v]) {
                dist[v] = dist[u] + l;
                pq.push({dist[v], v});
            }
        }
    }

    vector <LL> ans(m);
    rep (i, 0, m - 1) ans[i] = dist[id[i]] == dist[0] ? -1 : dist[id[i]];

    return ans;
}
/*#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define LL long long
#define eb emplace_back
#define PII pair <LL, int>
using namespace std;

const int N = 1e5 + 9;
int n, m, num, all, mn, rt;
int fa[N], in[N], out[N], C[N], sz[N], mxsz[N], vis[N];
vector <int> G[N], dis[N];

const int LogN = 20;
const int Pt = 2 * N * LogN;

vector <pair <int, int> > edge[Pt];
LL dist[Pt];
void cmax(int &a, int b) {a < b && (a = b);}

int ecnt;
void add_edge(int u, int v, int l) {
    ++ecnt;
    edge[u].eb(v, l);
}
void add_edge(int u, int v) {
    G[u].eb(v), G[v].eb(u);
}

void getsz(int u, int lst) {
    sz[u] = 1, mxsz[u] = 0;
    for (int v : G[u]) if (v != lst && !vis[v]) {
        getsz(v, u);
        cmax(mxsz[u], sz[v]);
        sz[u] += sz[v];
    }
    cmax(mxsz[u], all - sz[u]);
    if (mxsz[u] < mn) mn = mxsz[u], rt = u;
}

vector <int> vert_in[N], vert_out[N];
int cur;

void getdis(int u, int d, int lst) {
    add_edge(vert_in[cur][d], in[u], 0);
    add_edge(out[u], vert_out[cur][d], 0);
    dis[u].eb(d);
    for (int v : G[u]) if (v != lst && !vis[v]) {
        getdis(v, d + 1, u);
    }
}
void build(int u) {
    vis[u] = 1;
    getsz(u, -1);
    vert_in[u].resize(sz[u]);
    vert_out[u].resize(sz[u]);
    for (int &v : vert_in[u]) v = ++num;
    for (int &v : vert_out[u]) v = ++num;
    
    rep (i, 0, sz[u] - 2) {
        add_edge(vert_in[u][i + 1], vert_in[u][i], 0);
        add_edge(vert_out[u][i], vert_out[u][i + 1], 0);
    }

    cur = u;
    getdis(u, 0, -1);

    for (int v : G[u]) if (!vis[v]) {
        rt = -1, mn = 1e9, all = sz[v];
        getsz(v, u); fa[rt] = u;
        build(rt);
    }
}

int id[N];
priority_queue <PII, vector <PII>, greater<PII> > pq;

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, u, v; i < n - 1; ++i) {
        u = A[i], v = B[i];
        add_edge(u, v);
    }

    rep (i, 0, n - 1) in[i] = ++num, out[i] = ++num;

    rt = -1, mn = 1e9, all = n;
    getsz(0, -1);
    fa[rt] = -1;
    build(rt);
    rep (i, 0, m - 1) {
        int p, d; p = P[i], d= D[i];
        id[i] = ++num;
        for (int x = p, j = dis[p].size() - 1; ~x; x = fa[x], --j) {
            int dt = min(d - dis[p][j], sz[x] - 1);
    }

    vector <LL> ans(m);
    rep (i, 0, m - 1) ans[i] = dist[id[i]] == dist[0] ? -1 : dist[id[i]];

    return ans;
}*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 7ms

memory: 36968kb

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:

result:

ok 5 lines

Test #2:

score: 5

Accepted

time: 8ms

memory: 38996kb

input:

output:

0
1000000000

result:

ok 2 lines

Test #3:

score: 5

Accepted

time: 0ms

memory: 39216kb

input:

1 1
0 0
1

output:

result:

ok single line: '0'

Test #4:

score: 5

Accepted

time: 8ms

memory: 36956kb

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:

result:

ok 5 lines

Test #5:

score: 5

Accepted

time: 3ms

memory: 36888kb

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:

result:

ok 5 lines

Test #6:

score: 5

Accepted

time: 4ms

memory: 36836kb

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

memory: 37100kb

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:

result:

ok 5 lines

Test #8:

score: 5

Accepted

time: 10ms

memory: 36908kb

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:

result:

ok 10 lines

Test #9:

score: 5

Accepted

time: 4ms

memory: 36884kb

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:

result:

ok 10 lines

Test #10:

score: 5

Accepted

time: 0ms

memory: 36968kb

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:

result:

ok 10 lines

Test #11:

score: 5

Accepted

time: 3ms

memory: 36948kb

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:

result:

ok 10 lines

Test #12:

score: 5

Accepted

time: 10ms

memory: 36936kb

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:

result:

ok 20 lines

Test #13:

score: 5

Accepted

time: 3ms

memory: 37188kb

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:

result:

ok 20 lines

Test #14:

score: 5

Accepted

time: 4ms

memory: 38952kb

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:

result:

ok 20 lines

Test #15:

score: 5

Accepted

time: 3ms

memory: 36964kb

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:

result:

ok 20 lines

Test #16:

score: 5

Accepted

time: 6ms

memory: 40060kb

input:

output:

result:

ok 500 lines

Test #17:

score: 5

Accepted

time: 9ms

memory: 37712kb

input:

output:

result:

ok 500 lines

Test #18:

score: 5

Accepted

time: 4ms

memory: 39852kb

input:

output:

result:

ok 500 lines

Test #19:

score: 5

Accepted

time: 9ms

memory: 37768kb

input:

output:

result:

ok 500 lines

Subtask #2:

score: 8

Accepted

Dependency #1:

100%

Accepted

Test #20:

score: 8

Accepted

time: 33ms

memory: 48356kb

input:

output:

result:

ok 5000 lines

Test #21:

score: 8

Accepted

time: 27ms

memory: 48476kb

input:

output:

result:

ok 5000 lines

Test #22:

score: 8

Accepted

time: 25ms

memory: 50156kb

input:

output:

result:

ok 5000 lines

Test #23:

score: 8

Accepted

time: 32ms

memory: 50504kb

input:

output:

result:

ok 5000 lines

Test #24:

score: 8

Accepted

time: 21ms

memory: 47180kb

input:

output:

result:

ok 5000 lines

Subtask #3:

score: 27

Accepted

Dependency #2:

100%

Accepted

Test #25:

score: 27

Accepted

time: 919ms

memory: 335616kb

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:

result:

ok 100000 lines

Test #26:

score: 27

Accepted

time: 1007ms

memory: 333092kb

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:

result:

ok 100000 lines

Test #27:

score: 27

Accepted

time: 962ms

memory: 330464kb

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:

result:

ok 100000 lines

Test #28:

score: 27

Accepted

time: 896ms

memory: 334664kb

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:

result:

ok 100000 lines

Test #29:

score: 27

Accepted

time: 875ms

memory: 312860kb

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:

result:

ok 100000 lines

Test #30:

score: 27

Accepted

time: 569ms

memory: 289500kb

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:

result:

ok 96036 lines

Test #31:

score: 27

Accepted

time: 502ms

memory: 275744kb

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

memory: 279136kb

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:

result:

ok 90128 lines

Test #33:

score: 27

Accepted

time: 594ms

memory: 286300kb

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

memory: 37104kb

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:

result:

ok 5 lines

Test #35:

score: 5

Accepted

time: 11ms

memory: 37168kb

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:

result:

ok 10 lines

Test #36:

score: 5

Accepted

time: 3ms

memory: 37188kb

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:

result:

ok 20 lines

Test #37:

score: 5

Accepted

time: 11ms

memory: 37188kb

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:

result:

ok 20 lines

Test #38:

score: 5

Accepted

time: 0ms

memory: 36960kb

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:

result:

ok 20 lines

Test #39:

score: 5

Accepted

time: 8ms

memory: 39004kb

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:

result:

ok 20 lines

Test #40:

score: 5

Accepted

time: 4ms

memory: 37772kb

input:

output:

result:

ok 500 lines

Test #41:

score: 5

Accepted

time: 6ms

memory: 37544kb

input:

output:

result:

ok 500 lines

Test #42:

score: 5

Accepted

time: 4ms

memory: 37728kb

input:

output:

result:

ok 500 lines

Test #43:

score: 5

Accepted

time: 4ms

memory: 37556kb

input:

output:

result:

ok 500 lines

Test #44:

score: 5

Accepted

time: 4ms

memory: 39824kb

input:

output:

result:

ok 500 lines

Test #45:

score: 5

Accepted

time: 4ms

memory: 37444kb

input:

output:

result:

ok 500 lines

Test #46:

score: 5

Accepted

time: 8ms

memory: 37412kb

input:

output:

result:

ok 500 lines

Test #47:

score: 5

Accepted

time: 4ms

memory: 39800kb

input:

output:

result:

ok 500 lines

Test #48:

score: 5

Accepted

time: 9ms

memory: 37484kb

input:

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

memory: 39708kb

input:

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

memory: 36836kb

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:

result:

ok 10 lines

Test #51:

score: 5

Accepted

time: 7ms

memory: 37140kb

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:

result:

ok 10 lines

Test #52:

score: 5

Accepted

time: 3ms

memory: 37132kb

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:

result:

ok 10 lines

Test #53:

score: 5

Accepted

time: 8ms

memory: 39224kb

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:

result:

ok 20 lines

Test #54:

score: 5

Accepted

time: 3ms

memory: 38928kb

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:

result:

ok 20 lines

Test #55:

score: 5

Accepted

time: 10ms

memory: 36960kb

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:

result:

ok 20 lines

Test #56:

score: 5

Accepted

time: 4ms

memory: 37524kb

input:

output:

result:

ok 500 lines

Test #57:

score: 5

Accepted

time: 6ms

memory: 37464kb

input:

output:

result:

ok 500 lines

Test #58:

score: 5

Accepted

time: 8ms

memory: 37588kb

input:

output:

result:

ok 500 lines

Test #59:

score: 5

Accepted

time: 3ms

memory: 36892kb

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:

result:

ok 5 lines

Test #60:

score: 5

Accepted

time: 3ms

memory: 37168kb

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:

result:

ok 5 lines

Test #61:

score: 5

Accepted

time: 5ms

memory: 36836kb

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

memory: 37108kb

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:

result:

ok 10 lines

Test #63:

score: 5

Accepted

time: 5ms

memory: 36944kb

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:

result:

ok 10 lines

Test #64:

score: 5

Accepted

time: 7ms

memory: 39140kb

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

memory: 36980kb

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:

result:

ok 20 lines

Test #66:

score: 5

Accepted

time: 3ms

memory: 36960kb

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:

result:

ok 20 lines

Test #67:

score: 5

Accepted

time: 3ms

memory: 36976kb

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

memory: 37728kb

input:

output:

result:

ok 500 lines

Test #69:

score: 5

Accepted

time: 4ms

memory: 37640kb

input:

output:

result:

ok 500 lines

Test #70:

score: 5

Accepted

time: 6ms

memory: 39644kb

input:

output:

result:

ok 500 lines

Subtask #5:

score: 8

Accepted

Dependency #4:

100%

Accepted

Test #71:

score: 8

Accepted

time: 19ms

memory: 43640kb

input:

output:

result:

ok 5000 lines

Test #72:

score: 8

Accepted

time: 27ms

memory: 43712kb

input:

output:

result:

ok 5000 lines

Test #73:

score: 8

Accepted

time: 17ms

memory: 43616kb

input:

output:

result:

ok 5000 lines

Test #74:

score: 8

Accepted

time: 23ms

memory: 43684kb

input:

output:

result:

ok 5000 lines

Test #75:

score: 8

Accepted

time: 23ms

memory: 43684kb

input:

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: 43648kb

input:

output:

result:

ok 5000 lines

Test #77:

score: 8

Accepted

time: 21ms

memory: 43696kb

input:

output:

result:

ok 5000 lines

Test #78:

score: 8

Accepted

time: 22ms

memory: 43612kb

input:

output:

result:

ok 5000 lines

Test #79:

score: 8

Accepted

time: 14ms

memory: 45312kb

input:

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

memory: 43172kb

input:

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

memory: 44320kb

input:

output:

result:

ok 5000 lines

Test #82:

score: 8

Accepted

time: 20ms

memory: 44516kb

input:

output:

result:

ok 5000 lines

Test #83:

score: 8

Accepted

time: 34ms

memory: 44776kb

input:

output:

result:

ok 5000 lines

Test #84:

score: 8

Accepted

time: 26ms

memory: 47560kb

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:

result:

ok 5000 lines

Test #85:

score: 8

Accepted

time: 24ms

memory: 47252kb

input:

output:

result:

ok 5000 lines

Test #86:

score: 8

Accepted

time: 25ms

memory: 46840kb

input:

output:

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

memory: 210992kb

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:

result:

ok 100000 lines

Test #88:

score: 47

Accepted

time: 715ms

memory: 211112kb

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:

result:

ok 100000 lines

Test #89:

score: 47

Accepted

time: 683ms

memory: 209320kb

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:

result:

ok 100000 lines

Test #90:

score: 47

Accepted

time: 678ms

memory: 210448kb

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:

result:

ok 100000 lines

Test #91:

score: 47

Accepted

time: 704ms

memory: 209020kb

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:

result:

ok 100000 lines

Test #92:

score: 47

Accepted

time: 666ms

memory: 211960kb

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:

result:

ok 100000 lines

Test #93:

score: 47

Accepted

time: 682ms

memory: 210836kb

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:

result:

ok 100000 lines

Test #94:

score: 47

Accepted

time: 698ms

memory: 210484kb

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:

result:

ok 100000 lines

Test #95:

score: 47

Accepted

time: 362ms

memory: 190120kb

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

memory: 196696kb

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:

result:

ok 100000 lines

Test #97:

score: 47

Accepted

time: 719ms

memory: 208968kb

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:

result:

ok 100000 lines

Test #98:

score: 47

Accepted

time: 740ms

memory: 222412kb

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:

result:

ok 100000 lines

Test #99:

score: 47

Accepted

time: 849ms

memory: 252176kb

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:

result:

ok 100000 lines

Test #100:

score: 47

Accepted

time: 877ms

memory: 255436kb

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:

result:

ok 100000 lines

Test #101:

score: 47

Accepted

time: 709ms

memory: 225856kb

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:

result:

ok 100000 lines

Test #102:

score: 47

Accepted

time: 766ms

memory: 227880kb

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:

result:

ok 100000 lines

Test #103:

score: 47

Accepted

time: 798ms

memory: 229564kb

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:

result:

ok 100000 lines

Test #104:

score: 47

Accepted

time: 772ms

memory: 313188kb

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:

result:

ok 100000 lines

Test #105:

score: 47

Accepted

time: 843ms

memory: 304076kb

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

memory: 287636kb

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:

result:

ok 100000 lines

Test #107:

score: 47

Accepted

time: 922ms

memory: 310772kb

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:

result:

ok 100000 lines

Test #108:

score: 47

Accepted

time: 997ms

memory: 307388kb

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:

result:

ok 100000 lines

Test #109:

score: 47

Accepted

time: 970ms

memory: 296052kb

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:

result:

ok 100000 lines

Test #110:

score: 47

Accepted

time: 124ms

memory: 87920kb

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:

result:

ok 100000 lines

Test #111:

score: 47

Accepted

time: 118ms

memory: 87856kb

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:

result:

ok 100000 lines

Test #112:

score: 47

Accepted

time: 129ms

memory: 89684kb

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:

result:

ok 100000 lines

Test #113:

score: 47

Accepted

time: 131ms

memory: 87900kb

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:

result:

ok 100000 lines

Test #114:

score: 47

Accepted

time: 159ms

memory: 86700kb

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:

result:

ok 100000 lines

Test #115:

score: 47

Accepted

time: 163ms

memory: 87104kb

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:

result:

ok 100000 lines

Test #116:

score: 47

Accepted

time: 111ms

memory: 77348kb

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:

result:

ok 100000 lines

Test #117:

score: 47

Accepted

time: 120ms

memory: 79884kb

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

memory: 181468kb

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:

result:

ok 100000 lines

Test #119:

score: 47

Accepted

time: 410ms

memory: 184832kb

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:

result:

ok 100000 lines

Test #120:

score: 47

Accepted

time: 388ms

memory: 183224kb

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:

result:

ok 100000 lines

Test #121:

score: 47

Accepted

time: 420ms

memory: 184068kb

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:

result:

ok 100000 lines

Test #122:

score: 47

Accepted

time: 490ms

memory: 179612kb

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:

result:

ok 100000 lines

Test #123:

score: 47

Accepted

time: 510ms

memory: 179744kb

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:

result:

ok 100000 lines

Test #124:

score: 47

Accepted

time: 444ms

memory: 173256kb

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:

result:

ok 100000 lines

Test #125:

score: 47

Accepted

time: 440ms

memory: 173660kb

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:

result:

ok 100000 lines

Test #126:

score: 47

Accepted

time: 747ms

memory: 307548kb

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:

result:

ok 100000 lines

Test #127:

score: 47

Accepted

time: 806ms

memory: 309032kb

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:

result:

ok 100000 lines

Test #128:

score: 47

Accepted

time: 778ms

memory: 307992kb

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:

result:

ok 100000 lines

Test #129:

score: 47

Accepted

time: 811ms

memory: 309200kb

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:

result:

ok 100000 lines

Test #130:

score: 47

Accepted

time: 881ms

memory: 305752kb

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:

result:

ok 100000 lines

Test #131:

score: 47

Accepted

time: 955ms

memory: 306272kb

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:

result:

ok 100000 lines

Test #132:

score: 47

Accepted

time: 792ms

memory: 298524kb

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:

result:

ok 100000 lines

Test #133:

score: 47

Accepted

time: 823ms

memory: 297768kb

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:

result:

ok 100000 lines