Skip to content

Instantly share code, notes, and snippets.

@yancya
Last active Aug 29, 2015
Embed
What would you like to do?
『ホリエモンからの挑戦状』への yancya の回答 https://codeiq.jp/q/1618

【問題】

  • つなぎ合わせたときの長さLと、N個(1≦N≦5000)の棒の長さが標準入力から与えられるとき、N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求めるプログラムを書いてください。ただし、個々の棒の長さや、つなぎ合わせた長さ(L)は正の整数で、32bit整数で十分扱える範囲です。また、棒の長さはすべて異なるものとします。

【入力】

  • 標準入力から、以下の形式で複数の整数値を読み込みます。
L
N
a1
a2
‥
‥
aN
  • 1行目のLは、つなぎ合わせた棒の長さです。
  • 2行目のNは、棒の数です。
  • 3行目以降のN行は個々の棒の長さで、長さはすべて異なるものとします。

【出力】

  • 標準出力に、整数値を1つ出力してください。行末での改行は有無を問いません
# 便宜上、標準入力の代わりに DATA から読む
L = DATA.gets.to_i
N = DATA.gets.to_i
# 予めソートしておく
BARS = N.times.map { DATA.gets.to_i }.sort
# 最小値を出しておく
MIN = BARS.min
# obj[ex] ||= 0
# obj[ex] += 1
# ループ中で↑みたいなことをすると処理時間が増えるので、NilClass をいじっておく
class NilClass
def +(num)
num
end
end
obj = []
bars1 = BARS.dup # 破壊的メソッドですりつぶしていくためにコピーしておく
while bar1 = bars1.pop # 大きい順で舐めていく
bars2 = bars1.dup # 配列の残りをコピーした配列を、このあとのループですりつぶしていく
pre_ex = L - bar1 # このあとのループで何度も使うので、予め計算しておく
while bar2 = bars2.pop # ループの最初から最後まで bar1 > bar2 である事は間違いない
ex = pre_ex - bar2 # 目標の長さまでの残り長さ(立直<リーチ>長)を算出
if ex < MIN
# 最短の棒よりも短い立直<リーチ>長で立直<リーチ>しても、bars2 の中には候補がないので、無視して次へ
next
elsif ex >= bar2
# bar2 以上の長さで立直<リーチ>しても bars2 の中には候補がないし、
# このループが続く限り候補がないことが確定なので break してループを抜ける
break
else
# 配列の立直<リーチ>長番目の数字を1増やす
# nil += 1 #=> 1 になるように予め拡張してある
obj[ex] += 1
end
end
end
# BARS は最大 5_000 件なので、reduce しても高が知れてる
# BARS の中にある棒で立直<リーチ>してたパターンの数を足し合わせる
puts BARS.reduce(0) { |sum, bar| sum + obj[bar].to_i }
# DATA の内容
__END__
15000
5000
962
6770
2957
6158
5495
6486
4122
586
2810
8076
2700
6483
7157
2766
2196
7557
6922
8445
7324
6089
4821
1188
3806
5096
3008
135
1229
5219
9344
9899
497
3732
4344
8120
9805
6383
7004
4711
4178
86
182
6587
5771
4216
7470
2417
9677
8024
5984
3689
230
4002
8367
2787
2158
7445
7719
6103
4766
8883
1156
9524
1962
9410
2651
8154
4037
113
6715
214
3938
5421
7576
6192
5107
435
1198
395
9912
8797
6720
6230
6642
4973
6034
7090
5166
2769
5585
9901
3830
9174
7078
3051
3324
2721
9826
7376
7777
3998
3299
2783
2383
1801
7363
3807
8439
8137
2023
3684
9407
1451
4694
4276
1937
6040
155
4315
9279
8356
3736
6172
6217
1478
5600
2653
7612
2649
2089
6054
5080
9784
2389
2648
554
4706
3196
4212
6408
5779
7821
1264
3594
4319
9212
797
8906
3553
652
814
6414
1585
8145
172
5042
7548
3961
1688
3063
3855
5768
9148
3086
6842
8141
715
9367
7667
932
3031
5723
4242
4006
1183
2457
5091
8902
4517
6515
9889
8704
4737
9296
1921
7178
735
7762
5802
4090
2876
7984
1409
3612
8016
7463
4435
5306
2210
5078
6047
7839
6221
7483
5276
8790
2765
8640
110
210
1534
2922
5470
1521
8773
8504
6013
9616
6576
6718
4180
6070
9127
5150
4742
9265
9613
4631
4464
4626
7271
4589
266
8187
4054
7167
1586
5481
4863
4086
3236
1240
6862
3622
979
6683
9056
7412
4860
985
7193
7511
7087
7943
7644
5261
8665
1768
9268
8266
5018
5975
277
6062
6020
9389
1931
7111
9806
3583
8744
9500
4732
1818
8559
7126
9905
7885
5000
6482
1935
1174
6613
7574
3702
4158
5123
8110
5139
2029
5497
8660
2926
3453
8600
2680
5063
2183
5725
323
3459
9381
3627
4055
4351
4439
2329
1851
4257
5902
4407
8934
6724
6936
15
1081
2391
5015
4989
5564
9998
8388
9879
1445
8492
3146
9833
2520
8022
3087
37
7478
156
2099
9937
5069
1873
7431
7575
605
6567
3194
5053
3827
220
2035
8687
1339
7495
4027
9108
1868
6897
4970
7529
8428
6708
1250
8158
8194
621
3987
8544
3137
7624
4083
9526
7960
157
626
7659
6640
7392
4734
8325
8468
4405
9094
6523
6231
741
3189
2581
4812
7471
3997
8909
7141
7599
4620
7747
1849
4255
6669
5674
1348
7759
2347
8348
5386
1482
3611
2142
7249
4490
1744
7456
1346
8732
9337
6570
5764
8978
1915
3588
631
2478
3405
389
3378
6076
5699
8594
885
8400
898
8414
3666
2650
7947
8129
9172
1315
7317
2295
6226
7674
85
1577
161
6583
8360
3700
2022
7426
3517
1614
7772
9629
4469
5962
9764
3072
6118
2114
8271
6925
3395
3385
7446
6488
3569
5845
4039
3093
3055
5147
4369
9882
683
3000
3548
2591
240
3826
4912
4188
6768
1375
687
2096
8050
8511
9439
8416
634
758
3948
2307
1179
9068
140
2654
473
2056
1205
9281
5931
3839
8396
7150
3054
4618
4539
188
3819
3941
7595
8737
9705
9040
969
2371
6868
8018
5664
5731
2501
2359
5009
5316
2281
4400
7850
6714
164
2606
5666
9057
9735
1143
3437
8599
4284
3911
6790
9948
6476
2770
5636
4847
801
3202
3311
5651
3560
3939
3497
4420
961
2465
3210
9685
6055
3896
5295
9263
5624
1558
6128
6585
1438
8538
9498
6672
9969
3593
8667
1280
7139
3401
5880
4427
9929
3922
1973
9698
6125
4577
6184
4424
1412
7664
4130
1440
8650
5260
282
5164
4072
281
6306
2533
423
6124
2832
6097
4865
1552
534
7677
470
5002
5595
3754
1595
6461
9580
9522
6524
8829
449
8419
6468
9972
1906
4265
5483
5173
8301
4142
3179
6518
2628
2754
8854
2815
1444
4472
8999
374
5192
7652
7468
5508
2988
499
9827
3270
4557
5245
5341
2913
6363
8212
3817
6209
5778
3607
587
5171
3279
2165
8827
8794
963
3749
747
5111
4744
3304
8593
2260
1837
6367
669
8983
7234
3418
2396
3098
904
5188
6262
4835
1532
362
8101
9317
2726
4995
6347
6348
6324
3215
9887
840
3154
2256
1379
6608
3814
9932
6504
3766
7444
3929
2924
7297
7052
2404
2111
7928
7222
1365
869
7056
7375
2020
3037
7939
8758
4819
8398
9014
5914
636
5605
2532
5420
3708
4077
5342
8347
5735
6345
2613
6478
1613
6303
8176
981
9017
1058
4651
6563
7721
7224
9006
7705
2324
1448
5620
1015
7211
8643
4878
2231
5471
5617
8857
1413
7054
8937
762
8097
4839
7992
3926
5705
2068
6105
9283
5607
2287
5733
4544
8533
8228
6707
4103
7997
4979
329
7505
8118
6624
5354
7255
3572
2374
7758
7523
9541
9993
900
7946
7503
6322
5533
9259
1446
8858
7040
1660
7452
8823
4050
2842
6181
358
6617
2512
8216
2527
2363
5419
2852
8871
778
3487
3445
8273
9886
7651
7761
3354
9534
3019
1381
3371
6310
6867
7638
4110
7966
8735
8550
731
2540
6508
2031
1007
485
4249
6031
2583
9201
2624
5484
3657
6529
415
1430
9489
9447
8229
6318
5789
5426
8545
1299
2013
5847
1782
123
3099
4085
6738
2615
1855
7107
3728
2166
2181
4208
1836
5114
1725
1704
5750
9119
6091
912
8122
2974
2150
2125
7707
648
8911
9908
8598
707
6704
8568
3979
7072
4623
8642
6699
564
4434
8178
5535
3455
2794
1756
6633
4935
941
2548
1553
9475
1213
8166
5928
9550
5088
7608
8343
6460
2879
1014
4813
6928
2048
361
5727
7411
680
1161
2487
7769
8435
6853
892
4908
8970
4069
6351
2424
9759
7359
1373
3780
3139
8961
4244
378
4098
8124
9514
8093
6822
4174
9921
6145
6392
9042
9762
598
6810
8763
3047
563
4983
1569
8248
4193
2026
5099
7462
5599
3319
187
8706
4849
9214
3974
8261
7611
6650
1720
8013
366
7237
6399
7454
2730
4682
7038
8409
6598
4488
6688
7122
4125
9150
2174
5392
4239
4529
4058
4295
9421
7974
122
333
9495
2122
2387
8619
3800
3584
698
7807
623
4465
6808
9878
3355
7941
3468
889
6311
7610
3977
5849
504
2699
8355
8681
9900
460
6763
6433
2966
6813
2661
5172
3101
4395
927
2110
4541
4461
6990
5017
4570
5155
1073
2050
834
2177
3260
4787
5251
8947
3275
5357
5307
8830
1251
350
7177
9237
4200
9277
2433
1501
5450
9807
3416
4553
380
9756
8529
9267
6526
6101
2566
6039
8062
2270
6218
2194
8837
7142
3104
931
9655
6467
2047
2689
3242
863
7486
4259
6584
252
1760
2969
9778
6273
708
7753
7012
7365
7283
5065
1293
4160
4479
4311
5626
6497
9964
4349
859
1709
7020
1273
1087
3064
6365
321
6779
6740
5503
4298
6929
1001
4362
7755
9488
1101
8941
9061
8256
5291
3096
4416
4857
1668
3048
9480
1207
7922
2965
74
831
414
3652
6972
1874
8964
2555
7035
159
29
1919
9022
8813
1020
6400
7934
2498
2015
3162
8123
5510
7277
4862
3757
781
3626
5330
2674
6656
4341
718
3845
1420
2950
492
9376
9156
1738
274
7192
7631
4164
5397
6211
4513
5144
7487
3300
5268
7533
112
9398
7041
8925
2657
8457
7968
6787
8258
3640
8222
7691
2670
6876
2658
2044
6157
7180
9577
6516
6259
6362
6167
7006
1176
9507
5908
4056
2789
3495
9326
12
3317
1327
2745
2975
6532
8405
7391
4378
6890
7609
2916
1887
877
4633
3625
5937
9847
944
5807
3126
8001
6249
8952
5043
3542
6437
8815
90
1815
6939
4724
1550
9626
879
8683
8133
4438
5921
8140
6164
3422
5872
5977
1883
3226
2422
9285
3818
9523
5064
141
180
1464
7163
8469
5886
4977
4384
2673
6783
6663
5695
8383
1202
1222
2982
7596
6935
7621
3849
2845
2686
8211
25
6323
6909
4030
2516
9836
3465
7408
9151
688
320
5590
5511
9331
5566
5852
7266
9370
2207
397
4299
4033
757
9412
8652
1954
1415
5493
5365
8184
3129
6095
202
5428
2668
7914
7418
614
9718
437
7813
519
4293
9458
2598
8899
4079
6346
9120
1810
1476
3234
6113
8986
4297
5168
4689
6749
9290
9521
2088
8473
1779
5868
229
3322
1529
2844
4575
4135
8993
4523
1208
4954
77
9709
581
6758
8781
7650
4016
447
5732
7925
5687
6573
6858
1513
8144
6975
7349
9311
8992
6689
4695
804
381
8979
4012
9262
208
5325
870
5285
663
1460
2368
5363
8056
1995
4455
2058
2834
2943
6835
4854
7121
7260
9627
6279
3007
7410
8520
6788
6156
233
3957
5627
36
6797
9393
8038
9748
5384
9465
4367
8188
4634
8720
3413
635
2894
2746
5046
3448
1945
3458
1061
6531
9314
8291
7725
2306
1831
6875
7728
1687
8860
7996
2728
3060
547
6879
1220
6017
9374
8628
5301
8219
1164
5391
439
5938
1594
9603
7847
4480
3476
8831
3950
5557
9792
4658
1859
8486
3890
7099
8649
3876
4292
4051
8086
8326
5583
6934
3364
1349
9321
3796
146
854
1823
1312
2921
558
8206
8190
3619
8242
5823
8423
9373
3352
1612
910
1190
3644
455
9091
2157
7876
5066
4829
9652
6834
815
3745
5039
1551
2603
3121
3457
8218
2602
6507
2337
8904
5672
9717
8434
344
7232
9100
2558
4340
4501
8516
9324
6747
5098
7328
743
4334
1587
4686
3073
8608
5532
5405
2198
7993
9883
1980
3530
4804
495
5372
1776
1163
3135
9861
2539
4844
3537
1093
1298
1322
7559
8645
2557
4915
317
8713
3473
867
2616
1854
7425
7196
1320
5119
787
2266
5293
1100
5467
1908
9204
7804
370
2579
1891
335
3292
1257
8378
5889
5273
8503
1638
8413
2229
4409
3113
9725
3823
4032
1153
1330
1107
3521
8061
8156
8930
2577
8767
8389
603
8567
9710
1186
8779
3502
3213
7341
1794
1022
9866
6451
4035
8799
4892
6053
4143
5918
3723
6996
8051
8940
9525
5728
4003
8778
7269
5369
5290
9202
7591
2343
425
7303
1132
7115
6082
1673
3727
886
6041
5277
1368
349
8243
9329
6029
7749
5874
5496
5011
6152
3500
8028
1150
5226
4717
838
9408
8788
7373
6104
6000
3492
3128
1645
9122
2681
9584
8251
7522
1911
9680
62
1401
5558
3070
3261
6182
3693
9027
1751
6540
5993
9672
8872
4622
4346
8663
5690
5274
760
4181
3892
3417
2920
1009
1494
7588
4217
1882
7819
3570
5969
4901
6045
7432
5783
9018
2864
8782
9199
9721
2118
1128
7881
3803
1649
7587
6513
9578
6906
2568
6701
7626
8130
5949
8475
6907
1283
1540
4609
1435
7982
9420
7279
7318
7895
6995
8972
2380
5995
7906
4792
2434
970
5781
8654
6983
6051
1003
8967
3482
8479
2711
4951
4382
2747
4769
7958
2285
4518
1475
107
3284
9340
4716
5747
1359
4507
7980
3889
3301
7261
4345
8244
6296
5799
8339
1031
7614
9582
1889
5377
7460
713
6430
723
5878
4052
3220
400
269
2124
475
2946
3636
7089
9560
7710
7931
2685
955
7994
3580
9441
1679
3372
4988
398
9415
7086
7949
8117
5667
8047
1452
805
6933
134
4662
8071
8079
3504
8234
9501
2208
6637
5805
3770
509
9695
9304
8068
1608
770
8945
980
2328
7799
5517
3118
7394
8225
2080
965
7174
6444
2440
591
8098
5940
3916
3084
9630
5190
3865
5117
5816
5216
577
4885
7845
2538
6443
3332
81
7370
8408
7484
5388
6864
1790
7896
8571
7472
6454
8402
5608
2370
5891
9107
6945
4361
7961
5774
1584
3432
133
2513
401
1228
8377
9142
7975
1418
6472
7871
3821
8342
308
1262
2690
6940
4102
2085
924
3512
8116
2333
4990
7641
4173
3737
198
9223
9291
7337
5948
2149
4677
2659
9045
4282
6389
8638
5449
5795
8610
4091
3273
5670
2211
6682
2200
5855
3887
4628
5469
7543
6234
7698
1842
9001
8143
1992
9739
4554
9716
4822
3863
9453
3706
4933
3579
7538
7700
860
6662
3486
7029
1167
9307
2952
1893
6638
6600
2084
3778
5102
6874
1247
7206
4377
4837
1875
3078
5120
4028
5479
1054
8275
4100
8034
5553
1292
5773
3558
6828
7093
79
4209
5031
6026
8324
2278
8611
2379
9849
4132
5563
4532
9682
4240
463
5905
7551
7053
8232
6769
3547
1182
936
3641
2283
1461
1266
5714
4982
4534
7251
7510
2585
4476
7098
5726
4231
7844
4413
8557
9429
8300
4163
7731
5058
774
7654
3799
4823
3854
883
3357
2152
6220
1892
5375
3771
9474
3110
5151
1442
3544
2996
9530
3982
9999
6522
3023
8341
3002
2895
3294
1515
6973
7907
1975
2463
6849
9732
7480
6865
5647
4855
8843
1424
5191
3885
9002
5684
8882
9264
6402
1516
1236
9208
9996
2385
8517
4508
4914
9733
7469
6384
6410
1214
5641
1841
9545
8943
4312
8684
5241
2406
1151
1434
8127
3733
162
7561
8743
9266
3005
7175
4801
7793
1570
9111
9568
7146
6651
4187
298
9227
1056
5591
9656
7568
9024
2614
1971
858
3825
7897
2456
1541
6087
3562
1088
6067
9543
4852
656
1113
3726
8395
6745
1989
7783
4137
6657
8946
9804
487
2985
6319
7190
9454
525
8149
1141
2399
5140
1904
3177
7384
1218
7764
7443
2706
5174
285
6333
154
5965
3191
6908
7903
4316
7879
6475
3245
6848
145
1565
4280
9713
6189
9190
4088
6255
4965
8955
3123
399
1410
9559
5797
3136
2873
1526
5076
7037
9841
3815
5242
2899
1542
4020
7683
9664
9834
1993
7630
9152
4684
2357
1730
983
3426
1799
7514
5680
6965
3873
8008
992
9157
9271
2763
231
5394
8307
3374
4610
7930
7154
2629
5160
6122
902
842
6331
1852
7797
951
150
479
5332
8394
6068
9863
3614
524
6732
557
1650
4171
2261
6767
6676
2912
5760
4206
6974
5256
9366
4468
7805
2011
1123
3241
219
8340
9483
1347
3419
6635
3681
1878
8148
2942
6010
3217
404
4739
2835
70
8010
94
9169
9871
3414
1742
6645
9144
3464
5125
9278
642
4596
3662
6491
8528
1485
1051
5761
4043
6242
1296
5745
5195
5319
9779
6961
3391
3262
3971
4101
6949
9953
597
8555
7058
311
3672
8458
721
9845
2304
8919
9508
8277
4223
1086
153
843
4281
2505
5141
7794
4910
262
2462
4156
9092
9518
7043
9844
4502
2472
2596
7034
9273
5527
2376
8777
9423
5239
824
2804
2288
9511
5416
9768
7094
4394
3267
498
7618
3599
8910
7097
5848
2898
876
9697
9761
6987
5082
2004
7372
1789
914
3466
2115
8220
9422
4726
4587
7530
7083
1216
7383
9967
5518
9726
9817
5435
1784
9720
1603
2414
5665
3784
1168
8987
2954
7161
1065
9110
3379
3568
3046
4816
6376
1956
792
535
1991
4826
6341
9011
725
7988
5101
9355
2239
5356
6660
4922
1965
4655
5431
6885
8020
5288
3944
7149
3434
6446
5947
7702
754
8848
427
516
5890
9090
1934
6866
6905
257
2156
8522
8850
3928
9974
4986
4946
1731
2918
4612
1307
5935
6263
6178
2297
6335
9854
4721
4023
5658
9435
7346
3528
8769
5991
4728
4019
6471
3829
5678
6395
1560
8591
9591
576
7661
6469
1740
5552
9028
5990
3712
5683
2972
4980
4337
97
4473
952
4162
1772
9372
7767
8526
3647
5131
6398
2666
7233
8121
1067
7736
675
8812
4258
3789
9769
1623
7615
7566
6952
5512
5933
676
1506
5994
9820
270
4309
3923
5335
5992
1571
8705
9059
6764
6869
5569
3664
6284
9155
3875
7108
8033
4442
9571
5438
6772
5766
3756
9788
7064
34
5482
9332
2382
5818
7356
8055
4278
9139
2062
8070
5442
4460
1806
6117
9897
9235
1600
9824
4411
6019
8358
2905
9062
3082
9843
1659
6085
8073
4659
6126
1684
6538
8345
1488
7678
5769
9048
3901
3474
2632
2869
2479
7802
6604
5385
7348
3991
7921
9161
3411
4329
3874
1527
6494
5303
5645
6404
3994
412
480
1370
1885
6243
1276
5314
2182
733
2641
8596
6466
9051
5212
6976
5498
3710
2973
6048
4267
3852
4850
9436
2682
625
3105
7344
6151
7704
744
1562
7779
1933
1712
8634
6754
4373
7096
9622
5870
763
3308
3531
9494
184
7665
4861
3752
9312
2838
8134
5524
6942
1626
3074
8532
699
3917
5544
5371
4907
126
9167
4773
3438
866
6382
6752
9775
7809
5440
1428
5225
4487
9907
8822
9075
1321
8404
3694
1094
1241
2159
6015
8752
8690
7518
1948
6615
8254
6137
9352
8023
9238
1154
5932
8523
5863
9141
6338
8560
8320
3786
3942
91
1733
7357
1109
9904
5900
2707
9857
2094
2131
4833
9173
2144
5153
4888
671
7439
7313
5366
6270
1669
6877
8924
5762
4676
5299
2163
3721
8805
4698
9478
8625
9737
3959
8151
8759
4096
1138
9924
2358
8666
9400
5227
3259
659
9005
6616
7734
3870
4082
2604
7102
316
2903
6547
8437
2928
9183
8572
7642
5676
239
232
851
1377
6186
1729
2388
7430
3878
3746
1040
974
5653
674
2145
8376
8496
6072
2238
7886
7202
6056
8733
1677
5671
2945
8072
8281
4228
7904
8659
7014
704
418
9782
6150
8893
8693
2828
2059
690
250
3274
9638
5649
5858
2506
8731
5909
1121
9791
1710
4649
2485
1563
3879
9819
5657
938
8862
7092
8653
8007
469
4755
165
8108
4509
1232
284
8346
3564
2409
6246
8197
6912
8614
4165
6294
6980
438
893
8881
2732
3095
1090
2932
7936
9084
4197
5333
8043
8075
6350
5204
4715
7007
9918
2082
8956
1663
2713
5941
3050
3915
8330
8540
8294
4584
2740
9074
3686
2446
4015
4301
7526
2701
9747
3185
6274
2530
6260
1369
8005
7436
8201
7074
6036
5338
468
9567
2251
6435
429
300
4672
1505
5199
6129
9443
5266
1106
292
2509
3248
3565
3919
618
2867
1092
4385
2246
7919
1675
7028
4360
1006
7494
2492
5480
2715
4288
9385
8531
7938
8135
407
1133
8679
6253
4882
8162
7201
2421
1076
9295
3713
1471
8954
6966
9159
2431
1000
3174
5749
1557
103
6959
8204
4419
260
394
6667
8235
3529
5072
6050
4607
8876
5755
3761
6802
7740
2381
9031
116
7757
1404
5719
6463
905
8514
1225
8279
786
8976
3056
4643
1966
906
9414
1920
7501
6079
6163
9176
5113
3705
7714
5832
5576
5804
8111
4364
9605
5656
2046
1863
6992
1769
9335
2267
6527
8657
4786
3674
9328
391
1502
8874
3022
5822
4046
7295
9053
5681
4848
4425
1944
1096
4073
7382
5071
7275
4920
158
9325
3192
8834
127
9041
9411
5406
9890
4396
5541
2683
4774
3748
6239
5443
6065
3057
829
9054
7869
2101
3375
5414
8878
7690
1780
874
3186
8748
500
4245
9592
111
4328
3782
3613
4700
2286
4260
909
2093
3683
8897
2636
9282
1686
7788
8867
1826
3682
3044
6892
3477
711
1008
6349
4938
2355
9424
5321
9675
2432
3649
6295
7042
2500
9236
9738
2069
6001
3141
2563
8223
8989
5451
4645
1746
2078
3675
4321
4859
39
3527
102
9063
972
6149
1131
4113
5089
2464
6947
5237
1177
538
7763
4119
4342
5777
3604
6593
6423
3669
6155
9378
632
6315
2176
785
1630
9837
7461
6895
573
7258
1427
2526
5323
2170
4930
5559
4932
5861
8323
6038
82
1927
697
6750
1230
3658
8157
784
8969
2067
5491
720
6511
2263
9476
6008
3801
2819
3323
6954
4836
6452
7878
283
7555
9377
313
701
8661
8543
6627
3567
6266
2086
7628
8990
4960
4687
9287
9258
6852
9244
2576
3969
9561
1752
2546
7688
4820
3877
4146
3840
4152
9660
3936
9771
8215
7890
9684
119
4828
2016
4457
4202
1732
43
8351
8944
7398
6141
8027
9300
7902
8542
5445
4902
6807
8938
7066
474
541
855
7908
1422
7420
1634
20
4578
2493
9146
5573
6275
3435
2989
2907
8025
2326
4747
5589
5612
4891
7228
5211
3618
1049
3804
5434
9086
309
2617
7320
5422
1253
9145
8633
2671
1910
1960
1719
357
9448
1787
22
3918
3550
1578
8031
8689
1329
1894
7182
7695
5254
9255
4254
1144
4022
9046
9812
7643
8289
5136
8957
1727
1978
8717
6816
9750
7846
9299
5579
9816
6387
1853
6729
9965
8386
2330
5157
246
2906
6544
2959
1661
9187
9832
291
2968
8415
5265
5027
5106
2497
6159
5395
3283
2562
1050
6773
5913
4991
5987
3888
3402
8433
4614
7830
2587
6733
2072
988
44
5737
529
7378
878
3115
6678
6984
9679
7801
2777
8714
6278
4112
3282
8901
821
2120
7491
7970
8851
925
5717
9455
4994
6841
3291
2811
6873
5410
4365
7323
4290
1098
8334
5347
1097
3773
2053
9600
4431
4619
3383
2395
9194
9342
1599
5669
5240
9333
3020
7770
9669
2151
5827
7044
8699
8272
2818
7267
4331
9961
7207
4790
4151
9853
7989
1554
4404
6339
9987
1536
6670
1069
7693
4463
3508
2993
6709
3467
8454
9593
2258
1192
3219
7884
6187
4693
5986
2977
3635
6276
7537
1066
9995
6049
137
9700
176
7940
9289
3983
6703
9740
3212
4795
4426
2240
8115
1045
2837
8002
7715
1215
4289
7393
8461
6969
30
3953
2753
9129
5614
364
3489
8290
450
5183
2722
4459
64
7143
2813
5648
4597
5446
5149
5613
8236
6777
2107
1074
1533
4159
9869
4066
4665
433
6765
9503
2535
4147
845
7577
3750
4972
742
4074
968
6247
5606
2525
7467
108
4976
6216
2331
7215
6711
3097
8991
4380
2511
5996
2040
1636
4723
2508
5297
6630
5927
4776
793
5061
5794
6814
3348
572
2477
7998
1085
6924
9880
3764
5571
443
5883
5346
9547
7025
6811
4593
8375
1114
4386
2824
5230
6632
5220
5334
4274
9757
8058
4318
8384
6844
7450
3254
8328
3077
2168
5531
1211
9339
9714
7924
508
8153
1124
6028
9674
4009
1914
1615
6596
8146
1922
7905
7935
7723
3510
3952
2609
4604
4909
2187
7131
2643
5109
4858
2032
2517
6702
2524
7464
1111
1913
2203
6658
4650
4213
454
273
7856
3642
3483
7244
5785
4877
9055
186
7605
4061
864
624
8425
9117
2365
832
456
2135
9230
2720
3513
3602
4545
3225
5877
2311
2574
5572
5979
2480
4811
8636
4515
1604
3592
7389
3114
3862
8620
9846
1439
2862
4809
9633
9876
7336
5663
1835
4366
2467
1680
5462
6946
2005
6018
1864
6543
1510
6094
7118
5616
9970
5751
4375
3171
4443
9272
5675
4109
9052
654
6578
7979
4681
8296
1886
7969
267
5044
6143
8575
1429
7050
4896
9760
1030
3362
8953
9930
1248
2979
6448
3776
2626
7520
4782
6280
1318
8997
5812
3346
2197
9115
9872
5843
2522
3188
9360
7113
8327
3080
7339
8502
2967
1590
5631
7422
6914