QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#170535	#7181. Graph Cuts	ucup-team859^#	AC ✓	1720ms	29684kb	C++17	4.7kb	2023-09-09 15:28:41	2023-09-09 15:28:42

Judging History

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

[2023-09-09 15:28:42]
评测

测评结果：AC
用时：1720ms
内存：29684kb

查看

[2023-09-09 15:28:41]
提交

answer

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;



int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n + 1);
    vector<pair<int, int>> edges(m + 1);
    vector<int> deg(n + 1);

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        deg[u]++, deg[v]++;
        edges[i] = {u, v};
    }

    const int LIM = sqrt(n) + 1;
    vector<int> bigNodes;
    vector<vector<pair<int, int>>> bigEdges(n + 1);

    for (int i = 1; i <= n; i++) {
        if (deg[i] >= LIM) {
            bigNodes.push_back(i);
            for (auto itr : g[i]) {
                if (deg[itr.first] >= LIM) {
                    bigEdges[i].push_back(itr);
                }
            }
        }
    }

    vector<bool> state(n + 1);
    unordered_set<int> activeBigEdges;
    unordered_set<int> activeSmallEdges;
    vector<unordered_set<int>> outSmallEdges(n + 1); // small nodes for big node that don't belong to set
    vector<unordered_set<int>> inSmallEdges(n + 1); // small nodes for big node that belong to set

    for (int i = 1; i <= m; i++) {
        int x = edges[i].first, y = edges[i].second;
        if (deg[x] >= LIM && deg[y] < LIM) {
            outSmallEdges[x].insert(i);
        }
        if (deg[y] >= LIM && deg[x] < LIM) {
            outSmallEdges[y].insert(i);
        }
    }

    vector<bool> blocked(m + 1);

    int q;
    cin >> q;
    for (int qq = 1; qq <= q; qq++) {
        char ch;
        cin >> ch;
    
        if (ch == '+' || ch == '-') {
            int node;
            cin >> node;
            if (deg[node] < LIM) {
                for (auto itr : g[node]) {
                    if (blocked[itr.second]) continue;

                    if (deg[itr.first] < LIM) {
                        if (state[node] ^ state[itr.first]) { // remove edge
                            activeSmallEdges.erase(itr.second);
                        } else { // add edge
                            activeSmallEdges.insert(itr.second);
                        }
                    } else {
                        if (state[node]) {
                            inSmallEdges[itr.first].erase(itr.second);
                            outSmallEdges[itr.first].insert(itr.second);
                        } else {
                            outSmallEdges[itr.first].erase(itr.second);
                            inSmallEdges[itr.first].insert(itr.second);
                        }
                    }
                }
            } else {
                for (auto bigEdge : bigEdges[node]) {
                    int bigNode, edgeId;
                    tie(bigNode, edgeId) = bigEdge;

                    if (blocked[edgeId]) continue;

                    if (state[bigNode] ^ state[node]) { // we should remove edge
                        activeBigEdges.erase(edgeId);
                    } else { // we should add edge
                        activeBigEdges.insert(edgeId);
                    }
                }
            }

            state[node] = (state[node] ^ 1);

        } else {
            int answer = 0;

            if (activeBigEdges.size() > 0) {
                answer = *activeBigEdges.begin();
                activeBigEdges.erase(activeBigEdges.begin());
            } else if (activeSmallEdges.size() > 0) {
                answer = *activeSmallEdges.begin();
                activeSmallEdges.erase(activeSmallEdges.begin());   
            } else {
                for (auto bigNode : bigNodes) {
                    if (state[bigNode]) {
                        if (outSmallEdges[bigNode].size() > 0) {
                            answer = *outSmallEdges[bigNode].begin();
                            outSmallEdges[bigNode].erase(outSmallEdges[bigNode].begin());
                            break;
                        }
                    } else {
                        if (inSmallEdges[bigNode].size() > 0) {
                            answer = *inSmallEdges[bigNode].begin();
                            inSmallEdges[bigNode].erase(inSmallEdges[bigNode].begin());
                            break;
                        }
                    }
                }
            }

            cout << answer << "\n";
            if (answer != 0) {   
                blocked[answer] = true;
            }
        }
    }

    return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3440kb

input:

output:

result:

ok q=10

Test #2:

score: 0

Accepted

time: 1ms

memory: 3440kb

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0

Accepted

time: 1ms

memory: 3412kb

input:

0 0
1
?

output:

result:

ok q=1

Test #4:

score: 0

Accepted

time: 9ms

memory: 3680kb

input:

output:

result:

ok q=100000

Test #5:

score: 0

Accepted

time: 1709ms

memory: 10020kb

input:

output:

result:

ok q=100000

Test #6:

score: 0

Accepted

time: 1243ms

memory: 9992kb

input:

output:

result:

ok q=100000

Test #7:

score: 0

Accepted

time: 911ms

memory: 9992kb

input:

output:

result:

ok q=100000

Test #8:

score: 0

Accepted

time: 616ms

memory: 10008kb

input:

output:

result:

ok q=100000

Test #9:

score: 0

Accepted

time: 360ms

memory: 9988kb

input:

output:

result:

ok q=100000

Test #10:

score: 0

Accepted

time: 187ms

memory: 10096kb

input:

output:

result:

ok q=100000

Test #11:

score: 0

Accepted

time: 100ms

memory: 7516kb

input:

output:

result:

ok q=100000

Test #12:

score: 0

Accepted

time: 1672ms

memory: 10012kb

input:

output:

result:

ok q=100000

Test #13:

score: 0

Accepted

time: 1295ms

memory: 9920kb

input:

output:

result:

ok q=100000

Test #14:

score: 0

Accepted

time: 927ms

memory: 9892kb

input:

output:

result:

ok q=100000

Test #15:

score: 0

Accepted

time: 624ms

memory: 9944kb

input:

output:

result:

ok q=100000

Test #16:

score: 0

Accepted

time: 370ms

memory: 10048kb

input:

output:

result:

ok q=100000

Test #17:

score: 0

Accepted

time: 178ms

memory: 9928kb

input:

output:

result:

ok q=100000

Test #18:

score: 0

Accepted

time: 54ms

memory: 10032kb

input:

output:

result:

ok q=100000

Test #19:

score: 0

Accepted

time: 1685ms

memory: 9948kb

input:

output:

result:

ok q=100000

Test #20:

score: 0

Accepted

time: 1324ms

memory: 9996kb

input:

output:

result:

ok q=100000

Test #21:

score: 0

Accepted

time: 905ms

memory: 9932kb

input:

output:

result:

ok q=100000

Test #22:

score: 0

Accepted

time: 620ms

memory: 10000kb

input:

output:

result:

ok q=100000

Test #23:

score: 0

Accepted

time: 371ms

memory: 10000kb

input:

output:

result:

ok q=100000

Test #24:

score: 0

Accepted

time: 188ms

memory: 9948kb

input:

output:

result:

ok q=100000

Test #25:

score: 0

Accepted

time: 112ms

memory: 10056kb

input:

output:

result:

ok q=100000

Test #26:

score: 0

Accepted

time: 1689ms

memory: 10008kb

input:

output:

result:

ok q=100000

Test #27:

score: 0

Accepted

time: 1293ms

memory: 9952kb

input:

output:

result:

ok q=100000

Test #28:

score: 0

Accepted

time: 947ms

memory: 10020kb

input:

output:

result:

ok q=100000

Test #29:

score: 0

Accepted

time: 667ms

memory: 9996kb

input:

output:

result:

ok q=100000

Test #30:

score: 0

Accepted

time: 381ms

memory: 10032kb

input:

output:

result:

ok q=100000

Test #31:

score: 0

Accepted

time: 192ms

memory: 9992kb

input:

output:

result:

ok q=100000

Test #32:

score: 0

Accepted

time: 95ms

memory: 7776kb

input:

output:

result:

ok q=100000

Test #33:

score: 0

Accepted

time: 1702ms

memory: 9932kb

input:

output:

result:

ok q=100000

Test #34:

score: 0

Accepted

time: 1259ms

memory: 10012kb

input:

output:

result:

ok q=100000

Test #35:

score: 0

Accepted

time: 945ms

memory: 9944kb

input:

output:

result:

ok q=100000

Test #36:

score: 0

Accepted

time: 605ms

memory: 9932kb

input:

output:

result:

ok q=100000

Test #37:

score: 0

Accepted

time: 382ms

memory: 10024kb

input:

output:

result:

ok q=100000

Test #38:

score: 0

Accepted

time: 190ms

memory: 9964kb

input:

output:

result:

ok q=100000

Test #39:

score: 0

Accepted

time: 62ms

memory: 10012kb

input:

output:

result:

ok q=100000

Test #40:

score: 0

Accepted

time: 1720ms

memory: 9944kb

input:

output:

result:

ok q=100000

Test #41:

score: 0

Accepted

time: 1304ms

memory: 10028kb

input:

output:

result:

ok q=100000

Test #42:

score: 0

Accepted

time: 943ms

memory: 10044kb

input:

output:

result:

ok q=100000

Test #43:

score: 0

Accepted

time: 634ms

memory: 10008kb

input:

output:

result:

ok q=100000

Test #44:

score: 0

Accepted

time: 368ms

memory: 9956kb

input:

output:

result:

ok q=100000

Test #45:

score: 0

Accepted

time: 186ms

memory: 9928kb

input:

output:

result:

ok q=100000

Test #46:

score: 0

Accepted

time: 98ms

memory: 10032kb

input:

output:

result:

ok q=100000

Test #47:

score: 0

Accepted

time: 55ms

memory: 25752kb

input:

100000 100000
5722 1
35633 1
76503 1
2 8454
2 93428
3 91414
4 55025
21132 5
6 22400
6 80941
7 22043
7 29361
7 73158
78568 7
8 24159
8 26175
27612 9
39375 9
5454 10
24262 10
40601 10
11 8620
59525 11
11 79781
11 92891
64034 12
33728 14
14 59378
14 79826
560 16
16 31445
35262 16
17911 17
28509 17
9364...

output:

result:

ok q=100000

Test #48:

score: 0

Accepted

time: 47ms

memory: 24952kb

input:

100000 100000
32763 1
1 41318
52251 1
66464 2
83572 2
67186 5
7 64990
34545 8
8 96178
8628 9
10 8181
94794 15
16 33467
16 34451
85594 16
17 20413
31799 17
17 41753
18 61787
71853 18
19 5788
19 49136
97968 19
34661 20
20 61751
95244 20
20211 21
31082 21
22 96882
53538 23
53831 24
81268 24
25 52202
61...

output:

result:

ok q=100000

Test #49:

score: 0

Accepted

time: 53ms

memory: 24480kb

input:

100000 100000
98 1
1 39536
2 7197
2 36925
64304 2
3 90981
4 55694
4 58594
6 14112
6 61223
49657 7
49961 8
9 63064
84290 9
9616 10
10 26834
10 81424
11 28592
66665 11
11 67518
12 65671
12 77007
13 83518
88724 13
14 22525
28934 14
38904 15
18454 16
16 34371
33103 17
63576 17
46939 18
67514 18
18 72374...

output:

result:

ok q=100000

Test #50:

score: 0

Accepted

time: 35ms

memory: 24020kb

input:

100000 100000
1 30554
51310 1
1 71883
94585 1
2 40250
59351 2
2 60517
72989 3
4 3248
14035 4
4 90751
5 786
6 10125
87221 6
22862 7
7 57323
67940 7
40455 8
8 66854
9 34854
9 87440
43694 10
10 57462
82982 10
94968 10
47934 11
11 71829
24007 12
44565 12
48286 12
70260 12
12 70368
98761 12
20547 14
7549...

output:

result:

ok q=100000

Test #51:

score: 0

Accepted

time: 32ms

memory: 23344kb

input:

100000 100000
26140 1
46196 2
2 54845
78912 3
3 90871
4 12358
5 33609
5 43410
5 78393
47818 6
7 48862
13216 8
8 36636
8 40979
52931 8
8 80000
94821 8
52306 10
14072 12
36807 12
66342 12
344 13
13 4469
13 14570
13 52573
15 29037
15 38532
86576 15
16 9718
43023 16
16 86523
19 16448
20 15703
20 62471
8...

output:

result:

ok q=100000

Test #52:

score: 0

Accepted

time: 26ms

memory: 23360kb

input:

100000 100000
2005 1
1 15170
57799 2
4 38977
4 57240
42542 5
5 53318
5 75678
6 88650
65147 7
8 53626
8 70633
22352 10
11 49862
12 14548
12 50661
12 69416
13 22675
13 57792
3230 14
61629 16
16 94304
19 4752
11292 19
19 23963
47970 19
3280 20
20 13431
37640 20
20 43437
22 59910
69629 22
94875 22
23 52...

output:

result:

ok q=100000

Test #53:

score: 0

Accepted

time: 16ms

memory: 23360kb

input:

100000 100000
40394 1
75982 2
3 18844
73366 3
88698 3
4020 6
6 73638
7 22013
65853 7
8 75952
8 91846
8 92431
35947 9
25852 10
60988 10
84698 10
49696 11
60792 11
94447 12
29797 13
14 32289
14 45866
85823 14
15 5953
19579 15
9976 16
16 26641
17 70399
80811 17
18 57277
19 24826
19 72978
15405 20
64474...

output:

result:

ok q=100000

Test #54:

score: 0

Accepted

time: 47ms

memory: 25664kb

input:

100000 100000
1 46719
1 85926
2 31507
3 10325
25701 3
4 20660
4 24390
5 28826
5 32895
5 65707
5 85849
26769 6
35848 6
8 31592
9 6175
10 10273
10 49762
8543 11
12 1257
12 49533
67310 12
12 85402
4042 13
13 91901
14 36759
95374 14
40235 16
16 95131
17 47185
49412 17
86267 17
30733 18
19 36525
99630 20...

output:

result:

ok q=100000

Test #55:

score: 0

Accepted

time: 46ms

memory: 25672kb

input:

100000 100000
1 14816
1 36843
1 67254
69974 1
3 22460
4 94861
51245 5
5 53683
54692 6
6 91387
6 91712
8 56288
8 88631
9 4475
23107 9
9 37340
18545 10
10 32507
10 37510
86500 10
57406 11
11 96238
486 12
12 44026
51175 13
14 92685
14 94886
14 99844
66818 15
58293 16
16 92531
17 32186
36963 18
18 53409...

output:

result:

ok q=100000

Test #56:

score: 0

Accepted

time: 51ms

memory: 25660kb

input:

100000 100000
1 92961
32241 2
2 81221
4608 3
16927 3
18769 3
3 43374
22317 4
55044 4
18810 5
6 72739
61007 7
9 25577
9 27864
34366 9
10 16913
30734 10
40980 10
60805 10
74697 10
82279 10
10021 11
23696 12
36468 12
51197 12
86124 12
12 89628
14 6535
14 21742
14 36158
57841 14
15 81216
15 84873
16 457...

output:

result:

ok q=100000

Test #57:

score: 0

Accepted

time: 49ms

memory: 25660kb

input:

100000 100000
1 27333
1 84324
96084 1
9114 2
85952 2
3 5372
4 6733
9091 4
58622 4
4 86657
14441 5
55881 5
77265 5
5 80838
6 348
8 52617
8 61683
11583 9
9 73540
93581 9
94661 9
9 98721
46654 10
10 52226
12 55380
12 79729
13 40841
13 58505
80468 13
57058 14
14 59095
23508 15
68757 15
6286 17
17 39373
...

output:

result:

ok q=100000

Test #58:

score: 0

Accepted

time: 52ms

memory: 25640kb

input:

100000 100000
60818 1
1 61357
77477 1
3 45025
59533 3
46950 4
78991 4
97104 4
36194 5
6 64485
1740 7
5623 8
23553 8
16292 9
62566 9
9 98158
10 23566
10 47129
84382 10
10 89508
11 12522
54918 11
82691 14
89591 14
15 22620
22939 16
56415 16
16 83923
18 29619
18 83502
19 24669
79130 19
43646 20
21 6966...

output:

result:

ok q=100000

Test #59:

score: 0

Accepted

time: 41ms

memory: 25652kb

input:

100000 100000
34616 1
58002 1
1 70045
10303 2
2 39631
40632 2
10056 3
41853 3
70173 3
4 92959
5 47483
16468 6
50684 6
67732 6
84535 7
47014 8
59046 9
10 65208
10 78362
11266 11
24545 11
12 21449
66415 12
92002 12
13 19643
13 23316
96267 14
91298 15
17801 16
49544 16
69757 16
4694 17
17 24548
221 18
...

output:

result:

ok q=100000

Test #60:

score: 0

Accepted

time: 55ms

memory: 25736kb

input:

100000 100000
1 14279
25034 1
1 25644
1 33907
55554 1
32635 2
48898 2
67742 2
30821 3
62159 3
62878 4
4 99567
5427 5
81073 5
40389 6
68943 6
86783 6
7 7357
8 43901
8 49165
66447 8
15193 10
10 27651
52896 10
11 21927
31071 11
65058 11
1885 12
12 86604
13 34951
13 57211
73415 13
76672 13
31146 14
4934...

output:

result:

ok q=100000

Test #61:

score: 0

Accepted

time: 57ms

memory: 25776kb

input:

100000 100000
36686 1
2 28317
3 43331
58975 3
9005 5
5 38587
85424 5
87253 5
91242 6
7 12636
7 28747
43112 7
56525 7
95056 7
8 67866
8 96414
15486 9
9 17569
9 27913
9 45216
57385 9
12037 10
10 26847
68194 10
10 69558
91082 10
1181 11
29864 11
11 51315
74564 11
11 99360
50347 12
12 70424
80616 12
810...

output:

result:

ok q=100000

Test #62:

score: 0

Accepted

time: 41ms

memory: 25732kb

input:

100000 100000
19575 1
26203 1
72508 1
1 97963
14667 2
16976 2
3 6175
3 67390
3 85817
3 95274
61098 4
5 63076
48837 6
6 85456
8 11139
8053 9
9 14304
9 42080
78302 9
87001 9
95714 9
10 11640
10 38250
11 68261
33284 12
34067 13
37576 13
13 83578
15 23823
35578 16
57809 16
17 35284
43161 17
17 47477
516...

output:

result:

ok q=100000

Test #63:

score: 0

Accepted

time: 52ms

memory: 25756kb

input:

100000 100000
36059 1
46485 1
23653 2
73424 2
2 74494
51828 3
4 33328
53661 4
34793 5
6 51871
55444 6
6 65656
8 16246
8 34477
10425 9
62445 9
21534 10
10 30313
60761 10
96061 10
7597 11
11 15469
63367 12
40382 13
14 75126
15 56288
15 84929
53927 16
64468 16
17 53139
18 5845
76176 18
19 24677
19 5891...

output:

result:

ok q=100000

Test #64:

score: 0

Accepted

time: 51ms

memory: 25748kb

input:

100000 100000
20177 2
2 98955
3 46743
3 46866
62628 3
12631 4
75181 4
5 54593
27546 6
6 31901
6 83336
6 90688
7 32220
7 63366
8 61776
37721 9
9 48206
9 70008
96585 9
10 62990
98079 10
11 11607
21944 11
11 80964
13 9208
13 49235
13 69968
13 85800
38176 14
57272 14
15 3765
16 67576
17 40546
17 44435
1...

output:

result:

ok q=100000

Test #65:

score: 0

Accepted

time: 62ms

memory: 25640kb

input:

100000 100000
1 33218
2 26924
4 22063
4 72727
83189 4
5 26165
50928 5
6 12110
17480 7
39161 7
7 76692
20436 8
36025 8
9 52297
9 58874
67940 9
10 17168
10 40179
10665 11
11 26766
11 26798
28558 11
41443 11
91932 11
11 96520
12 38384
89050 13
14 44040
14 60933
63286 14
14 91796
38298 15
83369 15
20977...

output:

result:

ok q=100000

Test #66:

score: 0

Accepted

time: 56ms

memory: 25740kb

input:

100000 100000
97038 1
2 12394
73478 2
27345 3
3 52828
3 94198
17649 4
34700 4
4 48092
90308 4
4 92571
5 73178
5 96066
1197 6
79796 6
6 95080
7 6897
7 96564
8 57604
8 70048
29738 10
10 42975
10 99064
11 20156
11 25952
51206 11
11 97949
38714 12
92965 12
10950 13
15 6617
8272 15
17383 15
37580 15
5035...

output:

result:

ok q=100000

Test #67:

score: 0

Accepted

time: 43ms

memory: 25784kb

input:

100000 100000
1 43054
1 66061
45045 4
81759 5
15827 6
6 40801
78430 6
6 83704
3488 9
32237 9
10 8261
10 37635
98555 10
82566 11
30294 12
68894 12
13 32989
92708 14
94972 14
15 41948
16 28327
20490 17
52712 17
18 23230
18 77251
9533 19
66382 19
20 10583
23214 22
32369 22
24 32167
75443 24
26 9052
278...

output:

result:

ok q=100000

Test #68:

score: 0

Accepted

time: 25ms

memory: 29584kb

input:

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

output:

result:

ok q=100000

Test #69:

score: 0

Accepted

time: 14ms

memory: 28616kb

input:

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

output:

result:

ok q=100000

Test #70:

score: 0

Accepted

time: 18ms

memory: 28492kb

input:

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

output:

result:

ok q=100000

Test #71:

score: 0

Accepted

time: 22ms

memory: 28512kb

input:

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

