input.txt

18313
2404
10479

7011
10279
1496
10342
8918
3162
4525
4368

17242

10920
14072
9754
4435
9396

5915
2602
4032
3303
2685
1856
1334
4865
6385
1733
5328

8899
5482
3195
7837
8986
13794

25121
22211
21257

6360
4007
5124
2266
6943
6966
3887
3427
1255
5266
6119
2841

6167
3883
2776
5894
2013
6930
6613
4637
5259
2347
3550
5639
5117

4530
5961
5956
2503
5060
4770
5240
4123
4089
6794
3333
5244
4415

1733
1209
4458
1223
3859
7728
9793
8350

2278
3241
4668
1836
3669
2996
1772
5016
6294
6367
1080
5964
5547

4793
13744
9478
7979
1490
12490

6770
7282
2059
5242
13237
9365

2230
6498
1352
3846
3863
6205
5803
2646
4188
4431
6380
1526
2620
4438

24331
23578

4199
5126
5725
1123
2415
5427
5789
4856
2610
4833
3398
4239
1432
5122

5013
4939
11760
8419
5706
3765
10182

11795
9688
1712
2091
9651
13022

10393
11862
1672
5431
6812
1866
5599

2036
6561
4097
3467
4739
7656
3252
4322
5068
2345
4155

3090
1228
1270
8407
8118
4996
7157
3944
6230
2728

5669
2113
3076
1290
7673
1022
5805
5128
7912
7862
4955

20640

4131
4874
5220
9947
9739
1662
9418
9684

4875
3073
1151
11911
10310
10793
10307

6979
4265
8322
3518
1855
4912
5481
7124
4664

19975
16112
19450
7231

3909
4743
3794
4448
3200
3447
3331
7011
3345
3935
6750

3900
14850
4890
9625
4832

23682
1375

7463
8112
10624
1105
6625
5157
5839
1019

19089
36719

5372
7085
8536
8717
6255
5961
3198
7729
3055

4406
2263
6686
1458
2377
2740
1284
3045
7121
3070

19161
10515
1027

7782
1703
1864
3611
1039
2394
3472
6964
5824
8011
3341

56690

5107
1876
4973
5485
4325
6079
3187
3565
2875
7137
3887
6763

2633
2151
1105
2400
5338
3382
1330
3945
6556
1670
5526
4281
2168

5382
2347
4225
1905
4672
6706
5747
5808
1159
4878
5923

11148
8722
3896
15697
3499

46749

13315
20966

1625
6338
7882
1505
4226
9948
6438
6012

1003
10033
5066
7756
10151
10719
5299
5629

4466
6290
7220
3657
8261
7348
8525
4531
4892
7833

24723
7817

4234
4428
5810
2091
4301
1378
2342
3872
1167
2073
6867
7026

7005
10018
3954
4497
4951
1283
5383

4152
4390
8731
8521
5415
1029
8200
3769

7224
12281
8337
8969
13938
9651

10923
14358
8896
8401
7073

3934
4424
4538
4371
2335
6363
1264
4331
5107
2270
3109
2547
2304
5911

4600
5674
2620
1846
3804
2387
4094
3648
4241
5593
2974
2101
1621
3939

7429
9425
9653
5835

13414
4517
15783
3867

2287
1019
11604
11910
2591
2468
10543

13050
1396
13959
6883

6303
2889
4047
3954
2245
6672
4574
5731
5879
2837
5859
4812
6785

10290
10131
5605
3321
2122
6331
9107
7937

1786
1362
7409
2093
3901
1306
2089
1558
4163
6118
6270
1929

4224
3864
3922
3609
2496
2246
5397
1535
5499
4932
3684
1348
3437
3665

2973
4506
3971
2511
4563
3168
2687
6249
2593
6470
4100
6309
1316
4362

14966
2940
11485

6675
16873
5695
14706

3953

5620
1678
3630
5015
3277
4957
5288
5555
2860
1750
2795
6170
6308

3671
1354
4018
4730
4070
1685
4478
1918
5532
3970
3751
4890
4277
2737
5535

14799
8129

5254
2065
1282
2407
5174
4549
4326
1201
3372
3906
6234
4937
4234
2149

5194
2519
3555
6929
4367
4547

1024
37240

3693
6526
2679
5434
7924
2974
1754
4287
4744
4187
1348

6598
5963
6035
5404
3270
1250
5947
3037
3927
3702
5255
1640
6476

4499
5207
1991
4613
3088
5024
4737
5160
2450
3582
2605
2573
1100
3732

1633
5663
2415
4039
4957
2697
5428
5050
3979
3428
4563
3770
3635
4012
4773

7377
6189
10812
6905
11196
5394
10135

10008
2868
2630
8542
8897
2718
5831
4460

1303
4771
1574
2960
5070
1596
5530
4177
4210
6465
4179
1000
4460
6173

6654
1378
2148
8704
6875
4511
7540
6078
5585
4030

4333
5953
5095
4782
3651
4673
3267
6389
2358
2120
3684
3034
3420
1322

