QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360671#8174. Set Constructionucup-team1198#AC ✓4ms3964kbC++203.0kb2024-03-22 00:17:462024-03-22 00:17:46

Judging History

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

  • [2024-03-22 00:17:46]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3964kb
  • [2024-03-22 00:17:46]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define int int64_t

pair<vector<int>, int> get(int m) {
    if (m == 2) {
        return {{0, 1}, 1};
    }
    if (m % 2 == 0) {
        auto res = get(m / 2);
        vector<int> ans;
        int n = res.second;
        for (int x : res.first) {
            ans.push_back(x);
            ans.push_back(x + (1ll << n));
        }
        return {ans, n + 1};
    }
    auto res = get(m - 1);
    res.second++;
    res.first.push_back((1ll << res.second) - 1);
    return res;
}

bool check(vector<int> arr, int n, int m) {
    set<int> st;
    for (int x : arr) {
        st.insert(x);
    }
    assert(st.size() == m && arr.size() == m);
    assert(st.count(0) && st.count((1ll << n) - 1));
    for (int x : arr) {
        for (int y : arr) {
            if (!st.count(x & y) || !st.count(x | y)) {
                return false;
            }
        }
    }
    return true;
}

vector<int> mem = {0, 8, 12, 16, 17, 18, 19, 24, 25, 26, 27, 28, 29, 30, 31};

void solve() {
    int n, m;
    cin >> n >> m;
    /// m = n * (n + 1) / 2;
    if (n == 5 && m == 15) {
        for (int x : mem) {
            cout << x << " ";
        }
        cout << "\n";
        return;
    }
    auto res = get(m);
    int n1 = res.second;
    if (n < n1) {
        cout << "bad! " << n << endl;
        exit(0);
    }
    int add = (1ll << n) - (1ll << n1);
    for (int& x : res.first) {
        if (x % 2 == 1) {
            x += add;
        }
        cout << x << " ";
    }
    /**if (!check(res.first, n, m)) {
        cout << "! " << n << " " << m << endl;
        exit(0);
    }*/
    cout << "\n";
}