output:

result:

ok q=100000

Test #72:

score: 0

Accepted

time: 18ms

memory: 28252kb

input:

99970 100000
2 1
1 3
5 1
7 1
9 1
1 11
13 1
15 1
1 17
1 19
1 21
1 23
1 25
27 1
1 29
31 1
1 33
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
65 1
1 67
69 1
71 1
73 1
75 1
77 1
79 1
81 1
1 83
85 1
1 87
1 89
91 1
1 93
1 95
1 97
99 1
1 101
1 103
1 105
107 1
109 1
111 1
1 113
...

output:

result:

ok q=100000

Test #73:

score: 0

Accepted

time: 27ms

memory: 29684kb

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
1 11
1 13
15 1
1 17
19 1
21 1
23 1
1 25
27 1
29 1
1 31
33 1
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
1 51
53 1
1 55
1 57
59 1
61 1
63 1
65 1
67 1
69 1
1 71
73 1
1 75
1 77
79 1
1 81
1 83
85 1
1 87
89 1
91 1
1 93
1 95
97 1
99 1
1 101
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

result:

ok q=100000

Test #74:

score: 0

Accepted

time: 29ms

memory: 28308kb

input:

99970 100000
2 1
3 1
5 1
7 1
9 1
11 1
1 13
1 15
1 17
19 1
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
37 1
39 1
1 41
1 43
1 45
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
1 65
1 67
1 69
1 71
73 1
75 1
77 1
1 79
1 81
1 83
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
...

output:

result:

ok q=100000

Test #75:

score: 0

Accepted

time: 28ms

memory: 28300kb

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
11 1
13 1
1 15
1 17
1 19
21 1
1 23
25 1
27 1
1 29
1 31
1 33
1 35
37 1
1 39
41 1
43 1
1 45
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
65 1
1 67
69 1
1 71
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
1 97
99 1
101 1
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

result:

ok q=100000

Test #76:

score: 0

Accepted

time: 28ms

memory: 28936kb

input:

99970 100000
1 2
3 1
4 1
1 7
1 10
1 13
16 1
19 1
1 22
25 1
1 28
1 31
34 1
1 37
40 1
1 43
1 46
1 49
52 1
1 55
1 58
61 1
64 1
1 67
70 1
73 1
76 1
1 79
82 1
1 85
88 1
1 91
1 94
97 1
100 1
1 103
106 1
109 1
112 1
115 1
118 1
1 121
124 1
1 127
130 1
1 133
1 136
139 1
1 142
1 145
1 148
1 151
1 154
1 157
1...

output:

result:

ok q=100000

Test #77:

score: 0

Accepted

time: 26ms

memory: 28692kb

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
1 19
1 22
1 25
1 28
1 31
34 1
1 37
40 1
43 1
46 1
1 49
1 52
1 55
58 1
1 61
64 1
67 1
70 1
1 73
1 76
79 1
1 82
85 1
1 88
91 1
94 1
1 97
1 100
1 103
106 1
109 1
1 112
115 1
1 118
121 1
1 124
127 1
130 1
1 133
136 1
139 1
142 1
1 145
1 148
151 1
1 154
157 1
1 160...

output:

result:

ok q=100000

Test #78:

score: 0

Accepted

time: 23ms

memory: 28008kb

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
19 1
22 1
25 1
1 28
1 31
1 34
1 37
1 40
1 43
46 1
49 1
1 52
55 1
1 58
1 61
1 64
67 1
70 1
1 73
76 1
1 79
1 82
1 85
88 1
1 91
94 1
97 1
100 1
1 103
1 106
1 109
1 112
1 115
118 1
121 1
1 124
127 1
130 1
1 133
1 136
139 1
142 1
145 1
148 1
1 151
154 1
1 157
1 160...

output:

result:

ok q=100000

Test #79:

score: 0

Accepted

time: 29ms

memory: 28076kb

input:

99970 100000
1 2
3 1
4 1
7 1
1 10
1 13
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
1 43
1 46
1 49
1 52
55 1
1 58
61 1
64 1
67 1
70 1
1 73
76 1
79 1
82 1
85 1
88 1
91 1
94 1
1 97
1 100
103 1
106 1
109 1
1 112
115 1
1 118
1 121
124 1
127 1
130 1
1 133
136 1
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1...

output:

result:

ok q=100000

Test #80:

score: 0

Accepted

time: 30ms

memory: 29300kb

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
1 17
21 1
1 25
1 29
33 1
1 37
41 1
45 1
1 49
1 53
1 57
1 61
65 1
1 69
1 73
1 77
81 1
85 1
89 1
1 93
97 1
101 1
105 1
109 1
113 1
1 117
121 1
1 125
1 129
133 1
137 1
141 1
1 145
149 1
1 153
157 1
161 1
165 1
1 169
1 173
177 1
181 1
185 1
189 1
193 1
1 197
1 201
1 205...

output:

result:

ok q=100000

Test #81:

score: 0

Accepted

time: 24ms

memory: 29208kb

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
17 1
21 1
1 25
1 29
1 33
37 1
1 41
1 45
1 49
53 1
1 57
1 61
1 65
1 69
73 1
77 1
81 1
1 85
89 1
93 1
97 1
101 1
105 1
1 109
1 113
1 117
121 1
1 125
129 1
133 1
137 1
141 1
145 1
1 149
1 153
1 157
1 161
1 165
169 1
173 1
177 1
181 1
185 1
1 189
1 193
1 197
201 1
1 205...

output:

result:

ok q=100000

Test #82:

score: 0

Accepted

time: 25ms

memory: 28276kb

input:

99970 100000
4 1
1 5
9 1
1 13
17 1
1 21
25 1
29 1
33 1
37 1
41 1
1 45
1 49
53 1
57 1
61 1
1 65
69 1
1 73
77 1
1 81
85 1
89 1
1 93
1 97
1 101
105 1
109 1
113 1
1 117
121 1
1 125
129 1
133 1
1 137
141 1
145 1
149 1
153 1
1 157
161 1
165 1
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
205 1
209...

output:

result:

ok q=100000

Test #83:

score: 0

Accepted

time: 16ms

memory: 28352kb

input:

99970 100000
4 1
5 1
1 9
13 1
17 1
21 1
25 1
29 1
33 1
37 1
41 1
45 1
1 49
53 1
1 57
61 1
65 1
69 1
1 73
1 77
1 81
85 1
1 89
93 1
97 1
1 101
1 105
1 109
1 113
117 1
121 1
1 125
1 129
1 133
1 137
1 141
1 145
1 149
153 1
157 1
1 161
165 1
169 1
1 173
1 177
181 1
1 185
189 1
1 193
1 197
1 201
205 1
1 2...

output:

result:

ok q=100000

Test #84:

score: 0

Accepted

time: 24ms

memory: 28296kb

input:

99970 100000
1 2
4 1
6 1
11 1
1 16
21 1
26 1
31 1
36 1
1 41
46 1
1 51
56 1
61 1
66 1
1 71
1 76
81 1
86 1
1 91
96 1
101 1
106 1
111 1
1 116
121 1
126 1
1 131
136 1
1 141
1 146
1 151
1 156
1 161
1 166
171 1
176 1
181 1
186 1
1 191
1 196
1 201
206 1
211 1
216 1
221 1
226 1
1 231
1 236
241 1
246 1
251 1...

output:

result:

ok q=100000

Test #85:

score: 0

Accepted

time: 24ms

memory: 28300kb

input:

99970 100000
1 2
3 1
6 1
1 11
1 16
21 1
1 26
1 31
1 36
1 41
46 1
1 51
56 1
61 1
1 66
1 71
76 1
1 81
86 1
91 1
1 96
1 101
1 106
111 1
1 116
121 1
126 1
131 1
136 1
1 141
1 146
1 151
1 156
1 161
166 1
171 1
176 1
1 181
186 1
1 191
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
241 1
246 1
251 1...

output:

result:

ok q=100000

Test #86:

score: 0

Accepted

time: 18ms

memory: 27784kb

input:

99970 100000
3 1
4 1
5 1
1 6
11 1
1 16
1 21
1 26
1 31
36 1
1 41
46 1
1 51
1 56
1 61
66 1
1 71
1 76
81 1
1 86
91 1
96 1
1 101
106 1
111 1
1 116
121 1
126 1
131 1
136 1
141 1
146 1
151 1
1 156
1 161
166 1
1 171
1 176
181 1
186 1
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
1 241
246 1
2...

output:

result:

ok q=100000

Test #87:

score: 0

Accepted

time: 28ms

memory: 27644kb

input:

99970 100000
1 3
5 1
6 1
1 11
1 16
1 21
1 26
31 1
1 36
41 1
1 46
51 1
56 1
1 61
1 66
1 71
76 1
81 1
1 86
1 91
1 96
1 101
1 106
111 1
116 1
1 121
1 126
1 131
136 1
1 141
1 146
151 1
1 156
161 1
1 166
171 1
1 176
181 1
1 186
1 191
196 1
1 201
1 206
1 211
216 1
1 221
1 226
1 231
236 1
241 1
246 1
1 251...

output:

result:

ok q=100000

Test #88:

score: 0

Accepted

time: 24ms

memory: 28592kb

input:

99970 100000
1 3
1 4
1 5
1 6
7 1
1 13
1 19
25 1
31 1
1 37
1 43
49 1
55 1
1 61
1 67
1 73
79 1
85 1
91 1
1 97
103 1
109 1
115 1
121 1
1 127
133 1
139 1
145 1
1 151
157 1
1 163
169 1
1 175
181 1
1 187
1 193
1 199
1 205
1 211
1 217
223 1
229 1
1 235
1 241
1 247
253 1
259 1
1 265
271 1
277 1
1 283
1 289
...

output:

result:

ok q=100000

Test #89:

score: 0

Accepted

time: 26ms

memory: 28652kb

input:

99970 100000
3 1
1 4
5 1
6 1
7 1
13 1
19 1
1 25
1 31
37 1
43 1
1 49
1 55
1 61
1 67
73 1
1 79
1 85
1 91
1 97
1 103
109 1
115 1
121 1
127 1
133 1
139 1
1 145
151 1
1 157
1 163
1 169
1 175
1 181
187 1
1 193
1 199
1 205
1 211
1 217
223 1
229 1
235 1
1 241
247 1
1 253
1 259
1 265
1 271
1 277
1 283
289 1
...

output:

result:

ok q=100000

Test #90:

score: 0

Accepted

time: 22ms

memory: 28048kb

input:

99970 100000
1 2
1 3
1 4
7 1
13 1
1 19
25 1
31 1
37 1
1 43
1 49
55 1
61 1
1 67
73 1
1 79
85 1
1 91
97 1
1 103
109 1
115 1
121 1
1 127
1 133
139 1
1 145
1 151
1 157
1 163
169 1
1 175
181 1
187 1
1 193
1 199
205 1
1 211
1 217
1 223
229 1
1 235
1 241
1 247
253 1
1 259
1 265
271 1
1 277
1 283
289 1
1 29...