8922
9535
16357
16552

1378
1039
1262
2067
6491
2776
1352
4914
5832
1369
6105
1384
2474
1704

6256
2538
4701
4090
4077
5333
2777
4082
4640
2542
6356
3065
4855
2535

6510
3709
4197
4344
5906
6852
7398
3578
3308
1239
3817
5676

5441
3368
1752
2629
1923
4711
1667
3701
1350
4764
6439
2341
4052

6407
5327
1229
4834
6008
1302
5595
5260
3680
3220
3154
3353
1942
1740

2356
1908
3058
4668
3641
1663
4199
2190
6067
3923
3288
1978
6110
5330

7020
2487
6521
1084
6582
1784
7861
2759
8077
2961

68314

2160
15170
2267
3867
6851

8543
4118
22260

5313
3525
1483
3613
5798
1472
4020
5607
4391
2502
5512
5535
3755
5590
3668

25502
7623
15508

2138
1227
11355
1288
7062
5391
3994

7738
3667
5000
1691
7322
8054
4540
2353
6870
8475

4289
6415
1251
4933
7224
2608
2320
4432
4637
1395
6575
5581

6841
1161
5617
12505
6274
9171

13548
20154
20682

2843
7363
5967
15256
16032

7940
6992
3940
3100
1334
1389
5182
6666
4030
6116
3036

35234
19273

7268
10689

1846
4211
1504
3780
3789
2017
6279
5001
2341
6350
5169
1966
2640
5574

2125
8432
8339
8130
3506
6115
4684
9548
3300

6848
1274
6463
12007
10719
10590
5616

4471
1304
1635
5960
3702
1747
3658
2446
4724
5675
1739
3170
3556

9134
12963
6987

5728
7877
6499
5909
1119
3090
5033
4884
3151

10675
8053
9237
14206
11710

49154

5999
3861
1836
3451
3673
5193
2680
6068
1743
5600
4793
6211
2967
1021

24720

8749
11674
4039
5341
14256

4553
3893
1528
5490
2417
2392
4023
2430
4649
3163
3673
1378
1957
1055

10777
4742
16291
16430
12295

6502
6052
2944
8166
7567
3580
5957
4691
1623
3269

1013
5809
16958
4994

36633

8535
13662
24448

6651
7911

19793
2436

4671
4420
5322
1215
4952
1193
2387
2799
2748
1343
4123
1715
2978
2148
6050

2036
4670
5444
4584
4220
6061
2834
2319
1370
4572
4249
4144
3236
3812
3487

55521

3845
1473
6794
4597
5566
2735
2660
6402
2515
3439

3772
12809
5790
10817
9729

1788
2476
4333
2940
7232
3582
8604
3742
7644
4823

6128
6737
5712
4168
4465
2183
1217
2257
6326
5966
5699
2985
2290

5190
4155
10754
9830
4507
2165
7208
4409

4256
4158
1941
3124
5852
3376
6411
5508
5072
2374
4189
4032
4957
2050

2737
6772
4468
2072
1214
6231
7077
6100
6990
5676

7474
4524
8778
7129
8151
7975
7277
8672
8097
3847

29172
7125

50466

14169
22037

4483
1801
4863
1920
2776
1407
3998
1142
2664
3920
5708
5481
5701
5159
3654

1960
4419
5933
4941
4511
1120
5179
3447
5285
3675
1333
1418
4595
4140
2353

1995
5588
1443
5681
3439
6178
5795
5144
2788
6232
2620
4665
5624

37076
7362

3885
8268
10947
9084
3016
10383
9594

16223
16281
5352
11764
10192

5248
3151
7341
8125
10671
13510

1759
7635
7021
3620
7640
4967
3662
3840
7613
3948
1820

4010
3936
7375
8060
12396
8236

5033
2739
4296
5564
6502
3501
5637
5826
5862
5579
6416
2277
2471

4325
2621
1600
4290
15494

6834
15459
10418
12560
6382

8598
1089
11386
9538
6933
3943

14268
7172
7680
15936

5695

69893

7293
4968
7862
3210
1924
4742
3519
1095
5922
6335
2405

4233
3819
7282
10018
3820
5380
9377
8889

13183
9964
4473
12469
9862
6567

4903
1198
5238
1582
1820
6080
10178

4554
6315
2818
5956
2491
5291
5056
3699
2843
1243
5430
2175

31126

5392
1590
3738
2507
2817
6963
6140
4606
2814
7044
1282

12230
1430
4283
11385
2557
6868

3871
2558
1957
4058
1935
5738
1513
5744
4130
3321
3760
4155
1063
3694

67474

2215
8962
5442
7390
6223
3648
2390
5464

5125
3842
2131
3414
6085
3353
3660
1593
4395
2664
4987
2352
5693
1391
1661

6017
5013
5243
3734
3116
1541
6456
2806
6143
1344
5977
5422
2326
2164

33377

5950
5168
1348
3144
5760
6974
8537
6664
1248

9040
4510
5642
8547
9407
5058
6158
7726
6731

