from solution import Solution


class Sol(Solution):
    @property
    def cleaned(self):
        return [int(x) for x in self.input.split("\n") if x]

    @property
    def solution(self):
        return self.p1(self.p2())

    def p1(self, iterable):
        ans = []
        for i, depth in enumerate(iterable):
            if i == 0:
                continue
            else:
                delta = depth - iterable[i - 1]
                if delta > 0:
                    ans.append(delta)
        return len(ans)

    def p2(self):
        win = []
        for k, _ in enumerate(self.cleaned):
            v = self.get_next_3_sum(k)
            if v is not None:
                win.append(v)
        return win

    def get_next_3_sum(self, index):
        try:
            return sum(
                [self.cleaned[index], self.cleaned[index + 1], self.cleaned[index + 2]]
            )
        except IndexError:
            return None


input_ = """
198
208
209
212
213
217
218
223
222
224
216
233
238
239
240
250
263
264
267
274
288
316
319
330
340
347
349
354
350
349
351
352
353
371
383
385
405
413
455
451
459
458
459
461
463
475
480
486
489
497
502
512
513
516
517
528
559
560
558
565
566
567
571
573
574
582
583
585
589
597
608
607
614
619
608
624
665
666
675
695
698
703
711
733
738
739
742
743
763
775
778
804
806
810
812
818
819
828
867
866
876
878
881
875
881
858
859
868
869
860
888
890
891
893
894
919
924
925
933
937
950
955
966
984
989
993
996
997
1015
1031
1035
1039
1055
1057
1058
1059
1060
1061
1067
1069
1070
1059
1060
1077
1079
1078
1080
1087
1088
1090
1097
1082
1102
1105
1106
1120
1125
1130
1132
1154
1141
1135
1131
1133
1134
1137
1138
1141
1142
1143
1166
1175
1193
1201
1236
1238
1234
1240
1242
1243
1271
1276
1277
1272
1286
1288
1290
1292
1317
1341
1361
1363
1375
1376
1377
1383
1387
1390
1402
1404
1412
1418
1426
1429
1466
1480
1483
1478
1484
1486
1488
1491
1486
1489
1492
1517
1520
1523
1539
1546
1551
1521
1517
1518
1522
1525
1526
1539
1540
1544
1545
1561
1571
1572
1574
1575
1568
1573
1587
1588
1600
1603
1627
1629
1633
1645
1670
1671
1685
1690
1696
1698
1703
1698
1699
1702
1714
1716
1709
1738
1753
1761
1766
1769
1772
1761
1763
1774
1781
1782
1799
1802
1816
1818
1819
1805
1810
1817
1819
1831
1834
1835
1852
1855
1858
1859
1856
1857
1868
1885
1891
1893
1890
1891
1892
1893
1896
1911
1912
1914
1916
1914
1918
1930
1932
1958
1966
1976
1982
1985
1986
1987
1992
1997
2031
2041
2042
2044
2058
2060
2075
2073
2084
2087
2090
2125
2128
2129
2130
2131
2136
2137
2145
2150
2152
2155
2161
2162
2165
2167
2189
2197
2199
2214
2226
2233
2234
2241
2242
2256
2259
2263
2257
2267
2270
2269
2272
2273
2275
2279
2284
2285
2266
2271
2287
2291
2310
2313
2314
2317
2311
2312
2311
2312
2326
2331
2332
2338
2340
2352
2355
2360
2361
2357
2371
2384
2380
2392
2393
2396
2397
2400
2417
2420
2421
2422
2444
2457
2458
2464
2467
2494
2495
2498
2510
2514
2521
2526
2525
2533
2536
2547
2544
2547
2556
2557
2558
2561
2570
2571
2573
2575
2583
2584
2585
2572
2574
2575
2587
2589
2590
2602
2603
2604
2605
2589
2603
2608
2611
2616
2613
2617
2618
2619
2628
2629
2630
2631
2639
2645
2649
2657
2665
2673
2680
2679
2680
2702
2703
2709
2711
2714
2715
2716
2715
2721
2720
2739
2745
2748
2752
2749
2748
2749
2751
2752
2750
2760
2777
2778
2779
2780
2787
2800
2805
2810
2812
2820
2821
2843
2846
2853
2862
2861
2867
2880
2890
2891
2892
2885
2887
2890
2894
2897
2925
2926
2931
2933
2940
2943
2941
2959
2971
2982
2984
3002
3006
3008
3012
3013
3034
3043
3059
3063
3064
3060
3075
3090
3091
3104
3108
3114
3117
3106
3104
3110
3113
3114
3126
3119
3138
3140
3141
3143
3139
3145
3147
3153
3161
3170
3168
3180
3181
3177
3196
3210
3216
3232
3233
3234
3235
3239
3240
3242
3243
3244
3243
3248
3249
3275
3276
3278
3280
3286
3291
3293
3294
3301
3310
3319
3326
3338
3339
3348
3366
3376
3371
3372
3404
3407
3408
3425
3444
3451
3457
3452
3459
3468
3491
3475
3476
3481
3505
3516
3519
3542
3543
3541
3542
3541
3551
3553
3552
3533
3542
3543
3561
3562
3563
3566
3571
3572
3596
3600
3603
3607
3608
3609
3613
3654
3665
3672
3661
3662
3663
3670
3676
3683
3707
3709
3714
3717
3709
3710
3713
3714
3715
3716
3735
3749
3763
3770
3784
3782
3786
3790
3792
3794
3803
3805
3819
3823
3826
3828
3838
3839
3843
3870
3877
3888
3889
3891
3892
3893
3894
3880
3860
3878
3880
3888
3893
3898
3904
3906
3907
3910
3918
3927
3946
3973
3982
3979
3980
3993
3984
3988
3986
3987
3988
3989
3997
4000
4001
4025
4030
4034
4038
4040
4044
4046
4048
4057
4067
4079
4092
4094
4122
4124
4128
4127
4128
4132
4136
4141
4146
4151
4153
4163
4167
4168
4170
4172
4176
4177
4178
4194
4198
4199
4201
4203
4204
4205
4204
4209
4211
4213
4224
4240
4242
4255
4266
4280
4284
4295
4310
4323
4343
4351
4359
4383
4387
4388
4397
4401
4403
4404
4405
4425
4431
4435
4439
4444
4452
4461
4470
4466
4467
4469
4481
4482
4498
4496
4504
4505
4512
4518
4520
4521
4523
4534
4516
4527
4525
4534
4535
4551
4565
4570
4571
4578
4584
4595
4609
4610
4618
4628
4629
4630
4634
4636
4637
4640
4659
4664
4669
4665
4673
4687
4688
4693
4694
4697
4667
4678
4679
4702
4707
4706
4709
4711
4718
4725
4716
4718
4723
4724
4726
4727
4729
4735
4736
4738
4739
4758
4763
4773
4774
4776
4777
4778
4777
4785
4786
4771
4773
4774
4777
4781
4783
4788
4791
4794
4807
4816
4818
4825
4828
4838
4822
4831
4837
4841
4851
4854
4870
4876
4888
4889
4900
4906
4909
4910
4917
4919
4920
4926
4928
4934
4941
4943
4945
4948
4950
4956
4951
4948
4954
4958
4960
4959
4962
4969
4982
4986
4994
5000
5009
5027
5025
5029
5033
5037
5036
5037
5040
5032
5033
5034
5039
5045
5050
5045
5076
5077
5082
5083
5106
5107
5114
5117
5137
5138
5143
5147
5153
5156
5171
5182
5183
5184
5185
5189
5182
5189
5194
5201
5205
5213
5218
5221
5223
5230
5231
5243
5255
5230
5228
5237
5245
5248
5259
5260
5272
5278
5281
5287
5286
5287
5298
5328
5329
5333
5335
5337
5339
5341
5346
5349
5350
5351
5358
5359
5360
5374
5376
5359
5360
5388
5401
5406
5410
5412
5413
5414
5415
5435
5436
5441
5443
5448
5446
5448
5449
5464
5465
5466
5469
5470
5492
5493
5494
5509
5520
5528
5530
5537
5541
5542
5559
5562
5563
5588
5595
5596
5601
5618
5626
5627
5641
5667
5679
5685
5693
5695
5717
5733
5734
5754
5755
5757
5758
5759
5760
5761
5771
5774
5780
5784
5785
5787
5788
5790
5800
5811
5814
5810
5811
5794
5792
5803
5804
5812
5814
5815
5836
5852
5853
5855
5878
5879
5880
5883
5889
5897
5911
5932
5934
5935
5936
5938
5939
5941
5951
5955
5950
5951
5954
5970
5971
5974
5977
5978
5985
5986
6013
6024
6031
6037
6043
6052
6051
6053
6076
6096
6101
6106
6108
6115
6125
6106
6107
6104
6114
6142
6143
6162
6169
6170
6171
6181
6198
6199
6202
6206
6207
6244
6246
6249
6250
6254
6264
6271
6276
6277
6268
6271
6288
6293
6308
6309
6326
6341
6345
6344
6341
6364
6365
6366
6370
6371
6373
6376
6377
6378
6377
6379
6386
6396
6397
6420
6422
6429
6433
6463
6472
6473
6490
6491
6492
6497
6522
6523
6524
6519
6520
6521
6525
6530
6531
6534
6535
6543
6552
6558
6584
6586
6587
6588
6606
6614
6618
6646
6650
6651
6654
6677
6663
6665
6676
6655
6653
6655
6665
6667
6682
6692
6703
6704
6707
6715
6719
6730
6731
6733
6743
6747
6748
6750
6759
6771
6772
6776
6775
6776
6782
6785
6812
6841
6858
6860
6859
6877
6886
6895
6914
6919
6922
6924
6933
6935
6936
6937
6938
6952
6962
6965
6984
6987
6986
6985
6977
6967
6968
6966
6980
6997
6994
7002
7008
7000
6975
7009
7014
7015
7026
7027
7034
7036
7041
7040
7041
7045
7048
7065
7074
7075
7082
7087
7092
7098
7097
7111
7127
7124
7135
7136
7137
7140
7153
7156
7158
7174
7176
7177
7163
7166
7159
7157
7158
7164
7165
7172
7190
7194
7199
7200
7205
7208
7207
7222
7227
7244
7249
7271
7272
7273
7274
7281
7286
7288
7314
7315
7317
7318
7319
7304
7307
7308
7309
7312
7319
7322
7337
7338
7345
7346
7350
7360
7361
7362
7360
7395
7400
7404
7405
7407
7406
7411
7420
7435
7440
7442
7446
7453
7446
7448
7467
7471
7469
7470
7482
7485
7492
7488
7489
7492
7493
7494
7497
7504
7520
7525
7547
7554
7543
7553
7560
7561
7577
7589
7591
7593
7587
7596
7597
7584
7590
7591
7599
7626
7627
7628
7630
7645
7639
7645
7652
7657
7662
7664
7674
7680
7681
7694
7698
7716
7704
7705
7706
7708
7712
7716
7715
7717
7722
7723
7728
7721
7722
7724
7727
7735
7737
7725
7746
7747
7750
7761
7762
7765
7777
7780
7776
7777
7778
7759
7769
7770
7787
7797
7798
7804
7803
7804
7805
7811
7825
7824
7826
7827
7828
7851
7867
7887
7889
7890
7900
7904
7917
7918
7935
7941
7942
7946
7947
7948
7949
7976
7979
7981
7983
7988
7999
8000
8009
8011
8012
8019
8021
8025
8027
8006
8011
8034
8036
8037
8038
8013
8024
8029
8032
8033
8034
8032
8034
8036
8059
8060
8063
8064
8081
8090
8097
8122
8135
8147
8149
8150
8151
8162
8174
8154
8158
8162
8170
8171
8188
8189
8190
8191
8196
8205
8216
8217
8222
8233
8239
8240
8242
8257
8249
8262
8264
8274
8309
8311
8328
8333
8335
8338
8344
8350
8349
8350
8363
8366
8370
8371
8395
8398
8401
8410
8425
8429
8430
8441
8443
8445
8451
8452
8455
8458
8431
8443
8453
8459
8477
8474
8479
8476
8487
8488
8489
8500
8501
8503
8504
8538
8523
8529
8530
8556
8573
8576
8589
8595
8624
8632
8634
8628
8636
8635
8636
8644
8659
8661
8641
8652
8659
8650
8664
8667
8674
8676
8678
8686
8696
8697
8735
8740
8749
8767
8769
8747
8751
8760
8755
8766
8768
8777
8782
8788
8796
8799
8801
8809
8807
8816
8827
8831
8835
8836
8843
8844
8845
8851
8858
8860
8862
8863
8889
8891
8912
8913
8924
8928
8929
8939
8955
8957
8958
8963
8988
8989
8997
8995
8999
8968
8990
8991
8992
8994
8996
9013
9024
9026
9035
9046
9047
9083
9084
9089
9096
9108
9107
9116
9123
9122
9128
9132
9151
9155
9163
9174
9178
9183
9199
9209
9217
9219
9232
9233
9232
9237
9241
9244
9245
9247
9251
9252
9266
9285
9284
9291
9294
9295
9296
9300
9322
9328
9333
9337
9345
9346
9347
9371
9375
9394
9397
9404
9406
9422
9425
9438
9440
9435
9442
9455
9473
9475
9496
9499
9500
9511
9512
9513
9539
9540
9543
9547
9550
9557
9571
9577
9593
9600
9609
9615
9620
9621
9616
9625
9626
9637
9638
9642
9648
9656
9654
9661
9665
9696
9705
9710
9719
9720
9717
9718
9717
9719
9724
9725
9738
9741
9743
9744
9745
9765
9778
9779
9789
9791
9773
9778
9780
9782
9783
9782
9797
9799
9800
9801
9823
9824
9834
9836
9841
9845
9847
9865
9868
9883
9884
9887
9890
9892
9899
9908
9910
9911
9915
9918
9922
9926
9923
9944
9947
9948
9949
9958
9959
9961
9973
9954
9976
9978
10001
10000
9992
9997
9985
9995
9996
10005
9999
10001
10002
10009
10041
10045
10051
10070
10071
10073
10100
10099
10100
10101
10102
10105
10082
10083
10082
10086
10112
10113
10114
10122
10124
10127
10140
10156
10157
10158
10159
10162
10163
10166
10177
10178
10180
10178
10179
10191
10186
10198
10201
10204
10227
10229
10232
10234
10246
10247
10248
10249
10250
10269
10277
10278
10279
10289
10291
10294
10292
10304
10324
10339
10342
10343
10349
10354
10371
10370
10374
10376
10379
10405
10406
10405
10403
10411
10412
10411
10419
10422
10435
10437
10438
10437
10440
10427
10421
10432
10434
10439
10449
10442
10469
10471
10476
10480
10481
10485
10507
10508
10511
10512
10513
10523
10524
10529
10536
10552
10563
10569
10573
10575
10576
10578
10596
10602
10630
10647
10657
10659
10684
10687
10692
10693
10700
10702
10703
10709
10714
10716
10727
10746
10744
10754
10753
10754
10755
10759
10763
10764
10765
10769
10770
10771
10777
10796
10807
10813
10818
10825
10830
10835
10836
10849
10858
10873
10882
10879
10882
10886
10902
10903
10931
10930
"""

