QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#855966#8417. Kraniki [B]GGapaggl10 ✓802ms193100kbC++142.0kb2025-01-13 13:54:102025-01-13 13:54:10

Judging History

This is the latest submission verdict.

  • [2025-01-13 13:54:10]
  • Judged
  • Verdict: 10
  • Time: 802ms
  • Memory: 193100kb
  • [2025-01-13 13:54:10]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwrh = (b); i <= stOwrh; i++)
#define per(i, a, b) for(int i = (a), stOwrh = (b); i >= stOwrh; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;
using AI = array<int, 2>;

constexpr int mod = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);   
    int n; cin >> n;
    vector<int> L(n + 1), R(n + 1);
    rep(i, 1, n) cin >> L[i] >> R[i];

    vector<int> inv(n + 1);
    inv[1] = 1;
    rep(i, 2, n) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;

    vector<VI> tl(n + 1, VI(__lg(n) + 1)), tr(n + 1, VI(__lg(n) + 1));
    {
        set<array<int, 2>> s;
        per(i, n, 1) {
            auto it = s.lower_bound({L[i], 0});
            while(it != s.end() && (*it)[0] <= R[i]) {
                int t = (*it)[1];
                if(t < 0) tr[-t][0] = i;
                else tl[t][0] = i;
                it = s.erase(it);
            }
            s.insert({L[i], i});
            s.insert({R[i], -i});
        }
    }


    rep(j, 1, __lg(n)) rep(i, 1, n) tl[i][j] = tl[tl[i][j - 1]][j - 1], tr[i][j] = tr[tr[i][j - 1]][j - 1];

    map<AI, int> mp;
    function<int(int, int)> lca = [&](int x, int y) {      // 注意这里编号越大深度越小。
        if(x == y) return x;
        if(!x || !y) return 0;
        if(mp.count({x, y})) return mp[{x, y}];

        int ox = x, oy = y;
        if(x > y) {
            per(i, __lg(n), 0) if(tr[x][i] > y) 
                x = tr[x][i];
            x = tr[x][0];
        }
        else {
            per(i, __lg(n), 0) if(tl[y][i] > x) 
                y = tl[y][i];
            y = tl[y][0];
        }
        return mp[{ox, oy}] = lca(x, y);
    };
 
    vector<int> F(n + 1);
    per(i, n, 1) {
        int l = tl[i][0], r = tr[i][0];
        F[i]++;
        F[l] += F[i], F[r] += F[i];
        F[lca(l, r)] -= F[i];
    }

    int ans = 0;
    rep(i, 1, n) (ans += inv[F[i]]) %= mod;

    cout << ans << '\n';
 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

1
1 2

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2
1 2
3 4

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

7

result:

ok single line: '7'

Test #4:

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

input:

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

output:

8

result:

ok single line: '8'

Test #5:

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

input:

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

output:

7

result:

ok single line: '7'

Test #6:

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

input:

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

output:

8

result:

ok single line: '8'

Subtask #2:

score: 1
Accepted

Test #7:

score: 1
Accepted
time: 2ms
memory: 4292kb

input:

2000
1999 2002
2001 2004
1997 2000
2003 2006
1995 1998
2005 2008
1993 1996
2007 2010
1991 1994
2009 2012
1989 1992
2011 2014
1987 1990
2013 2016
1985 1988
2015 2018
1983 1986
2017 2020
1981 1984
2019 2022
1979 1982
2021 2024
1977 1980
2023 2026
1975 1978
2025 2028
1973 1976
2027 2030
1971 1974
2029 ...

output:

494865289

result:

ok single line: '494865289'

Test #8:

score: 1
Accepted
time: 2ms
memory: 4216kb

input:

1999
2 3997
1999 2003
1996 2000
1998 2001
2002 2006
1993 1997
1995 2004
2005 2009
1990 1994
1992 2007
2008 2012
1987 1991
1989 2010
2011 2015
1984 1988
1986 2013
2014 2018
1981 1985
1983 2016
2017 2021
1978 1982
1980 2019
2020 2024
1975 1979
1977 2022
2023 2027
1972 1976
1974 2025
2026 2030
1969 197...

output:

479499918

result:

ok single line: '479499918'

Test #9:

score: 1
Accepted
time: 2ms
memory: 4108kb

input:

2000
3 3995
1988 1995
1986 1990
1994 2000
1984 1987
1997 2008
1982 1985
2003 2013
1980 1983
2012 2017
1978 1981
2015 2021
1975 1979
2019 2026
1973 1977
2025 2031
1970 1974
2028 2037
1965 1972
2033 2040
1962 1969
2039 2049
1955 1963
2044 2053
1951 1961
2052 2058
1943 1954
2056 2061
1940 1947
2060 206...

output:

51694802

result:

ok single line: '51694802'

Test #10:

score: 1
Accepted
time: 2ms
memory: 4140kb

input:

2000
2 3999
1045 1054
1053 1070
1065 1075
1074 1079
1078 1084
1082 1093
1090 1096
1095 1102
1101 1107
1104 1113
1110 1120
1119 1124
1123 1131
1128 1136
1135 1141
1139 1147
1145 1150
1149 1159
1153 1162
1161 1167
1166 1174
1170 1178
1177 1182
1181 1187
1186 1193
1190 1196
1195 1201
1198 1208
1205 121...

output:

302739621

result:

ok single line: '302739621'

Test #11:

score: 1
Accepted
time: 1ms
memory: 4116kb

input:

2000
1 2
5 9
11 12
14 15
18 22
25 26
27 28
29 31
33 34
41 45
46 49
53 54
55 58
64 65
67 68
70 71
72 75
76 77
83 85
86 88
91 93
95 100
101 102
104 105
110 112
115 116
117 122
124 125
126 128
131 132
134 137
143 144
146 148
150 151
152 153
154 155
156 157
159 160
161 162
163 164
165 166
167 168
170 17...

output:

884525541

result:

ok single line: '884525541'

Test #12:

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

input:

2000
958 2985
2468 3497
485 1455
1207 1702
2232 2730
1570 1828
2574 2850
1769 1901
2789 2912
2764 2819
1742 1796
3214 3759
3630 3869
1867 1929
1517 1636
2879 2951
2865 2903
1091 1351
2894 2908
3570 3687
3531 3594
1782 1811
2905 2910
2935 2967
1803 1820
2100 2350
3096 3348
2920 2946
2904 2907
2855 28...

output:

420696688

result:

ok single line: '420696688'

Test #13:

score: 1
Accepted
time: 2ms
memory: 4136kb

input:

1980
5 77
81 260
262 425
429 597
599 753
755 891
893 1062
1064 1214
1216 1349
1350 1500
1501 1612
1613 1737
1738 1876
1877 1997
1999 2117
2121 2251
2252 2372
2374 2490
2494 2601
2603 2695
2696 2790
2793 2902
2903 2992
2993 3074
3075 3150
3151 3231
3232 3293
3294 3358
3361 3430
3431 3501
3502 3563
35...

output:

822568109

result:

ok single line: '822568109'

Test #14:

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

input:

2000
1955 1958
2053 2057
2045 2047
2062 2067
2006 2009
2046 2054
2052 2066
1889 1894
1944 1950
2007 2013
2012 2015
1946 1956
2358 2360
1860 1865
1893 1897
1896 1901
1844 1847
1878 1884
1977 1983
2113 2121
2059 2069
2116 2126
2359 2366
1952 1967
1880 1900
2080 2085
1979 2000
2362 2369
1923 1931
2323 ...

output:

895138859

result:

ok single line: '895138859'

Test #15:

score: 1
Accepted
time: 2ms
memory: 4036kb

input:

2000
4 18
69 72
91 113
181 183
224 229
231 277
280 339
365 512
514 521
530 550
573 614
620 649
677 697
724 733
736 739
764 793
816 916
919 943
950 1012
1015 1032
1034 1050
1084 1099
1121 1132
1145 1150
1162 1168
1183 1198
1214 1216
1217 1230
1265 1321
1327 1345
1348 1369
1375 1391
1420 1486
1501 156...

output:

273445223

result:

ok single line: '273445223'

Subtask #3:

score: 1
Accepted

Test #16:

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

input:

5000
4999 5002
5001 5004
4997 5000
5003 5006
4995 4998
5005 5008
4993 4996
5007 5010
4991 4994
5009 5012
4989 4992
5011 5014
4987 4990
5013 5016
4985 4988
5015 5018
4983 4986
5017 5020
4981 4984
5019 5022
4979 4982
5021 5024
4977 4980
5023 5026
4975 4978
5025 5028
4973 4976
5027 5030
4971 4974
5029 ...

output:

130853634

result:

ok single line: '130853634'

Test #17:

score: 1
Accepted
time: 4ms
memory: 5284kb

input:

4999
2 9997
4999 5003
4996 5000
4998 5001
5002 5006
4993 4997
4995 5004
5005 5009
4990 4994
4992 5007
5008 5012
4987 4991
4989 5010
5011 5015
4984 4988
4986 5013
5014 5018
4981 4985
4983 5016
5017 5021
4978 4982
4980 5019
5020 5024
4975 4979
4977 5022
5023 5027
4972 4976
4974 5025
5026 5030
4969 497...

output:

278177911

result:

ok single line: '278177911'

Test #18:

score: 1
Accepted
time: 4ms
memory: 4824kb

input:

5000
7 9994
5018 5025
5016 5021
5023 5031
5013 5017
5030 5036
5006 5014
5035 5039
5004 5009
5038 5044
5002 5005
5042 5049
5000 5003
5048 5058
4996 5001
5057 5068
4991 4997
5065 5075
4988 4993
5074 5080
4981 4989
5079 5083
4978 4982
5082 5088
4975 4980
5086 5093
4967 4977
5092 5101
4964 4968
5099 510...

output:

102553560

result:

ok single line: '102553560'

Test #19:

score: 1
Accepted
time: 4ms
memory: 4916kb

input:

5000
1 9995
2480 2484
2483 2492
2489 2503
2502 2507
2506 2510
2509 2516
2514 2520
2518 2527
2525 2531
2530 2540
2533 2544
2543 2553
2548 2560
2557 2567
2565 2578
2576 2581
2580 2588
2585 2591
2590 2596
2595 2600
2599 2606
2602 2612
2611 2617
2615 2624
2622 2627
2626 2633
2632 2638
2637 2642
2641 264...

output:

863270394

result:

ok single line: '863270394'

Test #20:

score: 1
Accepted
time: 3ms
memory: 4864kb

input:

5000
1 4
6 7
8 9
10 11
12 13
14 15
16 17
18 19
21 23
24 26
27 28
29 31
34 35
36 37
38 39
40 41
42 43
47 48
49 51
52 53
54 55
58 59
60 61
63 65
67 69
70 71
73 74
75 76
78 79
80 81
82 83
84 85
86 87
88 89
91 92
93 94
95 96
98 100
101 103
104 105
106 107
108 109
110 111
112 113
114 115
116 117
119 120
...

output:

583337920

result:

ok single line: '583337920'

Test #21:

score: 1
Accepted
time: 2ms
memory: 4732kb

input:

5000
2504 7507
1243 3776
6272 8774
8120 9397
7814 8450
7653 7957
8290 8594
3128 4388
7569 7737
4064 4665
8216 8367
8172 8261
5648 6867
6557 7199
2815 3447
7695 7772
7881 8041
8005 8074
6417 6708
3302 3618
8140 8190
8512 8683
7751 7792
8326 8418
7982 8019
7530 7611
7844 7922
7677 7713
7667 7689
8131 ...

output:

700931101

result:

ok single line: '700931101'

Test #22:

score: 1
Accepted
time: 4ms
memory: 4804kb

input:

4971
4 175
176 462
466 734
736 1002
1003 1290
1291 1546
1547 1804
1806 2055
2056 2291
2292 2514
2517 2767
2773 3004
3006 3232
3233 3485
3486 3689
3693 3926
3927 4166
4167 4387
4388 4591
4593 4796
4798 5002
5005 5210
5211 5381
5382 5577
5578 5764
5765 5938
5939 6122
6124 6306
6307 6466
6467 6642
6644...

output:

849300855

result:

ok single line: '849300855'

Test #23:

score: 1
Accepted
time: 4ms
memory: 4720kb

input:

5000
6933 6939
6965 6967
6935 6942
6947 6961
7076 7084
6940 6948
6946 6966
7080 7090
7106 7108
7146 7150
6976 6980
6963 6977
6983 6990
6985 6994
7178 7183
7100 7103
7692 7696
7089 7096
7094 7102
6483 6487
7189 7194
7149 7153
6912 6916
7107 7112
7182 7191
6902 6910
6972 6992
7099 7111
7020 7024
7262 ...

output:

94724372

result:

ok single line: '94724372'

Test #24:

score: 1
Accepted
time: 4ms
memory: 4732kb

input:

5000
47 78
98 126
158 180
189 227
247 255
307 318
326 332
335 340
353 358
413 437
493 498
501 507
540 580
581 597
600 681
690 695
748 754
780 796
826 831
834 851
864 878
902 935
939 966
1052 1072
1082 1106
1126 1196
1201 1235
1257 1270
1273 1356
1372 1386
1387 1402
1404 1407
1436 1440
1445 1481
1497...

output:

192582190

result:

ok single line: '192582190'

Subtask #4:

score: 1
Accepted

Test #25:

score: 1
Accepted
time: 23ms
memory: 18088kb

input:

50000
1 2
3 4
5 6
7 8
10 11
13 14
15 16
21 22
23 24
25 26
28 30
31 32
33 35
36 37
39 40
41 43
44 45
46 47
48 50
51 52
54 55
57 58
59 60
61 62
63 64
66 67
68 69
70 71
73 74
75 76
77 79
80 81
82 83
86 87
88 89
90 92
94 95
96 97
98 99
102 103
104 105
106 109
110 112
113 114
115 116
117 119
120 121
123 ...

output:

966712525

result:

ok single line: '966712525'

Test #26:

score: 1
Accepted
time: 40ms
memory: 20172kb

input:

50000
14 41
121 213
261 264
506 620
809 867
1084 1234
1249 1298
1429 1468
1472 1508
1628 1633
1659 1735
2162 2189
2195 2221
2275 2284
2343 2417
2423 2550
2579 2581
2590 2690
2702 2741
3023 3163
3198 3321
3389 3599
3602 3627
3650 3657
3687 3701
3754 3813
3959 3961
4044 4184
4209 4217
4266 4317
4369 4...

output:

268837610

result:

ok single line: '268837610'

Test #27:

score: 1
Accepted
time: 29ms
memory: 17068kb

input:

50000
38 129
161 290
443 526
534 587
855 906
931 1251
1417 1593
1639 1669
1764 1964
1995 2089
2152 2239
2253 2349
2575 2608
2732 2735
2749 2904
2985 3226
3318 3344
3361 3466
3492 3502
3887 3888
3954 4044
4190 4290
4401 4569
4633 4718
4779 4802
4837 4855
4868 4931
5017 5238
5338 5360
5465 5490
5579 5...

output:

970973520

result:

ok single line: '970973520'

Test #28:

score: 1
Accepted
time: 43ms
memory: 18420kb

input:

50000
236 2169
5910 7260
9602 9662
10144 13113
13261 13343
14984 15147
15195 15906
16594 17296
19416 20464
20734 21793
22873 25537
26109 26245
28494 29258
29898 31430
32621 33607
34481 34486
35775 36709
37216 39209
39976 40012
40497 41697
42113 42260
44282 44657
47438 47848
49240 49326
50917 53807
5...

output:

605508660

result:

ok single line: '605508660'

Test #29:

score: 1
Accepted
time: 44ms
memory: 20516kb

input:

50000
38 55
81 97
176 180
350 362
406 417
429 488
493 496
548 558
595 636
655 720
757 772
814 867
875 952
1227 1249
1334 1470
1497 1566
1588 1605
1611 1683
1685 1703
1729 1923
1934 1968
1986 1995
2141 2174
2241 2269
2325 2359
2376 2385
2502 2518
2568 2601
2603 2607
2610 2612
2651 2774
2795 2806
2819...

output:

611222557

result:

ok single line: '611222557'

Test #30:

score: 1
Accepted
time: 49ms
memory: 20332kb

input:

50000
49 73
96 222
223 236
242 291
301 319
334 397
492 603
655 656
676 712
742 760
773 871
908 912
913 940
958 978
1067 1068
1204 1211
1289 1400
1582 1607
1628 1670
1718 1774
1779 1821
1883 1936
1961 1969
1997 1999
2063 2094
2148 2179
2388 2391
2480 2493
2590 2667
2730 2831
2881 2915
2934 2997
3027 ...

output:

525677044

result:

ok single line: '525677044'

Test #31:

score: 1
Accepted
time: 50ms
memory: 18652kb

input:

50000
76 129
157 173
233 340
373 432
482 528
638 755
848 876
922 933
966 991
1056 1129
1136 1165
1177 1198
1248 1263
1270 1286
1318 1322
1335 1423
1588 1624
1631 1777
1786 1816
1876 2068
2116 2154
2180 2199
2256 2258
2330 2372
2386 2446
2553 2579
2583 2607
2644 2698
2706 2875
2918 2949
2965 2968
298...

output:

575461278

result:

ok single line: '575461278'

Test #32:

score: 1
Accepted
time: 43ms
memory: 17164kb

input:

50000
18 33
113 265
309 447
509 544
554 564
583 631
710 721
762 794
816 852
873 924
1009 1041
1058 1084
1129 1175
1212 1316
1320 1371
1381 1441
1498 1552
1598 1636
1742 1783
1797 1804
1826 1836
1922 1950
1960 1966
1992 2023
2029 2079
2087 2137
2158 2212
2253 2325
2363 2438
2443 2486
2512 2531
2583 2...

output:

495318105

result:

ok single line: '495318105'

Test #33:

score: 1
Accepted
time: 27ms
memory: 17180kb

input:

50000
4 99997
12 99996
22 99994
29 99992
36 99990
42 99989
47 99987
51 99985
55 99984
60 99983
68 99982
78 99980
86 99979
90 99974
98 99973
102 99972
113 99968
118 99967
125 99966
128 99964
133 99963
142 99956
146 99955
150 99950
155 99949
158 99948
162 99947
165 99943
171 99941
180 99938
185 99937
...

output:

299301983

result:

ok single line: '299301983'

Test #34:

score: 1
Accepted
time: 30ms
memory: 15824kb

input:

50000
33 164
179 2181
3742 4315
5003 6441
7602 8921
9044 9831
12635 13406
13516 14075
14148 14981
15047 17827
18498 20294
20560 22806
24050 26296
27025 27231
28564 28940
28985 29569
32234 34611
38271 40198
41195 42322
42393 42701
43883 44240
44845 45925
46145 48791
50504 50945
51071 51298
51443 5162...

output:

846259638

result:

ok single line: '846259638'

Test #35:

score: 1
Accepted
time: 33ms
memory: 18092kb

input:

50000
14 125
150 163
231 237
238 242
293 366
379 394
489 514
550 588
591 667
718 790
799 802
818 822
837 849
915 931
939 964
987 993
1043 1253
1310 1368
1408 1423
1479 1579
1593 1645
1648 1657
1685 1734
1762 1828
1895 1972
2130 2213
2218 2239
2242 2255
2374 2385
2411 2456
2507 2557
2583 2630
2637 27...

output:

656899268

result:

ok single line: '656899268'

Test #36:

score: 1
Accepted
time: 31ms
memory: 17004kb

input:

50000
20 92
133 159
179 240
260 309
372 375
404 544
565 579
602 653
662 709
723 854
869 871
1011 1052
1104 1171
1212 1225
1272 1365
1408 1614
1622 1651
1690 1695
1805 1816
1836 1840
1844 1848
1867 1996
2116 2203
2440 2477
2483 2539
2545 2547
2572 2609
2616 2663
2672 2710
2759 2793
2809 2847
2864 287...

output:

919601002

result:

ok single line: '919601002'