4182
5246
2686
4196
3809
3253
3260
3162
2703
6373
6136
2904
6356
5038

3368
11040
5793
13747
10478
5166

11697
10072
8434
5732

5244
6374
1877
2902
4263
4835
2283
2086
6044
6343
6232
2849
3694
6392

13062
12405
12869
16366
1652

8036
1720
7759
13661
1370
3505

5885
1708
10440
7438
11480
4904
8387

4788
10326
6143
11063
9649
9384

5849
1935
7411
4694
4435
1321
5301
2096
2422
5484
6560
3070

5008
5405
9444
6355
13150
12686

1618
5831
1957
1288
1382
2946
1926
1828
1646
4823
3637
1309
5727
4450

66234

4016
4075
4551
5869
2866
2461
1055
4712
7220
1973
4650

2387
1102
4558
2290
1969
3624
2383
4059
4877
3439
6891
3819
5824

3440
11447
5522
16700

8373
1356
7249
8484
6767
7990
8778
2235
5995
8511

5466
6088
2583
5235
6093
3089
1570
6112
3668
2187
5582
1380
4800
5529
2987

12323
4775
11105
3805
7671
6737

3197
1256
4539
6383
1476
2134
6785
7337
1229
4965
5055

13128
8149
4426
8087
2873

1695
8214
7147
7216
1070
2801
5033
8103
7750
5749

4082
1630
1958
6113
4486
2111
1486
6451
5630
5682
4558

10475
30751

5397
5067
1178
2106
5557
4847
1661
3469
4908
2590
4686
2118
4495
2994

12590
12902
8742
15433
2777

7451
8722
7302
2269
9592
6162

1907
6741
4442
6526
8289
7479
9481
1642
4982

2001
12803
7255
13545
10713

14621
25826
20771

1055
8331
7422
8400
2208
6688
8425
6883
4192
4725

9970
10127
2777
3933
9274
3791
9906

2779
1118
2823
1563
9917
6065
1863
1885

5053
1922
5356
8266
7335
4260
8730
7307
3140

4340
1080
2120
5498
6769
6170
2944
4677
1155
4676
2420
4945
5941

14838
3844
19712
16283

1906
3672
4274
6550
6072
5299
4493
3348
2804
3747
3208
5359

59156

6128
5959
12262
12166
4945
9635

8095
1757
13656
7215
2545
6298

7873
6515
6407
4182
4911
3966
1942
7281
5082
7446
5545

3876
5618
4226
4445
3915
1250
5469
3872
5157
5539
2894
1357
1419
4214
3009

3364
6618
1432
7583
6192
2529
2076
6231
7333

5028
2989
3801
1895
2367
5747
2724
1304
3085
2524
1295
1022
2613
4239
4413

3418
23885

3895
3302
1097
3150
1379
1815
1484
2074
2616
3395
6100
5488
1006
3046

1951
8238
6010
3652
6640
7990
3900
8191

6978
3025
1966
7152
5963
7326
1866
2507
4764
1434
3194
3326

3081
6828
6495
3257
4236
4938
7090
2826
6614
1341
7098
6771

18885
3826
13103
1193

16653
13676
19294
13878

7460
4327
7335
4898
6259
7941
5940
5603
3095
5674
2886

8680
4662
8044
8210
5886
9057
7917
3258
5995

2800

31568

5423
33845

8988
13780
9059
14650
9824

10327
13747
10937
4594
6882

2696
2860
1070
1662
6098
2369
2821
3603
3593
5347
4871
4967
2211
3330
5226

8520
1896
1906
5172
6845
1565
6366
5509
5068

4047
4661
2384
1904
4705
5402
6650
6120
4834
5897
6492
6200
5868

4130
1530
9654
9306
8529
2508
8918
4040
3717

3245
4195
11698
10053
6635
4749

12283
11894
8168

6418
7151
4827
2391
8643
2315
8664
3547
6900
4418

65083

5164
1748
8739
4945
2604
5493
5310
3763
6011
4091

4342
2566
6021
4067
1385
2486
4444
1713
3380
4253
4720
1602
4814
3234
1739

13603
22634

7845

4139
8832
7441
1967
6707
7981
3416
10633

4808
9206
6975
4257
6024
5176

10639
9329
5010
7215
4522
8168
9936
9792

4326
4601
6508
2501
3866
3060
2188
6429
1014
1383
6937
5313
4392

8977
2420
1013
4267
9689
2955
5583
2947
5570

5067
1139
4531
3001
7698
2028
8025
1424
6837
1357
2186

5433
19739
5321

5019
4714
2688
5290
1593
1320
1703
2978
1476
3034
3538
2825
5819
5547

6441
1104
3128
7940
5977
8434
4493
2139
1617
4933

3219
3273
12383
6076
11222
5523

8875
1005
4958
3234
3196
5527
9875
7306

1591
6031
2124
1224
7008
2559
4540
7670

5927
4323
5630
1067
5482
1939
5428
3416
3494
2469
4287
5538
1190
4234
1734

10808
15234
14069
10497
7697