if __name__ == "__main__":
    Sol(input_).solve()

from solution import Solution


class Sol(Solution):
    @property
    def cleaned(self):
        return [int(x) for x in self.input.split("\n") if x]

    @property
    def solution(self):
        return self.p1(self.p2())

    def p1(self, iterable):
        ans = []
        for i, depth in enumerate(iterable):
            if i == 0:
                continue
            else:
                delta = depth - iterable[i - 1]
                if delta > 0:
                    ans.append(delta)
        return len(ans)

    def p2(self):
        win = []
        for k, _ in enumerate(self.cleaned):
            v = self.get_next_3_sum(k)
            if v is not None:
                win.append(v)
        return win

    def get_next_3_sum(self, index):
        try:
            return sum(
                [self.cleaned[index], self.cleaned[index + 1], self.cleaned[index + 2]]
            )
        except IndexError:
            return None


input_ = """
198
208
209
212
213
217
218
223
222
224
216
233
238
239
240
250
263
264
267
274
288
316
319
330
340
347
349
354
350
349
351
352
353
371
383
385
405
413
455
451
459
458
459
461
463
475
480
486
489
497
502
512
513
516
517
528
559
560
558
565
566
567
571
573
574
582
583
585
589
597
608
607
614
619
608
624
665
666
675
695
698
703
711
733
738
739
742
743
763
775
778
804
806
810
812
818
819
828
867
866
876
878
881
875
881
858
859
868
869
860
888
890
891
893
894
919
924
925
933
937
950
955
966
984
989
993
996
997
1015
1031
1035
1039
1055
1057
1058
1059
1060
1061
1067
1069
1070
1059
1060
1077
1079
1078
1080
1087
1088
1090
1097
1082
1102
1105
1106
1120
1125
1130
1132
1154
1141
1135
1131
1133
1134
1137
1138
1141
1142
1143
1166
1175
1193
1201
1236
1238
1234
1240
1242
1243
1271
1276
1277
1272
1286
1288
1290
1292
1317
1341
1361
1363
1375
1376
1377
1383
1387
1390
1402
1404
1412
1418
1426
1429
1466
1480
1483
1478
1484
1486
1488
1491
1486
1489
1492
1517
1520
1523
1539
1546
1551
1521
1517
1518
1522
1525
1526
1539
1540
1544
1545
1561
1571
1572
1574
1575
1568
1573
1587
1588
1600
1603
1627
1629
1633
1645
1670
1671
1685
1690
1696
1698
1703
1698
1699
1702
1714
1716
1709
1738
1753
1761
1766
1769
1772
1761
1763
1774
1781
1782
1799
1802
1816
1818
1819
1805
1810
1817
1819
1831
1834
1835
1852
1855
1858
1859
1856
1857
1868
1885
1891
1893
1890
1891
1892
1893
1896
1911
1912
1914
1916
1914
1918
1930
1932
1958
1966
1976
1982
1985
1986
1987
1992
1997
2031
2041
2042
2044
2058
2060
2075
2073
2084
2087
2090
2125
2128
2129
2130
2131
2136
2137
2145
2150
2152
2155
2161
2162
2165
2167
2189
2197
2199
2214
2226
2233
2234
2241
2242
2256
2259
2263
2257
2267
2270
2269
2272
2273
2275
2279
2284
2285
2266
2271
2287
2291
2310
2313
2314
2317
2311
2312
2311
2312
2326
2331
2332
2338
2340
2352
2355
2360
2361
2357
2371
2384
2380
2392
2393
2396
2397
2400
2417
2420
2421
2422
2444
2457
2458
2464
2467
2494
2495
2498
2510
2514
2521
2526
2525
2533
2536
2547
2544
2547
2556
2557
2558
2561
2570
2571
2573
2575
2583
2584
2585
2572
2574
2575
2587
2589
2590
2602
2603
2604
2605
2589
2603
2608
2611
2616
2613
2617
2618
2619
2628
2629
2630
2631
2639
2645
2649
2657
2665
2673
2680
2679
2680
2702
2703
2709
2711
2714
2715
2716
2715
2721
2720
2739
2745
2748
2752
2749
2748
2749
2751
2752
2750
2760
2777
2778
2779
2780
2787
2800
2805
2810
2812
2820
2821
2843
2846
2853
2862
2861
2867
2880
2890
2891
2892
2885
2887
2890
2894
2897
2925
2926
2931
2933
2940
2943
2941
2959
2971
2982
2984
3002
3006
3008
3012
3013
3034
3043
3059
3063
3064
3060
3075
3090
3091
3104
3108
3114
3117
3106
3104
3110
3113
3114
3126
3119
3138
3140
3141
3143
3139
3145
3147
3153
3161
3170
3168
3180
3181
3177
3196
3210
3216
3232
3233
3234
3235
3239
3240
3242
3243
3244
3243
3248
3249
3275
3276
3278
3280
3286
3291
3293
3294
3301
3310
3319
3326
3338
3339
3348
3366
3376
3371
3372
3404
3407
3408
3425
3444
3451
3457
3452
3459
3468
3491
3475
3476
3481
3505
3516
3519
3542
3543
3541
3542
3541
3551
3553
3552
3533
3542
3543
3561
3562
3563
3566
3571
3572
3596
3600
3603
3607
3608
3609
3613
3654
3665
3672
3661
3662
3663
3670
3676
3683
3707
3709
3714
3717
3709
3710
3713
3714
3715
3716
3735
3749
3763
3770
3784
3782
3786
3790
3792
3794
3803
3805
3819
3823
3826
3828
3838
3839
3843
3870
3877
3888
3889
3891
3892
3893
3894
3880
3860
3878
3880
3888
3893
3898
3904
3906
3907
3910
3918
3927
3946
3973
3982
3979
3980
3993
3984
3988
3986
3987
3988
3989
3997
4000
4001
4025
4030
4034
4038
4040
4044
4046
4048
4057
4067
4079
4092
4094
4122
4124
4128
4127
4128
4132
4136
4141
4146
4151
4153
4163
4167
4168
4170
4172
4176
4177
4178
4194
4198
4199
4201
4203
4204
4205
4204
4209
4211
4213
4224
4240
4242
4255
4266
4280
4284
4295
4310
4323
4343
4351
4359
4383
4387
4388
4397
4401
4403
4404
4405
4425
4431
4435
4439
4444
4452
4461
4470
4466
4467
4469
4481
4482
4498
4496
4504
4505
4512
4518
4520
4521
4523
4534
4516
4527
4525
4534
4535
4551
4565
4570
4571
4578
4584
4595
4609
4610
4618
4628
4629
4630
4634
4636
4637
4640
4659
4664
4669
4665
4673
4687
4688
4693
4694
4697
4667
4678
4679
4702
4707
4706
4709
4711
4718
4725
4716
4718
4723
4724
4726
4727
4729
4735
4736
4738
4739
4758
4763
4773
4774
4776
4777
4778
4777
4785
4786
4771
4773
4774
4777
4781
4783
4788
4791
4794
4807
4816
4818
4825
4828
4838
4822
4831
4837
4841
4851
4854
4870
4876
4888
4889
4900
4906
4909
4910
4917
4919
4920
4926
4928
4934
4941
4943
4945
4948
4950
4956
4951
4948
4954
4958
4960
4959
4962
4969
4982
4986
4994
5000
5009
5027
5025
5029
5033
5037
5036
5037
5040
5032
5033
5034
5039
5045
5050
5045
5076
5077
5082
5083
5106
5107
5114
5117
5137
5138
5143
5147
5153
5156
5171
5182
5183
5184
5185
5189
5182
5189
5194
5201
5205
5213
5218
5221
5223
5230
5231
5243
5255
5230
5228
5237
5245
5248
5259
5260
5272
5278
5281
5287
5286
5287
5298
5328
5329
5333
5335
5337
5339
5341
5346
5349
5350
5351
5358
5359
5360
5374
5376
5359
5360
5388
5401
5406
5410
5412
5413
5414
5415
5435
5436
5441
5443
5448
5446
5448
5449
5464
5465
5466
5469
5470
5492
5493
5494
5509
5520
5528
5530
5537
5541
5542
5559
5562
5563
5588
5595
5596
5601
5618
5626
5627
5641
5667
5679
5685
5693
5695
5717
5733
5734
5754
5755
5757
5758
5759
5760
5761
5771
5774
5780
5784
5785
5787
5788
5790
5800
5811
5814
5810
5811
5794
5792
5803
5804
5812
5814
5815
5836
5852
5853
5855
5878
5879
5880
5883
5889
5897
5911
5932
5934
5935
5936
5938
5939
5941
5951
5955
5950
5951
5954
5970
5971
5974
5977
5978
5985
5986
6013
6024
6031
6037
6043
6052
6051
6053
6076
6096
6101
6106
6108
6115
6125
6106
6107
6104
6114
6142
6143
6162
6169
6170
6171
6181
6198
6199
6202
6206
6207
6244
6246
6249
6250
6254
6264
6271
6276
6277
6268
6271
6288
6293
6308
6309
6326
6341
6345
6344
6341
6364
6365
6366
6370
6371
6373
6376
6377
6378
6377
6379
6386
6396
6397
6420
6422
6429
6433
6463
6472
6473
6490
6491
6492
6497
6522
6523
6524
6519
6520
6521
6525
6530
6531
6534
6535
6543
6552
6558
6584
6586
6587
6588
6606
6614
6618
6646
6650
6651
6654
6677
6663
6665
6676
6655
6653
6655
6665
6667
6682
6692
6703
6704
6707
6715
6719
6730
6731
6733
6743
6747
6748
6750
6759
6771
6772
6776
6775
6776
6782
6785
6812
6841
6858
6860
6859
6877
6886
6895
6914
6919
6922
6924
6933
6935
6936
6937
6938
6952
6962
6965
6984
6987
6986
6985
6977
6967
6968
6966
6980
6997
6994
7002
7008
7000
6975
7009
7014
7015
7026
7027
7034
7036
7041
7040
7041
7045
7048
7065
7074
7075
7082
7087
7092
7098
7097
7111
7127
7124
7135
7136
7137
7140
7153
7156
7158
7174
7176
7177
7163
7166
7159
7157
7158
7164
7165
7172
7190
7194
7199
7200
7205
7208
7207
7222
7227
7244
7249
7271
7272
7273
7274
7281
7286
7288
7314
7315
7317
7318
7319
7304
7307
7308
7309
7312
7319
7322
7337
7338
7345
7346
7350
7360
7361
7362
7360
7395
7400
7404
7405
7407
7406
7411
7420
7435
7440
7442
7446
7453
7446
7448
7467
7471
7469
7470
7482
7485
7492
7488
7489
7492
7493
7494
7497
7504
7520
7525
7547
7554
7543
7553
7560
7561
7577
7589
7591
7593
7587
7596
7597
7584
7590
7591
7599
7626
7627
7628
7630
7645
7639
7645
7652
7657
7662
7664
7674
7680
7681
7694
7698
7716
7704
7705
7706
7708
7712
7716
7715
7717
7722
7723
7728
7721
7722
7724
7727
7735
7737
7725
7746
7747
7750
7761
7762
7765
7777
7780
7776
7777
7778
7759
7769
7770
7787
7797
7798
7804
7803
7804
7805
7811
7825
7824
7826
7827
7828
7851
7867
7887
7889
7890
7900
7904
7917
7918
7935
7941
7942
7946
7947
7948
7949
7976
7979
7981
7983
7988
7999
8000
8009
8011
8012
8019
8021
8025
8027
8006
8011
8034
8036
8037
8038
8013
8024
8029
8032
8033
8034
8032
8034
8036
8059
8060
8063
8064
8081
8090
8097
8122
8135
8147
8149
8150
8151
8162
8174
8154
8158
8162
8170
8171
8188
8189
8190
8191
8196
8205
8216
8217
8222
8233
8239
8240
8242
8257
8249
8262
8264
8274
8309
8311
8328
8333
8335
8338
8344
8350
8349
8350
8363
8366
8370
8371
8395
8398
8401
8410
8425
8429
8430
8441
8443
8445
8451
8452
8455
8458
8431
8443
8453
8459
8477
8474
8479
8476
8487
8488
8489
8500
8501
8503
8504
8538
8523
8529
8530
8556
8573
8576
8589
8595
8624
8632
8634
8628
8636
8635
8636
8644
8659
8661
8641
8652
8659
8650
8664
8667
8674
8676
8678
8686
8696
8697
8735
8740
8749
8767
8769
8747
8751
8760
8755
8766
8768
8777
8782
8788
8796
8799
8801
8809
8807
8816
8827
8831
8835
8836
8843
8844
8845
8851
8858
8860
8862
8863
8889
8891
8912
8913
8924
8928
8929
8939
8955
8957
8958
8963
8988
8989
8997
8995
8999
8968
8990
8991
8992
8994
8996
9013
9024
9026
9035
9046
9047
9083
9084
9089
9096
9108
9107
9116
9123
9122
9128
9132
9151
9155
9163
9174
9178
9183
9199
9209
9217
9219
9232
9233
9232
9237
9241
9244
9245
9247
9251
9252
9266
9285
9284
9291
9294
9295
9296
9300
9322
9328
9333
9337
9345
9346
9347
9371
9375
9394
9397
9404
9406
9422
9425
9438
9440
9435
9442
9455
9473
9475
9496
9499
9500
9511
9512
9513
9539
9540
9543
9547
9550
9557
9571
9577
9593
9600
9609
9615
9620
9621
9616
9625
9626
9637
9638
9642
9648
9656
9654
9661
9665
9696
9705
9710
9719
9720
9717
9718
9717
9719
9724
9725
9738
9741
9743
9744
9745
9765
9778
9779
9789
9791
9773
9778
9780
9782
9783
9782
9797
9799
9800
9801
9823
9824
9834
9836
9841
9845
9847
9865
9868
9883
9884
9887
9890
9892
9899
9908
9910
9911
9915
9918
9922
9926
9923
9944
9947
9948
9949
9958
9959
9961
9973
9954
9976
9978
10001
10000
9992
9997
9985
9995
9996
10005
9999
10001
10002
10009
10041
10045
10051
10070
10071
10073
10100
10099
10100
10101
10102
10105
10082
10083
10082
10086
10112
10113
10114
10122
10124
10127
10140
10156
10157
10158
10159
10162
10163
10166
10177
10178
10180
10178
10179
10191
10186
10198
10201
10204
10227
10229
10232
10234
10246
10247
10248
10249
10250
10269
10277
10278
10279
10289
10291
10294
10292
10304
10324
10339
10342
10343
10349
10354
10371
10370
10374
10376
10379
10405
10406
10405
10403
10411
10412
10411
10419
10422
10435
10437
10438
10437
10440
10427
10421
10432
10434
10439
10449
10442
10469
10471
10476
10480
10481
10485
10507
10508
10511
10512
10513
10523
10524
10529
10536
10552
10563
10569
10573
10575
10576
10578
10596
10602
10630
10647
10657
10659
10684
10687
10692
10693
10700
10702
10703
10709
10714
10716
10727
10746
10744
10754
10753
10754
10755
10759
10763
10764
10765
10769
10770
10771
10777
10796
10807
10813
10818
10825
10830
10835
10836
10849
10858
10873
10882
10879
10882
10886
10902
10903
10931
10930
"""