Test #37:

score: 1
Accepted
time: 32ms
memory: 17140kb

input:

50000
33 102
180 220
268 286
315 357
358 477
478 536
579 590
672 677
691 863
952 1115
1185 1235
1302 1355
1356 1370
1459 1621
1645 1693
1705 1724
1808 1830
1923 1993
2078 2097
2136 2255
2382 2426
2473 2475
2661 2678
2704 2749
2756 2795
2806 2902
2923 2955
3016 3039
3058 3090
3129 3134
3181 3220
3229...

output:

363339644

result:

ok single line: '363339644'

Test #38:

score: 1
Accepted
time: 36ms
memory: 17096kb

input:

50000
38 115
120 214
444 502
503 565
594 657
668 734
793 816
817 836
848 857
925 985
1171 1245
1265 1396
1402 1403
1419 1454
1477 1510
1521 1527
1596 1698
1785 1855
1864 1903
1923 1933
1954 1968
2008 2140
2266 2315
2406 2536
2659 2698
2750 2851
2923 2963
3046 3083
3129 3136
3171 3227
3382 3405
3505 ...

output:

726567990

result:

ok single line: '726567990'

Test #39:

score: 1
Accepted
time: 40ms
memory: 17160kb

input:

50000
2 48004
36001 48003
35998 36002
35995 35999
35992 35996
35989 35993
35986 35990
35983 35987
35980 35984
35977 35981
35974 35978
35971 35975
35968 35972
35965 35969
35962 35966
35959 35963
35956 35960
35953 35957
35950 35954
35947 35951
35944 35948
35941 35945
35938 35942
35935 35939
35932 3593...

output:

205572749

result:

ok single line: '205572749'

Test #40:

score: 1
Accepted
time: 32ms
memory: 17344kb

input:

50000
258 298
418 438
569 632
723 776
1094 1504
1530 1619
1720 2366
2386 2625
2720 2985
3080 3102
3202 3211
3258 3358
3363 3451
3747 3913
4213 4305
4448 4642
4657 4806
4880 5026
5082 5111
5199 5707
5727 5980
6216 6479
6695 6719
6833 6835
7136 7165
7543 7640
7722 7734
7822 7887
7963 8028
8124 8242
83...

output:

395867237

result:

ok single line: '395867237'

Test #41:

score: 1
Accepted
time: 18ms
memory: 13292kb

input:

32768
65535 65536
65533 65534
65531 65532
65529 65530
65527 65528
65525 65526
65523 65524
65521 65522
65519 65520
65517 65518
65515 65516
65513 65514
65511 65512
65509 65510
65507 65508
65505 65506
65503 65504
65501 65502
65499 65500
65497 65498
65495 65496
65493 65494
65491 65492
65489 65490
65487 ...

output:

32768

result:

ok single line: '32768'

Test #42:

score: 1
Accepted
time: 21ms
memory: 13308kb

input:

32767
65533 65534
65531 65532
65529 65530
65527 65528
65525 65526
65523 65524
65521 65522
65519 65520
65517 65518
65515 65516
65513 65514
65511 65512
65509 65510
65507 65508
65505 65506
65503 65504
65501 65502
65499 65500
65497 65498
65495 65496
65493 65494
65491 65492
65489 65490
65487 65488
65485 ...

output:

32767

result:

ok single line: '32767'

Subtask #5:

score: 1
Accepted

Test #43:

score: 1
Accepted
time: 58ms
memory: 33384kb

input:

100000
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
60 61
62 63
64 65
66 67
68 69
70 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
101 103...

output:

316762037

result:

ok single line: '316762037'

Test #44:

score: 1
Accepted
time: 90ms
memory: 37280kb

input:

100000
612 1234
1381 1421
2102 3323
3374 3418
3693 4342
4742 4902
6100 6338
6410 7269
7712 9011
9343 9715
11083 11206
12207 12476
12988 15621
15767 17590
18093 18183
18218 19098
19121 19495
20314 21523
21680 22118
22886 24781
24835 24942
25113 25903
26230 27124
27591 27926
28133 28352
28459 28553
28...

output:

709474369

result:

ok single line: '709474369'

Test #45:

score: 1
Accepted
time: 98ms
memory: 31348kb

input:

100000
375 539
917 1199
1395 1444
1879 1900
2053 2119
2445 2485
2715 2823
2955 3182
3691 3922
4047 4385
4455 4464
4515 4903
5156 5234
5508 5826
5924 5974
5989 6122
6314 6553
6594 6648
7008 7169
7229 7263
7545 7630
7882 8165
8203 8518
8598 8659
9821 10048
10226 10655
11119 11343
11415 12698
12819 128...

output:

713034826

result:

ok single line: '713034826'

Test #46:

score: 1
Accepted
time: 89ms
memory: 33456kb

input:

100000
142 180
207 750
811 915
1231 1296
1454 1479
1485 1503
1595 1654
1677 1981
2124 2126
2213 2233
2485 2641
2689 3273
3301 3304
3336 3496
3551 3567
3831 4124
4136 4191
4197 4362
4378 4390
4507 4625
4767 5001
5106 5170
5182 5427
5429 5471
5632 5732
5745 5837
5931 6258
6336 6398
6793 6979
7123 7131...

output:

688638341

result:

ok single line: '688638341'

Test #47:

score: 1
Accepted
time: 102ms
memory: 38356kb

input:

100000
700 1257
1419 1530
1756 1807
1951 2226
2239 2376
2516 2566
2780 2906
3007 3227
3412 3716
4048 4220
4538 4826
5048 5091
5533 6099
6111 6381
6676 6861
6995 7014
7056 7075
7354 7419
7708 7765
8192 8355
8402 8479
8499 8735
8839 8852
9280 9341
9525 9727
9801 10529
10723 10729
10951 11014
11338 115...

output:

188842913

result:

ok single line: '188842913'

Test #48:

score: 1
Accepted
time: 101ms
memory: 37556kb

input:

100000
9 13
28 83
201 207
230 296
372 409
429 446
503 543
697 863
958 1016
1044 1096
1219 1225
1236 1249
1538 1577
1668 1776
1784 1819
1822 1959
2022 2032
2063 2163
2164 2170
2224 2305
2378 2399
2403 2445
2489 2639
2672 2695
2699 2712
2733 2760
2833 2856
2864 2872
2880 2906
3040 3231
3278 3286
3429 ...

output:

393616772

result:

ok single line: '393616772'

Test #49:

score: 1
Accepted
time: 99ms
memory: 33980kb

input:

100000
45 81
177 284
327 364
451 456
468 556
719 749
828 862
908 912
1003 1014
1123 1130
1139 1192
1235 1250
1264 1309
1433 1476
1534 1646
1764 1841
1856 1867
1915 1933
2021 2024
2042 2056
2066 2108
2177 2183
2188 2216
2236 2282
2340 2373
2388 2617
2786 2789
2877 2908
2953 2996
3078 3104
3105 3229
3...

output:

772167965

result:

ok single line: '772167965'

Test #50:

score: 1
Accepted
time: 91ms
memory: 31148kb

input:

100000
57 280
302 342
359 368
373 394
421 446
504 598
670 788
863 920
992 1004
1060 1129
1137 1176
1196 1213
1269 1405
1425 1476
1549 1695
1909 1917
1920 1931
1952 1971
1972 2005
2037 2156
2294 2523
2525 2551
2585 2679
2714 2717
2937 2941
2948 2980
3097 3155
3163 3235
3252 3280
3324 3326
3474 3553
3...

output:

36859894

result:

ok single line: '36859894'

Test #51:

score: 1
Accepted
time: 71ms
memory: 30924kb

input:

100000
9 199997
13 199995
18 199994
24 199992
27 199991
36 199990
49 199988
54 199987
57 199986
62 199985
69 199983
74 199979
79 199977
85 199976
90 199974
93 199972
96 199970
101 199969
108 199968
116 199967
123 199966
129 199964
132 199961
138 199957
147 199955
152 199949
160 199947
167 199946
170...

output:

655937126

result:

ok single line: '655937126'

Test #52:

score: 1
Accepted
time: 62ms
memory: 28008kb

input:

100000
68 263
344 357
630 634
873 957
1081 1154
1294 1460
1534 1605
1667 1669
1701 1716
1826 1887
2033 2311
2420 2543
2603 2610
2651 2696
2703 2937
2989 3026
3368 3608
3791 3850
4028 4145
4246 4587
4799 4911
4980 5072
5343 5400
5598 5844
6092 6118
6163 6720
6748 6808
6813 6929
6954 7002
7003 7011
71...

output:

484682687

result:

ok single line: '484682687'

Test #53:

score: 1
Accepted
time: 59ms
memory: 33264kb

input:

100000
18 86
100 108
512 604
609 896
998 1427
1509 1713
2180 2508
2690 2921
3065 3250
3386 3557
3564 3969
4015 4384
4485 4902
5159 5252
5541 5671
5746 5822
5994 6081
6104 6242
6315 6550
6636 6959
7262 7272
7373 7458
7681 7714
7858 8067
8151 8867
8968 9162
9189 9290
9461 10321
10402 10624
11309 11400...

output:

323078447

result:

ok single line: '323078447'

Test #54:

score: 1
Accepted
time: 58ms
memory: 31032kb

input:

100000
81 102
137 166
315 720
801 900
912 937
960 983
1005 1075
1141 1158
1164 1175
1196 1228
1231 1258
1277 1359
1381 1395
1432 1442
1509 1698
1765 1773
1792 1816
1879 1893
1899 1938
2025 2044
2048 2061
2116 2122
2174 2188
2249 2306
2312 2324
2348 2375
2384 2406
2457 2527
2656 2661
2691 2804
2973 3...

output:

531257608

result:

ok single line: '531257608'

Test #55:

score: 1
Accepted
time: 74ms
memory: 30972kb

input:

100000
16 78
91 106
166 210
214 347
362 464
493 518
688 745
750 870
880 895
921 923
949 1028
1124 1244
1259 1263
1266 1309
1314 1320
1393 1407
1424 1460
1519 1634
1669 1700
1756 1813
1831 1854
1937 2014
2058 2101
2127 2136
2335 2381
2458 2538
2871 2878
3111 3169
3171 3263
3359 3487
3563 3591
3607 36...