void get(int mask, int id) {
    int cnt = __builtin_popcountll(mask);
    if (cnt > 15) return;
    if (cnt == 15) {
        cout << "found! " << endl;
        for (int i = 0; i < 32; ++i) {
            if (mask & (1ll << i)) {
                cout << i << ", ";
            }
        }
        cout << endl;
        exit(0);
    }
    if (id == 32) return;
    get(mask, id + 1);
    if (mask & (1ll << id)) {
        return;
    }
    int mask1 = (mask | (1ll << id));
    for (int i = 0; i < 32; ++i) {
        if ((mask & (1ll << i)) == 0) continue;
        int j = i & id;
        if (j < id && ((mask & (1ll << j)) == 0)) return;
    }
    for (int i = 0; i < 32; ++i) {
        if ((mask & (1ll << i)) == 0) continue;
        int j = i | id;
        mask1 |= (1ll << j);
    }
    get(mask1, id + 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    /// get((1ll << 31) + 1, 1);
    /// assert(check(mem, 5, 15));

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
3 5
4 8
60 2

output:

0 2 1 3 7 
0 4 2 6 9 13 11 15 
0 1152921504606846975 

result:

ok AC

Test #2:

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

input:

30
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
6 21
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
7 11

output:

0 63 
0 61 63 
0 2 61 63 
0 2 57 59 63 
0 4 57 61 59 63 
0 4 49 53 51 55 63 
0 4 2 6 57 61 59 63 
0 4 2 6 49 53 51 55 63 
0 8 2 10 49 57 51 59 55 63 
0 8 2 10 33 41 35 43 39 47 63 
0 8 4 12 49 57 53 61 51 59 55 63 
0 8 4 12 33 41 37 45 35 43 39 47 63 
0 16 4 20 33 49 37 53 35 51 39 55 47 63 
0 16 4 ...

result:

ok AC

Test #3:

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

input:

30
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
7 21
7 22
7 23
7 24
7 25
7 26
7 27
7 28
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
8 11
8 12
8 13
8 14

output:

0 8 4 12 113 121 117 125 115 123 119 127 
0 8 4 12 97 105 101 109 99 107 103 111 127 
0 16 4 20 97 113 101 117 99 115 103 119 111 127 
0 16 4 20 65 81 69 85 67 83 71 87 79 95 127 
0 8 4 12 2 10 6 14 113 121 117 125 115 123 119 127 
0 8 4 12 2 10 6 14 97 105 101 109 99 107 103 111 127 
0 16 4 20 2 18...

result:

ok AC

Test #4:

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

input:

30
8 15
8 16
8 17
8 18
8 19
8 20
8 21
8 22
8 23
8 24
8 25
8 26
8 27
8 28
8 29
8 30
8 31
8 32
8 33
8 34
8 35
8 36
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9

output:

0 16 4 20 193 209 197 213 195 211 199 215 207 223 255 
0 8 4 12 2 10 6 14 241 249 245 253 243 251 247 255 
0 8 4 12 2 10 6 14 225 233 229 237 227 235 231 239 255 
0 16 4 20 2 18 6 22 225 241 229 245 227 243 231 247 239 255 
0 16 4 20 2 18 6 22 193 209 197 213 195 211 199 215 207 223 255 
0 16 8 24 2...

result:

ok AC

Test #5:

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

input:

30
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
9 21
9 22
9 23
9 24
9 25
9 26
9 27
9 28
9 29
9 30
9 31
9 32
9 33
9 34
9 35
9 36
9 37
9 38
9 39

output:

0 8 2 10 497 505 499 507 503 511 
0 8 2 10 481 489 483 491 487 495 511 
0 8 4 12 497 505 501 509 499 507 503 511 
0 8 4 12 481 489 485 493 483 491 487 495 511 
0 16 4 20 481 497 485 501 483 499 487 503 495 511 
0 16 4 20 449 465 453 469 451 467 455 471 463 479 511 
0 8 4 12 2 10 6 14 497 505 501 509...

result:

ok AC

Test #6:

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

input:

6
9 40
9 41
9 42
9 43
9 44
9 45

output:

0 32 16 48 8 40 24 56 2 34 18 50 10 42 26 58 449 481 465 497 457 489 473 505 451 483 467 499 459 491 475 507 455 487 471 503 463 495 479 511 
0 32 16 48 8 40 24 56 2 34 18 50 10 42 26 58 385 417 401 433 393 425 409 441 387 419 403 435 395 427 411 443 391 423 407 439 399 431 415 447 511 
0 64 16 80 8...

result:

ok AC

Test #7:

score: 0
Accepted
time: 4ms
memory: 3948kb

input:

30
60 1801
60 1802
60 1803
60 1804
60 1805
60 1806
60 1807
60 1808
60 1809
60 1810
60 1811
60 1812
60 1813
60 1814
60 1815
60 1816
60 1817
60 1818
60 1819
60 1820
60 1821
60 1822
60 1823
60 1824
60 1825
60 1826
60 1827
60 1828
60 1829
60 1830

output:

0 4096 2048 6144 1024 5120 3072 7168 256 4352 2304 6400 1280 5376 3328 7424 128 4224 2176 6272 1152 5248 3200 7296 384 4480 2432 6528 1408 5504 3456 7552 64 4160 2112 6208 1088 5184 3136 7232 320 4416 2368 6464 1344 5440 3392 7488 192 4288 2240 6336 1216 5312 3264 7360 448 4544 2496 6592 1472 5568 3...

result:

ok AC

Test #8:

score: 0
Accepted
time: 4ms
memory: 3728kb

input:

30
59 1741
59 1742
59 1743
59 1744
59 1745
59 1746
59 1747
59 1748
59 1749
59 1750
59 1751
59 1752
59 1753
59 1754
59 1755
59 1756
59 1757
59 1758
59 1759
59 1760
59 1761
59 1762
59 1763
59 1764
59 1765
59 1766
59 1767
59 1768
59 1769
59 1770

output:

0 16384 8192 24576 2048 18432 10240 26624 512 16896 8704 25088 2560 18944 10752 27136 256 16640 8448 24832 2304 18688 10496 26880 768 17152 8960 25344 2816 19200 11008 27392 128 16512 8320 24704 2176 18560 10368 26752 640 17024 8832 25216 2688 19072 10880 27264 384 16768 8576 24960 2432 18816 10624 ...

result:

ok AC

Test #9:

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

input:

30
58 1682
58 1683
58 1684
58 1685
58 1686
58 1687
58 1688
58 1689
58 1690
58 1691
58 1692
58 1693
58 1694
58 1695
58 1696
58 1697
58 1698
58 1699
58 1700
58 1701
58 1702
58 1703
58 1704
58 1705
58 1706
58 1707
58 1708
58 1709
58 1710
58 1711

output:

0 8192 2048 10240 1024 9216 3072 11264 512 8704 2560 10752 1536 9728 3584 11776 128 8320 2176 10368 1152 9344 3200 11392 640 8832 2688 10880 1664 9856 3712 11904 64 8256 2112 10304 1088 9280 3136 11328 576 8768 2624 10816 1600 9792 3648 11840 192 8384 2240 10432 1216 9408 3264 11456 704 8896 2752 10...

result:

ok AC

Test #10:

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

input:

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

output:

0 3 
0 1 3 
0 7 
0 5 7 
0 2 5 7 
0 2 1 3 7 
0 4 1 5 3 7 
0 15 
0 13 15 
0 2 13 15 
0 2 9 11 15 
0 4 9 13 11 15 
0 4 1 5 3 7 15 
0 4 2 6 9 13 11 15 
0 4 2 6 1 5 3 7 15 
0 8 2 10 1 9 3 11 7 15 
0 31 
0 29 31 
0 2 29 31 
0 2 25 27 31 
0 4 25 29 27 31 
0 4 17 21 19 23 31 
0 4 2 6 25 29 27 31 
0 4 2 6 17...

result:

ok AC

Test #11:

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

input:

30
2 3
5 4
4 9
5 4
2 2
5 11
2 2
5 15
3 5
2 3
5 15
2 2
5 9
4 7
4 2
3 5
4 6
2 3
2 2
5 13
5 11
5 9
4 5
4 9
4 6
3 3
5 4
3 5
4 3
4 6

output:

0 1 3 
0 2 29 31 
0 4 2 6 1 5 3 7 15 
0 2 29 31 
0 3 
0 8 2 10 1 9 3 11 7 15 31 
0 3 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 2 1 3 7 
0 1 3 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 3 
0 4 2 6 17 21 19 23 31 
0 4 1 5 3 7 15 
0 15 
0 2 1 3 7 
0 4 9 13 11 15 
0 1 3 
0 3 
0 8 4 12 1 9 5 13 ...

result:

ok AC

Test #12:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

30
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15
5 15

output:

0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29 30 31 
0 8 12 16 17 18 19 24 25 26 27 28 29...

result:

ok AC

Test #13:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

30
29 242
30 171
41 291
4 7
57 306
30 107
53 75
36 493
47 946
28 376
11 44
31 256
47 672
33 361
55 1258
8 10
13 57
5 15
52 760
17 17
25 145
58 436
49 1087
29 175
57 1015
5 12
42 595
4 6
49 987
54 660

output:

0 1024 256 1280 128 1152 384 1408 64 1088 320 1344 192 1216 448 1472 16 1040 272 1296 144 1168 400 1424 80 1104 336 1360 208 1232 464 1488 4 1028 260 1284 132 1156 388 1412 68 1092 324 1348 196 1220 452 1476 20 1044 276 1300 148 1172 404 1428 84 1108 340 1364 212 1236 468 1492 536868865 536869889 53...

result:

ok AC

Test #14:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

30
48 131
20 28
57 765
59 1532
52 881
56 660
22 19
31 192
47 255
36 487
21 170
18 68
4 9
5 13
8 16
53 1071
19 16
10 2
48 1044
58 933
7 16
60 1410
57 1413
45 213
31 49
26 214
4 3
54 31
59 1075
46 393

output:

0 128 32 160 16 144 48 176 8 136 40 168 24 152 56 184 4 132 36 164 20 148 52 180 12 140 44 172 28 156 60 188 2 130 34 162 18 146 50 178 10 138 42 170 26 154 58 186 6 134 38 166 22 150 54 182 14 142 46 174 30 158 62 190 281474976710145 281474976710273 281474976710177 281474976710305 281474976710161 2...

result:

ok AC

Test #15:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

30
23 155
51 597
36 137
22 41
32 181
15 13
50 538
51 1239
13 83
22 17
51 896
31 170
10 34
5 13
18 165
13 6
52 340
60 570
60 7
57 494
20 5
13 55
16 15
6 7
22 160
38 427
55 315
56 233
29 48
58 1320

output:

0 512 128 640 64 576 192 704 16 528 144 656 80 592 208 720 4 516 132 644 68 580 196 708 20 532 148 660 84 596 212 724 2 514 130 642 66 578 194 706 18 530 146 658 82 594 210 722 6 518 134 646 70 582 198 710 22 534 150 662 86 598 214 726 8386561 8387073 8386689 8387201 8386625 8387137 8386753 8387265 ...

result:

ok AC

Test #16:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

30
56 489
21 111
3 3
8 23
41 834
27 145
22 172
52 413
17 57
3 2
35 232
5 11
59 113
33 47
38 475
20 114
16 133
46 265
6 10
18 3
8 28
60 1429
40 373
46 882
4 9
54 1257
20 182
11 54
3 4
22 54

output:

0 2048 1024 3072 512 2560 1536 3584 128 2176 1152 3200 640 2688 1664 3712 64 2112 1088 3136 576 2624 1600 3648 192 2240 1216 3264 704 2752 1728 3776 16 2064 1040 3088 528 2576 1552 3600 144 2192 1168 3216 656 2704 1680 3728 80 2128 1104 3152 592 2640 1616 3664 208 2256 1232 3280 720 2768 1744 3792 4...

result:

ok AC

Test #17:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

30
53 261
40 344
32 159
11 23
41 739
6 14
14 54
20 146
9 22
20 194
44 524
17 13
22 247
48 1142
37 282
33 41
33 205
31 141
31 270
3 6
57 773
60 1036
12 77
22 98
45 994
7 24
23 209
10 33
37 657
57 179

output:

0 256 128 384 32 288 160 416 16 272 144 400 48 304 176 432 8 264 136 392 40 296 168 424 24 280 152 408 56 312 184 440 4 260 132 388 36 292 164 420 20 276 148 404 52 308 180 436 12 268 140 396 44 300 172 428 28 284 156 412 60 316 188 444 2 258 130 386 34 290 162 418 18 274 146 402 50 306 178 434 10 2...

result:

ok AC

Test #18:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

30
36 401
40 314
11 22
18 99
26 313
25 90
41 13
43 388
26 74
45 846
53 1400
24 54
21 160
38 231
54 493
26 270
57 1410
23 242
41 826
5 9
59 370
41 185
56 1344
34 342
49 453
52 118
46 36
35 227
58 324
6 10

output:

0 512 256 768 128 640 384 896 64 576 320 832 192 704 448 960 16 528 272 784 144 656 400 912 80 592 336 848 208 720 464 976 8 520 264 776 136 648 392 904 72 584 328 840 200 712 456 968 24 536 280 792 152 664 408 920 88 600 344 856 216 728 472 984 4 516 260 772 132 644 388 900 68 580 324 836 196 708 4...

result:

ok AC

Test #19:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

30
47 781
34 565
24 65
51 211
20 148
24 272
36 382
3 6
59 1251
36 485
30 273
18 118
25 266
31 352
60 144
15 96
56 732
57 1376
20 159
39 397
29 330
14 17
51 1317
57 639
12 38
2 2
38 661
40 578
27 308
18 141

output:

0 2048 1024 3072 256 2304 1280 3328 64 2112 1088 3136 320 2368 1344 3392 32 2080 1056 3104 288 2336 1312 3360 96 2144 1120 3168 352 2400 1376 3424 16 2064 1040 3088 272 2320 1296 3344 80 2128 1104 3152 336 2384 1360 3408 48 2096 1072 3120 304 2352 1328 3376 112 2160 1136 3184 368 2416 1392 3440 8 20...

result:

ok AC

Test #20:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

30
25 161
34 346
39 713
31 172
27 222
36 650
5 15
52 902
33 453
22 229
21 83
43 338
31 282
56 1472
12 59
44 511
15 3
36 398
48 762
48 943
10 13
43 896
38 159
14 80
11 20
26 28
53 1355
2 3
51 649
24 47

output:

0 128 64 192 32 160 96 224 16 144 80 208 48 176 112 240 8 136 72 200 40 168 104 232 24 152 88 216 56 184 120 248 2 130 66 194 34 162 98 226 18 146 82 210 50 178 114 242 10 138 74 202 42 170 106 234 26 154 90 218 58 186 122 250 33553921 33554049 33553985 33554113 33553953 33554081 33554017 33554145 3...

result:

ok AC

Test #21:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

30
53 1388
3 6
3 6
41 29
2 3
34 581
50 790
5 15
6 13
23 188
14 64
47 694
51 69
47 155
16 105
23 70
32 520
8 3
37 488
47 85
41 300
36 487
32 106
36 175
50 117
27 3
13 58
57 786
35 105
3 4

output:

0 16384 8192 24576 2048 18432 10240 26624 512 16896 8704 25088 2560 18944 10752 27136 256 16640 8448 24832 2304 18688 10496 26880 768 17152 8960 25344 2816 19200 11008 27392 64 16448 8256 24640 2112 18496 10304 26688 576 16960 8768 25152 2624 19008 10816 27200 320 16704 8512 24896 2368 18752 10560 2...

result:

ok AC

Test #22:

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

input:

30
25 321
51 371
19 131
4 2
25 176
28 305
52 538
43 411
43 852
58 817
33 253
36 59
47 207
4 4
60 80
36 3
49 287
57 545
37 191
24 39
57 681
49 641
48 674
38 378
22 68
39 201
29 359
45 330
8 19
59 377

output:

0 256 128 384 64 320 192 448 32 288 160 416 96 352 224 480 16 272 144 400 80 336 208 464 48 304 176 432 112 368 240 496 8 264 136 392 72 328 200 456 40 296 168 424 104 360 232 488 24 280 152 408 88 344 216 472 56 312 184 440 120 376 248 504 2 258 130 386 66 322 194 450 34 290 162 418 98 354 226 482 ...

result:

ok AC

Test #23:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

30
20 81
36 479
59 459
24 204
27 231
24 231
39 270
7 15
40 90
21 137
46 603
33 461
39 244
48 556
19 103
9 7
10 33
16 97
8 10
53 985
54 1383
27 375
57 1527
37 336
54 822
3 5
24 261
22 35
9 18
58 103

output:

0 64 32 96 16 80 48 112 8 72 40 104 24 88 56 120 2 66 34 98 18 82 50 114 10 74 42 106 26 90 58 122 1048321 1048385 1048353 1048417 1048337 1048401 1048369 1048433 1048329 1048393 1048361 1048425 1048345 1048409 1048377 1048441 1048323 1048387 1048355 1048419 1048339 1048403 1048371 1048435 1048331 1...

result:

ok AC

Test #24:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

30
49 575
44 266
38 706
49 462
5 14
57 1386
42 147
51 941
12 14
2 3
25 295
47 636
20 86
30 4
47 1019
11 56
41 42
55 1428
55 1227
16 13
35 606
49 915
38 703
56 3
31 241
49 352
27 230
14 97
54 1147
39 432

output:

0 8192 2048 10240 512 8704 2560 10752 128 8320 2176 10368 640 8832 2688 10880 32 8224 2080 10272 544 8736 2592 10784 160 8352 2208 10400 672 8864 2720 10912 8 8200 2056 10248 520 8712 2568 10760 136 8328 2184 10376 648 8840 2696 10888 40 8232 2088 10280 552 8744 2600 10792 168 8360 2216 10408 680 88...

result:

ok AC

Test #25:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

30
45 755
31 23
26 167
22 197
58 527
24 207
8 24
11 33
56 1138
42 94
46 825
33 309
52 2
28 391
33 558
7 24
18 31
51 219
59 1720
42 707
38 239
21 226
60 953
46 132
38 9
34 62
41 50
47 862
19 6
17 69

output:

0 8192 2048 10240 1024 9216 3072 11264 512 8704 2560 10752 1536 9728 3584 11776 128 8320 2176 10368 1152 9344 3200 11392 640 8832 2688 10880 1664 9856 3712 11904 32 8224 2080 10272 1056 9248 3104 11296 544 8736 2592 10784 1568 9760 3616 11808 160 8352 2208 10400 1184 9376 3232 11424 672 8864 2720 10...

result:

ok AC

Test #26:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

30
11 60
49 190
48 228
60 60
13 13
36 427
21 159
31 425
34 303
59 101
37 571
33 135
21 111
45 638
60 1399
6 6
45 178
29 241
20 86
50 262
60 241
17 86
25 149
7 5
59 609
43 151
14 48
59 1060
47 140
12 35

output:

0 128 64 192 16 144 80 208 4 132 68 196 20 148 84 212 1793 1921 1857 1985 1809 1937 1873 2001 1797 1925 1861 1989 1813 1941 1877 2005 1795 1923 1859 1987 1811 1939 1875 2003 1799 1927 1863 1991 1815 1943 1879 2007 1807 1935 1871 1999 1823 1951 1887 2015 1855 1983 1919 2047 
0 2048 512 2560 128 2176 ...

result:

ok AC

Test #27:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

30
42 456
27 250
9 24
60 1201
31 119
46 460
45 177
8 24
8 10
45 212
28 262
2 2
46 97
35 72
19 149
44 296
16 98
55 626
18 44
34 40
33 293
22 214
27 352
28 347
44 418
4 6
54 1147
28 203
7 5
43 47

output:

0 1024 512 1536 256 1280 768 1792 64 1088 576 1600 320 1344 832 1856 32 1056 544 1568 288 1312 800 1824 96 1120 608 1632 352 1376 864 1888 16 1040 528 1552 272 1296 784 1808 80 1104 592 1616 336 1360 848 1872 48 1072 560 1584 304 1328 816 1840 112 1136 624 1648 368 1392 880 1904 4 1028 516 1540 260 ...

result:

ok AC

Test #28:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

30
51 1193
51 241
33 525
42 382
50 512
56 346
50 947
43 237
54 1024
49 241
12 25
50 141
33 442
51 987
37 498
24 153
15 110
33 103
34 460
3 4
3 5
34 70
20 79
15 103
47 1112
45 150
48 207
33 181
53 1023
19 4

output:

0 4096 2048 6144 1024 5120 3072 7168 256 4352 2304 6400 1280 5376 3328 7424 128 4224 2176 6272 1152 5248 3200 7296 384 4480 2432 6528 1408 5504 3456 7552 32 4128 2080 6176 1056 5152 3104 7200 288 4384 2336 6432 1312 5408 3360 7456 160 4256 2208 6304 1184 5280 3232 7328 416 4512 2464 6560 1440 5536 3...

result:

ok AC

Test #29:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

30
25 222
48 693
57 48
33 555
41 78
11 44
11 44
43 551
50 1262
5 11
30 193
57 1176
48 762
28 315
29 391
47 774
6 12
51 526
54 521
5 4
26 245
20 145
55 759
13 3
58 937
57 1542
17 149
16 95
41 137
36 333

output:

0 2048 512 2560 128 2176 640 2688 32 2080 544 2592 160 2208 672 2720 8 2056 520 2568 136 2184 648 2696 40 2088 552 2600 168 2216 680 2728 4 2052 516 2564 132 2180 644 2692 36 2084 548 2596 164 2212 676 2724 12 2060 524 2572 140 2188 652 2700 44 2092 556 2604 172 2220 684 2732 33550337 33552385 33550...

result:

ok AC

Test #30:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

29
50 179
36 37
14 47
15 3
52 734
25 246
33 92
42 327
56 1017
19 84
50 720
13 71
34 141
25 31
29 183
11 40
14 58
28 383
27 45
47 428
19 103
9 40
58 1437
40 222
10 29
59 112
39 510
56 1194
44 875

output:

0 512 128 640 64 576 192 704 32 544 160 672 96 608 224 736 8 520 136 648 72 584 200 712 40 552 168 680 104 616 232 744 2 514 130 642 66 578 194 706 34 546 162 674 98 610 226 738 10 522 138 650 74 586 202 714 42 554 170 682 106 618 234 746 1125899906840577 1125899906841089 1125899906840705 1125899906...

result:

ok AC

Test #31:

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

input:

29
53 491
27 267
55 1268
7 28
7 25
31 224
22 122
36 338
30 102
4 3
18 112
43 596
45 534
24 255
15 22
26 291
17 70
33 243
47 556
44 117
24 70
35 375
26 232
44 361
46 678
4 2
19 139
46 1056
47 323

output:

0 4096 1024 5120 512 4608 1536 5632 128 4224 1152 5248 640 4736 1664 5760 64 4160 1088 5184 576 4672 1600 5696 192 4288 1216 5312 704 4800 1728 5824 16 4112 1040 5136 528 4624 1552 5648 144 4240 1168 5264 656 4752 1680 5776 80 4176 1104 5200 592 4688 1616 5712 208 4304 1232 5328 720 4816 1744 5840 4...

result:

ok AC

Test #32:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

29
48 527
20 42
31 377
19 102
38 130
14 63
38 271
54 1151
14 28
46 312
57 326
2 2
7 23
13 56
59 119
37 376
31 217
50 773
49 1204
53 107
13 55
31 251
46 712
51 802
52 799
36 661
38 581
28 100
29 21

output:

0 2048 512 2560 128 2176 640 2688 32 2080 544 2592 160 2208 672 2720 16 2064 528 2576 144 2192 656 2704 48 2096 560 2608 176 2224 688 2736 8 2056 520 2568 136 2184 648 2696 40 2088 552 2600 168 2216 680 2728 24 2072 536 2584 152 2200 664 2712 56 2104 568 2616 184 2232 696 2744 4 2052 516 2564 132 21...

result:

ok AC

Test #33:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

30
53 25
49 23
20 23
23 9
32 9
54 15
26 11
35 19
33 7
35 8
34 30
16 17
24 5
35 30
29 5
25 12
12 28
52 27
53 7
21 27
36 16
45 12
55 26
32 7
31 2
19 20
10 14
36 4
46 30
21 23

output:

0 16 8 24 4 20 12 28 9007199254740929 9007199254740945 9007199254740937 9007199254740953 9007199254740933 9007199254740949 9007199254740941 9007199254740957 9007199254740931 9007199254740947 9007199254740939 9007199254740955 9007199254740935 9007199254740951 9007199254740943 9007199254740959 9007199...

result:

ok AC

Test #34:

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

input:

30
44 8
44 31
38 8
15 9
29 16
14 23
24 15
18 7
36 2
21 5
12 4
34 23
28 20
15 23
48 32
51 21
19 5
37 8
10 16
49 5
18 11
49 10
36 21
13 12
59 2
52 13
53 5
60 29
25 15
46 17

output:

0 4 2 6 17592186044409 17592186044413 17592186044411 17592186044415 
0 64 16 80 4 68 20 84 17592186044161 17592186044225 17592186044177 17592186044241 17592186044165 17592186044229 17592186044181 17592186044245 17592186044163 17592186044227 17592186044179 17592186044243 17592186044167 17592186044231...

result:

ok AC

Test #35:

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

input:

30
54 13
56 27
40 9
47 19
48 3
55 6
34 30
57 21
57 23
41 24
38 27
59 19
31 9
52 15
26 28
28 16
20 32
34 19
28 24
55 15
32 23
50 20
55 27
52 32
40 13
57 28
48 27
37 5
20 2
26 11

output:

0 8 4 12 18014398509481953 18014398509481961 18014398509481957 18014398509481965 18014398509481955 18014398509481963 18014398509481959 18014398509481967 18014398509481983 
0 32 8 40 4 36 12 44 72057594037927809 72057594037927841 72057594037927817 72057594037927849 72057594037927813 72057594037927845...

result:

ok AC

Test #36:

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

input:

30
33 26
29 6
39 24
23 11
46 19
19 5
37 27
23 17
42 25
42 16
16 32
41 17
44 31
55 26
26 2
14 2
58 9
43 15
56 16
14 17
41 11
38 16
20 16
27 18
44 2
45 3
15 21
24 29
40 23
17 25

output:

0 32 8 40 4 36 12 44 8589934529 8589934561 8589934537 8589934569 8589934533 8589934565 8589934541 8589934573 8589934531 8589934563 8589934539 8589934571 8589934535 8589934567 8589934543 8589934575 8589934559 8589934591 
0 4 536870905 536870909 536870907 536870911 
0 16 8 24 4 20 12 28 549755813857 5...

result:

ok AC

Test #37:

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

input:

30
30 26
25 8
40 11
55 15
44 6
18 29
33 6
11 21
45 5
25 8
55 29
42 23
34 2
47 7
21 13
25 31
58 20
37 31
51 14
38 30
14 22
15 5
28 21
60 9
47 7
16 32
50 7
56 18
23 14
10 27

output:

0 32 8 40 4 36 12 44 1073741761 1073741793 1073741769 1073741801 1073741765 1073741797 1073741773 1073741805 1073741763 1073741795 1073741771 1073741803 1073741767 1073741799 1073741775 1073741807 1073741791 1073741823 
0 4 2 6 33554425 33554429 33554427 33554431 
0 8 2 10 1099511627745 109951162775...

result:

ok AC

Test #38:

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

input:

30
10 23
26 32
42 23
18 10
51 8
38 13
53 31
58 20
56 30
54 17
37 25
36 6
26 20
60 13
27 7
44 32
60 11
55 17
46 18
50 17
57 28
28 8
30 10
18 31
45 28
34 26
56 29
30 29
60 13
42 23

output:

0 32 8 40 2 34 10 42 897 929 905 937 899 931 907 939 903 935 911 943 927 959 1023 
0 16 8 24 4 20 12 28 2 18 10 26 6 22 14 30 67108833 67108849 67108841 67108857 67108837 67108853 67108845 67108861 67108835 67108851 67108843 67108859 67108839 67108855 67108847 67108863 
0 32 8 40 2 34 10 42 43980465...

result:

ok AC

Test #39:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

30
22 253
55 1512
44 980
25 318
60 1814
24 287
55 1535
16 124
53 1423
36 661
44 975
25 313
22 240
54 1475
33 556
37 697
48 1147
60 1805
42 883
48 1154
45 1020
50 1272
27 378
51 1320
47 1122
50 1263
23 254
57 1624
32 514
38 724

output:

0 2048 1024 3072 256 2304 1280 3328 64 2112 1088 3136 320 2368 1344 3392 16 2064 1040 3088 272 2320 1296 3344 80 2128 1104 3152 336 2384 1360 3408 4 2052 1028 3076 260 2308 1284 3332 68 2116 1092 3140 324 2372 1348 3396 20 2068 1044 3092 276 2324 1300 3348 84 2132 1108 3156 340 2388 1364 3412 418611...

result:

ok AC

Test #40:

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

input:

30
42 897
30 463
22 226
57 1647
38 735
59 1751
16 113
17 152
18 146
22 241
26 322
10 43
39 758
11 44
14 98
34 570
46 1057
26 338
19 163
58 1684
34 586
28 385
57 1645
11 36
56 1573
27 370
48 1160
32 498
24 295
28 402

output:

0 1024 512 1536 256 1280 768 1792 128 1152 640 1664 384 1408 896 1920 64 1088 576 1600 320 1344 832 1856 192 1216 704 1728 448 1472 960 1984 32 1056 544 1568 288 1312 800 1824 160 1184 672 1696 416 1440 928 1952 96 1120 608 1632 352 1376 864 1888 224 1248 736 1760 480 1504 992 2016 16 1040 528 1552 ...

result:

ok AC

Test #41:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

30
41 834
57 1653
55 1512
29 413
12 66
54 1459
34 569
50 1249
34 590
21 203
58 1681
35 609
47 1118
11 59
10 29
50 1270
10 31
26 322
42 899
46 1059
18 171
35 613
27 363
33 541
55 1525
31 469
47 1098
42 879
46 1065
23 275

output:

0 2048 512 2560 256 2304 768 2816 128 2176 640 2688 384 2432 896 2944 64 2112 576 2624 320 2368 832 2880 192 2240 704 2752 448 2496 960 3008 32 2080 544 2592 288 2336 800 2848 160 2208 672 2720 416 2464 928 2976 96 2144 608 2656 352 2400 864 2912 224 2272 736 2784 480 2528 992 3040 8 2056 520 2568 2...

result:

ok AC

Test #42:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

30
16 123
23 269
53 1421
42 887
60 1808
31 480
33 538
49 1225
35 609
59 1744
48 1150
52 1350
35 612
44 987
17 144
15 94
16 123
21 216
23 268
57 1633
23 273
28 406
54 1455
32 507
28 380
11 51
14 98
32 526
45 1022
53 1404

output:

0 512 128 640 64 576 192 704 16 528 144 656 80 592 208 720 4 516 132 644 68 580 196 708 20 532 148 660 84 596 212 724 63489 64001 63617 64129 63553 64065 63681 64193 63505 64017 63633 64145 63569 64081 63697 64209 63493 64005 63621 64133 63557 64069 63685 64197 63509 64021 63637 64149 63573 64085 63...

result:

ok AC

Test #43:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

30
28 393
40 819
56 1571
11 37
41 849
27 375
20 202
53 1430
56 1584
32 510
43 937
25 300
22 225
55 1529
11 42
18 151
17 126
36 662
13 91
60 1813
28 383
53 1418
60 1826
25 297
33 536
58 1683
14 102
47 1101
32 509
32 516

output:

0 512 256 768 128 640 384 896 32 544 288 800 160 672 416 928 16 528 272 784 144 656 400 912 48 560 304 816 176 688 432 944 8 520 264 776 136 648 392 904 40 552 296 808 168 680 424 936 24 536 280 792 152 664 408 920 56 568 312 824 184 696 440 952 4 516 260 772 132 644 388 900 36 548 292 804 164 676 4...

result:

ok AC

Test #44:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

30
35 626
11 60
46 1053
47 1098
38 727
54 1455
27 363
40 814
29 412
19 169
49 1216
34 578
10 29
22 240
51 1312
57 1642
44 966
36 655
27 368
35 617
59 1747
53 1423
26 325
49 1209
34 574
11 45
53 1414
57 1645
35 606
40 814

output:

0 4096 1024 5120 512 4608 1536 5632 256 4352 1280 5376 768 4864 1792 5888 64 4160 1088 5184 576 4672 1600 5696 320 4416 1344 5440 832 4928 1856 5952 16 4112 1040 5136 528 4624 1552 5648 272 4368 1296 5392 784 4880 1808 5904 80 4176 1104 5200 592 4688 1616 5712 336 4432 1360 5456 848 4944 1872 5968 4...

result:

ok AC

Test #45:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

30
60 1102
60 403
58 82
58 65
59 428
58 1173
58 626
58 1153
58 1448
59 1581
58 929
60 1019
58 530
60 1629
60 1546
60 824
59 3
58 1399
59 1165
60 417
59 1260
59 1310
58 1164
60 384
59 1325
58 131
60 1559
59 224
59 1489
60 1129

output:

0 8192 2048 10240 512 8704 2560 10752 128 8320 2176 10368 640 8832 2688 10880 64 8256 2112 10304 576 8768 2624 10816 192 8384 2240 10432 704 8896 2752 10944 32 8224 2080 10272 544 8736 2592 10784 160 8352 2208 10400 672 8864 2720 10912 96 8288 2144 10336 608 8800 2656 10848 224 8416 2272 10464 736 8...

result:

ok AC

Test #46:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

30
60 452
60 169
59 682
60 1006
60 1426
60 585
59 1368
60 1572
60 761
59 1113
59 1271
59 793
60 890
58 620
60 1774
58 285
60 1525
59 1277
58 861
60 515
60 1529
58 523
58 1129
59 917
60 1459
60 491
60 872
58 624
58 711
59 953

output:

0 1024 512 1536 128 1152 640 1664 64 1088 576 1600 192 1216 704 1728 32 1056 544 1568 160 1184 672 1696 96 1120 608 1632 224 1248 736 1760 16 1040 528 1552 144 1168 656 1680 80 1104 592 1616 208 1232 720 1744 48 1072 560 1584 176 1200 688 1712 112 1136 624 1648 240 1264 752 1776 4 1028 516 1540 132 ...

result:

ok AC

Test #47:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

30
58 1370
59 14
60 79
59 1121
59 347
59 843
60 110
60 301
58 480
58 597
59 648
59 482
58 1169
60 340
58 681
59 1725
60 568
60 719
60 1327
59 577
60 380
58 882
58 934
58 1238
58 347
59 1007
59 143
60 1021
59 567
59 1572

output:

0 16384 4096 20480 2048 18432 6144 22528 512 16896 4608 20992 2560 18944 6656 23040 128 16512 4224 20608 2176 18560 6272 22656 640 17024 4736 21120 2688 19072 6784 23168 64 16448 4160 20544 2112 18496 6208 22592 576 16960 4672 21056 2624 19008 6720 23104 192 16576 4288 20672 2240 18624 6336 22720 70...

result:

ok AC

Extra Test:

score: 0
Extra Test Passed