QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504904#7610. Bus LinespandapythonerAC ✓2008ms75616kbC++235.5kb2024-08-04 17:09:472024-08-04 17:09:49

Judging History

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

  • [2024-08-04 17:09:49]
  • 评测
  • 测评结果:AC
  • 用时:2008ms
  • 内存:75616kb
  • [2024-08-04 17:09:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);

const int logn = 18;
const int maxn = 2e5 + 1000;
const int maxm = 2e5 + 1000;
int n, m;
vector<vector<int>> g;
pair<int, int> busses[maxm];
int bup[maxn][logn];
int sz[maxn];
int c;
int tin[maxn], tout[maxn];
int h[maxn];
int par[maxn];
int up[maxn], up_deg[maxn];
ll dp_down[maxn], dp_up[maxn];
vector<int> busses_graph[maxn];

struct tin_comp {
    bool operator()(int u, int v) const { return tin[u] < tin[v]; }
};

ll sum = 0;
ll great_val[maxn];
ll great_val_sum[maxn];
int total_lca = -1;
set<int, tin_comp> st;

ll result[maxn];


int lca(int u, int v);

void clear() {
    st.clear();
    total_lca = -1;
    sum = 0;
}


void add_vertex(int v) {
    if (st.count(v)) return;
    if (total_lca == -1) total_lca = v;
    else total_lca = lca(total_lca, v);
    auto it = st.insert(v).first;
    sum += great_val_sum[v];
    int a = -1;
    int b = -1;
    if (it != st.begin()) {
        a = *prev(it);
        int t = lca(a, v);
        sum -= great_val_sum[t];
    }
    if (next(it) != st.end()) {
        b = *next(it);
        int t = lca(b, v);
        sum -= great_val_sum[t];
    }
    if (a != -1 and b != -1) {
        sum += great_val_sum[lca(a, b)];
    }
}



ll get_sum() {
    ll result = sum;
    if (total_lca != -1 and total_lca != 0) {
        result -= great_val_sum[par[total_lca]];
        result += dp_down[total_lca];
    }
    return result;
}

void dfs1(int v, int p) {
    par[v] = bup[v][0] = p;
    for (int i = 1; i < logn; i += 1) {
        bup[v][i] = bup[bup[v][i - 1]][i - 1];
    }
    rep(i, len(g[v])) if (g[v][i] == p) {
        g[v].erase(g[v].begin() + i);
        break;
    }
    sz[v] = 1;
    int mxsz = -1;
    int mxszi = -1;
    rep(i, len(g[v])) {
        int to = g[v][i];
        dfs1(to, v);
        sz[v] += sz[to];
        if (mxsz < sz[to]) {
            mxsz = sz[to];
            mxszi = i;
        }
    }
    if (mxszi != -1) {
        swap(g[v][0], g[v][mxszi]);
    }
}


void dfs2(int v, int mh = 0) {
    tin[v] = c++;
    h[v] = mh;
    for (auto to : g[v]) {
        dfs2(to, mh + 1);
    }
    tout[v] = c;
}


int go_up(int v, int x) {
    rep(i, logn) {
        if ((x >> i) & 1) {
            v = bup[v][i];
        }
    }
    return v;
}


int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    u = go_up(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = logn - 1; i >= 0; i -= 1) {
        if (bup[u][i] != bup[v][i]) {
            u = bup[u][i];
            v = bup[v][i];
        }
    }
    assert(u != v);
    return par[u];
}


void dfs3(int v) {
    for (auto to : g[v]) {
        dfs3(to);
        if (h[up[v]] > h[up[to]]) {
            up[v] = up[to];
        }
    }
    assert(v == 0 or h[up[v]] < h[v]);
    up_deg[v] += 1;
    up_deg[up[v]] += up_deg[v];
    dp_down[v] = up_deg[v];
    for (auto to : g[v]) {
        dp_down[v] += dp_down[to];
    }
}



void dfs4(int v, ll sum = 0) {
    sum += great_val[v];
    great_val_sum[v] = sum;
    for (auto to : g[v]) {
        dfs4(to, sum);
    }
}


void dfs6(int);


void dfs5(int v) {
    for (int i = len(g[v]) - 1; i >= 0; i -= 1) {
        clear();
        int to = g[v][i];
        dfs5(to);
    }
    for (int i = 1; i < len(g[v]); i += 1) {
        int to = g[v][i];
        dfs6(to);
    }
    for (auto u : busses_graph[v]) {
        add_vertex(u);
    }
    if (g[v].empty()) add_vertex(v);
    dp_up[v] = n - sz[v] + get_sum();
}


void dfs6(int v) {
    for (auto u : busses_graph[v]) {
        add_vertex(u);
    }
    if (g[v].empty()) add_vertex(v);
    for (auto to : g[v]) dfs6(to);
}


void dfs7(int v) {
    if (v != 0 and up[v] != 0) {
        dp_up[v] += dp_up[up[v]];
    }
    for (auto to : g[v]) dfs7(to);
}


void solve() {
    dfs1(0, 0);
    c = 0;
    dfs2(0);
    rep(v, n) up[v] = v;
    rep(v, n) up_deg[v] = 0;
    rep(i, m) {
        auto [u, v] = busses[i];
        int t = lca(u, v);
        if (h[up[u]] > h[t]) {
            up[u] = t;
        }
        if (h[up[v]] > h[t]) {
            up[v] = t;
        }
    }
    dfs3(0);
    dp_down[0] = 0;
    rep(v, n) {
        great_val[v] = -dp_down[v];
        for (auto to : g[v]) great_val[v] += dp_down[to];
    }
    dfs4(0);
    rep(i, n) dp_up[i] = 0;
    rep(i, n) busses_graph[i] = {};
    rep(i, m) {
        auto [u, v] = busses[i];
        busses_graph[u].push_back(v);
        busses_graph[v].push_back(u);
    }
    clear();
    dfs5(0);
    dp_up[0] = 0;
    dfs7(0);
    rep(v, n) {
        result[v] = dp_up[v];
        for (auto to : g[v]) {
            result[v] += dp_down[to];
        }
    }
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    g.assign(n, vector<int>());
    rep(i, n - 1) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> m;
    rep(i, m) {
        int u, v; cin >> u >> v; --u; --v;
        busses[i] = make_pair(u, v);
    }
    solve();
    rep(v, n) cout << result[v] << " ";
    cout << "\n";
    return 0;
}