output:

386241641

result:

ok single line: '386241641'

Test #56:

score: 1
Accepted
time: 73ms
memory: 31076kb

input:

100000
63 176
201 214
252 373
408 559
621 667
678 733
793 829
848 855
892 897
951 991
1014 1018
1226 1233
1241 1249
1260 1321
1368 1438
1440 1446
1455 1468
1529 1575
1581 1582
1630 1652
1745 1760
1869 1953
2041 2045
2114 2238
2323 2373
2429 2482
2485 2499
2533 2595
2695 2781
2904 2924
2950 2992
2993...

output:

719327704

result:

ok single line: '719327704'

Test #57:

score: 1
Accepted
time: 79ms
memory: 31012kb

input:

100000
2 96004
72001 96003
71998 72002
71995 71999
71992 71996
71989 71993
71986 71990
71983 71987
71980 71984
71977 71981
71974 71978
71971 71975
71968 71972
71965 71969
71962 71966
71959 71963
71956 71960
71953 71957
71950 71954
71947 71951
71944 71948
71941 71945
71938 71942
71935 71939
71932 719...

output:

894804508

result:

ok single line: '894804508'

Test #58:

score: 1
Accepted
time: 85ms
memory: 31592kb

input:

100000
316 361
664 908
1014 1030
1103 1166
1185 1233
1289 1345
1509 1604
1767 1887
2174 2242
2247 2470
2505 2640
2703 2812
2851 3064
3274 3589
3704 3814
3894 3971
3999 4140
4151 4184
4336 4456
4585 4622
4651 4680
4733 4766
4779 4832
4960 5098
5241 5363
5365 5562
5665 5988
6030 6090
6138 6264
6352 64...

output:

987435061

result:

ok single line: '987435061'

Test #59:

score: 1
Accepted
time: 43ms
memory: 23340kb

input:

65536
131071 131072
131069 131070
131067 131068
131065 131066
131063 131064
131061 131062
131059 131060
131057 131058
131055 131056
131053 131054
131051 131052
131049 131050
131047 131048
131045 131046
131043 131044
131041 131042
131039 131040
131037 131038
131035 131036
131033 131034
131031 131032
...

output:

65536

result:

ok single line: '65536'

Test #60:

score: 1
Accepted
time: 42ms
memory: 23476kb

input:

65535
131069 131070
131067 131068
131065 131066
131063 131064
131061 131062
131059 131060
131057 131058
131055 131056
131053 131054
131051 131052
131049 131050
131047 131048
131045 131046
131043 131044
131041 131042
131039 131040
131037 131038
131035 131036
131033 131034
131031 131032
131029 131030
...

output:

65535

result:

ok single line: '65535'

Subtask #6:

score: 1
Accepted

Test #61:

score: 1
Accepted
time: 205ms
memory: 73460kb

input:

250000
4 13
21 22
23 24
27 29
30 31
32 33
38 39
42 46
48 51
54 55
57 59
60 64
65 66
69 72
74 81
85 88
91 92
97 98
102 103
107 108
110 111
114 122
125 126
129 132
134 139
140 145
146 149
151 153
154 155
158 162
163 164
168 170
171 173
175 178
180 181
182 183
186 188
190 192
193 194
195 197
202 204
20...

output:

188702306

result:

ok single line: '188702306'

Test #62:

score: 1
Accepted
time: 263ms
memory: 88936kb

input:

250000
1486 2685
2803 6441
7269 7385
7892 7918
10260 11213
11236 14747
15467 16746
16942 16954
18618 20080
20125 21255
21884 25814
26720 29105
29347 29364
31741 32307
32479 33714
37633 38621
39200 39738
39884 40495
42277 42632
44314 45153
45614 46018
46483 46516
48750 49435
51684 51780
51884 53632
5...

output:

17385521

result:

ok single line: '17385521'

Test #63:

score: 1
Accepted
time: 233ms
memory: 70308kb

input:

250000
3 7
11 15
31 41
47 58
65 94
100 126
127 147
158 166
168 171
175 204
206 229
239 241
255 260
265 267
270 274
279 288
293 296
299 303
319 321
325 335
342 358
362 369
378 387
391 402
429 431
444 452
470 476
487 491
508 523
529 532
543 548
556 560
592 593
616 640
650 683
693 698
702 707
732 734
7...

output:

839419492

result:

ok single line: '839419492'

Test #64:

score: 1
Accepted
time: 251ms
memory: 78496kb

input:

250000
32 111
129 164
214 252
265 298
304 336
397 413
415 425
526 601
642 659
678 710
739 801
987 1026
1043 1086
1087 1135
1180 1186
1189 1201
1237 1240
1247 1281
1285 1305
1342 1377
1482 1515
1596 1608
1670 1680
1694 1781
1808 1930
2011 2108
2250 2252
2408 2434
2439 2522
2525 2570
2650 2667
2748 28...

output:

868553974

result:

ok single line: '868553974'

Test #65:

score: 1
Accepted
time: 313ms
memory: 90544kb

input:

250000
18 44
48 78
81 91
99 340
388 431
461 497
503 622
725 807
846 913
918 936
982 1076
1122 1151
1416 1485
1538 1547
1705 1715
1735 1767
1791 1799
1830 1873
2078 2104
2141 2158
2193 2231
2464 2487
2547 2809
2915 2997
3005 3009
3095 3149
3151 3213
3221 3256
3321 3340
3402 3422
3445 3520
3593 3642
3...

output:

413514972

result:

ok single line: '413514972'

Test #66:

score: 1
Accepted
time: 311ms
memory: 89204kb

input:

250000
14 74
89 118
127 159
186 368
514 524
543 572
605 617
626 631
694 707
736 836
906 916
1016 1026
1042 1062
1103 1159
1248 1251
1391 1397
1402 1438
1486 1543
1567 1583
1681 1698
1781 1838
1872 1884
2005 2031
2050 2084
2102 2117
2173 2176
2187 2239
2290 2433
2515 2527
2645 2682
2834 2899
2983 303...

output:

981229241

result:

ok single line: '981229241'

Test #67:

score: 1
Accepted
time: 314ms
memory: 80388kb

input:

250000
23 26
38 53
113 160
196 241
273 312
335 339
375 418
434 444
632 677
777 785
869 924
969 1162
1170 1187
1693 1767
1838 1855
1867 1986
2039 2074
2082 2124
2227 2245
2293 2298
2406 2411
2460 2487
2668 2690
2712 2780
2792 2817
2847 2857
2891 2910
2973 3013
3087 3090
3160 3182
3207 3273
3329 3637
...

output:

653382019

result:

ok single line: '653382019'

Test #68:

score: 1
Accepted
time: 272ms
memory: 72756kb

input:

250000
17 27
76 146
237 247
548 598
656 683
862 897
933 989
992 1026
1103 1111
1139 1163
1224 1247
1263 1312
1370 1419
1520 1528
1566 1628
1652 1671
1723 1824
1910 1945
1993 2042
2147 2237
2240 2256
2276 2284
2308 2407
2486 2536
2680 2691
2866 2969
3035 3037
3058 3074
3091 3132
3162 3235
3254 3342
3...

output:

170816133

result:

ok single line: '170816133'

Test #69:

score: 1
Accepted
time: 226ms
memory: 72760kb

input:

250000
5 499992
10 499989
15 499986
22 499985
29 499984
37 499982
50 499980
55 499977
58 499976
61 499974
67 499972
74 499967
80 499965
88 499964
92 499963
98 499962
106 499960
111 499958
115 499957
122 499954
131 499953
138 499952
141 499950
146 499949
151 499946
157 499944
163 499943
174 499942
18...

output:

839963611

result:

ok single line: '839963611'

Test #70:

score: 1
Accepted
time: 212ms
memory: 72860kb

input:

250000
16 499990
18 499989
24 499986
28 499977
29 499975
35 499963
36 499954
37 499952
39 499951
41 499943
47 499939
57 499931
66 499929
68 499926
70 499924
73 499910
95 499907
98 499902
111 499893
115 499882
135 499867
136 499833
139 499832
149 499827
158 499818
170 499815
173 499803
176 499793
184...

output:

183577200

result:

ok single line: '183577200'

Test #71:

score: 1
Accepted
time: 260ms
memory: 74856kb

input:

250000
118 129
190 458
506 520
596 682
744 989
1009 1133
1148 1259
1279 1402
1503 1621
1839 1845
1877 2013
2021 2068
2195 2304
2320 2445
2462 2474
2689 2717
2747 2884
2968 3023
3129 3437
3592 3644
3843 3863
3895 3928
4020 4021
4200 4492
4504 4602
4618 4762
4834 4868
5226 5934
6076 6129
6393 6418
642...

output:

672497595

result:

ok single line: '672497595'

Test #72:

score: 1
Accepted
time: 95ms
memory: 43628kb

input:

131071
262141 262142
262139 262140
262137 262138
262135 262136
262133 262134
262131 262132
262129 262130
262127 262128
262125 262126
262123 262124
262121 262122
262119 262120
262117 262118
262115 262116
262113 262114
262111 262112
262109 262110
262107 262108
262105 262106
262103 262104
262101 262102...

output:

131071

result:

ok single line: '131071'

Test #73:

score: 1
Accepted
time: 323ms
memory: 74052kb

input:

250000
8 41
68 100
132 161
168 221
226 260
265 271
292 321
343 395
406 418
426 428
495 498
516 522
534 556
580 589
597 599
650 670
690 703
704 737
748 788
798 831
832 880
893 897
901 912
935 936
940 949
966 975
985 1021
1035 1075
1102 1128
1139 1159
1210 1292
1317 1377
1414 1419
1461 1501
1515 1518
...

output:

389958504

result:

ok single line: '389958504'

Test #74:

score: 1
Accepted
time: 252ms
memory: 76208kb

input:

250000
445 1713
2353 2511
2941 3066
3555 3659
4089 6321
6581 8021
8145 8775
9821 9959
10177 11180
11252 11866
12180 15172
16292 19063
20384 22743
22861 25735
25868 26362
26668 26899
27128 27233
28271 29959
31436 31714
35949 36108
37613 38919
39578 40468
40859 41242
43324 43340
44381 44575
49024 4953...

output:

315323457

result:

ok single line: '315323457'

Test #75:

score: 1
Accepted
time: 175ms
memory: 65404kb

input:

250000
52 63
104 120
311 327
343 356
390 476
521 584
597 602
638 677
707 774
789 909
958 965
1095 1130
1199 1204
1248 1249
1256 1290
1511 1540
1554 1585
1614 1630
1706 1729
1812 1835
1867 1902
1945 1980
2012 2136
2172 2174
2232 2263
2300 2310
2376 2388
2467 2486
2501 2650
2691 2730
2733 2829
2859 28...

output:

587413658

result:

ok single line: '587413658'

Test #76:

score: 1
Accepted
time: 219ms
memory: 77876kb

input:

250000
50 98
134 153
183 220
350 450
464 684
733 778
800 823
884 983
1031 1103
1140 1160
1303 1373
1431 1449
1499 1662
1667 1822
1842 1856
1913 1970
2033 2056
2060 2158
2232 2259
2338 2363
2413 2467
2502 2504
2585 2615
2637 2639
2666 2686
2703 2709
2732 2823
2865 2879
2899 2939
2962 2977
3004 3160
3...

output:

284890192

result:

ok single line: '284890192'

Test #77:

score: 1
Accepted
time: 222ms
memory: 72800kb

input:

250000
31 80
125 255
285 368
433 510
557 563
566 629
634 674
807 863
906 977
1024 1081
1084 1090
1096 1195
1232 1285
1344 1381
1429 1543
1669 1763
1805 1901
1957 1974
1982 2057
2091 2095
2099 2144
2146 2255
2344 2354
2417 2494
2497 2501
2514 2528
2561 2626
2633 2722
2737 2800
2843 2846
2848 2878
292...

output:

79028581

result:

ok single line: '79028581'

Test #78:

score: 1
Accepted
time: 232ms
memory: 72712kb

input:

250000
4 65
136 172
229 239
303 402
423 426
428 466
653 680
699 744
909 956
1017 1085
1157 1272
1297 1303
1305 1396
1453 1483
1527 1532
1540 1637
1642 1647
1715 1746
1778 1823
1831 1891
1898 1925
1953 2000
2081 2094
2138 2173
2196 2212
2231 2482
2673 2733
2750 2821
2824 2956
2984 3018
3146 3151
3172...

output:

310388374

result:

ok single line: '310388374'

Test #79:

score: 1
Accepted
time: 217ms
memory: 72904kb

input:

250000
140 147
214 219
290 301
334 351
368 394
665 752
768 885
954 980
1002 1028
1165 1232
1311 1329
1383 1388
1401 1415
1579 1596
1598 1678
1758 1859
1872 1901
1903 1919
1941 1965
2020 2047
2078 2096
2197 2254
2313 2370
2401 2411
2502 2505
2510 2590
2594 2657
2679 2769
2790 2821
2831 2942
2957 3073...

output:

393045114

result:

ok single line: '393045114'

Test #80:

score: 1
Accepted
time: 247ms
memory: 72696kb

input:

250000
2 240004
180001 240003
179998 180002
179995 179999
179992 179996
179989 179993
179986 179990
179983 179987
179980 179984
179977 179981
179974 179978
179971 179975
179968 179972
179965 179969
179962 179966
179959 179963
179956 179960
179953 179957
179950 179954
179947 179951
179944 179948
1799...

output:

107803271

result:

ok single line: '107803271'

Test #81:

score: 1
Accepted
time: 269ms
memory: 80420kb

input:

250000
60 125
132 140
150 166
186 206
318 333
344 362
423 510
561 604
682 707
792 823
973 1081
1122 1214
1242 1273
1296 1373
1377 1384
1397 1454
1487 1542
1591 1623
1656 1710
1811 1901
1944 1959
1979 2231
2316 2318
2362 2403
2485 2652
2718 2729
2743 2806
2879 3041
3121 3173
3241 3266
3273 3335
3348 ...

output:

266485835

result:

ok single line: '266485835'

Test #82:

score: 1
Accepted
time: 252ms
memory: 74512kb

input:

250000
178 209
213 291
354 504
605 686
972 1013
1222 1264
1511 1558
1563 1791
1948 2004
2295 2301
2356 2445
2684 2853
2860 2896
2909 2936
3004 3023
3171 3208
3249 3288
3358 3398
3457 3527
3599 3629
3720 3773
3989 4049
4076 4110
4125 4155
4166 4181
4243 4271
4363 4411
4637 4730
4877 4897
5123 5192
53...

output:

572319096

result:

ok single line: '572319096'

Test #83:

score: 1
Accepted
time: 263ms
memory: 73748kb

input:

250000
22 251
369 422
534 600
662 663
735 1015
1016 1152
1285 1388
1496 1548
1692 1735
1781 1808
1867 1892
1896 1898
1999 2101
2112 2145
2320 2373
2374 2530
2664 2726
2742 2857
3079 3113
3238 3249
3265 3330
3364 3451
3501 3657
3760 3765
3932 3972
4148 4187
4498 4507
4537 4616
4678 4723
4758 5057
507...

output:

832908714

result:

ok single line: '832908714'

Test #84:

score: 1
Accepted
time: 223ms
memory: 75328kb

input:

250000
1 500000
499987 499989
499977 499979
499959 499961
499933 499935
499919 499921
499913 499915
499903 499905
499877 499879
499863 499865
499845 499847
499835 499837
499821 499823
499803 499805
499789 499791
499767 499769
499757 499759
499731 499733
499717 499719
499711 499713
499689 499691
4996...

output:

491475895

result:

ok single line: '491475895'

Test #85:

score: 1
Accepted
time: 84ms
memory: 43632kb

input:

131072
262143 262144
262141 262142
262139 262140
262137 262138
262135 262136
262133 262134
262131 262132
262129 262130
262127 262128
262125 262126
262123 262124
262121 262122
262119 262120
262117 262118
262115 262116
262113 262114
262111 262112
262109 262110
262107 262108
262105 262106
262103 262104...

output:

131072

result:

ok single line: '131072'

Subtask #7:

score: 1
Accepted

Test #86:

score: 1
Accepted
time: 341ms
memory: 129584kb

input:

400000
1 2
4 5
7 9
11 13
15 16
17 18
20 21
23 25
26 29
30 31
33 35
37 40
41 42
44 46
48 49
50 51
53 55
56 57
59 63
65 68
70 71
72 75
76 77
79 85
87 89
91 93
95 98
102 104
105 108
113 115
117 119
121 123
124 125
126 127
129 131
133 135
137 138
139 141
143 145
146 147
149 151
153 154
158 160
161 162
1...

output:

156680922

result:

ok single line: '156680922'

Test #87:

score: 1
Accepted
time: 452ms
memory: 148272kb

input:

400000
16 42
51 77
88 97
105 156
175 187
189 267
285 294
308 311
321 347
376 378
433 457
459 461
475 490
499 522
535 561
565 586
610 620
637 658
684 707
750 780
799 827
832 840
864 871
878 903
933 958
995 996
1013 1032
1041 1085
1117 1123
1134 1151
1160 1169
1236 1250
1289 1301
1314 1321
1351 1358
1...

output:

822523058

result:

ok single line: '822523058'

Test #88:

score: 1
Accepted
time: 421ms
memory: 127756kb

input:

400000
192 263
287 303
360 433
527 767
783 850
902 1030
1158 1162
1166 1232
1284 1287
1497 1568
1732 1748
1798 1809
1884 1891
1903 2038
2172 2178
2297 2354
2367 2372
2676 2804
2847 3043
3294 3396
3470 3501
3532 3538
3987 4014
4073 4140
4265 4410
4445 4490
4493 4505
4548 4622
4778 4794
4803 4883
4900...

output:

246643509

result:

ok single line: '246643509'

Test #89:

score: 1
Accepted
time: 535ms
memory: 155964kb

input:

400000
165 183
185 202
330 353
376 396
516 621
704 748
788 850
870 992
1062 1069
1125 1174
1309 1381
1440 1505
1564 1663
2059 2098
2267 2318
2380 2432
2447 2528
2647 2788
2808 3102
3161 3197
3217 3296
3464 3573
3584 3729
3748 3775
3836 3914
3928 3963
3968 3988
4085 4098
4106 4190
4282 4357
4393 4408...

output:

813973491

result:

ok single line: '813973491'

Test #90:

score: 1
Accepted
time: 588ms
memory: 153944kb

input:

400000
104 156
164 204
400 446
600 710
750 782
919 1006
1008 1197
1313 1327
1379 1455
1597 1691
1697 1778
1936 1993
2054 2165
2381 2390
2392 2403
2416 2564
2709 2826
2958 3049
3091 3282
3325 3738
3838 3938
3963 4070
4085 4210
4420 4581
4618 4663
4721 4966
5041 5097
5151 5267
5290 5467
5473 5488
5557...

output:

696519468

result:

ok single line: '696519468'

Test #91:

score: 1
Accepted
time: 567ms
memory: 138684kb

input:

400000
36 162
175 190
219 244
251 293
395 441
453 500
523 562
572 598
625 655
678 713
765 768
799 852
860 897
902 958
983 1017
1020 1106
1259 1305
1322 1448
1465 1490
1592 1627
1644 1656
1734 1737
1744 1761
1809 1936
1945 1959
1972 1986
2043 2068
2098 2112
2251 2286
2315 2321
2344 2357
2412 2448
245...

output:

749944734

result:

ok single line: '749944734'

Test #92:

score: 1
Accepted
time: 488ms
memory: 127040kb

input:

400000
65 161
163 172
186 252
292 344
386 405
424 449
462 515
544 559
618 672
698 819
823 843
869 888
949 957
968 978
1015 1040
1109 1120
1133 1161
1200 1250
1256 1259
1278 1368
1422 1506
1518 1520
1588 1596
1650 1664
1673 1685
1777 1799
1837 1841
1896 2014
2054 2064
2097 2123
2139 2144
2155 2197
22...