output:

result:

ok q=100000

Test #91:

score: 0

Accepted

time: 21ms

memory: 27944kb

input:

99970 100000
3 1
6 1
1 7
13 1
19 1
25 1
1 31
1 37
1 43
1 49
55 1
61 1
67 1
1 73
1 79
1 85
1 91
97 1
103 1
109 1
1 115
121 1
127 1
133 1
139 1
145 1
151 1
157 1
163 1
169 1
175 1
181 1
187 1
193 1
199 1
205 1
1 211
217 1
223 1
229 1
1 235
1 241
247 1
1 253
259 1
265 1
271 1
277 1
1 283
1 289
295 1
1 ...

output:

result:

ok q=100000

Test #92:

score: 0

Accepted

time: 30ms

memory: 28864kb

input:

99970 100000
3 1
1 4
5 1
1 8
15 1
22 1
1 29
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
99 1
1 106
1 113
1 120
1 127
1 134
1 141
1 148
1 155
162 1
169 1
176 1
1 183
190 1
197 1
1 204
1 211
218 1
225 1
232 1
239 1
1 246
1 253
260 1
1 267
274 1
1 281
288 1
295 1
302 1
309 1
316 1
1 323
330 1
1 337
1 ...

output:

result:

ok q=100000

Test #93:

score: 0

Accepted

time: 20ms

memory: 28724kb

input:

99970 100000
1 3
1 5
6 1
7 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
1 99
106 1
113 1
1 120
127 1
134 1
141 1
148 1
155 1
1 162
169 1
176 1
1 183
190 1
197 1
204 1
211 1
1 218
1 225
232 1
239 1
246 1
1 253
1 260
267 1
274 1
1 281
1 288
1 295
1 302
1 309
316 1
323 1
1 330
337 ...

output:

result:

ok q=100000

Test #94:

score: 0

Accepted

time: 16ms

memory: 28092kb

input:

99970 100000
2 1
1 3
1 5
1 7
8 1
15 1
1 22
1 29
36 1
43 1
50 1
57 1
1 64
1 71
78 1
85 1
1 92
1 99
106 1
113 1
120 1
127 1
134 1
141 1
1 148
1 155
162 1
169 1
1 176
1 183
190 1
197 1
204 1
1 211
218 1
225 1
1 232
239 1
1 246
253 1
1 260
267 1
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
330 1
337 ...

output:

result:

ok q=100000

Test #95:

score: 0

Accepted

time: 25ms

memory: 28048kb

input:

99970 100000
2 1
3 1
4 1
1 6
7 1
8 1
1 15
1 22
29 1
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
1 99
106 1
113 1
1 120
1 127
1 134
141 1
1 148
155 1
1 162
1 169
176 1
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
239 1
246 1
253 1
1 260
267 1
1 274
281 1
1 288
1 295
1 302
1 309
1 316
323 1
330 1
...

output:

result:

ok q=100000

Test #96:

score: 0

Accepted

time: 24ms

memory: 29160kb

input:

99970 100000
2 1
3 1
4 1
1 5
1 6
9 1
17 1
25 1
33 1
1 41
49 1
57 1
65 1
73 1
1 81
89 1
1 97
1 105
113 1
1 121
1 129
137 1
145 1
153 1
1 161
1 169
1 177
1 185
1 193
1 201
1 209
217 1
1 225
1 233
1 241
1 249
1 257
1 265
1 273
281 1
1 289
297 1
1 305
313 1
321 1
1 329
337 1
1 345
1 353
361 1
369 1
1 37...

output:

result:

ok q=100000

Test #97:

score: 0

Accepted

time: 25ms

memory: 29196kb

input:

99970 100000
1 2
1 4
1 5
1 6
1 9
1 17
25 1
33 1
41 1
1 49
57 1
1 65
1 73
81 1
89 1
97 1
1 105
113 1
1 121
129 1
137 1
145 1
1 153
161 1
169 1
1 177
185 1
193 1
1 201
209 1
217 1
1 225
1 233
1 241
249 1
257 1
1 265
273 1
281 1
289 1
297 1
305 1
1 313
321 1
329 1
337 1
345 1
353 1
1 361
369 1
377 1
1 ...

output:

result:

ok q=100000

Test #98:

score: 0

Accepted

time: 28ms

memory: 28440kb

input:

99970 100000
4 1
5 1
1 8
1 9
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
1 81
1 89
97 1
105 1
1 113
1 121
1 129
137 1
145 1
1 153
1 161
169 1
177 1
185 1
1 193
1 201
1 209
217 1
1 225
1 233
241 1
1 249
1 257
265 1
1 273
1 281
289 1
297 1
305 1
1 313
1 321
329 1
337 1
345 1
1 353
1 361
1 369
377 1
1 385
...

output:

result:

ok q=100000

Test #99:

score: 0

Accepted

time: 26ms

memory: 28468kb

input:

99970 100000
6 1
9 1
1 17
1 25
1 33
41 1
1 49
1 57
1 65
73 1
1 81
89 1
97 1
1 105
113 1
1 121
129 1
137 1
1 145
1 153
1 161
169 1
1 177
1 185
1 193
201 1
209 1
217 1
1 225
1 233
1 241
249 1
257 1
265 1
1 273
281 1
1 289
1 297
1 305
313 1
321 1
1 329
337 1
345 1
353 1
361 1
369 1
1 377
1 385
393 1
1 ...

output:

result:

ok q=100000

Test #100:

score: 0

Accepted

time: 118ms

memory: 10372kb

input:

10000 100000
62 1
1 552
818 1
1 1204
1993 1
1 4007
1 4095
5262 1
1 5367
5784 1
1 6036
6091 1
1 6559
8108 1
1 8154
1 9191
9482 1
41 2
2 294
1572 2
1852 2
2 1895
3322 2
4360 2
4905 2
2 5027
5934 2
6198 2
6504 2
2 6870
8364 2
722 3
812 3
1347 3
1856 3
1990 3
2008 3
2578 3
3 3019
3 3248
3 3495
3 3616
3 ...

output:

result:

ok q=100000

Test #101:

score: 0

Accepted

time: 95ms

memory: 10352kb

input:

10000 100000
1 278
1 1411
1906 1
2107 1
2178 1
1 2299
2526 1
1 2856
1 3613
3796 1
1 4128
1 4196
1 4250
1 4631
5135 1
5224 1
1 5279
6206 1
1 6985
1 7310
1 7357
7722 1
7815 1
1 8282
9362 1
9571 1
1 9782
1 9999
874 2
2 1055
1187 2
2010 2
2 2173
2250 2
2511 2
2699 2
2756 2
2876 2
2 3802
4047 2
4937 2
2 ...

output:

result:

ok q=100000

Test #102:

score: 0

Accepted

time: 86ms

memory: 10432kb

input:

10000 100000
1 257
1 1150
1 2495
4714 1
5052 1
5128 1
5130 1
1 5235
1 6273
1 7279
7296 1
1 7899
8429 1
8895 1
9133 1
1 9402
2 378
2 434
1060 2
2991 2
5009 2
5316 2
2 5857
2 5984
2 6490
2 6494
6963 2
2 7560
2 7816
7996 2
8202 2
2 8218
2 9608
893 3
3 1127
3 1318
1863 3
3136 3
3 3927
4162 3
4273 3
3 49...

output:

result:

ok q=100000

Test #103:

score: 0

Accepted

time: 73ms

memory: 10372kb

input:

10000 100000
1 32
366 1
1164 1
1 1881
2317 1
2931 1
1 2932
3853 1
4011 1
1 4090
1 5006
5656 1
5696 1
1 6055
6674 1
7367 1
7599 1
8265 1
2 1468
2 1486
1670 2
2375 2
2 2729
3116 2
2 3202
2 3560
2 4047
2 4643
2 4645
4794 2
4958 2
5887 2
5947 2
2 6549
2 6992
2 7179
7436 2
2 7513
2 8130
2 8703
2 9686
514...

output:

result:

ok q=100000

Test #104:

score: 0

Accepted

time: 55ms

memory: 9640kb

input:

10000 100000
1 1173
1 2045
1 2146
1 2314
2389 1
1 2586
1 2796
1 3622
3650 1
1 3692
1 3985
4433 1
4520 1
5493 1
1 5514
6563 1
7220 1
1 7472
1 8043
1 8385
8565 1
9622 1
1 9735
2 97
2 131
167 2
1663 2
3416 2
2 4187
2 4386
2 4447
2 5022
5025 2
5179 2
2 5885
2 6919
8335 2
8400 2
2 8671
8807 2
9147 2
3 83...

output:

result:

ok q=100000

Test #105:

score: 0

Accepted

time: 31ms

memory: 9080kb

input:

10000 100000
1 380
1 873
1 1618
1838 1
1 2767
3506 1
1 4453
4602 1
4754 1
4880 1
1 5778
1 5811
1 6230
7868 1
1 7911
8126 1
1 8233
9049 1
9356 1
2 10
2 537
658 2
2 1129
1461 2
2 2035
2237 2
3097 2
3513 2
2 3524
2 3931
2 4956
5072 2
2 5204
2 5302
2 5454
2 5562
5607 2
5774 2
2 5909
6017 2
2 6193
6622 2...

output:

result:

ok q=100000

Test #106:

score: 0

Accepted

time: 15ms

memory: 8312kb

input:

10000 100000
1 223
924 1
1010 1
1 2164
1 2599
3130 1
3294 1
1 3555
1 3759
4080 1
1 4841
4948 1
1 5358
1 6539
7363 1
1 7747
9377 1
1 9393
1 9596
1 9941
376 2
2 623
878 2
1665 2
1759 2
2 1941
2135 2
3573 2
3685 2
3843 2
2 4021
5156 2
2 6157
2 6758
6934 2
2 7220
2 7354
7620 2
2 7815
2 8287
2 8564
8772 ...

output:

result:

ok q=100000

Test #107:

score: 0

Accepted

time: 113ms

memory: 10348kb

input:

10000 100000
1 246
483 1
1 766
1 1389
1 1977
1 2314
2563 1
2637 1
2826 1
1 4125
4414 1
4737 1
1 5172
1 5460
1 5727
1 6441
1 6611
1 6654
1 7016
7208 1
1 7265
1 7459
7666 1
1 7680
1 7784
8265 1
8518 1
9031 1
2 1115
2 1194
2 1496
1533 2
2 1578
1655 2
2455 2
2 2537
2785 2
2 3661
2 5953
2 6095
2 6250
728...

output:

result:

ok q=100000

Test #108:

score: 0

Accepted

time: 99ms

memory: 10412kb

input:

10000 100000
1 4
1 262
480 1
1661 1
1942 1
3141 1
3242 1
1 4520
5039 1
5322 1
5617 1
5702 1
6596 1
7549 1
8091 1
1 8150
1 8300
8880 1
8976 1
9057 1
1 9615
2 361
986 2
2 1260
1571 2
1831 2
2903 2
2 3659
2 4398
4775 2
4780 2
2 5425
6353 2
2 6520
2 7157
2 7742
2 8973
9025 2
50 3
3 677
3 816
924 3
1742 ...

output:

result:

ok q=100000

Test #109:

score: 0

Accepted

time: 75ms

memory: 10356kb

input:

10000 100000
637 1
1879 1
1 2512
1 3578
3828 1
4117 1
1 4420
4468 1
4698 1
1 6029
6048 1
6553 1
6615 1
1 6970
7457 1
7626 1
1 7647
1 9559
9862 1
2 362
2 2514
2764 2
2 2982
3679 2
6566 2
2 8237
8441 2
8654 2
8754 2
8796 2
2 8905
9184 2
3 1285
3 1795
2932 3
3 3025
3 3149
3 3537
5987 3
3 6361
3 6710
3 ...

output:

result:

ok q=100000

Test #110:

score: 0

Accepted

time: 62ms

memory: 10356kb

input:

10000 100000
6 1
1 399
891 1
1 1247
1269 1
1 1839
1 4072
4089 1
1 4245
1 4901
5339 1
1 7182
7459 1
8149 1
8208 1
1 8881
8937 1
1 9259
2 997
2 1065
2 2100
2 2796
2 3802
2 4857
2 5518
2 5539
5952 2
2 5973
7487 2
2 8574
2 9917
61 3
3 70
591 3
3 594
3 1502
3 1606
3 1616
3106 3
3 3523
3 3742
3 4162
4550 ...

output:

result:

ok q=100000

Test #111:

score: 0

Accepted

time: 56ms

memory: 10288kb

input:

10000 100000
1 362
793 1
1 2340
1 2929
1 3619
1 3663
1 3789
6135 1
6331 1
6700 1
1 6901
7815 1
8192 1
1 8615
8676 1
1 8849
1 9273
1 9310
323 2
512 2
2 847
2 967
2 970
1006 2
1716 2
2102 2
2 2739
3298 2
2 3444
2 3472
3889 2
2 4569
2 5985
6892 2
7135 2
7675 2
7854 2
7871 2
8179 2
8656 2
8719 2
2 8799
...

output:

result:

ok q=100000

Test #112:

score: 0

Accepted

time: 39ms

memory: 10296kb

input:

10000 100000
1 53
1 1122
1949 1
1965 1
1 2760
1 6345
6354 1
1 6764
1 7825
1 8453
8734 1
9046 1
1 9160
9875 1
2 29
167 2
754 2
2 867
1007 2
1040 2
2 1421
2752 2
2 3046
2 3444
2 3627
2 4830
2 5453
2 6492
2 8157
2 8480
2 9226
2 9460
9525 2
369 3
572 3
3 648
1053 3
3 1356
3 2369
3153 3
3155 3
3 5471
604...

output:

result:

ok q=100000

Test #113:

score: 0

Accepted

time: 18ms

memory: 10312kb

input:

10000 100000
303 1
1 306
1 309
603 1
1 624
1 713
1 954
1019 1
1921 1
2013 1
1 2239
2768 1
1 2899
4285 1
4773 1
1 5281
1 5596
5739 1
5755 1
5849 1
6228 1
1 7029
1 7255
7597 1
7679 1
9099 1
1 9342
966 2
2 1630
2 1984
2339 2
2 2603
2 3021
2 3661
2 3766
6428 2
2 7230
2 7652
7773 2
7997 2
9437 2
9475 2
9...

output:

result:

ok q=100000

Test #114:

score: 0

Accepted

time: 123ms

memory: 10308kb

input:

10000 100000
1 687
1 2238
2339 1
2540 1
3744 1
1 4048
1 5868
1 6041
7833 1
8786 1
9222 1
935 2
2 1185
2 1659
1973 2
2 2048
2 2569
3163 2
3286 2
2 4612
5511 2
2 5535
5942 2
2 6222
2 6365
2 6547
6954 2
2 7976
8670 2
9133 2
2 9507
1116 3
1283 3
3 1886
3 2675
4460 3
5444 3
3 6072
3 7681
8072 3
8104 3
3 ...

output:

result:

ok q=100000

Test #115:

score: 0

Accepted

time: 89ms

memory: 10376kb

input:

10000 100000
16 1
1 226
1 546
1 751
1 1332
1 2446
2702 1
2853 1
4522 1
4669 1
1 4771
1 5035
5108 1
1 5221
1 5265
5519 1
8583 1
1 8612
1 9249
1 9798
20 2
2 312
534 2
689 2
1484 2
2304 2
2351 2
2 3520
2 3886
4324 2
4432 2
4630 2
4977 2
6737 2
7547 2
2 7610
2 7638
7669 2
7678 2
7894 2
2 8781
2 8824
904...

output:

result:

ok q=100000

Test #116:

score: 0

Accepted

time: 77ms

memory: 10380kb

input:

10000 100000
1 634
1 773
973 1
1993 1
1 2206
1 2258
1 2674
2934 1
3289 1
1 3486
1 3665
3870 1
1 4202
1 4222
4916 1
1 5131
5341 1
1 5589
1 7234
1 7419
1 7603
1 7647
1 7871
1 7887
8704 1
2 165
2 334
2 896
2 1110
1438 2
1649 2
1824 2
2158 2
2 2205
2781 2
2 2912
2 4077
2 4501
4528 2
2 5391
2 5496
2 5811...

output:

result:

ok q=100000

Test #117:

score: 0

Accepted

time: 72ms

memory: 10360kb

input:

10000 100000
141 1
1 864
1 1515
1 1659
1 1665
1 1986
1 2432
2546 1
1 2598
1 2721
2792 1
3557 1
3736 1
1 7164
7510 1
1 9187
9424 1
2 2738
2 2936
3033 2
2 4575
4971 2
2 5719
6196 2
2 6465
2 6500
2 6665
2 7093
7520 2
2 7675
2 9723
3 130
3 279
755 3
3 964
1475 3
1750 3
3 1879
3 1961
3 2223
3 3125
3 3484...

output:

result:

ok q=100000

Test #118:

score: 0

Accepted

time: 48ms

memory: 10372kb

input:

10000 100000
1 496
1 976
1674 1
1 2091
1 2796
1 3047
1 3734
1 4361
1 4620
6855 1
1 6896
1 8073
8352 1
1 8572
8781 1
1 8857
1 8915
1 9035
1 9294
9490 1
9985 1
673 2
855 2
2 1012
1711 2
2 1902
2426 2
2 2597
2960 2
2 4925
2 5659
7946 2
7990 2
2 8450
2 8638
2 8646
2 8918
9379 2
3 443
3 458
3 1247
3 1405...

output:

result:

ok q=100000

Test #119:

score: 0

Accepted

time: 45ms

memory: 10308kb

input:

10000 100000
155 1
1 312
458 1
1 1772
1 2247
2334 1
1 2939
1 3031
4298 1
1 4460
1 6773
6873 1
7230 1
7285 1
7408 1
8385 1
1 8469
1 9022
9310 1
245 2
883 2
2 1068
1159 2
2 1844
2 2177
2 2407
2670 2
2820 2
2 2948
3701 2
3801 2
2 4259
2 4406
4662 2
5265 2
2 6295
7931 2
9316 2
2 9595
88 3
125 3
1259 3
3...

output:

result:

ok q=100000

Test #120:

score: 0

Accepted

time: 39ms

memory: 10304kb

input:

10000 100000
121 1
1 242
1 1247
1325 1
1 1445
2211 1
2687 1
3212 1
1 3458
1 4405
1 4473
5781 1
1 5987
6973 1
7680 1
1 9000
9059 1
1 9514
9600 1
51 2
2 693
1286 2
1391 2
2 1705
2 3339
3471 2
2 3864
2 5097
2 5130
5658 2
2 6647
6819 2
2 7138
2 7764
2 7810
8298 2
2 8369
8894 2
2 9880
3 53
3 625
3 779
14...

output:

result:

ok q=100000

Test #121:

score: 0

Accepted

time: 53ms

memory: 10844kb

input:

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

output:

result:

ok q=100000

Test #122:

score: 0

Accepted

time: 75ms

memory: 10744kb

input:

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

output:

result:

ok q=100000

Test #123:

score: 0

Accepted

time: 22ms

memory: 8228kb

input:

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

output:

result:

ok q=100000

Test #124:

score: 0

Accepted

time: 20ms

memory: 8360kb

input:

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

output:

result:

ok q=100000

Test #125:

score: 0

Accepted

time: 44ms

memory: 9476kb

input:

9970 100000
1 2
3 1
1 5
7 1
1 9
11 1
1 13
15 1
17 1
19 1
21 1
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
39 1
1 41
43 1
45 1
47 1
1 49
1 51
1 53
1 55
1 57
1 59
61 1
1 63
65 1
1 67
69 1
71 1
1 73
1 75
77 1
1 79
1 81
83 1
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
101 1
1 103
1 105
1 107
109 1
111 1
113 1
1...

output:

result:

ok q=100000

Test #126:

score: 0

Accepted

time: 68ms

memory: 9432kb

input:

9970 100000
2 1
3 1
5 1
1 7
9 1
1 11
13 1
1 15
17 1
19 1
1 21
23 1
1 25
1 27
29 1
1 31
33 1
35 1
37 1
1 39
41 1
43 1
1 45
1 47
49 1
1 51
53 1
55 1
1 57
1 59
61 1
63 1
1 65
1 67
1 69
1 71
73 1
1 75
1 77
79 1
1 81
1 83
1 85
87 1
89 1
91 1
93 1
95 1
1 97
1 99
1 101
103 1
105 1
107 1
109 1
111 1
1 113
1...

output:

result:

ok q=100000

Test #127:

score: 0

Accepted

time: 23ms

memory: 8308kb

input:

9970 100000
1 2
1 3
1 5
1 7
9 1
11 1
13 1
1 15
1 17
19 1
1 21
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
1 39
41 1
1 43
45 1
1 47
1 49
51 1
53 1
55 1
1 57
59 1
1 61
1 63
1 65
1 67
1 69
1 71
1 73
75 1
77 1
79 1
1 81
83 1
85 1
87 1
89 1
1 91
93 1
1 95
97 1
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
1...

output:

result:

ok q=100000

Test #128:

score: 0

Accepted

time: 8ms

memory: 8328kb

input:

9970 100000
1 2
1 3
1 5
7 1
1 9
1 11
1 13
1 15
17 1
1 19
21 1
23 1
25 1
1 27
1 29
1 31
33 1
35 1
1 37
39 1
1 41
1 43
1 45
47 1
49 1
1 51
53 1
1 55
57 1
59 1
61 1
63 1
65 1
67 1
1 69
1 71
1 73
1 75
1 77
79 1
81 1
1 83
85 1
87 1
1 89
1 91
93 1
1 95
1 97
1 99
101 1
103 1
1 105
107 1
109 1
1 111
1 113
1...

output:

result:

ok q=100000

Test #129:

score: 0

Accepted

time: 64ms

memory: 9072kb

input:

9970 100000
3 1
1 4
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
31 1
1 34
37 1
1 40
43 1
1 46
49 1
52 1
1 55
58 1
1 61
1 64
1 67
1 70
73 1
1 76
1 79
1 82
1 85
1 88
91 1
94 1
97 1
100 1
103 1
1 106
109 1
112 1
1 115
1 118
121 1
124 1
1 127
130 1
133 1
136 1
139 1
1 142
145 1
1 148
1 151
1 154
1 157
160 1
...

output:

result:

ok q=100000

Test #130:

score: 0

Accepted

time: 67ms

memory: 9168kb

input:

9970 100000
3 1
1 4
7 1
10 1
13 1
1 16
19 1
1 22
25 1
1 28
1 31
1 34
1 37
1 40
43 1
1 46
1 49
1 52
1 55
1 58
1 61
1 64
1 67
1 70
73 1
1 76
79 1
1 82
1 85
1 88
1 91
1 94
1 97
1 100
1 103
1 106
1 109
1 112
1 115
118 1
1 121
124 1
127 1
130 1
1 133
1 136
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1 160
...

output:

result:

ok q=100000

Test #131:

score: 0

Accepted

time: 19ms

memory: 8316kb

input:

9970 100000
2 1
3 1
1 4
1 7
10 1
1 13
1 16
19 1
22 1
25 1
1 28
1 31
1 34
37 1
1 40
1 43
1 46
49 1
1 52
1 55
1 58
1 61
1 64
67 1
1 70
73 1
1 76
1 79
82 1
1 85
1 88
91 1
94 1
97 1
100 1
1 103
1 106
109 1
1 112
115 1
118 1
121 1
1 124
1 127
1 130
133 1
1 136
139 1
1 142
145 1
1 148
1 151
1 154
1 157
16...

output:

result:

ok q=100000

Test #132:

score: 0

Accepted

time: 24ms

memory: 8256kb

input:

9970 100000
1 2
1 3
4 1
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
43 1
46 1
1 49
1 52
1 55
1 58
1 61
64 1
1 67
70 1
1 73
76 1
1 79
82 1
1 85
1 88
91 1
1 94
1 97
1 100
1 103
1 106
109 1
1 112
1 115
118 1
121 1
124 1
127 1
130 1
133 1
1 136
1 139
142 1
145 1
1 148
151 1
1 154
1 157
1 ...

output:

result:

ok q=100000

Test #133:

score: 0

Accepted

time: 47ms

memory: 9300kb

input:

9970 100000
3 1
1 5
1 9
1 13
17 1
21 1
25 1
1 29
33 1
1 37
1 41
45 1
49 1
53 1
57 1
61 1
65 1
1 69
1 73
1 77
1 81
85 1
1 89
93 1
97 1
101 1
105 1
1 109
113 1
117 1
121 1
125 1
1 129
133 1
1 137
1 141
1 145
149 1
1 153
157 1
1 161
1 165
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
1 205
209 ...

output:

result:

ok q=100000

Test #134:

score: 0

Accepted

time: 64ms

memory: 9312kb

input:

9970 100000
1 2
1 3
1 5
9 1
1 13
1 17
1 21
1 25
29 1
1 33
37 1
1 41
45 1
1 49
1 53
1 57
1 61
65 1
69 1
73 1
1 77
1 81
1 85
1 89
1 93
1 97
101 1
105 1
109 1
1 113
1 117
121 1
125 1
1 129
1 133
137 1
1 141
145 1
1 149
153 1
1 157
1 161
1 165
169 1
173 1
1 177
1 181
1 185
1 189
193 1
1 197
1 201
205 1
...

output:

result:

ok q=100000

Test #135:

score: 0

Accepted

time: 19ms

memory: 8252kb

input:

9970 100000
1 2
1 5
9 1
13 1
17 1
1 21
25 1
1 29
33 1
1 37
41 1
1 45
1 49
1 53
1 57
61 1
65 1
69 1
73 1
77 1
1 81
85 1
89 1
93 1
1 97
101 1
1 105
1 109
1 113
1 117
1 121
1 125
129 1
1 133
1 137
1 141
1 145
1 149
153 1
1 157
1 161
165 1
169 1
1 173
177 1
181 1
1 185
189 1
193 1
197 1
1 201
205 1
1 20...

output:

result:

ok q=100000

Test #136:

score: 0

Accepted

time: 19ms

memory: 8588kb

input:

9970 100000
1 3
5 1
9 1
13 1
1 17
21 1
25 1
1 29
33 1
1 37
1 41
1 45
1 49
53 1
57 1
61 1
65 1
69 1
73 1
77 1
1 81
85 1
1 89
1 93
1 97
1 101
105 1
109 1
113 1
1 117
1 121
1 125
129 1
1 133
137 1
141 1
145 1
1 149
153 1
157 1
1 161
1 165
1 169
1 173
1 177
181 1
1 185
1 189
193 1
1 197
1 201
1 205
1 20...

output:

result:

ok q=100000

Test #137:

score: 0

Accepted

time: 46ms

memory: 8820kb

input:

9970 100000
3 1
4 1
1 5
6 1
11 1
1 16
1 21
1 26
1 31
36 1
41 1
1 46
1 51
1 56
61 1
66 1
1 71
76 1
81 1
86 1
91 1
1 96
101 1
106 1
111 1
1 116
1 121
1 126
131 1
136 1
1 141
146 1
151 1
156 1
1 161
1 166
171 1
176 1
181 1
186 1
1 191
196 1
201 1
206 1
211 1
216 1
221 1
226 1
231 1
1 236
1 241
1 246
1 ...

output:

result:

ok q=100000

Test #138:

score: 0

Accepted

time: 61ms

memory: 8844kb

input:

9970 100000
3 1
6 1
11 1
1 16
1 21
26 1
1 31
1 36
1 41
46 1
51 1
56 1
61 1
1 66
1 71
1 76
81 1
86 1
1 91
96 1
1 101
1 106
1 111
116 1
1 121
126 1
131 1
1 136
141 1
1 146
151 1
156 1
161 1
166 1
1 171
176 1
1 181
186 1
1 191
196 1
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
1 246
251 1
1 25...

output:

result:

ok q=100000

Test #139:

score: 0

Accepted

time: 23ms

memory: 8256kb

input:

9970 100000
1 2
1 6
11 1
16 1
1 21
26 1
31 1
1 36
41 1
46 1
51 1
56 1
1 61
66 1
1 71
1 76
81 1
1 86
91 1
1 96
1 101
106 1
111 1
116 1
121 1
126 1
1 131
1 136
141 1
1 146
151 1
156 1
161 1
166 1
171 1
176 1
181 1
186 1
191 1
1 196
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
246 1
1 251
256 ...

output:

result:

ok q=100000

Test #140:

score: 0

Accepted

time: 15ms

memory: 8244kb

input:

9970 100000
1 2
3 1
6 1
1 11
1 16
1 21
1 26
31 1
36 1
41 1
1 46
51 1
56 1
1 61
1 66
71 1
1 76
81 1
86 1
91 1
96 1
1 101
106 1
111 1
116 1
121 1
126 1
131 1
136 1
1 141
1 146
151 1
1 156
1 161
1 166
1 171
1 176
1 181
1 186
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
1 236
1 241
1 246
251 1
...

output:

result:

ok q=100000

Test #141:

score: 0

Accepted

time: 55ms

memory: 8828kb

input:

9970 100000
2 1
1 6
1 7
13 1
19 1
1 25
1 31
1 37
1 43
1 49
1 55
1 61
1 67
73 1
79 1
1 85
91 1
1 97
103 1
109 1
115 1
121 1
127 1
1 133
1 139
145 1
151 1
157 1
1 163
1 169
175 1
181 1
187 1
1 193
199 1
1 205
1 211
1 217
223 1
1 229
1 235
241 1
247 1
253 1
1 259
1 265
271 1
277 1
1 283
289 1
1 295
301...

output:

result:

ok q=100000

Test #142:

score: 0

Accepted

time: 61ms

memory: 8816kb

input:

9970 100000
2 1
1 3
4 1
1 6
7 1
1 13
1 19
1 25
1 31
1 37
43 1
1 49
1 55
61 1
67 1
1 73
79 1
85 1
1 91
1 97
1 103
109 1
115 1
121 1
1 127
133 1
1 139
145 1
1 151
157 1
163 1
1 169
175 1
181 1
187 1
193 1
1 199
205 1
1 211
217 1
223 1
229 1
1 235
241 1
1 247
1 253
259 1
265 1
271 1
1 277
1 283
289 1
2...

output:

result:

ok q=100000

Test #143:

score: 0

Accepted

time: 17ms

memory: 8304kb

input:

9970 100000
4 1
1 5
6 1
7 1
1 13
1 19
25 1
31 1
37 1
1 43
49 1
55 1
61 1
67 1
1 73
1 79
85 1
1 91
97 1
103 1
1 109
1 115
121 1
1 127
133 1
1 139
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
1 199
1 205
211 1
1 217
1 223
229 1
235 1
1 241
247 1
253 1
1 259
265 1
1 271
1 277
1 283
1 289
1 295...

output:

result:

ok q=100000

Test #144:

score: 0

Accepted

time: 22ms

memory: 8308kb

input:

9970 100000
3 1
1 4
5 1
1 7
13 1
19 1
1 25
1 31
37 1
43 1
1 49
55 1
61 1
67 1
73 1
79 1
1 85
1 91
1 97
1 103
109 1
1 115
1 121
1 127
1 133
139 1
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
199 1
205 1
211 1
217 1
1 223
1 229
235 1
1 241
1 247
1 253
259 1
1 265
271 1
1 277
283 1
1 289
295 1...

output:

result:

ok q=100000

Test #145:

score: 0

Accepted

time: 60ms

memory: 8892kb

input:

9970 100000
3 1
6 1
1 7
1 8
15 1
1 22
29 1
1 36
43 1
1 50
1 57
1 64
71 1
1 78
1 85
92 1
1 99
1 106
1 113
1 120
1 127
1 134
141 1
148 1
1 155
162 1
169 1
176 1
183 1
190 1
197 1
204 1
211 1
1 218
225 1
1 232
239 1
246 1
1 253
1 260
1 267
1 274
281 1
1 288
1 295
302 1
309 1
1 316
1 323
330 1
1 337
344...

output:

result:

ok q=100000