/*
6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4


*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 18180kb

input:

6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4

output:

6 9 9 10 7 7 

result:

ok single line: '6 9 9 10 7 7 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 19884kb

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

score: 0
Accepted
time: 75ms
memory: 24180kb

input:

16384
9137 490
3442 7239
1621 6904
13769 10250
14672 12572
14906 9437
6163 12339
15244 12016
3022 8670
3211 9106
11966 14817
15798 15876
6423 7394
894 7695
13877 1983
16342 15158
13574 15932
15125 10722
6989 15683
10335 8801
12301 4246
6166 3893
9347 12073
7897 12195
6510 3101
4526 15385
7017 7001
4...

output:

34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...

result:

ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '

Test #4:

score: 0
Accepted
time: 373ms
memory: 34044kb

input:

65536
44501 44259
59772 51161
51582 2027
2699 8610
5021 57211
60597 10270
29222 11423
38503 3833
52021 47503
47160 15296
61201 13465
20807 17239
7705 20234
32708 25663
7800 42265
29410 44963
32173 38920
49438 61282
25922 4342
40171 9819
12256 3995
41600 39383
57051 60932
44275 8351
8356 8295
3557 64...

output:

140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...

result:

ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '

Test #5:

score: 0
Accepted
time: 1166ms
memory: 51848kb

input:

131071
28270 44685
69228 113487
10873 80967
30958 109340
53006 103488
49569 111875
65021 32861
83043 36671
73613 119374
22104 91373
31527 27737
19718 27803
90762 87148
4096 41649
79425 111516
111950 123500
94580 61416
30879 18640
71251 76344
61698 28557
104875 59268
130832 61334
110927 109064
114115...

output:

273557 262588 264936 265663 265875 266353 265834 265712 376149 272370 267699 267626 267023 265515 266009 265333 278296 265843 265760 268149 267395 265340 271825 358266 268835 264845 266112 265586 265886 266374 265323 265391 266080 265499 278600 267120 265190 266164 266010 265240 265690 265370 264312...

result:

ok single line: '273557 262588 264936 265663 26...42 266079 265822 265939 266211 '

Test #6:

score: 0
Accepted
time: 361ms
memory: 57980kb

input:

131071
4458 33223
28971 26710
73930 35887
19953 56582
19448 128895
117093 55994
68752 16511
37373 128666
1236 73891
64724 74049
67901 130974
130547 112357
99689 77958
76785 17021
37348 91813
67628 67488
96598 83555
17348 74226
98935 43076
75325 83600
59427 80746
74874 122816
71615 76503
112584 12953...

output:

131070 131070 131070 131070 131070 131070 131071 131071 131071 131071 131070 131071 131070 131070 131071 131071 131070 131071 131071 131070 131070 131070 131070 131070 131071 131070 131070 131070 131070 131070 131070 131071 131070 131071 131070 131070 131070 131070 131070 131071 131070 131070 131071...

result:

ok single line: '131070 131070 131070 131070 13...70 131071 131070 131070 131071 '

Test #7:

score: 0
Accepted
time: 1206ms
memory: 50332kb

input:

131072
20415 30901
24973 116658
50309 77228
14138 108175
122283 105254
80524 41943
16756 109108
113505 71325
9649 106367
125747 68730
27704 18831
12993 123364
57489 129424
96113 82877
44188 4472
5704 86388
73653 70774
41742 33080
6701 59595
80297 22453
59925 75977
88478 91057
97666 26155
30080 55382...

output:

267346 265658 267019 267148 266495 270630 265327 266124 266100 265926 265909 266766 265785 266284 265064 266584 266146 266937 271485 265805 265480 266087 267189 264771 266288 266965 270451 265977 265706 265268 265845 267259 265723 266249 266047 266159 270563 266086 265976 265845 265431 265535 265930...

result:

ok single line: '267346 265658 267019 267148 26...80 270694 266015 266101 265704 '

Test #8:

score: 0
Accepted
time: 353ms
memory: 59768kb

input:

131072
48550 41416
47329 96006
106074 122239
948 75631
112525 117270
3358 7210
30446 101867
16965 11336
78371 58088
21081 102637
76025 92177
102359 2073
11618 50130
79150 120277
30847 51845
72881 58212
125170 71210
1909 8660
120236 81594
127702 49237
32584 53272
5049 20955
31844 125464
119524 100808...

output:

131071 131072 131078 131071 131071 131072 131072 131072 131074 131071 131071 131071 131072 131071 131071 131072 131072 131072 131071 131115 131078 131072 131074 131071 131072 131074 131071 131071 131072 131072 131074 131074 131072 131072 131074 131072 131078 131072 131077 131074 131071 131072 131072...

result:

ok single line: '131071 131072 131078 131071 13...71 131074 131072 131072 131072 '

Test #9:

score: 0
Accepted
time: 1148ms
memory: 50260kb

input:

131073
113890 124822
124669 105393
128510 64051
106729 33462
46677 33217
73570 96913
47532 130531
8593 45487
31793 58221
49510 82943
60351 62272
42636 37378
105049 94689
124230 45945
13194 123517
107928 62129
7572 15657
84304 122943
19818 59980
104221 18821
66457 91449
5072 101241
61822 5975
74471 6...

output:

266326 266281 266163 265817 265563 266929 265938 266796 265751 265513 266249 269598 266832 267310 265225 266439 266351 265499 397338 269917 266647 266193 266663 266655 269976 266497 326968 266761 266261 266672 265613 266103 265821 265496 265891 266411 265820 266598 266583 266154 265794 265587 266472...

result:

ok single line: '266326 266281 266163 265817 26...69 266180 266343 268563 266527 '

Test #10:

score: 0
Accepted
time: 396ms
memory: 56336kb

input:

131073
30694 94981
78010 61921
83010 76565
7176 94673
24081 63906
107002 35122
72499 90887
98339 109807
48362 125168
5335 63101
127350 85675
13421 77562
2375 93853
10090 23323
91852 109502
21899 90367
56580 125803
108402 88380
30465 25789
73326 29902
60781 28952
113429 111420
15039 5166
48046 85049
...

output:

131072 131072 131073 131072 131072 131072 131072 131072 131072 131072 131072 131205 131072 131072 131072 131083 131073 131072 131083 131073 131072 131072 131072 131072 131073 131073 131072 131072 131072 131072 131072 131072 131072 131072 131072 131083 131073 131073 131072 131194 131205 131072 131072...

result:

ok single line: '131072 131072 131073 131072 13...72 131072 131072 131072 131072 '

Test #11:

score: 0
Accepted
time: 543ms
memory: 72148kb

input:

200000
303 187602
17443 90857
141584 9689
98281 37564
34044 95754
47052 855
176062 121958
162738 96296
89316 164507
150496 42874
12673 1114
24877 131213
196802 28543
78558 84878
102156 146853
143846 158517
167159 69770
16743 9610
169056 115672
127506 149401
4110 24877
150803 72957
71484 24773
50738 ...

output:

200000 200000 200001 200009 200000 200000 200000 200004 200000 200001 200009 200040 200000 200000 200371 200001 200001 200000 200005 200000 200103 200000 200005 200001 200002 200000 200004 200000 200004 200002 200001 200004 200000 200004 200103 200000 200001 200001 200009 200004 200000 200000 200009...

result:

ok single line: '200000 200000 200001 200009 20...00 200000 200000 200001 200001 '

Test #12:

score: 0
Accepted
time: 542ms
memory: 72024kb

input:

200000
91261 108952
134236 7809
30750 140934
69514 100626
174539 64746
143756 139270
75999 163614
73309 112948
110641 128653
77295 196144
112549 15212
29529 58568
34742 48981
160465 37279
60772 47631
116260 164168
140007 138837
152400 41600
46137 103771
122809 991
98335 53547
71446 60454
182926 9505...

output:

259717 224832 623118 233065 221904 225116 248347 347328 229609 227413 369557 318840 231176 228808 255754 223173 224794 339975 239690 230310 252630 225403 411260 227236 240962 241886 231002 333731 242413 226478 294844 238042 224724 260233 244253 330794 247474 231750 283982 269581 221874 223906 258662...

result:

ok single line: '259717 224832 623118 233065 22...21 228869 224599 227932 221883 '

Test #13:

score: 0
Accepted
time: 0ms
memory: 17904kb

input:

3
3 2
1 3
1
1 2

output:

2 2 2 

result:

ok single line: '2 2 2 '

Test #14:

score: 0
Accepted
time: 735ms
memory: 66352kb

input:

200000
139347 147721
117297 105382
77192 197023
48135 123968
192172 102714
134778 129103
89903 62952
133541 38908
157094 5072
98697 154745
126329 161358
10578 175752
174214 105555
128475 68598
37906 187226
161543 11243
153891 97890
8751 74708
1967 76185
67263 189209
68782 199622
163887 141633
176004...

output:

322099 242574 317560 692202 290760 228294 365767 338369 353452 316822 250525 392353 334147 230213 228522 235083 402948 230055 390730 404058 356419 260604 408966 344671 228306 285866 230909 242013 251050 312234 247399 300014 275307 396635 301629 245071 324672 317767 338521 318599 251342 394339 233005...

result:

ok single line: '322099 242574 317560 692202 29...72 316661 233236 238848 229144 '

Test #15:

score: 0
Accepted
time: 779ms
memory: 65644kb

input:

200000
48091 145114
125125 28630
12239 122518
46999 28599
9536 79090
173383 59215
130797 80267
19356 192091
70170 63308
51543 84599
75128 23622
67565 61168
59080 1306
169051 40849
189030 31373
186212 42004
87480 32135
81468 163743
112945 69079
83894 23714
71122 15016
66755 85285
115054 110310
3811 4...

output:

352484 361697 353433 343102 240568 351386 298596 364831 245058 343138 260208 258681 345310 370366 432737 233034 361503 405572 231637 345073 347968 358736 232149 353892 398610 251240 431731 345221 343820 346239 347060 263522 231954 393526 360199 379830 373877 236327 353553 603138 426721 241772 231332...

result:

ok single line: '352484 361697 353433 343102 24...94 353707 382734 557096 397978 '

Test #16:

score: 0
Accepted
time: 873ms
memory: 64380kb

input:

200000
100856 98512
7263 55794
118589 8600
181408 78844
136926 96808
184915 65090
34153 123222
81629 114888
41173 81343
115395 158775
74974 23534
3836 68657
105617 97663
76598 41608
28787 13900
100912 96168
68712 136985
80113 56372
112283 126282
119777 137629
165008 120438
53426 26030
78094 83600
18...

output:

385605 380500 397966 236324 577262 360773 233242 371405 362611 369437 365600 386222 381693 250148 585672 376752 366566 253349 377273 388253 269521 263111 427010 369947 392348 389317 423904 233334 252314 359670 387478 359580 233140 434587 321068 233635 234253 365444 235007 599141 373618 362626 360872...

result:

ok single line: '385605 380500 397966 236324 57...45 241541 407294 372787 439030 '

Test #17:

score: 0
Accepted
time: 975ms
memory: 62992kb

input:

200000
180714 64749
50294 63588
118425 45210
19449 119242
106397 111631
165556 58767
54399 99326
53093 31192
63207 75350
36668 124604
80509 124402
69687 129300
190278 28893
50196 134511
46249 169905
58139 53110
87694 22713
75518 99566
179781 17413
110365 34464
27454 193678
130171 47991
174341 58040
...

output:

409591 396787 395821 239526 599035 470672 428144 397055 392027 394551 439143 394596 388894 404545 405346 348418 392047 593706 389817 326075 394143 396508 393233 425007 399946 397646 399058 595850 413576 389700 412903 417007 392550 401326 462627 392588 275297 400751 395385 395593 398254 244287 415091...

result:

ok single line: '409591 396787 395821 239526 59...05 410665 400756 392347 468683 '

Test #18:

score: 0
Accepted
time: 1094ms
memory: 62644kb

input:

200000
30933 92193
77862 62042
158213 175855
16780 145844
1108 114460
160478 9352
82719 112145
142088 62191
15793 183238
129644 169759
70407 173026
113244 57481
56239 24998
45541 79142
119610 110586
99594 22588
198974 169804
99392 125472
63750 161647
119893 161584
25389 132271
48396 138568
63641 385...

output:

603675 406633 422392 407572 409097 406433 406205 407058 420803 408723 464911 425536 410465 481876 407605 576569 607865 431005 412229 419713 410499 412896 408749 606713 403730 427776 408406 407828 606627 417814 407449 407308 404474 470975 410304 412734 413266 406163 408984 403576 406249 405420 406787...

result:

ok single line: '603675 406633 422392 407572 40...37 412018 406965 408388 609396 '

Test #19:

score: 0
Accepted
time: 1302ms
memory: 62480kb

input:

200000
53058 81131
171867 48542
51107 57582
48378 14960
8723 5010
161623 59486
63739 114343
146033 97144
38395 143404
106830 120862
166654 142711
17747 75675
115326 57950
141271 125647
172839 194710
87377 142587
179489 111106
83353 29003
25273 100804
126366 129214
377 22864
136214 154742
26790 69245...

output:

410194 414485 812212 409671 417799 607529 444323 439505 398218 413075 406897 417525 409744 418032 416266 417491 409650 420260 411460 411034 412949 416088 409367 613828 410798 608605 411940 403730 303206 404280 403397 612430 415487 395351 408532 419160 418430 410453 416946 618525 408493 411347 423058...

result:

ok single line: '410194 414485 812212 409671 41...85 413258 416216 407728 410996 '

Test #20:

score: 0
Accepted
time: 1432ms
memory: 62268kb

input:

200000
59158 51892
164326 130454
199875 147324
154595 198150
175219 8364
108094 125630
131696 93091
63992 91024
129143 10985
79964 129833
193970 137750
130697 130080
103615 11370
83315 137120
141683 168619
130441 168268
163828 3410
76009 110247
59575 155246
124663 70547
152379 94187
114650 89902
282...

output:

418785 413603 418648 419139 412502 406320 410977 412124 407379 402640 419358 416320 407945 412692 414142 413490 413278 416746 410595 418751 415083 413390 420604 412779 418777 613129 408587 406350 413893 413360 413188 418726 401511 408363 419082 414357 526212 413422 601652 413018 411076 418011 413908...

result:

ok single line: '418785 413603 418648 419139 41...13 414570 417977 436541 415929 '

Test #21:

score: 0
Accepted
time: 286ms
memory: 75616kb

input:

200000
118922 134567
199816 52066
84326 118291
140839 91527
41156 196216
193057 168156
5712 147301
151841 143708
95806 153816
135331 166094
167087 140971
112587 136986
97546 33542
171749 67249
173810 197325
61841 77212
116769 138505
62675 30261
101896 50402
91780 178503
28880 20528
87860 154449
8267...

output:

13168057510 11173781860 10146494712 16156520832 13448332006 10989071050 10508931040 10037228302 12324541582 10347691962 10028724240 12081412506 11563767480 10187676300 12443176612 10048783240 11774557750 16609608700 15055565506 14134682902 10028318362 11956514056 10158873420 15322067256 11664028056 ...

result:

ok single line: '13168057510 11173781860 101464...110756 18856409772 13401863950 '

Test #22:

score: 0
Accepted
time: 292ms
memory: 71252kb

input:

200000
74212 14285
54279 26014
34653 159417
195912 97270
147173 32677
7753 76853
47200 73990
93075 63990
186243 107173
105569 133096
11068 124684
66637 118271
143298 65684
108858 167243
83551 3112
227 38450
120359 109554
42942 133316
29887 192012
143614 97487
95789 105585
33495 155927
63945 45781
13...

output:

9636839798 7803026188 5944133824 5022351612 5824014810 5466796520 5799132740 5020579868 5118628970 5167194124 5461475062 5089909366 9928608548 5018143302 8863291306 5172571016 6712586160 5054073146 6479682294 5284856118 6274156336 8690429520 8083401824 5218118942 5428913248 9540526484 5044191702 640...

result:

ok single line: '9636839798 7803026188 59441338...48485482 5237756436 7380188354 '

Test #23:

score: 0
Accepted
time: 349ms
memory: 65692kb

input:

200000
92107 93965
159733 109184
192340 76154
84291 151200
22927 32573
60309 166432
136353 52220
46466 195262
169506 58576
155186 181682
129591 45964
5016 99216
173166 72054
186200 95903
105499 17449
196067 122431
177329 57447
66939 50332
67438 62704
184758 103097
13997 9543
159320 119688
67521 1795...

output:

2647717540 2669067610 2536317714 4564900018 4938957828 2523583466 2587289770 4089042968 2538144128 3083739956 2846104828 4939992978 3010058766 2640028282 3303357298 3059661060 3682213356 2518446598 4593066520 3175275992 3500605592 2512952006 2728454602 4496768570 3328605822 3999565194 3852256448 268...

result:

ok single line: '2647717540 2669067610 25363177...80561904 3193035228 3613793802 '

Test #24:

score: 0
Accepted
time: 0ms
memory: 17888kb

input:

3
2 1
2 3
2
1 2
2 3

output:

3 2 3 

result:

ok single line: '3 2 3 '

Test #25:

score: 0
Accepted
time: 490ms
memory: 63844kb

input:

200000
97274 52191
170698 12492
56055 38209
195479 171683
182171 104124
48099 163495
28208 143687
98769 194755
69808 115617
120295 101563
38553 94131
23270 112248
131587 158997
31823 162234
83013 181537
191160 172757
189345 102179
151357 192653
101899 101918
118524 182209
14724 52904
14881 114877
65...

output:

315521802 582270214 374296028 430835082 461750522 547580860 458554994 341017246 385629432 318527132 308318016 304520182 306364072 333253596 574032542 314446098 521022698 407699078 460444652 298495576 297416182 437728058 483072350 552191872 358261158 439148560 390171338 424559912 452883186 322464158 ...

result:

ok single line: '315521802 582270214 374296028 ... 501733906 435471700 498539190 '

Test #26:

score: 0
Accepted
time: 577ms
memory: 63852kb

input:

200000
149275 37122
186803 180793
142343 25474
2212 104891
153840 36431
70840 95284
71111 176237
88737 94284
132867 69692
115881 67641
31109 97047
21627 157384
46886 161629
143575 184545
168978 54964
39205 42574
168223 32975
102385 50620
84750 126621
109786 165166
80248 112638
7161 54171
108145 1160...

output:

156800727 185140211 160861639 163079193 181736213 166433065 169894763 127848699 165191659 128374161 137184613 136296451 122378297 150527067 186298237 142165489 171740743 163923655 144726201 186139667 216535769 143134125 206500761 150034699 166563761 130542877 215959573 147380353 174762851 188816095 ...

result:

ok single line: '156800727 185140211 160861639 ... 198578685 168950583 138834499 '

Test #27:

score: 0
Accepted
time: 891ms
memory: 51256kb

input:

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

output:

131070 131070 131070 182280 182358 182396 182254 212773 212880 212959 212834 212906 212874 212780 212908 231778 231899 231958 231796 231820 231879 231765 231895 231892 231897 231788 231917 231935 231630 231878 231824 243684 243863 243938 243663 243836 243843 243815 243694 243798 243698 243831 243802...

result:

ok single line: '131070 131070 131070 182280 18...10 262108 262110 262109 262109 '

Test #28:

score: 0
Accepted
time: 2008ms
memory: 63560kb

input:

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

output:

199999 199999 199999 270262 270338 256650 263828 314788 314651 314909 314789 296669 306837 306858 307041 344034 344207 343935 344033 344234 344132 343944 344267 323943 338165 338282 338012 338010 338278 338024 338183 363927 363728 363701 364016 363891 363723 363903 363943 364207 363770 364084 363899...

result:

ok single line: '199999 199999 199999 270262 27...38 399935 399952 399941 399950 '

Test #29:

score: 0
Accepted
time: 2007ms
memory: 63396kb

input:

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

output:

199999 199999 199999 270280 270281 256568 264051 314791 314703 314807 314898 296686 306740 307060 307152 343985 344188 343968 343978 344132 343950 344140 344015 323926 338128 337970 338070 338265 338213 338358 338125 363833 363803 363874 363896 363900 363746 363692 363889 363786 363925 363911 363775...

result:

ok single line: '199999 199999 199999 270280 27...39 399953 399937 399939 399937 '

Test #30:

score: 0
Accepted
time: 537ms
memory: 43396kb

input:

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

output:

131070 131070 131070 184799 184843 184800 184829 217005 217033 217100 216971 216982 216966 216950 217126 236023 236111 236122 236094 236140 236171 236092 236061 236028 236043 236068 236008 236123 236095 236158 236268 247294 247277 247287 247231 247276 247264 247224 247281 247294 247216 247256 247270...

result:

ok single line: '131070 131070 131070 184799 18...08 262108 262108 262108 262108 '

Test #31:

score: 0
Accepted
time: 1734ms
memory: 55612kb

input:

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

output:

199999 199999 199999 266202 266155 240079 246034 305437 305423 305403 305492 277024 288045 288193 288165 334579 334476 334657 334517 334515 334737 334772 334673 307254 324135 324262 324310 323971 324233 324346 324298 357001 356766 356841 356766 357114 356952 356916 356789 356939 356889 356833 356904...

result:

ok single line: '199999 199999 199999 266202 26...16 399899 399907 399904 399893 '

Test #32:

score: 0
Accepted
time: 1709ms
memory: 55748kb

input:

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

output:

199999 199999 199999 266198 266176 240035 245995 305476 305528 305426 305350 276894 288169 288156 287994 334767 334568 334626 334738 334701 334412 334616 334539 307261 324335 324446 324383 324266 324369 324449 324205 356954 356892 356897 356815 356935 356814 356889 356968 356924 356904 356664 356857...

result:

ok single line: '199999 199999 199999 266198 26...92 399892 399906 399896 399893 '

Test #33:

score: 0
Accepted
time: 1461ms
memory: 64648kb

input:

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

output:

199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005 200006 200006 200007 200007 200008 200008 200009 200009...

result:

ok single line: '199988 199989 199989 199990 19...30 389951 389957 389943 389968 '

Test #34:

score: 0
Accepted
time: 466ms
memory: 66064kb

input:

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

output:

199984 199985 199985 199986 199986 199987 199987 199988 199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005...

result:

ok single line: '199984 199985 199985 199986 19...64 374965 374967 374967 374967 '

Test #35:

score: 0
Accepted
time: 0ms
memory: 19932kb

input:

4
2 1
4 3
1 3
4
3 2
3 4
2 1
2 1

output:

4 4 3 5 

result:

ok single line: '4 4 3 5 '

Test #36:

score: 0
Accepted
time: 1677ms
memory: 64592kb

input:

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

output:

199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005 200006 200006 200007 200007 200008 200008 200009 200009...

result:

ok single line: '199988 199989 199989 199990 19...46 384959 384960 384948 384961 '

Test #37:

score: 0
Accepted
time: 1934ms
memory: 63512kb

input:

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

output:

199978 199979 199979 199980 199980 199981 199981 199982 199982 199983 199983 199984 199984 199985 199985 199986 199986 199987 199987 199988 199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999...

result:

ok single line: '199978 199979 199979 199980 19...39 399411 399411 399440 399441 '

Test #38:

score: 0
Accepted
time: 1455ms
memory: 64064kb

input:

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

output:

199980 199982 199982 199982 199984 199984 199984 199986 199986 199986 199988 199988 199988 199990 199990 199990 199992 199992 199992 199994 199994 199994 199996 199996 199996 199998 199998 199998 200000 200000 200000 200002 200002 200002 200004 200004 200004 200006 200006 200006 200008 200008 200008...

result:

ok single line: '199980 199982 199982 199982 19...84 393279 393281 393287 393287 '

Test #39:

score: 0
Accepted
time: 390ms
memory: 65464kb

input:

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

output:

199980 199982 199982 199982 199984 199984 199984 199986 199986 199986 199988 199988 199988 199990 199990 199990 199992 199992 199992 199994 199994 199994 199996 199996 199996 199998 199998 199998 200000 200000 200000 200002 200002 200002 200004 200004 200004 200006 200006 200006 200008 200008 200008...

result:

ok single line: '199980 199982 199982 199982 19...91 383291 383292 383293 383293 '

Test #40:

score: 0
Accepted
time: 1320ms
memory: 64380kb

input:

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

output:

199983 199985 199985 199985 199987 199987 199987 199989 199989 199989 199991 199991 199991 199993 199993 199993 199995 199995 199995 199997 199997 199997 199999 199999 199999 200001 200001 200001 200003 200003 200003 200005 200005 200005 200007 200007 200007 200009 200009 200009 200011 200011 200011...

result:

ok single line: '199983 199985 199985 199985 19...49 389950 389951 389951 389952 '

Test #41:

score: 0
Accepted
time: 1476ms
memory: 63528kb

input:

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

output:

199983 199985 199985 199985 199987 199987 199987 199989 199989 199989 199991 199991 199991 199993 199993 199993 199995 199995 199995 199997 199997 199997 199999 199999 199999 200001 200001 200001 200003 200003 200003 200005 200005 200005 200007 200007 200007 200009 200009 200009 200011 200011 200011...

result:

ok single line: '199983 199985 199985 199985 19...15 399615 399617 399617 399617 '

Test #42:

score: 0
Accepted
time: 1417ms
memory: 63960kb

input:

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

output:

199988 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997 249997 249997 249999 249999 249999 249999 250001 250001 250001 250001 250003 250003 250003 250003 250005 250005 250005 250005 250007 250007...

result:

ok single line: '199988 249987 249987 249987 24...64 394965 394958 394970 394965 '

Test #43:

score: 0
Accepted
time: 414ms
memory: 64964kb

input:

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

output:

199980 249977 249977 249977 249977 249979 249979 249979 249979 249981 249981 249981 249981 249983 249983 249983 249983 249985 249985 249985 249985 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997...

result:

ok single line: '199980 249977 249977 249977 24...58 387459 387459 387459 387460 '

Test #44:

score: 0
Accepted
time: 1311ms
memory: 64112kb

input:

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

output:

199976 249972 249972 249972 249972 249974 249974 249974 249974 249976 249976 249976 249976 249978 249978 249978 249978 249980 249980 249980 249980 249982 249982 249982 249982 249984 249984 249984 249984 249986 249986 249986 249986 249988 249988 249988 249988 249990 249990 249990 249990 249992 249992...

result:

ok single line: '199976 249972 249972 249972 24...36 392437 392437 392437 392438 '

Test #45:

score: 0
Accepted
time: 1441ms
memory: 63252kb

input:

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

output:

199980 249977 249977 249977 249977 249979 249979 249979 249979 249981 249981 249981 249981 249983 249983 249983 249983 249985 249985 249985 249985 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997...

result:

ok single line: '199980 249977 249977 249977 24...94 399695 399695 399695 399696 '

Test #46:

score: 0
Accepted
time: 0ms
memory: 19892kb

input:

16
6 5
4 7
16 7
14 10
10 6
1 9
10 2
15 11
8 13
15 5
13 16
12 1
15 3
15 8
1 15
16
1 14
11 6
3 15
7 8
12 1
10 11
2 16
5 4
10 8
6 12
11 1
10 2
9 12
4 14
16 1
13 2

output:

19 24 30 22 17 17 22 19 32 18 25 25 19 20 16 19 

result:

ok single line: '19 24 30 22 17 17 22 19 32 18 25 25 19 20 16 19 '

Test #47:

score: 0
Accepted
time: 348ms
memory: 71244kb

input:

200000
75181 178691
167132 24574
21481 90765
81460 60919
82245 108152
65683 173513
76902 84549
123226 91319
41694 165036
94669 192530
154076 153602
100902 20831
90175 147499
51312 16926
14772 167477
163013 122912
24100 55416
173417 128164
199861 186216
78608 76991
124298 91595
80825 119577
116094 13...

output:

50474638 50191810 69503436 54366029 53258199 60296221 52039784 63630859 58868296 82953818 78426866 93062178 83112557 93454169 75434369 78265902 54132728 47597410 82596185 89438443 91127263 53191470 50080591 48325373 47681641 71491673 66757053 88685300 59982978 77322154 65296864 49874706 88673812 784...

result:

ok single line: '50474638 50191810 69503436 543...982 47643953 69957694 70926955 '

Test #48:

score: 0
Accepted
time: 409ms
memory: 69272kb

input:

200000
188991 38536
19016 131514
34849 20659
146565 5563
127586 152943
139286 134818
165140 30444
41931 86603
26615 112397
5469 101689
26521 160202
21149 159878
45079 178089
131738 108012
177334 9239
90377 50876
196994 10435
91399 34143
27718 169370
83553 132616
178465 132491
162334 63031
180808 818...

output:

24993686 22535318 25093599 27418706 26197310 42204273 24869573 40511446 26130536 30057368 22369507 25394625 42596441 23199608 27299672 31766039 24448003 22320557 27297716 27659652 22792436 38332932 21704042 22267391 33757501 37465239 31090331 24057816 30435937 26269042 23201120 24094869 21714600 265...

result:

ok single line: '24993686 22535318 25093599 274...128 22141964 32257994 23383007 '

Test #49:

score: 0
Accepted
time: 460ms
memory: 66964kb

input:

200000
906 199746
107936 138177
62750 153929
59299 197264
68283 134308
168204 152703
87690 5885
182724 6013
60916 76081
80301 163580
84788 189716
168885 124983
54096 2802
106732 8500
163252 162533
6080 48703
187591 162568
45014 26781
68652 99032
25806 136034
67122 181202
177859 27996
193698 78737
17...

output:

32929020 34069370 40028545 37661564 38678342 30750107 33322391 43647777 32966166 34540745 56091894 30722580 31073744 45982654 30727586 32999951 30851744 30791018 43063835 31353181 59457024 30812724 36789879 51721870 31193313 33619943 38916209 31423361 34479112 35924734 51894027 57940165 40097310 322...

result:

ok single line: '32929020 34069370 40028545 376...609 56226588 30772657 47877102 '

Test #50:

score: 0
Accepted
time: 492ms
memory: 65912kb

input:

200000
40440 24070
53985 146625
68335 41905
37111 154568
87025 93999
166749 178229
90621 133195
94566 176393
80877 7309
51016 173297
84683 122464
50093 33531
29390 14574
144254 197157
59901 32183
136953 3045
144780 97707
142252 9994
161963 106725
67833 93692
66691 19180
11168 70696
174478 27071
3568...

output:

26783886 24103262 24341471 31558721 23646973 22561030 37838773 21854798 25488172 40353549 21486080 23151361 21678943 23151035 39659953 39278145 24645201 25186116 21622484 39624225 41304011 24995081 21578951 27711490 23503882 29970542 25286710 21544886 41336232 42304747 37134867 34719974 21513967 224...

result:

ok single line: '26783886 24103262 24341471 315...831 22937500 37317332 35645125 '

Test #51:

score: 0
Accepted
time: 533ms
memory: 64712kb

input:

200000
46568 142176
92040 6143
182603 189978
72891 67409
159519 191115
67289 86172
185549 11506
98061 180309
77000 107263
58451 198920
170080 170714
46827 3206
32273 27342
83368 67894
175680 1078
78837 62988
161130 70582
5223 133157
101436 14577
154937 193873
17799 162737
23687 54641
85214 82353
193...

output:

33798263 32555933 48157520 43134079 32532199 50632136 49287897 56378466 42412373 33334251 44502560 33503605 36741434 55532750 35496162 32950017 34702169 56715631 42046007 33522284 36821057 64726295 34295338 36626392 45068949 45658390 40083911 33131584 47703579 47126418 41396118 42826295 40135185 583...

result:

ok single line: '33798263 32555933 48157520 431...765 46003035 32567705 33923064 '

Test #52:

score: 0
Accepted
time: 567ms
memory: 63464kb

input:

200000
51240 130378
64520 44156
59560 155045
51704 99909
59561 134357
126256 63666
15949 140681
72887 126011
170282 13437
57032 131896
185862 98012
95093 141872
183438 41646
64877 11578
94960 153354
41961 196982
183878 180510
44417 102166
184835 136493
122867 168934
183074 115227
34126 58709
126803 ...

output:

24103329 18147085 17013747 18290357 20541449 19479085 25359019 25641877 28533173 19426147 26188760 21312766 20714945 23031381 20633574 17122927 22665153 21993733 18528212 20431080 17741588 18150951 33210156 29200169 17201878 20185600 25179090 32284344 25471417 19801285 18042747 19661852 17046147 285...

result:

ok single line: '24103329 18147085 17013747 182...236 28034076 21443078 33448613 '

Test #53:

score: 0
Accepted
time: 754ms
memory: 62744kb

input:

200000
99719 120749
26467 12087
64651 169043
103895 184334
118838 55887
75096 145169
182647 90953
129978 141482
10983 185683
96556 30195
16919 25618
197146 54090
143967 159127
133629 167436
108954 105218
129783 115593
148324 58557
125717 70523
147382 32019
90141 77494
71835 14416
32734 108007
169625...

output:

4540663 4671456 4428939 5535385 6892497 5557766 7408781 7410797 4275469 4194013 4158930 5352076 4606566 6293647 4412235 6511061 7420271 5893908 5945178 4670589 6227712 4356763 4735789 4239261 5558620 6429973 7060108 5150232 6201608 6290625 4361744 6511328 4485881 7060130 7219599 7961307 4325850 6159...

result:

ok single line: '4540663 4671456 4428939 553538...195899 5352787 6260023 6734375 '

Test #54:

score: 0
Accepted
time: 938ms
memory: 62248kb

input:

200000
39006 155355
59936 58989
114072 52126
144417 130838
192407 125631
98060 126007
63946 143554
97804 5617
179450 175794
135854 130826
141387 199480
84980 116863
107663 189000
148102 30432
182946 27437
113614 13034
82327 164808
48176 58845
147970 62823
189143 186194
11550 183879
93591 122219
1449...

output:

800775 621521 690096 695843 715598 824539 563225 932567 798424 760340 696182 923151 684252 799804 796222 752250 799208 797506 796713 922821 755995 689309 799710 923878 759527 690023 925395 739686 756049 922539 1105590 923584 667962 730115 752095 800875 922109 756461 751538 796525 932456 897174 95477...

result:

ok single line: '800775 621521 690096 695843 71...75 682165 587557 756755 698636 '

Test #55:

score: 0
Accepted
time: 1309ms
memory: 62420kb

input:

200000
66301 173363
129318 127908
128408 164206
12510 80814
80498 147845
185443 78596
153018 23013
139590 103971
42588 68867
89578 101577
73679 13597
71140 188721
118546 118625
121316 30257
178132 133021
28694 128971
55640 177671
40134 81023
133914 50892
175589 367
94401 129808
59739 185865
197921 9...

output:

417997 415952 416904 415957 416020 418169 409679 412301 614369 413756 416345 415805 416075 412592 424787 418842 408384 418210 413973 818569 417973 412425 413548 411639 414520 623624 615600 413791 417718 416669 415289 404658 454610 433763 398469 550769 416076 416056 405714 423859 415449 415930 415310...

result:

ok single line: '417997 415952 416904 415957 41...07 411842 617991 408427 409265 '

Test #56:

score: 0
Accepted
time: 343ms
memory: 72044kb

input:

200000
61396 81570
55536 113950
46900 141787
43935 87423
194884 117890
20095 131408
134063 62971
172244 47759
25833 30615
167427 63421
122035 15558
157184 113222
27992 192054
100424 67032
66630 153777
185783 42049
115814 71168
125770 19171
88777 5184
11269 56730
51095 36238
154829 14343
3544 175070
...

output:

1125442347 897306694 1001004565 649092624 723128284 631343757 704511677 734670273 882958790 777386128 629240951 1049280047 639632957 832483529 1104153491 1192296126 1253461863 633258056 795563764 775937775 917503230 641793821 1007312973 1024531355 726813868 967214610 911983580 797826440 629818720 69...

result:

ok single line: '1125442347 897306694 100100456... 829324349 804021626 644347161 '

Test #57:

score: 0
Accepted
time: 0ms
memory: 20024kb

input:

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

output:

174 120 120 113 99 124 98 121 99 117 119 81 71 82 121 114 112 95 182 113 140 121 89 157 125 103 120 117 184 122 114 125 124 115 117 117 117 151 116 119 91 124 131 109 122 125 124 109 78 74 106 124 129 174 119 121 108 128 121 124 121 142 120 108 

result:

ok single line: '174 120 120 113 99 124 98 121 ...08 128 121 124 121 142 120 108 '

Test #58:

score: 0
Accepted
time: 441ms
memory: 67560kb

input:

200000
151798 54121
50378 178642
145024 73817
137584 180522
105434 166414
95728 89567
81830 36549
195511 54760
55208 127964
33742 181666
178737 123474
37713 158296
52229 192513
2285 190186
19962 58300
79487 196840
151032 194269
114019 3746
128197 4441
99945 191537
105525 107799
72341 117203
36561 14...

output:

10634193 15723004 16345762 14071076 12822659 11416194 12325965 16025945 12852678 10658740 10567204 11672494 15537903 13442275 10993458 14286284 16957123 18409808 17915298 11611947 10655142 17218735 12516512 12683865 18002109 10632883 16504736 15533329 12299631 10881149 13932098 18275622 13209522 105...

result:

ok single line: '10634193 15723004 16345762 140...173 10659417 10615978 14045553 '

Test #59:

score: 0
Accepted
time: 444ms
memory: 64516kb

input:

200000
70195 37550
90611 70195
52647 70195
119470 70195
68644 70195
70195 78334
120998 70195
26479 70195
70195 36317
70195 138045
70195 15345
111105 70195
50529 70195
70195 171759
114026 70195
70195 28292
70195 107531
70195 186922
108409 70195
164172 70195
70195 147304
70195 125251
70195 61283
70195...

output:

399996 399995 399997 399996 399997 399997 399995 399995 399996 399996 399996 399997 399996 399997 399993 399994 399996 399996 399996 399997 399994 399993 399995 399995 399996 399994 399996 399996 399996 399997 399996 399996 399995 399996 399997 399994 399995 399996 399996 399997 399995 399993 399997...

result:

ok single line: '399996 399995 399997 399996 39...97 399994 399995 399997 399996 '

Test #60:

score: 0
Accepted
time: 522ms
memory: 65376kb

input:

200000
87477 195400
173272 39212
32721 141918
144675 39203
91467 24819
134447 99751
173513 74604
192792 190552
189104 80092
122421 37724
112794 8299
7731 197135
99749 182732
70522 139763
74047 115370
30624 61605
168403 56560
50864 89579
100515 21011
160135 149767
64663 148316
199277 94803
31445 4914...

output:

6194693 3363282 5258336 3093303 3965440 4665391 4486150 3931493 3010307 3121102 3565241 5942965 6160943 3766569 3360814 3889613 5457213 5515010 3467278 5936184 2834265 5759750 4440628 3005431 3484870 5085028 6137698 3669788 4671712 5655091 3235721 3553236 4325772 3673265 3911328 3769367 3352780 4219...

result:

ok single line: '6194693 3363282 5258336 309330...918987 3398829 5678981 2928525 '

Test #61:

score: 0
Accepted
time: 637ms
memory: 63268kb

input:

200000
85439 30600
73628 143172
94528 56713
60433 11700
162850 1717
67215 114048
125603 14417
136543 67393
27773 172979
3306 173392
151603 90063
165745 140576
37845 117956
193012 21945
154586 129677
140083 49377
113109 117037
143624 94767
109404 86771
24880 161247
114438 160962
110924 103481
39580 8...

output:

2583731 3524621 2376028 3528726 2487799 2387709 2637106 3186771 2205471 2569658 4743262 3503474 2325163 3056478 4050326 2409235 3488850 2304502 2396363 3583287 2596711 2237203 2926833 3638708 2576197 2775843 3453905 2486956 2307381 2890969 3757566 3693466 2915172 3671685 2479833 3016672 3811964 2217...

result:

ok single line: '2583731 3524621 2376028 352872...501726 2552418 3519939 4025430 '

Test #62:

score: 0
Accepted
time: 651ms
memory: 63592kb

input:

200000
101253 133884
161023 179465
146180 167585
73836 167629
181637 61177
153518 90494
180411 128220
143663 52464
45744 103680
190838 186745
115678 180066
71265 98439
134376 61236
3313 191788
6017 42295
146020 169428
3015 82222
118310 169273
195832 80228
80846 13936
150889 80201
46688 63709
117472 ...

output:

3022541 2863104 2050833 2200313 2492308 2778408 2065196 1630179 2848659 1971695 1616699 1726806 1873549 2154897 1692391 3118750 2347576 1915477 1844188 1795856 3043729 1867794 2616673 3150023 1710245 2230556 2078113 1640400 2261684 2761081 1636800 1662700 2183496 2735993 2760334 2563027 1716458 1937...

result:

ok single line: '3022541 2863104 2050833 220031...728652 1843756 1627820 1745386 '

Test #63:

score: 0
Accepted
time: 534ms
memory: 65108kb

input:

200000
71474 141281
21131 190770
166504 43257
14359 51681
132595 102961
198412 178537
178888 165923
79682 24117
51450 133748
188373 199835
129666 132794
29485 14931
5503 175213
97509 5223
179715 169606
79431 135639
51764 28576
127204 97752
164765 29782
112288 188592
45105 21766
16081 165872
119622 7...

output:

3607100 4071362 4860306 3420680 3520295 4551372 6702346 7138062 4110507 3367639 3405329 4508598 4657321 5064106 6405449 3453667 4076134 3664077 3570811 3413046 3936113 3908705 3979964 5050095 5859751 4374096 3444629 4722548 3475687 3650429 3661367 4443784 3947781 3621545 4186669 5926952 4225527 3559...

result:

ok single line: '3607100 4071362 4860306 342068...666329 5738735 4091200 4788132 '

Test #64:

score: 0
Accepted
time: 654ms
memory: 63884kb

input:

200000
12647 114265
89650 71121
48795 174687
55878 55011
41042 70046
128974 78729
169784 114391
165509 1199
148948 75775
73828 130475
8676 17475
77586 107518
28170 41745
45184 115162
36099 177438
94873 80232
14199 127887
124894 98540
131980 132925
44456 102588
31296 124857
73907 39176
83498 65717
14...

output:

2740217 2277647 3831876 3229121 3390510 2220434 4196031 2553746 2277846 2646843 3894033 2293704 2832567 2451446 3402180 4451576 3917847 2620579 3439305 2887617 3076165 4534977 2911030 3604015 3787194 2450157 2511552 2313462 2985103 3521182 3387539 2896914 3378313 2258840 3957508 2346163 3884895 2391...

result:

ok single line: '2740217 2277647 3831876 322912...727473 3294093 2854580 2887201 '

Test #65:

score: 0
Accepted
time: 723ms
memory: 62744kb

input:

200000
9527 94152
146053 122142
151175 53726
137277 46273
21925 199504
34754 133663
115276 169024
164032 169864
53412 199735
32570 168773
8012 9680
40920 48052
70121 197701
137933 31670
157764 183660
95295 142880
124013 113011
169527 16616
162734 109694
99587 159405
70761 151544
177595 47602
8193 13...

output:

2130784 1086498 1088077 1886042 1359271 1505763 1980920 1141795 1187148 2529020 1374164 1655559 1408724 1325279 1415417 2202828 1449186 1330929 1113980 2179256 1693369 1428522 1451766 1142163 1369537 1442761 1678893 1124124 2131912 1124076 2086655 1478305 2070080 1900113 1383528 1304718 1738608 1837...

result:

ok single line: '2130784 1086498 1088077 188604...340715 1685394 1413848 1501135 '

Test #66:

score: 0
Accepted
time: 600ms
memory: 63336kb

input:

200000
64321 79007
134698 25912
55202 156769
43677 165615
163493 56112
52785 154943
94004 154030
3222 10824
173904 96601
192767 69328
37045 55584
166187 137509
91232 6047
1725 33224
198582 146070
73087 154719
130684 157300
80921 7165
56886 10897
165636 439
2179 109630
53895 20647
75011 179398
113060...

output:

3216415 4003185 3188637 5671920 5085110 4580285 6286291 5675527 5726760 4954015 3658799 3256399 3229926 4452066 4320545 3299316 3565976 4323100 5182319 6038849 3725487 5336971 3478746 3110613 6249568 3673952 3324042 4041492 3488684 3192732 4749858 6006522 3130167 4372954 4584937 3201987 6495566 6567...

result:

ok single line: '3216415 4003185 3188637 567192...269668 3279079 3654056 4423055 '

Test #67:

score: 0
Accepted
time: 668ms
memory: 62808kb

input:

200000
132634 25975
167323 47819
53039 40655
32742 109181
17217 95146
176891 182393
34915 10165
120939 128624
6787 193796
180678 135986
190374 197501
195634 68495
3541 91174
114834 78593
105347 193760
61618 155366
156146 81639
24804 47578
143407 171294
127377 148107
10921 137552
182198 115349
133205...

output:

2231643 2015504 1884740 1457340 1974987 1413303 1242859 1336960 2296406 2216740 2001345 1477939 1831882 2079298 2263830 2121544 1848236 1480732 1728727 1652652 2044124 1536902 2882734 2991491 1462343 2022910 2236041 2102252 1339638 2440196 2336095 1998648 1808796 1501717 1337806 1396482 1843642 1999...

result:

ok single line: '2231643 2015504 1884740 145734...443435 1243645 1723962 1666617 '

Test #68:

score: 0
Accepted
time: 3ms
memory: 20032kb

input:

256
175 31
81 13
225 111
184 187
59 221
79 103
90 86
46 198
49 212
199 233
46 251
186 246
167 235
232 55
174 214
172 179
43 199
179 72
166 104
129 21
208 66
111 146
242 174
170 71
182 59
161 137
15 26
103 150
148 157
3 73
173 202
1 65
167 121
40 114
242 239
83 207
111 223
1 60
218 45
174 101
249 126...

output:

454 514 464 760 507 773 519 549 529 308 503 529 338 492 510 392 512 512 749 502 494 347 296 514 481 496 661 515 526 507 740 617 532 490 515 493 746 518 518 519 529 506 308 305 504 502 509 510 580 554 519 533 543 549 467 509 778 520 510 506 496 760 520 756 518 515 507 518 497 548 496 523 493 514 475 ...

result:

ok single line: '454 514 464 760 507 773 519 54...20 749 468 527 516 527 499 494 '

Test #69:

score: 0
Accepted
time: 779ms
memory: 62212kb

input:

200000
15416 7979
69244 101223
126238 160437
49943 57191
88680 24539
1779 54042
192116 99497
187439 82878
95673 172817
11996 57391
104713 174935
20305 30617
88902 174205
58022 81908
65133 128347
176040 44735
148361 38533
115777 97657
160652 58483
185632 57972
11213 26084
93870 190215
175218 190951
1...

output:

1180731 1056371 1612134 1378262 1624527 1012776 1112859 1566211 1310536 1714743 1407847 1742571 1671536 1740797 1149290 2027093 1368592 1090640 1075085 1274189 1609461 1267924 1607220 1037533 1532439 1740735 1184763 1189321 1362621 1021988 1405653 1511438 1631634 1517605 1263317 1761842 1371378 1144...

result:

ok single line: '1180731 1056371 1612134 137826...012821 1367193 1140120 1062140 '

Test #70:

score: 0
Accepted
time: 440ms
memory: 63524kb

input:

200000
180392 39292
71358 43871
56360 42180
121413 187197
156785 26595
14838 123219
117993 149881
43528 109763
99332 73419
65699 140906
65071 93546
147027 68576
174066 137502
17373 136777
124039 32023
11506 90063
43646 94883
49947 140393
126263 87521
150742 61123
72228 72191
114890 80911
130520 1567...

output:

819009954 1372137863 1467951618 760700605 1242057328 990053065 828093652 886399518 1027366858 991040315 1008488672 1055479826 1133487270 958645367 816904419 1069406692 1016404627 1654994970 1404472528 929007763 816878877 1140544525 780665799 848605797 1137730367 933131651 1483065427 1040799047 10823...

result:

ok single line: '819009954 1372137863 146795161...591165731 766543810 1218459840 '

Test #71:

score: 0
Accepted
time: 525ms
memory: 62740kb

input:

200000
5592 20651
175675 154967
5456 67803
92451 32979
193060 29325
90651 114785
21845 168241
117360 168300
119716 14151
177116 173612
36977 92239
119341 36196
171998 53503
18495 140811
75886 23558
34218 11994
161621 146769
16036 55434
33487 67102
50733 145002
52418 151429
72220 110981
168111 142013...

output:

128676808 127282331 174061914 169744068 141220429 152601663 244458823 221032841 197728057 190236367 141356272 158291296 128817307 140014014 136637098 203753576 127376689 128598671 172487392 166103817 139273310 127323316 184668159 202070964 247751358 136278435 236391766 167240430 218684964 169659120 ...

result:

ok single line: '128676808 127282331 174061914 ... 127626279 243581911 170714245 '

Test #72:

score: 0
Accepted
time: 0ms
memory: 20388kb

input:

1024
283 440
599 501
628 55
268 211
368 490
134 50
348 905
982 71
422 790
442 219
896 285
1013 217
319 30
85 194
1 50
922 722
81 514
635 572
556 633
304 910
720 750
209 476
289 728
109 721
397 919
29 677
889 151
981 80
740 1001
402 168
415 693
970 548
213 840
983 589
893 875
191 132
191 568
482 691
...

output:

2122 2188 2114 3112 2095 1791 2131 2103 2113 1957 2115 2087 2170 2185 2172 2148 2339 3238 2341 2107 2481 2098 2099 2137 2150 2116 3152 2116 2121 2121 2165 2112 2127 2084 2136 1935 2134 2979 2112 2178 1828 2106 2146 1936 2148 2099 2137 2138 2071 2090 2086 2123 2125 2087 3124 2122 2223 2085 2156 2165 ...

result:

ok single line: '2122 2188 2114 3112 2095 1791 ... 2122 1586 2117 2103 2074 2082 '

Test #73:

score: 0
Accepted
time: 16ms
memory: 20628kb

input:

4096
1984 1595
1539 3196
1286 733
2311 1347
2222 266
726 1088
211 3356
2752 604
1173 4010
1391 393
3752 4094
2487 3589
2985 475
3497 2425
2466 1235
32 3265
1583 3837
722 3656
2423 257
2261 173
3290 913
2209 2489
3807 3594
3132 3440
3721 1134
2628 1255
2764 615
3089 290
1513 688
3231 1508
2379 3955
2...

output:

8451 8920 8299 8515 8448 6496 8515 8930 8713 10932 8545 8503 8493 8558 8183 8493 8475 8412 8704 8577 8611 9660 8389 8455 8503 8436 8574 8708 8800 8477 8486 8361 8915 8443 8442 8466 8656 8680 8649 8504 8501 8382 8555 8545 8710 8508 10945 8413 16688 8617 6989 7669 8548 8059 8494 8704 12542 8613 8535 8...

result:

ok single line: '8451 8920 8299 8515 8448 6496 ... 8509 8566 8520 8404 8574 8406 '

Extra Test:

score: 0
Extra Test Passed