output:

404830004

result:

ok single line: '404830004'

Test #93:

score: 1
Accepted
time: 374ms
memory: 126844kb

input:

400000
17 799992
20 799988
23 799987
27 799983
44 799982
46 799978
47 799974
48 799972
53 799971
59 799970
63 799963
65 799959
67 799953
69 799951
72 799948
80 799942
81 799931
83 799928
91 799926
92 799923
98 799920
100 799914
107 799909
125 799908
126 799900
137 799897
139 799885
141 799882
142 79...

output:

530051583

result:

ok single line: '530051583'

Test #94:

score: 1
Accepted
time: 477ms
memory: 130760kb

input:

400000
471 666
987 1022
1095 1097
1300 1307
1485 2361
2570 2815
2959 2965
3109 3202
3204 3302
3541 3592
3954 4028
4214 4365
4582 4940
4971 5053
5522 5675
5898 5992
6052 6318
6379 6503
6716 7652
7713 8177
8598 8628
8862 8911
9316 9606
9656 9796
9982 10015
10233 10263
10351 10458
10579 10607
10686 109...

output:

881661915

result:

ok single line: '881661915'

Test #95:

score: 1
Accepted
time: 210ms
memory: 84188kb

input:

262143
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248
524245 524246...

output:

262143

result:

ok single line: '262143'

Test #96:

score: 1
Accepted
time: 593ms
memory: 129260kb

input:

400000
17 18
40 75
107 129
183 191
249 367
373 401
501 515
531 609
776 841
865 955
970 1029
1060 1091
1128 1148
1157 1187
1300 1329
1396 1423
1483 1577
1592 1626
1650 1666
1698 1703
1741 1774
1851 1923
1935 2061
2136 2140
2186 2188
2194 2213
2221 2257
2262 2323
2419 2475
2505 2531
2589 2633
2647 273...

output:

303566769

result:

ok single line: '303566769'

Test #97:

score: 1
Accepted
time: 460ms
memory: 132452kb

input:

400000
1509 5918
7282 8686
9293 9401
10735 12029
13062 22290
22362 22998
23482 23959
31624 40399
40879 41531
41858 44178
44866 45114
45679 48823
50325 50488
50894 53678
55250 56211
57767 62390
62626 63437
64612 70822
71846 71940
72270 73335
73340 73655
75620 76259
76297 78496
79886 82544
82788 82902...

output:

228188290

result:

ok single line: '228188290'

Test #98:

score: 1
Accepted
time: 318ms
memory: 115064kb

input:

400000
3 19
41 47
56 70
144 151
198 237
247 250
266 285
296 307
320 330
345 369
371 378
398 426
437 447
483 494
514 522
531 556
599 614
635 669
700 732
758 783
800 880
914 919
926 944
973 1019
1048 1065
1069 1075
1094 1131
1135 1144
1161 1170
1179 1183
1212 1224
1244 1252
1265 1276
1283 1291
1307 13...

output:

390195235

result:

ok single line: '390195235'

Test #99:

score: 1
Accepted
time: 395ms
memory: 135640kb

input:

400000
100 184
209 239
306 331
439 493
520 802
985 1063
1144 1226
1312 1329
1333 1635
1671 1777
1805 2014
2117 2269
2597 2653
2678 2806
2931 2936
3081 3169
3339 3410
3467 3490
3592 3886
4009 4045
4115 4203
4320 4357
4468 4491
4505 4518
4555 4806
4843 4865
4933 5146
5189 5253
5267 5272
5358 5416
5456...

output:

723278460

result:

ok single line: '723278460'

Test #100:

score: 1
Accepted
time: 412ms
memory: 127548kb

input:

400000
58 81
264 372
408 420
519 558
569 609
865 953
961 1086
1212 1250
1355 1443
1568 1591
1606 1618
1857 1966
1977 2318
2600 2624
2725 2744
2786 2835
2863 2937
2997 3049
3054 3154
3176 3353
3367 3490
3538 3839
4075 4147
4200 4345
4597 4634
4730 4743
4889 4898
4971 4976
4984 5040
5086 5151
5181 520...

output:

132278008

result:

ok single line: '132278008'

Test #101:

score: 1
Accepted
time: 389ms
memory: 126940kb

input:

400000
23 40
62 63
73 83
111 226
309 393
429 444
456 509
538 580
588 643
669 678
690 711
763 797
817 825
858 874
895 953
954 967
1018 1187
1246 1298
1303 1305
1328 1361
1373 1385
1412 1459
1471 1490
1494 1507
1577 1889
1958 2042
2057 2098
2100 2124
2130 2219
2224 2254
2258 2271
2335 2367
2403 2436
2...

output:

515866482

result:

ok single line: '515866482'

Test #102:

score: 1
Accepted
time: 429ms
memory: 127044kb

input:

400000
48 73
74 140
145 197
373 405
436 474
604 608
618 656
685 691
715 769
817 838
1003 1028
1188 1274
1337 1346
1399 1413
1451 1533
1561 1566
1597 1620
1636 1657
1678 1721
1765 1818
1823 1830
1888 1926
1940 2041
2127 2156
2179 2234
2311 2399
2412 2420
2432 2459
2462 2563
2565 2570
2592 2638
2643 2...

output:

554695925

result:

ok single line: '554695925'

Test #103:

score: 1
Accepted
time: 492ms
memory: 138656kb

input:

400000
245 424
538 640
846 864
1455 1523
1648 1763
1817 2057
2906 3079
3336 3442
3618 4010
4070 4083
4324 4666
4991 5080
5292 5322
5351 5368
5577 5695
5731 5951
6181 6246
6423 6532
6572 6897
7040 7322
7479 7628
7759 7911
8251 8334
8435 8778
8867 8917
9275 9564
9633 10155
10236 10295
10542 10565
1081...

output:

757694958

result:

ok single line: '757694958'

Test #104:

score: 1
Accepted
time: 456ms
memory: 128732kb

input:

400000
20 31
161 423
1051 1066
1167 1531
1572 1752
1785 1845
1907 1925
1945 2115
2246 2394
2402 2912
2974 3174
3315 3391
3441 3517
4231 4624
5188 5338
5635 5760
6323 6384
6428 6484
6532 6637
6910 7029
7178 7211
7284 7306
7379 7484
7684 7743
7813 8097
8111 8458
8685 8708
8846 9149
9210 9252
9297 9530...

output:

33578735

result:

ok single line: '33578735'

Test #105:

score: 1
Accepted
time: 222ms
memory: 92264kb

input:

262144
524287 524288
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248...

output:

262144

result:

ok single line: '262144'

Subtask #8:

score: 1
Accepted

Test #106:

score: 1
Accepted
time: 388ms
memory: 144284kb

input:

450000
1 5
7 9
11 15
22 24
26 28
30 34
36 37
39 41
43 45
46 48
49 50
53 55
56 57
58 60
62 64
67 69
71 76
77 80
81 84
86 89
95 97
100 101
105 107
109 111
113 116
117 118
120 121
125 126
129 133
136 137
139 141
144 146
149 150
156 157
159 162
165 168
171 174
176 177
180 183
184 187
191 194
195 197
199...

output:

451957895

result:

ok single line: '451957895'

Test #107:

score: 1
Accepted
time: 513ms
memory: 170184kb

input:

450000
10 69
172 200
365 379
411 420
446 729
812 856
882 925
992 1008
1014 1023
1043 1101
1389 1397
1399 1494
1709 1887
1906 1925
1937 1979
1993 2649
2740 2754
2763 3169
3210 3225
3242 3480
3532 3539
3614 3793
3808 3905
3937 3959
4050 4198
4324 4374
4405 4447
4449 4466
4522 4568
4570 4669
4712 4768
...

output:

989396320

result:

ok single line: '989396320'

Test #108:

score: 1
Accepted
time: 466ms
memory: 141264kb

input:

450000
2 23
52 68
82 97
118 128
132 137
149 207
221 223
248 270
283 287
295 307
323 340
359 360
368 374
435 462
474 487
500 528
537 539
541 546
560 570
572 600
656 664
700 711
744 753
755 757
763 795
811 814
820 828
842 856
866 881
886 894
909 959
972 1017
1018 1042
1052 1064
1089 1092
1103 1113
112...

output:

317368158

result:

ok single line: '317368158'

Test #109:

score: 1
Accepted
time: 614ms
memory: 174596kb

input:

450000
20 23
45 66
68 139
207 233
265 267
331 357
378 397
422 487
562 678
696 710
786 803
826 869
943 978
1034 1065
1100 1150
1156 1160
1208 1240
1344 1350
1424 1488
1511 1514
1518 1625
1690 1720
1800 1831
1849 1871
1892 1952
1979 2052
2060 2170
2203 2254
2330 2333
2338 2346
2357 2397
2420 2431
2465...

output:

993715063

result:

ok single line: '993715063'

Test #110:

score: 1
Accepted
time: 623ms
memory: 170384kb

input:

450000
29 31
36 45
66 137
151 158
174 200
209 215
296 321
338 415
438 475
482 534
543 549
570 589
594 605
644 656
687 758
770 783
800 816
847 912
955 997
1009 1013
1015 1066
1138 1176
1228 1237
1251 1256
1264 1275
1344 1349
1371 1373
1407 1431
1434 1459
1461 1533
1584 1632
1642 1660
1670 1679
1684 1...

output:

850153953

result:

ok single line: '850153953'

Test #111:

score: 1
Accepted
time: 632ms
memory: 157040kb

input:

450000
12 75
225 232
274 596
607 762
1013 1038
1110 1122
1130 1189
1260 1431
1504 1512
1695 1741
1799 1855
1966 2023
2144 2234
2285 2303
2337 2355
2426 2447
2589 2922
3081 3389
3545 3591
3623 3684
3762 3920
4049 4093
4152 4211
4298 4317
4343 4363
4532 4926
5073 5093
5189 5334
5380 5429
5437 5727
579...