Test #146:

score: 0

Accepted

time: 67ms

memory: 8920kb

input:

9970 100000
1 3
5 1
6 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
99 1
106 1
113 1
1 120
127 1
134 1
141 1
1 148
1 155
1 162
169 1
1 176
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
1 239
1 246
253 1
1 260
1 267
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
1 330
1 337
344...

output:

result:

ok q=100000

Test #147:

score: 0

Accepted

time: 26ms

memory: 8320kb

input:

9970 100000
3 1
4 1
6 1
8 1
1 15
1 22
1 29
36 1
43 1
50 1
1 57
64 1
1 71
78 1
1 85
1 92
99 1
106 1
113 1
120 1
127 1
134 1
1 141
1 148
155 1
162 1
1 169
1 176
183 1
1 190
197 1
1 204
1 211
218 1
1 225
232 1
1 239
1 246
1 253
260 1
267 1
1 274
1 281
288 1
1 295
1 302
1 309
1 316
323 1
1 330
1 337
1 3...

output:

result:

ok q=100000

Test #148:

score: 0

Accepted

time: 22ms

memory: 8320kb

input:

9970 100000
3 1
5 1
1 8
15 1
1 22
1 29
36 1
43 1
50 1
57 1
64 1
1 71
1 78
85 1
1 92
1 99
106 1
1 113
120 1
127 1
1 134
141 1
1 148
155 1
1 162
169 1
176 1
1 183
190 1
197 1
1 204
211 1
218 1
225 1
1 232
239 1
1 246
253 1
260 1
1 267
274 1
1 281
288 1
295 1
1 302
1 309
316 1
323 1
330 1
337 1
344 1
3...

output:

result:

ok q=100000

Test #149:

score: 0

Accepted

time: 53ms

memory: 8864kb

input:

9970 100000
2 1
1 3
1 4
5 1
7 1
8 1
1 9
1 17
25 1
1 33
1 41
1 49
1 57
1 65
73 1
1 81
1 89
1 97
1 105
1 113
121 1
1 129
137 1
145 1
1 153
161 1
169 1
177 1
1 185
193 1
201 1
209 1
1 217
1 225
233 1
241 1
1 249
257 1
265 1
1 273
1 281
289 1
297 1
305 1
1 313
321 1
329 1
1 337
345 1
353 1
1 361
1 369
1...

output:

result:

ok q=100000

Test #150:

score: 0

Accepted

time: 65ms

memory: 8884kb

input:

9970 100000
1 4
1 5
6 1
8 1
9 1
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
81 1
89 1
97 1
105 1
1 113
121 1
1 129
137 1
145 1
1 153
1 161
1 169
177 1
1 185
1 193
1 201
209 1
217 1
1 225
233 1
1 241
249 1
257 1
265 1
1 273
1 281
289 1
1 297
305 1
1 313
321 1
1 329
1 337
345 1
1 353
361 1
369 1
377 1
385...

output:

result:

ok q=100000

Test #151:

score: 0

Accepted

time: 25ms

memory: 8272kb

input:

9970 100000
1 3
1 6
8 1
1 9
17 1
25 1
33 1
1 41
1 49
57 1
65 1
73 1
81 1
89 1
1 97
105 1
113 1
121 1
1 129
1 137
1 145
1 153
161 1
169 1
177 1
1 185
193 1
1 201
209 1
1 217
1 225
233 1
1 241
249 1
257 1
265 1
1 273
281 1
289 1
1 297
1 305
1 313
1 321
1 329
1 337
345 1
353 1
1 361
1 369
1 377
385 1
1...

output:

result:

ok q=100000

Test #152:

score: 0

Accepted

time: 18ms

memory: 8248kb

input:

9970 100000
2 1
1 3
5 1
1 9
17 1
25 1
1 33
41 1
1 49
1 57
65 1
73 1
81 1
89 1
1 97
105 1
1 113
121 1
1 129
1 137
145 1
153 1
1 161
1 169
1 177
185 1
193 1
201 1
1 209
1 217
225 1
1 233
241 1
249 1
257 1
265 1
1 273
1 281
1 289
297 1
1 305
1 313
1 321
1 329
337 1
345 1
353 1
1 361
1 369
377 1
1 385
1...

output:

result:

ok q=100000

Test #153:

score: 0

Accepted

time: 820ms

memory: 10460kb

input:

1000 100000
1 5
17 1
22 1
33 1
1 34
35 1
41 1
1 55
1 56
60 1
75 1
76 1
1 77
88 1
1 89
1 93
1 95
1 96
97 1
98 1
1 103
1 105
108 1
1 112
1 115
116 1
143 1
1 147
156 1
164 1
1 168
183 1
188 1
197 1
198 1
199 1
210 1
1 213
215 1
1 217
223 1
224 1
225 1
228 1
1 233
236 1
240 1
249 1
250 1
258 1
259 1
1 2...

output:

result:

ok q=100000

Test #154:

score: 0

Accepted

time: 619ms

memory: 10536kb

input:

1000 100000
1 10
1 16
21 1
23 1
1 28
30 1
1 31
1 36
39 1
1 44
1 45
1 48
1 57
61 1
62 1
1 63
67 1
69 1
77 1
1 78
1 84
1 91
94 1
96 1
1 100
1 104
112 1
115 1
1 120
1 124
128 1
130 1
137 1
148 1
1 161
164 1
170 1
1 173
1 185
188 1
189 1
1 192
1 195
1 200
207 1
1 210
1 219
230 1
237 1
239 1
245 1
247 1
...

output:

result:

ok q=100000

Test #155:

score: 0

Accepted

time: 467ms

memory: 10572kb

input:

1000 100000
1 10
1 13
14 1
16 1
1 19
21 1
32 1
1 39
40 1
1 44
49 1
1 51
52 1
1 54
1 56
61 1
63 1
70 1
1 73
1 83
1 87
1 99
101 1
104 1
111 1
114 1
119 1
121 1
122 1
126 1
1 130
133 1
135 1
1 146
150 1
158 1
170 1
183 1
1 184
185 1
186 1
187 1
1 190
192 1
196 1
205 1
208 1
223 1
227 1
1 235
1 242
244 ...

output:

result:

ok q=100000

Test #156:

score: 0

Accepted

time: 319ms

memory: 10556kb

input:

1000 100000
1 2
3 1
5 1
1 8
9 1
10 1
1 11
19 1
21 1
42 1
44 1
45 1
1 46
1 67
69 1
1 75
1 87
1 88
100 1
103 1
114 1
121 1
1 123
127 1
131 1
1 143
1 149
151 1
153 1
159 1
1 163
1 174
176 1
1 185
1 186
191 1
1 194
1 205
210 1
1 215
1 217
1 219
1 220
222 1
1 229
232 1
234 1
1 237
240 1
1 241
245 1
1 247...

output:

result:

ok q=100000

Test #157:

score: 0

Accepted

time: 212ms

memory: 10632kb

input:

1000 100000
1 6
1 12
18 1
19 1
34 1
1 37
41 1
53 1
58 1
1 63
1 66
1 70
73 1
1 80
1 82
94 1
1 104
1 110
1 112
1 114
1 115
118 1
121 1
126 1
131 1
136 1
1 137
139 1
1 145
146 1
148 1
1 149
1 159
1 161
164 1
170 1
186 1
189 1
191 1
193 1
1 197
1 206
207 1
208 1
212 1
224 1
1 225
1 226
228 1
229 1
233 1...

output:

result:

ok q=100000

Test #158:

score: 0

Accepted

time: 104ms

memory: 10572kb

input:

1000 100000
1 10
1 20
23 1
26 1
32 1
35 1
1 41
47 1
1 52
1 54
57 1
1 58
61 1
68 1
71 1
1 82
1 85
90 1
103 1
1 114
1 124
125 1
129 1
1 133
1 135
139 1
140 1
1 143
1 158
1 160
1 161
164 1
1 169
174 1
181 1
186 1
187 1
188 1
189 1
199 1
1 208
1 227
1 228
1 232
1 240
1 243
250 1
1 255
260 1
270 1
272 1
...

output:

result:

ok q=100000

Test #159:

score: 0

Accepted

time: 220ms

memory: 8524kb

input:

1000 100000
5 1
1 11
1 20
1 37
43 1
44 1
47 1
48 1
54 1
1 63
69 1
1 70
72 1
73 1
83 1
84 1
1 86
1 93
1 94
1 95
1 101
1 108
114 1
115 1
124 1
137 1
1 141
1 144
1 151
158 1
159 1
160 1
167 1
175 1
181 1
1 183
1 191
1 196
1 198
1 203
1 213
1 215
216 1
239 1
245 1
246 1
249 1
1 254
261 1
264 1
277 1
289...

output:

result:

ok q=100000

Test #160:

score: 0

Accepted

time: 812ms

memory: 10548kb

input:

1000 100000
2 1
15 1
1 18
21 1
1 23
33 1
52 1
54 1
55 1
1 56
1 57
1 61
62 1
1 66
69 1
1 72
1 73
1 75
79 1
1 85
87 1
1 88
1 89
95 1
104 1
121 1
1 123
1 127
1 131
1 135
1 136
137 1
1 139
1 148
150 1
1 156
1 162
1 189
192 1
193 1
1 194
1 197
1 209
1 213
1 216
1 218
220 1
221 1
222 1
1 230
248 1
1 249
1...

output:

result:

ok q=100000

Test #161:

score: 0

Accepted

time: 630ms

memory: 10492kb

input:

1000 100000
5 1
11 1
1 15
23 1
25 1
1 26
1 27
1 30
35 1
39 1
1 49
1 53
1 57
1 72
1 73
1 78
1 81
83 1
1 85
1 87
88 1
96 1
101 1
1 107
110 1
1 112
116 1
118 1
1 121
1 123
124 1
125 1
131 1
134 1
1 137
1 140
141 1
143 1
155 1
1 157
1 168
171 1
177 1
182 1
184 1
185 1
1 187
193 1
1 206
207 1
1 208
209 1...

output:

result:

ok q=100000

Test #162:

score: 0

Accepted

time: 474ms

memory: 10556kb

input:

1000 100000
1 6
7 1
1 12
1 22
1 25
1 29
1 31
36 1
45 1
1 67
75 1
1 81
85 1
1 89
95 1
97 1
1 103
115 1
123 1
125 1
1 129
133 1
137 1
148 1
1 155
158 1
178 1
179 1
1 181
1 187
1 188
205 1
207 1
208 1
1 211
1 214
1 219
1 223
231 1
1 237
239 1
1 242
243 1
251 1
256 1
1 260
262 1
269 1
270 1
271 1
275 1
...

output:

result:

ok q=100000

Test #163:

score: 0

Accepted

time: 321ms

memory: 10456kb

input:

1000 100000
3 1
8 1
9 1
1 16
28 1
45 1
1 49
1 55
1 56
57 1
66 1
68 1
1 70
1 74
78 1
1 84
1 85
86 1
87 1
97 1
99 1
103 1
105 1
1 107
1 111
1 112
1 127
130 1
1 133
1 134
142 1
143 1
149 1
161 1
167 1
1 168
172 1
1 174
1 179
1 190
193 1
1 195
1 202
205 1
1 209
216 1
217 1
218 1
1 219
1 229
1 234
236 1
...

output:

result:

ok q=100000

Test #164:

score: 0

Accepted

time: 192ms

memory: 10548kb

input:

1000 100000
1 13
16 1
17 1
1 22
1 24
29 1
1 30
1 55
57 1
1 58
59 1
1 72
73 1
75 1
77 1
1 85
87 1
1 89
90 1
1 93
1 99
101 1
1 103
1 106
1 119
1 122
125 1
145 1
1 151
1 158
1 163
1 167
170 1
179 1
184 1
1 187
1 193
1 201
202 1
204 1
1 207
1 211
213 1
216 1
222 1
224 1
226 1
234 1
1 242
246 1
259 1
1 2...

output:

result:

ok q=100000

Test #165:

score: 0

Accepted

time: 99ms

memory: 10420kb

input:

1000 100000
2 1
3 1
9 1
11 1
22 1
1 33
1 39
1 42
1 43
1 44
1 49
67 1
68 1
73 1
76 1
78 1
81 1
1 84
85 1
87 1
88 1
1 93
1 99
108 1
128 1
1 129
1 132
134 1
135 1
138 1
1 142
144 1
1 150
1 155
158 1
160 1
1 170
1 175
183 1
1 193
1 197
213 1
1 215
216 1
222 1
1 225
1 233
234 1
235 1
242 1
258 1
268 1
1 ...

output:

result:

ok q=100000

Test #166:

score: 0

Accepted

time: 108ms

memory: 10460kb

input:

1000 100000
13 1
22 1
1 24
1 29
32 1
42 1
46 1
50 1
1 56
1 62
66 1
1 68
1 69
71 1
1 73
1 75
81 1
1 87
88 1
94 1
1 96
101 1
107 1
1 108
110 1
111 1
126 1
1 143
148 1
1 150
160 1
166 1
176 1
1 180
1 183
1 195
1 206
211 1
1 213
1 216
219 1
236 1
1 238
1 242
1 249
251 1
252 1
256 1
266 1
1 277
1 293
295...

output:

result:

ok q=100000

Test #167:

score: 0

Accepted

time: 797ms

memory: 10460kb

input:

1000 100000
1 4
1 7
8 1
14 1
16 1
1 17
20 1
22 1
1 28
1 29
34 1
1 35
1 38
1 41
1 49
1 53
1 57
1 58
1 74
1 84
85 1
1 90
95 1
103 1
104 1
1 107
108 1
110 1
1 117
1 118
1 126
1 141
142 1
1 145
1 147
1 152
153 1
154 1
1 163
1 165
166 1
173 1
175 1
180 1
1 184
188 1
1 189
194 1
201 1
204 1
207 1
1 210
21...

output:

result:

ok q=100000

Test #168:

score: 0

Accepted

time: 662ms

memory: 10424kb

input:

1000 100000
15 1
18 1
1 26
31 1
1 37
1 40
42 1
1 46
1 48
1 49
1 53
55 1
1 68
75 1
82 1
83 1
89 1
92 1
102 1
106 1
1 113
1 114
1 119
1 121
1 123
128 1
129 1
130 1
1 133
140 1
1 143
1 153
1 154
1 163
1 167
168 1
171 1
176 1
178 1
1 190
191 1
1 192
1 200
201 1
204 1
205 1
1 206
212 1
1 215
1 218
1 223
...

output:

result:

ok q=100000

Test #169:

score: 0

Accepted

time: 447ms

memory: 10476kb

input:

1000 100000
5 1
14 1
1 17
33 1
40 1
55 1
1 58
59 1
1 61
1 66
70 1
1 71
1 75
76 1
79 1
1 81
90 1
95 1
1 102
1 104
1 109
119 1
130 1
1 131
142 1
144 1
147 1
1 154
158 1
1 161
170 1
178 1
1 182
187 1
189 1
1 211
217 1
1 229
1 233
245 1
248 1
1 249
254 1
256 1
1 257
258 1
271 1
1 273
1 277
286 1
1 287
1...

output:

result:

ok q=100000

Test #170:

score: 0

Accepted

time: 303ms

memory: 10596kb

input:

1000 100000
1 5
1 13
1 19
26 1
1 29
34 1
35 1
38 1
39 1
45 1
1 46
1 67
79 1
1 92
94 1
1 97
108 1
1 111
1 120
122 1
1 129
131 1
140 1
1 143
148 1
159 1
1 169
175 1
180 1
185 1
187 1
1 189
1 192
1 195
200 1
205 1
1 208
1 213
1 228
1 232
243 1
244 1
1 245
1 246
1 263
271 1
274 1
1 281
292 1
299 1
301 1...

output:

result:

ok q=100000

Test #171:

score: 0

Accepted

time: 205ms

memory: 10592kb

input:

1000 100000
1 3
4 1
1 5
8 1
1 11
1 21
1 24
1 27
36 1
45 1
1 51
1 74
1 75
79 1
1 80
83 1
1 86
1 93
1 95
98 1
101 1
106 1
109 1
110 1
117 1
127 1
1 130
1 131
1 137
1 141
145 1
1 154
155 1
160 1
1 164
166 1
168 1
169 1
172 1
1 173
174 1
181 1
1 185
1 188
198 1
1 202
1 212
217 1
1 228
230 1
1 234
1 235
...

output:

result:

ok q=100000

Test #172:

score: 0

Accepted

time: 102ms

memory: 10540kb

input:

1000 100000
4 1
1 6
8 1
1 9
12 1
16 1
1 20
1 32
50 1
1 62
70 1
1 72
1 74
1 77
78 1
1 79
1 84
88 1
89 1
94 1
95 1
1 97
107 1
114 1
1 115
126 1
130 1
132 1
1 138
1 144
1 156
1 162
1 163
165 1
178 1
1 181
1 185
1 192
200 1
214 1
1 215
1 218
1 221
1 226
1 232
1 235
1 237
246 1
1 249
1 256
1 269
279 1
28...

output:

result:

ok q=100000

Test #173:

score: 0

Accepted

time: 219ms

memory: 10536kb

input:

1000 100000
4 1
7 1
10 1
1 11
1 15
19 1
20 1
25 1
1 37
40 1
41 1
1 45
1 49
1 55
62 1
67 1
68 1
1 70
1 84
1 87
98 1
102 1
1 122
1 131
141 1
1 148
149 1
1 150
1 155
1 165
1 171
1 179
183 1
185 1
1 189
191 1
1 193
201 1
1 205
217 1
218 1
219 1
1 237
1 240
1 251
257 1
261 1
268 1
274 1
1 285
286 1
1 289...

output:

result:

ok q=100000

Test #174:

score: 0

Accepted

time: 395ms

memory: 10472kb

input:

output:

result:

ok q=100000

Test #175:

score: 0

Accepted

time: 478ms

memory: 10544kb

input:

output:

result:

ok q=100000

Test #176:

score: 0

Accepted

time: 187ms

memory: 8424kb

input:

output:

result:

ok q=100000

Test #177:

score: 0

Accepted

time: 189ms

memory: 8456kb

input:

output:

result:

ok q=100000

Test #178:

score: 0

Accepted

time: 395ms

memory: 9236kb

input:

output:

result:

ok q=100000

Test #179:

score: 0

Accepted

time: 473ms

memory: 9244kb

input:

output:

result:

ok q=100000

Test #180:

score: 0

Accepted

time: 141ms

memory: 8500kb

input:

output:

result:

ok q=100000

Test #181:

score: 0

Accepted

time: 191ms

memory: 8416kb

input:

output:

result:

ok q=100000

Test #182:

score: 0

Accepted

time: 417ms

memory: 8736kb

input:

output:

result:

ok q=100000

Test #183:

score: 0

Accepted

time: 450ms

memory: 8732kb

input:

output:

result:

ok q=100000

Test #184:

score: 0

Accepted

time: 119ms

memory: 8444kb

input:

output:

result:

ok q=100000

Test #185:

score: 0

Accepted

time: 158ms

memory: 8364kb

input:

output:

result:

ok q=100000

Test #186:

score: 0

Accepted

time: 368ms

memory: 8560kb

input:

output:

result:

ok q=100000

Test #187:

score: 0

Accepted

time: 428ms

memory: 8624kb

input:

output:

result:

ok q=100000

Test #188:

score: 0

Accepted

time: 129ms

memory: 8372kb

input:

output:

result:

ok q=100000

Test #189:

score: 0

Accepted

time: 146ms

memory: 8360kb

input:

output:

result:

ok q=100000

Test #190:

score: 0

Accepted

time: 349ms

memory: 8312kb

input:

output:

result:

ok q=100000

Test #191:

score: 0

Accepted

time: 393ms

memory: 8320kb

input:

output:

result:

ok q=100000

Test #192:

score: 0

Accepted

time: 120ms

memory: 8152kb

input:

output:

result:

ok q=100000

Test #193:

score: 0

Accepted

time: 143ms

memory: 8216kb

input:

output:

result:

ok q=100000

Test #194:

score: 0

Accepted

time: 312ms

memory: 8300kb

input:

output:

result:

ok q=100000

Test #195:

score: 0

Accepted

time: 329ms

memory: 8296kb

input:

output:

result:

ok q=100000

Test #196:

score: 0

Accepted

time: 118ms

memory: 8088kb

input:

output:

result:

ok q=100000

Test #197:

score: 0

Accepted

time: 142ms

memory: 8092kb

input:

output:

result:

ok q=100000

Test #198:

score: 0

Accepted

time: 273ms

memory: 8116kb

input:

output:

result:

ok q=100000

Test #199:

score: 0

Accepted

time: 297ms

memory: 8048kb

input:

output:

result:

ok q=100000

Test #200:

score: 0

Accepted

time: 118ms

memory: 7964kb

input:

output:

result:

ok q=100000

Test #201:

score: 0

Accepted

time: 138ms

memory: 8080kb

input:

output:

result:

ok q=100000

Test #202:

score: 0

Accepted

time: 233ms

memory: 5888kb

input:

output:

result:

ok q=100000

Test #203:

score: 0

Accepted

time: 262ms

memory: 5940kb

input:

output:

result:

ok q=100000

Test #204:

score: 0

Accepted

time: 117ms

memory: 5924kb

input:

output:

result:

ok q=100000

Test #205:

score: 0

Accepted

time: 147ms

memory: 5984kb

input:

output:

result:

ok q=100000

Extra Test:

score: 0

Extra Test Passed