if __name__ == "__main__":
    Sol(input_).solve()

198 208 209 212 213 217 218 223 222 224 216 233 238 239 240 250 263 264 267 274 288 316 319 330 340 347 349 354 350 349 351 352 353 371 383 385 405 413 455 451 459 458 459 461 463 475 480 486 489 497 502 512 513 516 517 528 559 560 558 565 566 567 571 573 574 582 583 585 589 597 608 607 614 619 608 624 665 666 675 695 698 703 711 733 738 739 742 743 763 775 778 804 806 810 812 818 819 828 867 866 876 878 881 875 881 858 859 868 869 860 888 890 891 893 894 919 924 925 933 937 950 955 966 984 989 993 996 997 1015 1031 1035 1039 1055 1057 1058 1059 1060 1061 1067 1069 1070 1059 1060 1077 1079 1078 1080 1087 1088 1090 1097 1082 1102 1105 1106 1120 1125 1130 1132 1154 1141 1135 1131 1133 1134 1137 1138 1141 1142 1143 1166 1175 1193 1201 1236 1238 1234 1240 1242 1243 1271 1276 1277 1272 1286 1288 1290 1292 1317 1341 1361 1363 1375 1376 1377 1383 1387 1390 1402 1404 1412 1418 1426 1429 1466 1480 1483 1478 1484 1486 1488 1491 1486 1489 1492 1517 1520 1523 1539 1546 1551 1521 1517 1518 1522 1525 1526 1539 1540 1544 1545 1561 1571 1572 1574 1575 1568 1573 1587 1588 1600 1603 1627 1629 1633 1645 1670 1671 1685 1690 1696 1698 1703 1698 1699 1702 1714 1716 1709 1738 1753 1761 1766 1769 1772 1761 1763 1774 1781 1782 1799 1802 1816 1818 1819 1805 1810 1817 1819 1831 1834 1835 1852 1855 1858 1859 1856 1857 1868 1885 1891 1893 1890 1891 1892 1893 1896 1911 1912 1914 1916 1914 1918 1930 1932 1958 1966 1976 1982 1985 1986 1987 1992 1997 2031 2041 2042 2044 2058 2060 2075 2073 2084 2087 2090 2125 2128 2129 2130 2131 2136 2137 2145 2150 2152 2155 2161 2162 2165 2167 2189 2197 2199 2214 2226 2233 2234 2241 2242 2256 2259 2263 2257 2267 2270 2269 2272 2273 2275 2279 2284 2285 2266 2271 2287 2291 2310 2313 2314 2317 2311 2312 2311 2312 2326 2331 2332 2338 2340 2352 2355 2360 2361 2357 2371 2384 2380 2392 2393 2396 2397 2400 2417 2420 2421 2422 2444 2457 2458 2464 2467 2494 2495 2498 2510 2514 2521 2526 2525 2533 2536 2547 2544 2547 2556 2557 2558 2561 2570 2571 2573 2575 2583 2584 2585 2572 2574 2575 2587 2589 2590 2602 2603 2604 2605 2589 2603 2608 2611 2616 2613 2617 2618 2619 2628 2629 2630 2631 2639 2645 2649 2657 2665 2673 2680 2679 2680 2702 2703 2709 2711 2714 2715 2716 2715 2721 2720 2739 2745 2748 2752 2749 2748 2749 2751 2752 2750 2760 2777 2778 2779 2780 2787 2800 2805 2810 2812 2820 2821 2843 2846 2853 2862 2861 2867 2880 2890 2891 2892 2885 2887 2890 2894 2897 2925 2926 2931 2933 2940 2943 2941 2959 2971 2982 2984 3002 3006 3008 3012 3013 3034 3043 3059 3063 3064 3060 3075 3090 3091 3104 3108 3114 3117 3106 3104 3110 3113 3114 3126 3119 3138 3140 3141 3143 3139 3145 3147 3153 3161 3170 3168 3180 3181 3177 3196 3210 3216 3232 3233 3234 3235 3239 3240 3242 3243 3244 3243 3248 3249 3275 3276 3278 3280 3286 3291 3293 3294 3301 3310 3319 3326 3338 3339 3348 3366 3376 3371 3372 3404 3407 3408 3425 3444 3451 3457 3452 3459 3468 3491 3475 3476 3481 3505 3516 3519 3542 3543 3541 3542 3541 3551 3553 3552 3533 3542 3543 3561 3562 3563 3566 3571 3572 3596 3600 3603 3607 3608 3609 3613 3654 3665 3672 3661 3662 3663 3670 3676 3683 3707 3709 3714 3717 3709 3710 3713 3714 3715 3716 3735 3749 3763 3770 3784 3782 3786 3790 3792 3794 3803 3805 3819 3823 3826 3828 3838 3839 3843 3870 3877 3888 3889 3891 3892 3893 3894 3880 3860 3878 3880 3888 3893 3898 3904 3906 3907 3910 3918 3927 3946 3973 3982 3979 3980 3993 3984 3988 3986 3987 3988 3989 3997 4000 4001 4025 4030 4034 4038 4040 4044 4046 4048 4057 4067 4079 4092 4094 4122 4124 4128 4127 4128 4132 4136 4141 4146 4151 4153 4163 4167 4168 4170 4172 4176 4177 4178 4194 4198 4199 4201 4203 4204 4205 4204 4209 4211 4213 4224 4240 4242 4255 4266 4280 4284 4295 4310 4323 4343 4351 4359 4383 4387 4388 4397 4401 4403 4404 4405 4425 4431 4435 4439 4444 4452 4461 4470 4466 4467 4469 4481 4482 4498 4496 4504 4505 4512 4518 4520 4521 4523 4534 4516 4527 4525 4534 4535 4551 4565 4570 4571 4578 4584 4595 4609 4610 4618 4628 4629 4630 4634 4636 4637 4640 4659 4664 4669 4665 4673 4687 4688 4693 4694 4697 4667 4678 4679 4702 4707 4706 4709 4711 4718 4725 4716 4718 4723 4724 4726 4727 4729 4735 4736 4738 4739 4758 4763 4773 4774 4776 4777 4778 4777 4785 4786 4771 4773 4774 4777 4781 4783 4788 4791 4794 4807 4816 4818 4825 4828 4838 4822 4831 4837 4841 4851 4854 4870 4876 4888 4889 4900 4906 4909 4910 4917 4919 4920 4926 4928 4934 4941 4943 4945 4948 4950 4956 4951 4948 4954 4958 4960 4959 4962 4969 4982 4986 4994 5000 5009 5027 5025 5029 5033 5037 5036 5037 5040 5032 5033 5034 5039 5045 5050 5045 5076 5077 5082 5083 5106 5107 5114 5117 5137 5138 5143 5147 5153 5156 5171 5182 5183 5184 5185 5189 5182 5189 5194 5201 5205 5213 5218 5221 5223 5230 5231 5243 5255 5230 5228 5237 5245 5248 5259 5260 5272 5278 5281 5287 5286 5287 5298 5328 5329 5333 5335 5337 5339 5341 5346 5349 5350 5351 5358 5359 5360 5374 5376 5359 5360 5388 5401 5406 5410 5412 5413 5414 5415 5435 5436 5441 5443 5448 5446 5448 5449 5464 5465 5466 5469 5470 5492 5493 5494 5509 5520 5528 5530 5537 5541 5542 5559 5562 5563 5588 5595 5596 5601 5618 5626 5627 5641 5667 5679 5685 5693 5695 5717 5733 5734 5754 5755 5757 5758 5759 5760 5761 5771 5774 5780 5784 5785 5787 5788 5790 5800 5811 5814 5810 5811 5794 5792 5803 5804 5812 5814 5815 5836 5852 5853 5855 5878 5879 5880 5883 5889 5897 5911 5932 5934 5935 5936 5938 5939 5941 5951 5955 5950 5951 5954 5970 5971 5974 5977 5978 5985 5986 6013 6024 6031 6037 6043 6052 6051 6053 6076 6096 6101 6106 6108 6115 6125 6106 6107 6104 6114 6142 6143 6162 6169 6170 6171 6181 6198 6199 6202 6206 6207 6244 6246 6249 6250 6254 6264 6271 6276 6277 6268 6271 6288 6293 6308 6309 6326 6341 6345 6344 6341 6364 6365 6366 6370 6371 6373 6376 6377 6378 6377 6379 6386 6396 6397 6420 6422 6429 6433 6463 6472 6473 6490 6491 6492 6497 6522 6523 6524 6519 6520 6521 6525 6530 6531 6534 6535 6543 6552 6558 6584 6586 6587 6588 6606 6614 6618 6646 6650 6651 6654 6677 6663 6665 6676 6655 6653 6655 6665 6667 6682 6692 6703 6704 6707 6715 6719 6730 6731 6733 6743 6747 6748 6750 6759 6771 6772 6776 6775 6776 6782 6785 6812 6841 6858 6860 6859 6877 6886 6895 6914 6919 6922 6924 6933 6935 6936 6937 6938 6952 6962 6965 6984 6987 6986 6985 6977 6967 6968 6966 6980 6997 6994 7002 7008 7000 6975 7009 7014 7015 7026 7027 7034 7036 7041 7040 7041 7045 7048 7065 7074 7075 7082 7087 7092 7098 7097 7111 7127 7124 7135 7136 7137 7140 7153 7156 7158 7174 7176 7177 7163 7166 7159 7157 7158 7164 7165 7172 7190 7194 7199 7200 7205 7208 7207 7222 7227 7244 7249 7271 7272 7273 7274 7281 7286 7288 7314 7315 7317 7318 7319 7304 7307 7308 7309 7312 7319 7322 7337 7338 7345 7346 7350 7360 7361 7362 7360 7395 7400 7404 7405 7407 7406 7411 7420 7435 7440 7442 7446 7453 7446 7448 7467 7471 7469 7470 7482 7485 7492 7488 7489 7492 7493 7494 7497 7504 7520 7525 7547 7554 7543 7553 7560 7561 7577 7589 7591 7593 7587 7596 7597 7584 7590 7591 7599 7626 7627 7628 7630 7645 7639 7645 7652 7657 7662 7664 7674 7680 7681 7694 7698 7716 7704 7705 7706 7708 7712 7716 7715 7717 7722 7723 7728 7721 7722 7724 7727 7735 7737 7725 7746 7747 7750 7761 7762 7765 7777 7780 7776 7777 7778 7759 7769 7770 7787 7797 7798 7804 7803 7804 7805 7811 7825 7824 7826 7827 7828 7851 7867 7887 7889 7890 7900 7904 7917 7918 7935 7941 7942 7946 7947 7948 7949 7976 7979 7981 7983 7988 7999 8000 8009 8011 8012 8019 8021 8025 8027 8006 8011 8034 8036 8037 8038 8013 8024 8029 8032 8033 8034 8032 8034 8036 8059 8060 8063 8064 8081 8090 8097 8122 8135 8147 8149 8150 8151 8162 8174 8154 8158 8162 8170 8171 8188 8189 8190 8191 8196 8205 8216 8217 8222 8233 8239 8240 8242 8257 8249 8262 8264 8274 8309 8311 8328 8333 8335 8338 8344 8350 8349 8350 8363 8366 8370 8371 8395 8398 8401 8410 8425 8429 8430 8441 8443 8445 8451 8452 8455 8458 8431 8443 8453 8459 8477 8474 8479 8476 8487 8488 8489 8500 8501 8503 8504 8538 8523 8529 8530 8556 8573 8576 8589 8595 8624 8632 8634 8628 8636 8635 8636 8644 8659 8661 8641 8652 8659 8650 8664 8667 8674 8676 8678 8686 8696 8697 8735 8740 8749 8767 8769 8747 8751 8760 8755 8766 8768 8777 8782 8788 8796 8799 8801 8809 8807 8816 8827 8831 8835 8836 8843 8844 8845 8851 8858 8860 8862 8863 8889 8891 8912 8913 8924 8928 8929 8939 8955 8957 8958 8963 8988 8989 8997 8995 8999 8968 8990 8991 8992 8994 8996 9013 9024 9026 9035 9046 9047 9083 9084 9089 9096 9108 9107 9116 9123 9122 9128 9132 9151 9155 9163 9174 9178 9183 9199 9209 9217 9219 9232 9233 9232 9237 9241 9244 9245 9247 9251 9252 9266 9285 9284 9291 9294 9295 9296 9300 9322 9328 9333 9337 9345 9346 9347 9371 9375 9394 9397 9404 9406 9422 9425 9438 9440 9435 9442 9455 9473 9475 9496 9499 9500 9511 9512 9513 9539 9540 9543 9547 9550 9557 9571 9577 9593 9600 9609 9615 9620 9621 9616 9625 9626 9637 9638 9642 9648 9656 9654 9661 9665 9696 9705 9710 9719 9720 9717 9718 9717 9719 9724 9725 9738 9741 9743 9744 9745 9765 9778 9779 9789 9791 9773 9778 9780 9782 9783 9782 9797 9799 9800 9801 9823 9824 9834 9836 9841 9845 9847 9865 9868 9883 9884 9887 9890 9892 9899 9908 9910 9911 9915 9918 9922 9926 9923 9944 9947 9948 9949 9958 9959 9961 9973 9954 9976 9978 10001 10000 9992 9997 9985 9995 9996 10005 9999 10001 10002 10009 10041 10045 10051 10070 10071 10073 10100 10099 10100 10101 10102 10105 10082 10083 10082 10086 10112 10113 10114 10122 10124 10127 10140 10156 10157 10158 10159 10162 10163 10166 10177 10178 10180 10178 10179 10191 10186 10198 10201 10204 10227 10229 10232 10234 10246 10247 10248 10249 10250 10269 10277 10278 10279 10289 10291 10294 10292 10304 10324 10339 10342 10343 10349 10354 10371 10370 10374 10376 10379 10405 10406 10405 10403 10411 10412 10411 10419 10422 10435 10437 10438 10437 10440 10427 10421 10432 10434 10439 10449 10442 10469 10471 10476 10480 10481 10485 10507 10508 10511 10512 10513 10523 10524 10529 10536 10552 10563 10569 10573 10575 10576 10578 10596 10602 10630 10647 10657 10659 10684 10687 10692 10693 10700 10702 10703 10709 10714 10716 10727 10746 10744 10754 10753 10754 10755 10759 10763 10764 10765 10769 10770 10771 10777 10796 10807 10813 10818 10825 10830 10835 10836 10849 10858 10873 10882 10879 10882 10886 10902 10903 10931 10930