output:

502953225

result:

ok single line: '502953225'

Test #112:

score: 1
Accepted
time: 541ms
memory: 143164kb

input:

450000
110 213
276 317
336 338
877 896
1020 1068
1186 1214
1417 1492
1502 1512
1600 1695
1698 1931
2006 2008
2054 2117
2206 2273
2292 2303
2305 2331
2338 2431
2494 2557
2688 2917
3088 3114
3188 3225
3372 3452
3573 3581
3681 3734
3773 4015
4099 4123
4298 4342
4502 4545
4595 4631
4665 4895
4950 5086
5...

output:

444243257

result:

ok single line: '444243257'

Test #113:

score: 1
Accepted
time: 443ms
memory: 144832kb

input:

450000
13 899995
21 899989
23 899984
30 899981
41 899979
59 899972
72 899968
74 899959
96 899956
101 899954
103 899928
110 899910
112 899906
114 899902
138 899899
164 899893
170 899889
180 899883
184 899879
198 899862
200 899861
213 899845
227 899839
234 899831
254 899823
263 899819
278 899812
296 8...

output:

429922511

result:

ok single line: '429922511'

Test #114:

score: 1
Accepted
time: 504ms
memory: 147012kb

input:

449980
67 149
322 626
745 1024
1591 1630
1660 1886
2249 2318
2502 2649
3318 3792
3998 4396
4428 4459
4572 4817
4821 4850
4877 5707
5884 5912
6074 6076
6357 6736
6814 6824
6839 6970
7073 7250
7709 7808
7978 8233
8253 8508
8569 8637
8678 8891
9014 9384
9495 9754
9981 10565
10644 10873
10897 11439
1175...

output:

913967268

result:

ok single line: '913967268'

Test #115:

score: 1
Accepted
time: 228ms
memory: 84040kb

input:

262143
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248
524245 524246...

output:

262143

result:

ok single line: '262143'

Test #116:

score: 1
Accepted
time: 660ms
memory: 143264kb

input:

450000
51 72
100 161
164 173
194 210
215 234
238 289
311 436
438 458
470 480
491 511
532 536
539 548
568 602
613 630
649 650
655 665
666 679
700 738
745 778
788 796
819 862
869 876
882 903
915 922
936 950
981 986
1014 1021
1034 1038
1062 1082
1119 1136
1145 1158
1166 1176
1180 1191
1201 1218
1229 12...

output:

51145952

result:

ok single line: '51145952'

Test #117:

score: 1
Accepted
time: 529ms
memory: 148884kb

input:

450000
99 987
1413 2039
2332 2851
3189 3554
4031 4342
4377 4410
5161 6117
6273 6281
6796 7079
7119 7145
7759 8036
8047 8998
9901 10775
11807 12373
12540 14346
14681 14780
15420 15485
17220 17419
17472 18297
18493 18814
18845 19393
19468 19863
20145 20154
20387 20826
21343 21568
22177 22451
22776 230...

output:

172876029

result:

ok single line: '172876029'

Test #118:

score: 1
Accepted
time: 356ms
memory: 128960kb

input:

450000
25 28
54 75
93 102
118 133
142 175
214 244
255 277
287 313
325 353
360 373
394 399
428 447
485 510
514 524
569 578
628 647
658 669
674 685
699 704
715 739
743 768
776 779
783 793
822 824
839 848
888 905
911 921
938 943
947 975
985 995
1009 1032
1035 1059
1063 1077
1079 1085
1102 1111
1124 117...

output:

799307489

result:

ok single line: '799307489'

Test #119:

score: 1
Accepted
time: 458ms
memory: 152052kb

input:

450000
46 55
57 79
158 279
285 291
294 300
330 415
436 462
473 477
508 579
598 659
814 838
882 940
1032 1046
1065 1122
1134 1216
1265 1313
1346 1352
1404 1422
1460 1544
1550 1634
1754 1845
1851 1895
1911 1931
2013 2078
2096 2216
2224 2294
2297 2304
2327 2332
2367 2414
2454 2489
2493 2537
2611 2675
2...

output:

49123409

result:

ok single line: '49123409'

Test #120:

score: 1
Accepted
time: 473ms
memory: 141892kb

input:

450000
14 75
183 191
210 225
285 315
348 351
369 386
391 403
422 424
488 509
513 536
571 608
617 671
747 754
797 807
861 864
898 903
940 943
994 1000
1029 1036
1049 1065
1069 1076
1169 1203
1244 1252
1288 1297
1403 1471
1477 1513
1564 1648
1707 1735
1773 1783
1887 1938
1976 2023
2044 2053
2057 2194
...

output:

370515600

result:

ok single line: '370515600'

Test #121:

score: 1
Accepted
time: 462ms
memory: 143340kb

input:

450000
201 247
280 285
318 352
360 392
405 454
554 610
624 701
747 773
806 948
949 980
993 1127
1248 1260
1370 1388
1406 1489
1522 1591
1604 1637
1641 1671
1708 1754
1815 1824
1906 2057
2191 2227
2290 2495
2516 2577
2764 2809
2811 2885
2955 3055
3140 3158
3233 3251
3283 3320
3392 3473
3584 3656
3712...

output:

213881417

result:

ok single line: '213881417'

Test #122:

score: 1
Accepted
time: 506ms
memory: 143240kb

input:

450000
41 55
104 159
180 217
379 396
712 740
788 834
872 885
909 977
1001 1158
1211 1241
1262 1285
1326 1507
1528 1537
1855 2019
2147 2173
2181 2255
2532 2540
2552 2579
2634 2636
2666 2675
2723 2990
3060 3067
3128 3148
3227 3239
3241 3247
3327 3355
3436 3446
3692 3770
3848 3893
3901 3943
3947 4020
4...

output:

517295480

result:

ok single line: '517295480'

Test #123:

score: 1
Accepted
time: 604ms
memory: 159016kb

input:

450000
85 628
775 1110
1389 1966
2213 2633
2662 3569
3762 4198
4710 6213
7063 7448
7616 7841
8123 8250
8648 8723
9053 9337
10121 11495
12270 12780
13593 13704
13712 14453
14917 14953
15053 15058
15261 15300
15305 15315
15936 16201
16370 16691
17328 17711
19072 19507
19783 19880
20780 20858
20939 220...

output:

953517513

result:

ok single line: '953517513'

Test #124:

score: 1
Accepted
time: 561ms
memory: 144168kb

input:

450000
59 86
164 181
200 300
468 567
678 718
849 871
891 1042
1191 1203
1270 1274
1326 1389
1424 1427
1585 1589
1621 1658
1749 1795
1815 1890
1952 1975
2020 2093
2101 2139
2198 2222
2225 2377
2396 2592
2596 2617
2638 2766
2855 2990
3004 3014
3019 3139
3305 3352
3375 3446
3575 3649
3759 3824
3859 387...

output:

751231259

result:

ok single line: '751231259'

Test #125:

score: 1
Accepted
time: 234ms
memory: 92236kb

input:

262144
524287 524288
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248...

output:

262144

result:

ok single line: '262144'

Subtask #9:

score: 1
Accepted

Test #126:

score: 1
Accepted
time: 468ms
memory: 173036kb

input:

500000
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
1...

output:

500000

result:

ok single line: '500000'

Test #127:

score: 1
Accepted
time: 448ms
memory: 173340kb

input:

500000
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
1...

output:

500000

result:

ok single line: '500000'

Test #128:

score: 1
Accepted
time: 557ms
memory: 169180kb

input:

500000
499999 500002
500001 500004
499997 500000
500003 500006
499995 499998
500005 500008
499993 499996
500007 500010
499991 499994
500009 500012
499989 499992
500011 500014
499987 499990
500013 500016
499985 499988
500015 500018
499983 499986
500017 500020
499981 499984
500019 500022
499979 499982...

output:

343697427

result:

ok single line: '343697427'

Test #129:

score: 1
Accepted
time: 643ms
memory: 159260kb

input:

500000
1 1000000
500000 999999
499999 999998
499998 999997
499997 999996
499996 999995
499995 999994
499994 999993
499993 999992
499992 999991
499991 999990
499990 999989
499989 999988
499988 999987
499987 999986
499986 999985
499985 999984
499984 999983
499983 999982
499982 999981
499981 999980
499...

output:

389417116

result:

ok single line: '389417116'

Test #130:

score: 1
Accepted
time: 581ms
memory: 189300kb

input:

500000
28 64
120 215
301 384
516 606
758 857
865 884
930 959
1006 1268
1687 1697
1799 1877
1964 1987
1992 2055
2318 2347
2641 2698
2765 2826
2851 2859
2933 3256
3328 3514
3639 3834
3947 4077
4120 4215
4301 4442
4506 4904
5002 5116
5281 5422
5593 5613
5639 5770
5823 5921
5926 6359
6405 6435
6441 6610...

output:

718237240

result:

ok single line: '718237240'

Test #131:

score: 1
Accepted
time: 549ms
memory: 157020kb

input:

500000
4 27
47 84
110 155
177 208
218 253
266 319
325 340
371 397
442 448
457 465
533 554
588 590
593 603
648 687
691 693
722 754
781 793
838 895
903 925
951 992
1019 1025
1027 1030
1032 1044
1054 1099
1140 1148
1152 1183
1245 1252
1255 1266
1282 1285
1290 1305
1315 1359
1382 1398
1404 1437
1462 146...

output:

998949769

result:

ok single line: '998949769'

Test #132:

score: 1
Accepted
time: 681ms
memory: 193100kb

input:

500000
6 30
34 73
158 175
306 372
477 485
523 535
545 620
673 679
687 769
920 971
987 1034
1124 1126
1200 1220
1257 1266
1324 1383
1401 1405
1423 1437
1508 1511
1533 1570
1596 1637
1740 1796
1811 1820
1921 1943
1990 1993
2026 2145
2217 2333
2397 2414
2599 2624
2674 2735
2751 2821
2847 2886
2926 2935...

output:

856698701

result:

ok single line: '856698701'

Test #133:

score: 1
Accepted
time: 719ms
memory: 190640kb

input:

500000
7 21
35 36
54 123
132 182
199 263
445 493
526 541
654 662
683 700
738 748
753 761
833 861
873 930
966 971
1009 1014
1053 1062
1136 1168
1210 1221
1232 1314
1339 1397
1441 1501
1516 1518
1551 1574
1724 1781
1797 1860
1872 1905
1974 1994
2147 2241
2271 2300
2326 2369
2389 2410
2449 2522
2588 25...

output:

172345000

result:

ok single line: '172345000'

Test #134:

score: 1
Accepted
time: 717ms
memory: 173252kb

input:

500000
36 45
79 84
105 169
185 309
316 328
331 370
377 394
414 554
573 578
612 614
660 679
705 765
867 967
1113 1198
1323 1413
1454 1495
1619 1741
1911 1984
2003 2237
2302 2309
2431 2456
2473 2541
2577 2637
2690 2760
2797 2878
2992 2997
3079 3166
3232 3248
3250 3265
3282 3316
3521 3558
3561 3633
379...

output:

160101730

result:

ok single line: '160101730'

Test #135:

score: 1
Accepted
time: 641ms
memory: 158148kb

input:

500000
48 52
86 143
168 194
274 363
405 466
643 650
712 744
746 760
775 787
898 920
994 1079
1102 1154
1292 1392
1439 1552
1585 1600
1604 1607
1680 1719
1754 1786
1807 1901
1913 1948
1983 2261
2318 2363
2382 2394
2396 2402
2446 2496
2515 2542
2560 2629
2794 2859
2929 2977
3017 3052
3104 3228
3236 32...

output:

972754794

result:

ok single line: '972754794'

Test #136:

score: 1
Accepted
time: 456ms
memory: 158764kb

input:

500000
15 999998
16 999997
17 999994
23 999993
26 999982
29 999974
30 999958
36 999956
44 999950
48 999947
49 999946
51 999943
56 999938
57 999934
61 999927
63 999922
66 999918
74 999915
76 999913
79 999911
81 999910
85 999903
91 999891
94 999883
100 999879
102 999876
103 999875
106 999856
107 99984...

output:

711706916

result:

ok single line: '711706916'

Test #137:

score: 1
Accepted
time: 585ms
memory: 162668kb

input:

500000
244 267
603 801
822 917
1180 1713
1738 1827
1841 2132
2158 2209
2235 2299
2345 2402
2411 2666
2834 2950
3022 3128
3560 3590
3807 4078
4507 4524
4562 4606
4916 5001
5025 5189
5414 5582
6319 6403
6445 6453
6867 6932
7242 7364
7376 7484
7619 7691
8182 8417
8466 9044
9089 9170
9334 9428
9614 9860...

output:

969288973

result:

ok single line: '969288973'

Test #138:

score: 1
Accepted
time: 218ms
memory: 84100kb

input:

262143
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248
524245 524246...

output:

262143

result:

ok single line: '262143'

Subtask #10:

score: 1
Accepted

Test #139:

score: 1
Accepted
time: 802ms
memory: 162140kb

input:

500000
80 94
171 186
270 342
402 426
599 692
729 835
873 977
993 1010
1095 1100
1109 1165
1186 1240
1349 1393
1470 1493
1497 1503
1541 1553
1582 1613
1734 1745
1815 1869
1890 1959
2025 2032
2094 2129
2139 2183
2200 2240
2243 2358
2397 2426
2445 2470
2500 2504
2515 2537
2567 2585
2590 2619
2628 2647
...

output:

164834289

result:

ok single line: '164834289'

Test #140:

score: 1
Accepted
time: 599ms
memory: 164564kb

input:

500000
183 264
622 658
724 968
1325 1397
1528 1558
1768 1889
1990 2032
2062 2067
2365 2805
2842 2969
2988 3140
3174 3316
3362 3815
4109 4122
4166 4751
4866 4930
4952 5137
5673 5883
5910 6396
6420 6632
6679 6752
6886 7028
7090 7632
7810 8111
8147 8242
8254 8286
8606 9456
9720 9881
9928 10355
10531 10...

output:

595176482

result:

ok single line: '595176482'

Test #141:

score: 1
Accepted
time: 446ms
memory: 143640kb

input:

500000
2 999999
3 999998
4 999997
5 999996
6 999995
7 999994
8 999993
9 999992
10 999991
11 999990
12 999989
13 999988
14 999987
15 999986
16 999985
17 999984
18 999983
19 999982
20 999981
21 999980
22 999979
23 999978
24 999977
25 999976
26 999975
27 999974
28 999973
29 999972
30 999971
31 999970
3...

output:

979024635

result:

ok single line: '979024635'

Test #142:

score: 1
Accepted
time: 530ms
memory: 168272kb

input:

500000
81 124
154 176
239 299
312 317
327 333
355 401
611 664
718 739
756 777
895 935
978 1017
1042 1120
1129 1229
1231 1296
1415 1458
1472 1531
1564 1587
1661 1736
1796 1827
1841 1852
1995 2012
2077 2098
2188 2194
2251 2285
2288 2342
2372 2394
2405 2428
2441 2479
2575 2669
2716 2755
2788 2845
2893 ...

output:

202559017

result:

ok single line: '202559017'

Test #143:

score: 1
Accepted
time: 540ms
memory: 158296kb

input:

500000
104 134
147 224
315 446
451 519
533 547
563 597
671 915
987 1031
1058 1068
1074 1120
1128 1151
1175 1177
1395 1407
1442 1454
1461 1619
1627 1663
1728 1787
1820 1869
1918 1966
1968 2098
2126 2212
2231 2287
2326 2361
2417 2456
2475 2479
2490 2497
2519 2541
2627 2645
2692 2812
2849 2903
2945 298...

output:

269616021

result:

ok single line: '269616021'

Test #144:

score: 1
Accepted
time: 516ms
memory: 158160kb

input:

500000
13 22
58 81
100 202
217 314
387 411
429 493
513 555
605 640
699 724
753 835
843 894
1052 1076
1144 1288
1360 1377
1395 1470
1563 1627
1633 1641
1660 1704
1769 1843
1898 1971
1977 1982
2008 2059
2113 2140
2149 2232
2247 2318
2433 2438
2530 2613
2731 2739
2741 2773
2799 2954
2974 3006
3070 3077...

output:

64735055

result:

ok single line: '64735055'

Test #145:

score: 1
Accepted
time: 591ms
memory: 158176kb

input:

500000
4 87
102 156
169 200
219 238
243 325
382 464
475 528
599 631
681 714
756 767
774 781
1001 1051
1162 1187
1212 1291
1334 1427
1495 1550
1552 1620
1633 1662
1690 1705
1708 1713
1772 1791
1799 1807
1832 1910
1972 1983
1997 2057
2059 2066
2108 2118
2171 2195
2237 2296
2397 2428
2579 2589
2614 268...

output:

22886399

result:

ok single line: '22886399'

Test #146:

score: 1
Accepted
time: 647ms
memory: 173940kb

input:

500000
264 359
385 518
979 1751
2065 2650
2862 3104
3225 3375
3721 4720
4775 4853
5481 5601
5989 6157
6856 6875
7239 7554
7613 8121
8203 8752
8897 9137
9277 9396
9416 9531
10284 10610
10702 10710
10862 10976
10980 11311
11333 11421
11444 11498
11704 11706
11901 11909
12473 13366
13498 13888
13979 14...

output:

111208865

result:

ok single line: '111208865'

Test #147:

score: 1
Accepted
time: 588ms
memory: 159040kb

input:

500000
54 124
128 155
195 202
216 332
443 474
512 529
544 562
607 633
639 726
759 786
804 827
833 851
893 967
993 1032
1132 1137
1143 1289
1293 1410
1695 1738
1757 1762
1787 1931
1947 2001
2072 2141
2155 2176
2224 2368
2385 2387
2391 2407
2417 2435
2438 2490
2510 2511
2513 2528
2539 2555
2602 2625
2...

output:

816815104

result:

ok single line: '816815104'

Test #148:

score: 1
Accepted
time: 573ms
memory: 159448kb

input:

500000
99 135
153 162
170 175
203 326
333 398
404 411
428 442
526 581
586 625
656 700
710 717
748 797
799 808
908 909
942 968
1032 1048
1052 1068
1096 1185
1191 1267
1347 1377
1457 1513
1554 1562
1689 1706
1708 1720
1733 1813
1823 1960
1983 2144
2169 2174
2285 2292
2384 2438
2461 2471
2485 2498
2500...

output:

932515149

result:

ok single line: '932515149'

Test #149:

score: 1
Accepted
time: 626ms
memory: 159544kb

input:

500000
50 166
187 269
322 331
362 380
486 564
608 670
733 763
800 850
924 946
964 976
1037 1087
1129 1133
1241 1320
1353 1359
1365 1445
1480 1491
1501 1507
1511 1539
1558 1571
1676 1681
1716 1723
1779 1803
1878 1900
1958 1964
1990 2088
2106 2115
2122 2155
2172 2181
2186 2243
2276 2329
2337 2360
2397...

output:

125539079

result:

ok single line: '125539079'

Test #150:

score: 1
Accepted
time: 463ms
memory: 158696kb

input:

500000
1 1000000
999997 999999
999993 999995
999989 999991
999985 999987
999981 999983
999977 999979
999971 999973
999967 999969
999963 999965
999959 999961
999955 999957
999949 999951
999945 999947
999941 999943
999937 999939
999933 999935
999927 999929
999923 999925
999919 999921
999915 999917
999...

output:

941546347

result:

ok single line: '941546347'

Test #151:

score: 1
Accepted
time: 235ms
memory: 92236kb

input:

262144
524287 524288
524285 524286
524283 524284
524281 524282
524279 524280
524277 524278
524275 524276
524273 524274
524271 524272
524269 524270
524267 524268
524265 524266
524263 524264
524261 524262
524259 524260
524257 524258
524255 524256
524253 524254
524251 524252
524249 524250
524247 524248...

output:

262144

result:

ok single line: '262144'

Extra Test:

score: 0
Extra Test Passed