Skip to content

Instantly share code, notes, and snippets.

@andriihomiak
Created May 29, 2018 17:43
Show Gist options
  • Save andriihomiak/4693809e5a8c7430d3cb0156b95ae895 to your computer and use it in GitHub Desktop.
Save andriihomiak/4693809e5a8c7430d3cb0156b95ae895 to your computer and use it in GitHub Desktop.
Лвба №3
"""
Функція яка виконує розбиття масиву
Аргумент kind відповідає за вибір опорного елемента:
m - обирається середнє значення з медіани, першого та останнього елементів;
значення за замовчуванням
s - перший елемент стає опорним
e - останній елемент стає опорним
Складність - O(e - s) (лінійна від розміру підмасиву що розбивається)
Повертає правильну позицію опорного елемента
"""
def partition(l, s, e, kind):
# обирано середнє значення
if kind == 'm':
median = (s + e) // 2
items = [l[s], l[median], l[e]]
middle_item = sum(items) - min(items) - max(items)
if l[median] == middle_item:
middle = median
elif l[s] == middle_item:
middle = s
else:
middle = e
l[e], l[middle] = l[middle], l[e]
# обрано перший елемент в якості опорного
elif kind == 's':
l[s], l[e] = l[e], l[s]
# коли опорний елемент - останній то додаткових операцій робити не тре
x = l[e] # значення опорного елемента
i = s # індекс який буде розмежовувати більші та менші за опрний елемент значення
for j in range(s, e):
# рахуємо кількість порівнянь
global comparisons
comparisons += 1
if l[j] < x: # елемент менший за опорний
l[i], l[j] = l[j], l[i] # міняємо поточний елмент місцями з розмежовувачем
i += 1 # сунемо розмежовувач на крок далі
# ставимо опорний елемент на його місце
l[e], l[i] = l[i], l[e]
return i # повертаємо позицію опорного елемента
"""
Функція швидкого сортування
Повертає відсортований масив
Середня складність - O(n * logn)
Найгірша складність - O(n ^ 2) (якщо масив вже відсортований або близький до відсортованого)
"""
def quick_sort(lst, start, end):
if start < end: # якщо start == end то цей підмасив вже відсортований
# розбиваємо масив
q = partition(lst, start, end, kind='m')
# рекурсивно сортуємо підмасиви
quick_sort(lst, start, q - 1)
quick_sort(lst, q + 1, end)
return lst
# зчитуємо файл
with open("input_quicksort__10000.txt") as f:
next(f)
lst = [int(i) for i in f]
# обнуляємо лічильник
comparisons = 0
# сортуємо список і виводимо кількість порівнянь
quick_sort(lst, 0, len(lst) - 1)
print(comparisons, "comparisons")
# сортування довільного масиву
print(quick_sort([3, 6, 2, 5, 8], 0, 4))
10000
3976
330
4559
754
3679
6549
2774
5267
2726
3800
2082
4320
4031
7240
9145
2841
1723
7328
9710
1374
3490
5246
1791
7493
8503
6719
4861
128
8409
9472
4355
7470
1265
3725
4947
4581
1534
1682
9544
1876
7734
1603
3125
7646
1044
6234
5276
6239
5696
6120
7737
6633
3701
4666
3250
8584
3367
3677
4786
5405
8679
2892
8487
9680
8801
4932
1333
6706
8034
798
252
5922
8396
9734
8817
8280
6243
2112
5296
2956
3724
785
4951
2027
3870
8434
2676
1038
6442
3572
91
2719
1944
6845
2177
2273
3828
7868
2604
4159
2624
5801
3086
3598
4964
4199
2292
2001
9085
819
6852
3881
188
5256
9507
6125
5915
5482
8515
504
8591
9033
6236
4357
5912
486
1800
2781
2787
3311
9313
2663
4532
149
2689
712
3670
2874
8301
7305
1173
8730
7024
1181
4729
9430
9098
9315
7892
9094
8539
3106
6567
3333
4188
7547
8401
6430
2821
7863
5125
4428
4782
4113
4657
7681
3315
397
4259
4712
7064
3935
5478
9944
513
4353
2098
138
2067
6928
6799
4553
530
1189
4745
210
8181
9893
6150
7577
6188
3336
6344
8668
4261
4600
9058
8738
6693
5110
3258
1092
8617
6872
7126
3281
574
7391
5399
8113
3330
6808
7316
6405
8140
7602
2403
5758
4630
4203
6816
7026
1689
7923
5176
3697
588
3251
9054
8709
9102
8293
937
8183
8673
4589
1706
9068
7841
7704
7604
101
5857
4922
1656
7908
2114
7658
5886
8450
7429
7544
2392
7079
3497
7540
1863
7824
3827
9811
7010
3656
5835
8019
3718
1594
6160
8203
5112
6543
3435
2402
6271
1985
1927
1095
4075
3980
7686
3922
7290
2682
9512
271
9373
267
7047
5040
826
4733
2214
6377
8527
4441
865
2368
2183
945
7000
5003
6917
4920
6447
6652
2301
5736
615
7475
8429
405
9712
6728
2594
2434
5070
7882
2314
8400
5665
3674
3170
7762
2942
5242
1376
7171
8578
884
340
2447
5864
8262
1616
9335
6778
6039
1353
4479
3686
8488
2479
8849
1424
8531
6413
5367
5951
500
1601
7876
8745
9298
2961
8805
7725
4094
5382
3319
1788
5077
6566
5187
2875
4638
4078
3813
8896
4975
9654
2824
342
2903
8139
5873
1681
6161
5080
9698
6452
7084
5311
8913
3853
7402
1190
4488
258
8086
4390
4403
8672
2701
5323
9457
9100
9667
1929
3240
6283
7789
7128
29
2506
8528
8413
2927
9286
8618
9762
9324
6662
3109
2393
6630
4422
3023
3056
5598
2407
5054
2150
6818
1161
1871
1299
4748
3710
6021
5421
6584
7947
6262
3646
7562
8686
3811
8803
5064
5139
7942
2912
3393
6869
3609
5612
2748
1664
7448
7563
5331
3267
2184
2348
4424
3142
4079
9914
8422
5018
1750
399
8715
8687
5251
1856
1329
6479
4157
61
2228
2102
2369
245
3286
5329
4958
9985
5755
9277
7121
6578
1330
3334
5512
9939
2564
7427
8765
4800
5095
8804
8932
7645
5235
9355
6883
2947
4938
1
614
7291
9522
9664
9278
9674
6628
6743
9570
4165
3098
3850
608
5740
1305
9360
3055
9964
6526
8834
5844
7059
1134
8901
5773
1256
887
8443
377
4974
5019
6402
4801
8895
6629
9771
859
1475
4458
5126
4469
4026
9269
7620
6417
1392
7885
8216
9624
7320
908
57
8300
2913
8785
7511
5671
1721
3559
3887
5840
9982
1727
6151
2894
8656
44
6600
3844
3808
2972
4857
2100
9233
5098
5149
99
8394
2524
5471
111
6207
8574
6914
7474
9550
8602
8282
488
1654
1416
3917
7361
7575
8258
8877
9737
7549
9925
4062
1517
876
544
5516
1516
5464
8245
720
2350
7700
9547
5415
1165
1306
611
4233
9596
8915
9065
6856
4036
8844
3664
1610
4562
5689
146
6265
9087
987
9521
8868
7076
6394
2124
3790
1028
6474
8667
3432
22
8659
3431
9958
3416
1963
7344
8270
1957
3695
8331
2
5363
6501
8492
4817
3241
8858
6051
2331
2570
9059
8384
2813
1634
225
5749
8558
4677
9651
6009
4641
5726
447
3085
9787
7262
3282
996
6291
5652
9394
3130
4005
833
9410
6550
3584
3768
2101
1779
4960
2623
2456
971
9427
2044
6208
3560
9363
2157
7356
372
3341
4508
7115
8431
5745
320
3909
2453
739
9312
6666
8116
796
4076
2744
3517
1704
3470
464
9128
623
2509
3359
260
9219
7617
6996
3506
8712
6179
4361
553
2380
5274
8553
881
9232
3503
2809
2413
2107
8655
3015
821
8345
4830
613
9714
3021
8212
8995
4708
8809
1130
7251
6388
1356
6061
7384
5129
2816
4007
9951
8156
9572
3395
1925
6678
7579
8306
1785
9195
2009
2028
7670
1343
1644
310
6460
8910
2326
4226
1157
2390
1082
8074
2584
1113
107
4072
5014
6702
3156
3168
1327
1734
1509
4914
8391
8549
5817
7757
3176
9963
5221
4096
5636
1378
6990
5190
7808
9120
9338
2923
734
8440
863
5157
7472
747
5701
2917
3381
3918
3812
5585
7796
4169
9802
9370
3038
2702
6364
1923
5180
7881
958
6821
3028
6372
3871
3299
5534
9349
2329
2536
3791
2278
9783
8446
4087
7395
1651
8155
9305
8363
5114
4303
2126
960
2495
3
8055
2070
3867
4519
8438
7581
8731
3895
6299
1332
5871
767
6361
5017
9072
1966
3036
8828
546
3619
4415
5498
3880
6534
4012
8290
2096
7707
7601
2712
1011
8696
7013
1692
8739
7242
1998
1537
7502
2709
4292
5185
8657
312
5142
3065
2270
7781
6386
8543
8722
816
4047
1441
1108
758
8233
381
5121
5865
4558
9301
3723
8039
6969
2188
2557
6337
8348
3324
4371
9765
2830
8070
2119
461
947
8797
5128
8761
151
1639
8052
9959
5634
9471
1622
5965
4463
4576
7578
5987
5744
5800
5927
6847
618
7993
8551
6435
7652
6858
3687
6297
6089
5066
8298
5827
6138
8333
5290
7295
9995
2817
4644
8423
1454
8000
6080
2869
8018
2396
8038
9205
5212
366
2944
2462
6342
4048
3535
9633
9117
5107
6066
9587
5376
6591
893
3262
3607
2297
230
7268
4825
407
8914
3239
765
3271
4221
7697
1621
813
5459
791
2007
1180
7452
166
3101
175
6260
7438
5791
6129
2052
8867
3415
5721
3729
8239
183
5770
8589
5232
5419
97
9403
1372
5660
1595
2718
6627
7756
2343
581
7468
3757
7623
332
638
3764
8254
8922
9751
6401
1456
5802
3581
9579
6429
1824
3795
3841
6889
5131
5918
9413
7991
9672
9534
4059
6517
4785
3544
3067
4704
1159
9648
3564
3692
7861
8790
4721
3339
8838
8777
7803
5163
3919
2863
9183
2020
1979
9097
1903
6241
10000
9264
333
3308
203
3923
6276
4182
8320
6456
5957
3249
5134
9851
3857
4455
171
6204
4632
8701
7675
8975
7098
2706
6551
164
9008
283
6062
1739
4691
4833
64
2036
8523
856
2330
8774
3134
5099
6721
298
3066
7040
3647
6959
1193
9208
5448
2099
8935
5698
6380
6060
4597
2494
7085
5379
115
9622
8726
7304
1429
3549
4502
2736
1718
8102
4136
7130
13
8125
4254
6995
1900
4176
2628
890
9439
5234
3323
3597
8115
523
2519
6254
6307
6742
2176
8510
5062
1043
371
7684
626
9724
3712
7498
8966
2473
3203
9399
7187
6168
5715
4440
420
7023
222
3029
3073
9605
184
1398
2311
7351
4763
5195
6602
534
1121
5381
909
1994
5831
2377
6004
3608
2904
5825
5703
8498
9758
4485
9514
6930
433
1001
9676
3594
3511
3425
3858
9896
9161
3579
182
233
1707
5710
8145
9495
6465
5113
3461
2309
9422
8720
6507
1362
1901
8417
4923
1170
4006
8099
8742
3093
3386
8577
3035
9062
4682
930
1902
716
7672
7709
6613
8353
3999
4568
2279
4380
7838
7319
6237
7062
9969
4343
1763
2496
1449
2812
339
9332
5617
4293
9539
53
4534
4617
4893
5580
4584
2987
2523
1599
3225
2668
9151
6216
9246
1371
6739
5260
2133
7692
3202
1758
5453
7616
7312
4909
9029
2759
5214
2621
7506
8717
3834
2749
466
3513
944
48
4445
5606
1530
2735
7260
2259
9621
4719
4962
3947
4013
6220
9497
2900
8768
5714
2525
3233
6057
5406
6840
4240
723
9358
5344
5401
7163
1365
4364
192
8636
2644
1255
3472
5264
6353
6015
6339
6201
6003
9421
4831
3502
7794
7976
6253
6809
3716
8041
5882
3902
6034
5659
9588
5262
3060
673
4448
4262
2529
1613
3177
2512
2192
9154
1635
484
7450
288
4123
4358
136
5849
6558
8587
5609
8379
4187
7278
6279
8977
7157
1403
9662
5621
6079
2882
65
552
204
3951
3223
7052
9782
1433
1893
1892
7736
148
4977
7401
1938
473
1040
5036
4229
4777
8988
5467
1342
5902
5967
9279
8967
3172
853
2637
3753
52
8460
7550
4908
5879
3963
2889
8595
5294
7419
7259
3057
9367
810
1273
2804
378
7819
7944
5690
4907
1518
7388
4889
5038
8996
6097
9016
197
1320
8001
3989
1019
3717
5063
6196
5159
2771
2620
6734
7598
5106
5884
8835
8962
7283
3765
1238
9042
4153
7357
4200
6282
1097
9247
2137
9542
8178
824
2287
2179
3521
1491
1829
5093
1780
4103
3356
5021
6944
98
3018
3452
8421
3792
8757
261
9990
2097
7702
602
3700
1117
6685
5626
1349
1854
6135
6171
2486
8330
8468
5734
6760
8911
2969
8174
8816
577
8631
8291
2155
2561
5775
5000
9850
8770
955
1919
6647
8336
1175
7664
3829
2998
7045
4265
6946
5514
4186
5434
8231
1507
2828
9079
4310
8395
3488
7583
9868
8979
8613
4255
8030
1469
7028
995
8746
6221
341
1773
9303
4807
3837
6857
8196
7915
5760
6885
9681
9638
8538
7890
4646
760
5895
7548
9056
8494
487
1852
2914
1655
9844
8095
2965
4565
7421
2076
1632
2860
5075
7505
7216
2705
911
8026
9915
5587
3705
4697
7451
5013
5866
5286
5525
1819
7068
8215
6968
4015
2556
4572
3967
5961
9207
3636
3972
3244
8011
5253
2911
4228
7780
5661
8840
3448
2711
7196
8081
732
7615
7714
2678
9122
1943
6156
9486
112
4225
3489
437
7776
4501
5946
3153
8435
776
6684
8474
2855
7168
7215
4263
7538
6504
1141
1748
1271
2474
6300
2258
9999
9323
7648
6140
9998
454
7954
442
6556
8940
7941
9504
4394
4703
2498
805
8042
5177
2951
9553
5985
5266
5932
2555
7434
1210
2428
1541
1825
46
5384
691
3654
1904
1690
5566
2200
8692
6056
87
1820
7372
8093
7261
1249
180
3078
5009
2008
1867
1882
8985
4744
9703
6896
9865
668
9359
8960
7323
8261
3424
3854
7390
6326
8339
2548
7425
9142
6292
713
9469
3685
3898
5455
844
4322
7527
7332
4931
4104
2241
8748
9840
6775
6577
2652
2616
6242
4160
3762
8234
1017
9543
5995
8012
9345
905
8189
3442
6519
3789
4608
5725
195
9831
7680
9443
2761
1177
6492
1202
2477
4661
1204
9972
7021
1442
3197
4614
5934
6583
2853
6971
1341
5852
7872
5904
5875
3094
8839
5999
694
4039
157
4211
6833
9435
3335
4207
3507
2596
5605
1328
9089
3820
2928
1166
631
8650
6048
2081
2321
3904
5430
5101
9481
692
8439
5293
5119
2547
3623
916
524
4981
6673
1457
9126
1391
5577
4362
3219
3110
7934
7159
3436
2142
4032
6476
7899
2940
9665
6287
8592
5977
314
2345
409
2386
753
1949
4752
6024
1364
847
6133
1784
362
5184
2290
4895
6403
9659
7795
910
9375
4622
1360
2842
7968
367
1461
4419
9318
5686
7572
9739
815
137
5579
4878
1291
6521
2215
7199
6359
8961
9053
1806
1736
5346
2571
1570
355
9480
3399
4781
2589
2520
9926
2958
5320
797
6143
8550
4764
4278
1196
8148
7195
4121
5377
5024
8180
5826
8521
3082
9971
4626
4383
1427
568
5414
3964
2050
9489
4899
5590
8973
4611
448
8837
3320
1749
2073
8945
9288
6147
8082
625
4739
6829
558
1890
5517
7537
7176
878
8343
404
4205
9253
8397
2398
3855
3145
2484
5997
6116
4163
275
6715
5711
6531
8947
7036
8496
9464
1973
4917
1348
2275
3318
1889
3869
5821
7981
4613
9936
4936
714
2898
8406
4912
598
3824
8796
8536
1234
2632
8576
3446
6586
4927
2057
3451
2053
6697
4736
480
2741
2481
6418
6765
9066
1503
5563
1419
9150
3458
6988
8729
7058
8119
4070
6174
478
9878
15
892
6843
8841
7414
8427
1665
8529
6104
3582
2973
1149
7275
1844
4366
6931
4494
1068
874
8211
7657
686
2742
9133
9296
9245
3287
475
1106
7070
8067
7904
3316
2806
9311
651
9956
3776
8502
8552
4398
6498
5794
3049
5694
2291
2094
281
4416
7586
2125
1703
6119
9236
7785
3331
5633
1647
9727
5229
3673
1221
1067
8930
5395
3391
975
6805
8079
2168
831
6854
7676
6121
6252
9319
882
6943
1874
2006
6126
3997
5656
3583
5677
9160
4107
7921
212
5248
3611
2537
5247
2733
7980
4116
8352
6574
5561
2411
5486
3617
1195
2686
3354
6043
696
6791
8882
5727
7349
6263
2072
1592
5615
3766
1446
4518
5986
7661
308
9389
3368
495
7063
9032
8800
4235
2799
3464
3778
7805
7926
5250
7353
4662
3849
9694
4095
1827
1947
1798
7556
3944
5781
9717
3678
6320
7837
4184
4132
250
773
7108
8226
8781
4615
4242
177
76
508
2039
8524
6677
1552
522
2626
2132
6414
3557
9129
83
1807
6446
2159
4311
3205
3289
1198
8389
8993
6986
1809
8236
9170
3434
8377
8541
5752
5387
5153
7875
9574
2543
5971
5795
6145
8263
7879
4449
4724
1490
5104
2382
2867
4126
8703
4789
3878
471
9496
7077
3526
9272
5975
110
1940
2655
5982
9760
1436
885
1179
4073
4270
2185
8201
7711
2999
3159
9254
3548
9794
4319
8665
2400
7436
1389
5351
3551
5034
9113
4127
8283
190
8859
9827
6774
1155
7233
4024
8225
3588
4696
2609
7342
1556
8866
1074
8110
3846
2545
9444
4796
8362
4557
4111
389
1559
9789
6030
9699
3116
3087
7593
2225
5733
8983
4213
4541
6163
8999
5591
9293
3037
8776
6336
6185
3970
4185
5380
8411
2113
9532
2480
6311
542
8847
6999
1073
9166
5022
4134
1661
1158
8689
2143
4633
6206
3469
5876
4587
1741
6581
4809
297
4429
1286
32
3536
4872
7334
1995
7763
8784
6473
8938
9341
5573
5037
9986
6462
4896
1578
9499
4698
9796
3297
9611
8548
9670
1544
7136
3659
8408
4305
7211
7903
7640
9347
8949
8307
4980
6992
7246
7898
9910
9216
5368
8364
4738
5
5785
1652
1687
4282
7382
9082
8341
593
9886
2274
39
2207
4142
6146
8124
3397
9957
9562
582
6665
3115
8976
264
8065
9281
768
7346
4819
1916
6948
6222
8904
9229
7464
5292
640
7338
209
5682
672
5569
9474
8721
70
8049
1883
3270
8368
3380
1642
5032
743
9738
8157
364
8238
2807
4969
3043
9432
8303
2445
7869
2037
2363
272
2475
5213
9602
1792
1958
2276
2446
7545
162
8612
5091
4802
1233
4172
1524
1696
2617
7978
7444
9441
8371
4701
6789
6468
3423
5412
7341
6730
211
1969
7004
7276
6469
4998
7846
7270
9163
3414
1408
8506
1047
3230
9962
8939
6475
682
1402
30
7392
6399
1991
949
6069
5647
6638
4193
9260
2765
5192
6851
9719
5488
7019
2664
2467
4038
9690
2535
6396
6416
4109
5643
1091
3622
7857
8278
956
8354
5998
5001
244
6749
8317
8795
7964
7902
6902
4506
6867
3524
4241
2334
1383
1319
3936
7296
5584
6373
1208
4312
4168
6404
4418
1462
1014
2286
299
121
5420
8894
4406
5550
1579
3234
6284
5370
6796
7147
309
3891
2079
2423
589
4901
9157
4482
5583
1268
9655
706
7753
5442
1608
1641
9416
4942
413
6722
8699
6328
7300
1870
578
8020
1046
1059
5285
4982
5206
5317
1623
274
4805
9280
7856
1999
5850
4681
4222
479
303
4813
5316
5011
6905
3385
778
4795
6980
7587
455
5499
4283
7487
6032
3896
9401
2294
3404
5557
4571
6688
1959
3004
9433
3301
5004
1838
658
4171
3259
8818
54
784
1853
7481
688
4301
9036
5073
5681
4700
8603
1322
6184
7447
2710
7239
1455
5575
6038
7012
8786
4930
5614
9494
6732
2755
7044
4231
9180
1842
1066
8177
5877
6827
8670
1659
4468
2441
4125
220
5358
7733
388
4395
923
7710
6953
8153
6964
7209
5560
7190
5373
8906
4812
8728
1308
9700
5446
8089
9950
6256
9346
9952
6037
8530
2674
9374
4158
5981
3667
9224
7327
8874
9186
8134
6123
5055
7014
2466
4010
2450
7237
2160
6423
1593
3658
5082
4548
6987
4
1434
7888
7574
4088
6381
7148
8693
3797
3208
6478
21
1618
756
7701
3690
3117
3596
9221
1700
6246
6197
7308
2918
5364
9983
1230
9960
5027
4058
8111
929
7551
5644
3264
952
8256
357
7082
1699
1187
7631
9491
1321
3306
1569
6938
9482
8743
143
1435
775
1596
247
1220
344
794
7257
559
5625
3422
7335
9741
3261
8596
8271
6619
1302
9777
6828
8571
9393
4055
3915
199
7817
7193
4190
2221
1954
7463
3763
7499
7630
2197
4669
270
5623
396
2675
3616
5148
102
9706
9597
2601
1866
8909
7150
6082
5386
9456
9395
9524
1550
1841
96
7235
2090
9006
5241
9881
2351
6346
5793
1172
3396
9576
353
6010
3401
3357
8888
1290
5484
7667
9168
4139
1672
2920
3959
6078
9833
1077
3449
2551
6972
6047
2239
9792
8707
9152
4451
8210
4346
6202
3662
491
8360
2427
5976
4972
2810
6027
8309
3641
1980
7773
9903
5237
5211
7735
379
5222
925
8467
5571
5462
2585
8214
988
2455
1562
8304
4514
9039
2328
5565
6112
6895
9684
1591
3732
8414
1285
2095
8965
8374
6632
2566
3328
596
1538
4277
6007
4850
2612
8415
9826
5140
7122
8471
8094
7373
2743
7273
4249
3467
34
1246
6443
7569
284
3888
7369
1388
8826
766
9911
8585
5048
3402
7107
9725
1564
5435
1167
7203
5426
6790
4046
1007
1796
3463
7982
9227
7217
9780
4778
410
7288
9839
5042
1960
6846
7698
2820
6000
645
4400
9513
232
1422
2295
3409
4692
4500
1941
6580
7522
4352
6913
9500
6470
2261
9701
95
9404
693
9273
4396
3682
2672
3453
8533
7352
7337
4003
2606
2284
3355
8642
2471
9308
786
296
1835
1885
3091
2146
4260
8154
1609
1810
5848
7696
4986
2248
6692
3639
5485
7410
6655
9900
3637
2303
9541
1089
2080
8120
1311
3527
2635
2800
2544
2296
7935
2189
4100
4061
7350
5762
5078
231
5772
9194
3265
6463
189
7724
7442
7951
2795
6624
1678
4269
940
2360
9855
9810
1228
3222
436
5669
9106
7409
9415
3543
3926
6876
5524
1352
2223
4021
440
7973
1440
1153
8407
9339
8694
6086
5783
9405
1259
9149
4717
564
9005
5664
5663
818
769
2429
6310
5313
8676
5592
8021
3843
9800
5170
295
5804
8724
9452
6523
7114
9723
8811
1865
6054
4882
5891
8883
733
3430
4251
6177
8024
6050
5209
5402
1174
1504
4498
370
1670
4302
369
7037
2231
2784
503
3748
1266
4037
3522
8442
10
6203
5906
2051
2219
5674
5261
6497
428
7771
3684
7961
4788
1674
841
9134
3932
1527
2075
5845
8077
3361
7642
4335
5858
3996
6744
3657
4523
8235
2438
4953
9660
4714
311
5984
4945
3856
8943
6620
2187
7977
5497
2307
7238
9838
1813
4245
7851
4834
7992
1897
3942
9879
1277
1432
8143
1542
717
3713
6102
8711
8864
6343
8390
5255
1521
9387
416
6703
5389
7844
9895
8135
174
8228
4609
8772
4324
8285
974
9268
4606
5278
8361
326
4280
3528
7155
9465
6803
4956
7792
6316
3481
483
2387
3044
1533
7596
4648
634
7055
6223
8850
7411
982
9859
6711
2873
3809
2580
637
8459
5554
2936
8808
1199
9693
6604
1076
1968
9317
3892
1169
9912
3786
2700
5204
6694
1981
8453
5297
3730
8766
6599
4481
3663
3547
1395
3866
8980
1053
9652
8465
6240
4315
156
5718
9691
6824
4141
345
4928
2106
1535
8194
2818
1002
9604
7906
8833
7396
9025
6659
328
3450
1753
229
7368
2282
205
8072
460
9115
4902
9074
3050
5136
6683
7755
6002
4328
1390
2047
6921
8806
1100
6763
2858
3128
1236
2685
7117
7649
5705
1125
2768
7219
3253
6815
868
5716
1474
6073
1557
854
8048
2092
5322
9080
3631
1272
5925
4290
5160
9310
4183
7477
3388
5818
9424
889
2789
2364
9880
9144
6787
6740
3228
6897
2264
7445
2266
8615
7408
7170
1845
4531
9722
4536
5522
5943
7080
4299
4034
7441
9923
7367
4890
6022
1116
5487
1862
3745
3589
9924
7883
5650
2935
5319
9834
7576
5539
6731
9238
468
8167
9420
5374
4064
1114
2691
4592
8482
1296
5469
9918
9158
2084
285
8616
9266
1952
7202
2250
4108
807
4156
3438
7582
4784
4756
1701
8131
1837
1483
1948
7503
1582
5520
1380
2249
2857
9075
599
9577
5051
690
687
9342
6982
5202
8393
2041
7532
1879
1855
6440
6680
1278
1604
6099
4284
9137
3769
742
4029
5537
2979
2317
4564
827
3930
4397
1974
3777
7440
6366
730
3602
8666
5269
759
3254
7131
3901
8561
6962
2130
2723
7041
9977
7192
7799
4753
9835
4579
5356
1828
9188
1614
1235
78
6773
3338
7674
1626
9860
4699
9685
521
9889
1031
2971
3538
307
147
527
6410
3821
9778
5878
8878
9307
9876
4573
3620
8058
1085
4685
2829
3383
7322
1869
360
218
968
6842
579
8546
5774
6304
4384
781
8852
2980
1913
6483
8562
1787
1887
8036
6449
5899
1156
4667
8053
2071
5198
5493
1713
4780
9282
7175
9987
9031
708
989
414
1275
4915
7135
1186
7523
8318
4074
3939
7158
5830
6385
4295
4686
6515
7412
2198
6529
8372
8507
1823
4150
7355
4727
7329
4983
3681
69
337
4605
3378
1385
3568
5023
4065
3118
1394
6525
8563
7786
2549
1737
5823
1126
2315
1154
6137
5165
652
9517
1905
1344
3689
6836
770
7979
9437
655
6911
6293
8580
4653
6777
8861
6696
7089
6426
3366
7743
901
1057
8610
7932
4427
2244
7253
1935
5548
8187
3263
4083
8941
6502
4234
1738
8719
5645
9018
6314
751
7424
4874
8112
6716
5613
3139
253
1054
4338
4308
301
8338
6686
8329
755
9836
3105
3780
1989
6597
7460
8737
1975
9720
2401
1293
9092
3476
2922
3314
5631
9024
2016
9109
1288
9793
6961
9289
3899
8716
5546
4818
6389
624
9189
7051
9614
9805
2156
4996
3638
9479
5468
3835
9961
6997
380
8863
3372
443
1575
8169
5901
2966
5881
3794
6565
7559
1104
1843
1683
3283
3052
4735
2526
1984
3213
2872
2285
5217
8229
3669
5343
6363
7629
993
9718
9578
9417
8582
9125
1567
2203
1423
8572
6085
1458
5846
2773
5347
852
77
4336
2055
11
6178
3196
1345
2354
5181
6920
9744
4860
8908
7515
1369
7566
1832
213
804
8752
9099
7662
7507
7726
1486
7125
4495
9426
6910
476
2777
6893
3840
9994
2925
8767
3907
8096
4713
6974
627
6422
6757
7046
4386
2138
4214
7722
3290
1977
3998
2932
6663
4086
6641
1317
7691
6656
8141
5029
1229
3017
2306
3465
970
7685
9257
9477
2131
1143
8517
3987
8986
3924
3441
2573
9250
3945
1404
402
7087
5257
3973
3982
811
1548
5277
6249
6169
8068
8386
8109
7750
5461
4935
8355
9450
6190
5007
2827
3456
7180
7966
4885
4583
6434
4879
6122
7820
6379
3352
5958
8387
5649
6266
2507
5936
6564
7917
7997
7376
4382
2181
8064
7797
3872
8594
3418
2003
81
5771
6797
5161
2066
1510
6154
5291
2876
783
1983
8252
4025
1039
7744
1822
867
569
5930
2163
8244
1370
9037
4387
3214
8230
1410
5843
5931
6058
3788
8061
2298
8764
8725
3954
3868
8522
8747
3884
8144
4376
5053
2716
4598
6294
6461
4863
556
1519
4237
9642
2217
176
1192
6457
1818
8565
7880
2680
4997
173
417
8946
37
7742
5960
3886
6049
1928
9201
3914
6863
9883
2558
7397
4329
3699
7457
5545
41
7406
6879
9283
3937
5684
7284
8022
8579
1129
3567
8162
4309
6764
2899
8942
2634
1107
6750
7489
9501
9863
9799
1213
7830
7097
8710
6458
4678
7509
5754
5735
9979
2846
5856
9696
4389
7565
4069
1409
1178
869
4421
6026
7393
3166
2063
193
873
4276
9843
4803
7102
17
9453
6070
6238
2645
2344
897
7975
6067
1351
8456
1000
4042
1615
719
9412
9573
2780
4404
9807
2043
814
9506
3633
9146
3575
5378
8220
5072
6108
5394
6117
3273
6813
3157
671
6994
3100
9515
5137
991
3379
7172
1232
8773
5258
2220
6094
9705
3649
1263
8383
6687
6547
7818
5199
4090
7127
2454
830
450
9970
583
2878
2045
7732
8951
9528
4618
5359
8749
3158
2562
5646
3096
1577
659
4875
9974
8279
2993
4373
8288
5729
1714
8690
639
4344
2740
9397
9292
9234
6288
977
5746
1122
6352
1987
2583
1808
5921
6614
6575
391
6615
4740
3292
6301
3830
8204
2915
2764
5279
1797
5594
1508
8881
3539
7546
4497
3410
8890
6835
7804
4149
927
7679
8380
9402
8286
6888
920
7299
3269
6891
5031
8066
1598
8335
9704
1324
6011
8175
6268
6527
5006
4377
302
9906
3787
363
9171
4883
2347
8404
731
1298
5839
5188
7933
2478
3046
3802
3629
1849
5326
3676
8441
5147
5813
3653
9153
8727
7006
1499
4840
548
4774
8900
653
8626
2775
5924
5245
4709
5111
6044
8622
6227
3034
7613
3257
5526
5067
3154
5662
6870
1023
9656
4821
531
9803
3864
8123
5588
526
2614
2527
5008
4918
4040
3164
4077
7654
8308
4525
4166
1201
6351
9540
2840
2575
7214
243
5806
6770
1447
5500
948
1920
8779
9885
20
8025
689
9601
72
7905
4799
159
3966
6491
5239
2444
304
5814
3720
2681
9398
6540
5812
6822
4314
6157
7387
6621
9284
1831
2649
9708
1581
3215
6141
8916
4731
1588
8184
5532
9981
5868
9223
7854
1478
1459
3421
4201
6783
2324
7139
2489
1061
7166
9932
6616
2565
4550
7787
215
5861
2333
7035
2864
6093
9096
4507
9369
9888
4434
6826
6012
3643
1270
4943
8069
7389
4913
5341
2435
9736
5041
7609
4043
5197
1765
7814
3558
1811
8063
8031
8128
7428
9000
4582
2440
965
5635
4028
1139
1282
2990
8005
8292
3600
6859
535
6865
7931
4555
5880
4151
7945
846
4668
662
2997
3482
8250
9538
1742
67
1657
3836
8733
6646
7359
7439
664
1526
565
9594
8462
5339
2268
6464
338
8968
7738
2237
9856
6792
2534
6313
3419
3492
9832
4533
9190
3604
8926
3940
1754
8136
9130
2419
1489
5581
3483
2002
9445
3642
3990
7423
2122
6495
3136
8425
808
728
7911
9067
6285
1142
9460
3014
477
5141
9847
8322
8312
8819
2717
1094
4446
3146
425
3655
6645
3377
8083
6970
6321
9127
9121
6180
2607
6568
938
9328
6919
9356
5889
7778
9014
7149
2721
3374
5533
2760
4503
412
1649
8887
9478
7761
3248
7315
1437
5551
3592
2038
2452
1705
5863
3122
7112
1896
5724
4499
5948
8007
8607
6675
9354
9333
4239
3746
9921
8505
7901
8328
2656
5808
2861
6908
6801
780
750
6325
681
6528
6182
6524
3187
1136
266
9187
50
5648
7134
7113
1625
566
5338
2627
6882
5191
3847
3715
8013
7309
7486
1817
1833
9034
9527
462
9791
6545
9759
327
4135
6927
4099
1218
5117
4244
6606
4884
1413
2930
683
8658
3555
1279
1497
9502
8147
963
3242
7801
8151
9093
6658
7573
9081
1163
3650
8192
6248
8843
2243
1774
9364
632
5321
9620
4603
6640
7713
3839
6244
8477
8448
7539
5306
1386
2974
5933
6532
7536
5458
8547
5723
7895
748
650
4894
6111
1956
8101
8621
9600
1488
4173
5911
699
3969
9785
7918
2662
8924
1482
7534
6109
6850
7398
2805
2108
6596
1323
496
1303
4470
411
4433
7996
4504
280
6259
2281
9155
2926
2690
5074
8899
5610
3961
1182
6590
4478
779
467
5481
2352
5169
5076
4045
2376
9612
7078
2588
313
8953
8221
7972
8027
8087
2643
3546
8599
3952
7873
2280
1961
8645
2491
1500
9295
541
7749
6834
1611
9487
6369
7069
9493
6516
8132
273
7758
2977
4152
3805
3369
9819
745
8778
9090
7897
7083
635
8433
9997
9484
9920
2850
1241
839
86
1804
7081
6436
9061
8925
9140
2208
9466
7227
4903
1358
3985
3238
278
7989
6485
300
6053
8357
3771
163
2854
727
8647
6958
6368
6979
5728
2791
1513
3042
9919
5472
7839
24
1514
9326
5201
3346
9235
2476
3822
8185
1669
2024
4017
1368
5327
2823
2880
8569
7659
2976
3708
7095
2116
7555
6226
187
6131
9244
4954
7765
7022
4509
537
825
4164
8581
3285
8342
8327
3003
5087
7983
2383
5460
1361
214
7325
1133
9824
2388
7987
6855
7458
1764
2139
7793
7495
14
6511
2405
1988
446
501
5597
3793
5564
9386
325
7727
8885
9929
5748
622
9533
3920
1930
8264
2459
7953
9372
6382
6098
7054
1018
6324
8478
126
8511
1686
5544
1472
9251
838
4300
4968
1907
5768
4472
8629
3160
152
277
6698
8314
812
3981
7889
2269
452
3147
4512
9043
5620
120
6553
6081
8978
5309
6880
8240
4060
1080
9105
7207
6487
8470
5956
4057
2340
1747
5423
9892
82
8744
9625
782
4180
540
7514
6983
4663
8897
2533
8889
6187
774
9679
7324
8759
4114
2042
7712
5083
5282
1964
2193
4360
4693
9593
3411
7330
1283
2332
1939
6723
976
7665
7816
7864
1576
2984
4970
1004
8981
6298
6533
140
9551
864
3983
2793
8956
3925
9377
6538
6494
4052
4049
943
1217
385
5010
2336
7950
3007
100
4447
6488
5123
6183
5739
1250
619
6860
979
5330
4266
2909
4837
4806
9809
5079
2358
1858
329
7585
5203
8537
3207
6428
5205
6340
6441
9285
9908
1715
1463
6700
9649
793
3974
2587
7104
1782
6950
8681
1629
9646
1695
5870
6676
5409
1262
3569
656
4892
1243
2449
2252
4625
4306
8190
3343
7922
7272
123
2907
1042
2568
4965
5408
4973
3499
4369
4995
7521
7363
8428
8267
7091
1041
8875
5391
9989
3772
787
7639
6035
5407
1450
5357
9967
9136
2487
9755
7336
6496
9003
8305
2254
6745
894
2242
5411
5737
5743
4291
8281
4432
6601
305
8653
5088
1617
6903
7920
8870
1826
2033
8200
9917
7600
4841
5056
9384
7301
1377
7611
1347
7362
6175
4516
2245
4888
5069
3738
3123
9274
8464
4824
7859
3095
6376
8534
3612
2406
7625
1814
7456
4783
7473
529
7719
8289
899
3885
3371
6649
2472
4330
3112
803
7597
8158
2069
7105
2384
9454
6412
7560
5081
7173
9209
2201
792
3217
7143
2671
8484
835
954
1492
6136
2247
5337
4865
8568
9695
75
7813
3875
4247
6755
2905
5923
2210
1839
1953
6544
8991
5792
9740
3206
4810
3137
7969
4538
1698
9049
4334
4474
2389
481
3651
5742
7599
19
3405
506
820
9192
2469
219
9063
5720
1978
7003
7518
3373
4527
8678
3661
6358
4720
2919
3995
6455
6063
7721
118
7960
9463
9862
4407
2752
5271
8780
8323
648
8032
6781
636
8807
7740
7302
990
4642
8046
3348
9423
2737
5335
1185
592
2323
8485
6155
7267
7788
6289
459
6390
3874
350
3785
3069
9299
7812
7834
2838
3247
9682
1719
4976
2145
4412
6954
1549
3455
3376
4385
567
4933
9564
3921
7213
1666
1768
6956
9510
2779
1972
9021
131
1627
3640
871
2603
7400
4224
2395
4439
5562
757
3088
8163
2897
4106
8257
3975
8266
3149
5688
315
5549
5243
1485
5226
8351
5829
8483
8416
5851
2934
5288
375
1183
9647
2359
9204
4706
1326
4528
6025
1367
7591
5942
1088
9825
2884
4770
8432
4174
1310
7197
2964
4577
6290
2757
5265
6371
9686
4650
4993
5383
3903
4456
4957
5799
3135
9798
8268
7161
1338
2460
6508
6952
5298
6668
8789
761
8382
4984
6898
9004
1476
268
2128
8195
6096
3593
8172
4317
9178
607
2605
1115
4760
6091
494
4115
8884
7535
3444
2945
7847
2031
5658
8418
3842
5283
7528
4966
5979
3237
6095
9095
1539
3275
1407
8191
1431
7394
1951
7092
4822
282
2713
8525
4250
7317
7432
5345
9255
5896
8704
4877
8326
7011
8251
2105
4921
6355
2463
6453
3340
4368
6710
904
4014
1881
8359
1724
1543
401
5216
3625
9743
4843
5700
510
4563
6643
4119
1062
5916
610
234
7497
5853
2191
1212
7730
1484
7321
5476
2499
8294
5168
6735
3832
6901
3515
7747
3107
3382
6674
4197
1147
1375
9754
538
9641
2263
9678
5429
7970
5432
2648
6681
2457
7849
4220
2235
9304
9498
7431
7224
3707
38
942
8045
8501
4217
2862
2994
9606
279
5837
1859
2310
737
3460
6164
6729
5994
2569
7543
9776
5628
3365
1646
8708
7647
4631
1580
5315
3195
7124
7066
9537
3929
8654
1209
1051
5604
2572
8508
3025
3508
8663
6397
6210
520
6198
2123
1554
9934
2227
2960
704
1281
4001
1553
9108
1247
4567
8544
3445
6303
512
5914
7303
449
1128
1297
5619
517
1884
5425
8160
7810
4405
2865
5196
5263
3351
2062
9728
6670
8512
7693
18
4274
6766
2631
9044
3873
6229
3865
6439
7741
5556
4120
7001
122
2349
6228
9556
1650
2669
4289
6415
4766
7552
822
3274
6212
9325
3550
1757
1304
2798
2814
8117
1010
8597
2636
9595
1693
453
2357
7416
7589
2778
158
6110
7018
6193
4442
7307
5790
415
1112
9752
5789
3743
1430
7236
49
2770
3906
1016
6454
1025
4326
8912
8037
764
7049
9431
5897
8509
9639
403
7891
6679
7666
7465
8137
2256
4054
4178
5970
2151
5227
1735
2602
5045
3291
9214
2517
4961
5642
3303
1506
6752
9644
7232
9871
3204
5275
40
7651
8880
3509
4987
9993
392
3051
6500
8476
3668
3953
2832
9788
1152
2000
9035
5763
5052
9566
5404
3606
8500
3949
5328
986
8150
8349
7374
573
9470
8519
6194
1751
4881
9237
1605
5200
5143
612
5302
3774
7138
127
1769
1448
8646
7090
7807
1274
1702
132
9609
2492
7644
1421
3823
8590
5463
721
8907
1894
8854
6040
7241
5990
562
7641
1168
8891
7542
7610
498
3475
9975
5935
2801
6830
9103
5332
207
1102
4855
1479
6031
7263
6825
8340
857
8740
2029
9849
1551
9813
3630
600
605
7313
2391
4093
8098
8106
5059
287
3819
9523
9742
6861
5489
4337
5950
685
8640
8644
6754
1144
2888
3266
1045
3199
8133
7595
4853
1531
3848
8751
5798
2325
1135
2758
7258
9485
7984
1631
6411
8963
6726
5452
950
7093
6672
5641
8598
9968
1761
5156
1264
7848
4020
424
8344
2120
7435
6334
6165
60
3825
6036
7103
3201
5929
6395
8664
4718
6991
3428
5228
6318
3817
8662
1316
6609
7985
8741
129
8825
6218
8381
4687
3603
5898
7123
7998
3224
4621
8820
2089
9894
5020
1222
8762
7039
2422
7832
8015
8713
5854
964
5841
4018
248
3890
9107
2046
2546
1717
291
8921
1340
6264
359
124
1762
2202
7952
7938
9873
1720
2212
423
1962
9769
6603
3337
3946
3672
9181
9626
8461
2451
9249
7418
5049
2694
9048
2164
7870
9721
1387
8822
6761
3104
6522
5765
1123
9027
5859
918
2078
6384
4011
1162
322
7186
5807
8255
3576
9425
3272
7230
9520
3360
3742
2167
9409
2732
2639
2852
1540
5417
7723
5304
8559
1124
8669
1691
2017
5966
9455
2608
5639
3911
5945
6664
7144
5530
8223
9795
2651
2174
45
9351
4296
9329
3734
842
3779
3977
9334
1668
3183
5318
5699
3938
9818
2786
829
5969
4281
1150
3403
5676
2468
4832
677
7946
4223
398
9529
8639
9689
8275
2728
9933
1211
6782
7699
6868
6200
4413
6090
1337
9473
1480
1793
6486
2283
654
595
6653
3652
2513
8449
5558
9779
907
5454
8075
4761
8873
5502
4393
4905
3190
5433
5352
5505
5215
7310
8545
2667
9526
4540
7271
3905
9182
3595
1079
5475
8129
8398
3948
6211
509
9132
7375
7245
3960
1096
9563
1671
170
2196
6582
2747
8405
5133
5252
2981
667
3304
8469
2782
9569
8412
6660
9045
2826
2404
8481
788
7959
2647
3955
393
6933
5025
3429
221
1860
3876
6431
7746
4273
9580
4145
5492
3556
2941
7930
1933
168
4484
3750
7594
1411
1399
6341
5786
4022
5953
7607
249
4845
490
2697
5179
9383
4554
6923
4431
9775
3553
3231
5832
7221
4457
1451
7340
2013
9897
356
6348
7525
9560
1547
2825
4676
7449
6886
6570
7971
2619
8454
318
7479
4331
1231
9084
3965
8295
8794
2802
7071
2318
6033
2218
4771
6142
4453
8426
2230
4656
2766
4750
3026
9677
9899
5805
66
3384
9306
6148
3958
5731
8059
5513
9947
6811
6759
5393
8127
3933
4219
7191
3818
629
7936
167
6233
4911
6866
5815
7156
1799
5375
3529
7852
9806
7116
4342
6014
6481
1568
5173
8775
4349
8845
3562
7671
4823
643
5155
3006
6877
4887
51
2058
5847
5189
4192
3210
236
3688
9368
7167
665
3537
3740
5570
1710
5811
1716
5536
2503
4758
9661
8218
1630
9711
6955
3683
519
2337
2158
7129
9118
8090
1583
7286
5764
6963
1012
5572
6055
6935
2327
4071
617
6960
3574
5450
6841
5422
6689
6712
4363
368
7663
9327
2432
7529
9745
7764
5342
9767
9909
8227
9988
9663
5719
5766
8376
9692
2508
1725
6848
9519
4655
3120
6083
9902
7433
7965
2995
1645
4985
4288
7751
518
4535
3561
7484
7417
8697
3831
4570
3758
8173
5608
9991
7072
8479
7223
6548
4452
3665
6383
3913
5601
6785
7900
8793
9530
4684
8373
9996
707
7118
3807
7181
7694
9210
7791
4209
4705
9353
4869
8920
9772
6588
7516
4660
9852
4181
8628
4204
2322
5473
8564
106
7928
6471
5097
474
7588
418
2134
8272
777
6717
1597
4167
8802
9610
3235
1636
8444
2372
9637
2172
7043
9175
2796
3143
8378
8573
1026
4318
6560
3144
4128
7031
7636
4601
1021
9890
2222
5138
7318
6162
6214
9729
8206
7668
7140
6159
5369
4585
4776
3950
2385
3313
983
7520
9265
2135
8682
408
6780
434
5624
5371
7886
563
8923
3530
5094
3062
6046
2518
5941
2140
5016
7567
8311
3345
603
8213
3801
2642
6557
4471
7570
3504
3739
1103
4430
8700
718
7517
9458
8164
2921
8971
7413
8028
2950
9561
1379
5372
4835
2851
1336
762
9976
7152
4595
5955
6812
7298
12
594
4246
1546
9905
3132
8832
9362
8903
8813
8857
7790
8791
4236
2111
7614
1918
1993
9212
27
6113
7459
5788
358
902
9046
4489
1888
9162
482
3525
6839
1048
2618
5938
7029
1473
5220
7798
9262
8369
1743
9786
3068
5120
6772
3694
4098
834
2788
2887
3440
851
4793
8365
5295
8555
2277
7366
7399
9418
6625
9173
6936
6572
2931
9366
3519
2421
5920
104
7963
740
9582
400
2048
1020
7494
2118
6636
8718
9814
9164
6608
1036
4757
3317
4297
992
1982
4673
7201
9916
9535
2505
4272
1899
2206
4851
8241
150
3863
1176
6424
1357
6701
6360
93
543
33
6152
2431
145
6075
8198
1477
969
4742
9857
2763
3759
2365
6219
8085
1836
3155
6758
4051
6631
1847
5547
8176
4867
3124
5506
3491
6909
1525
3370
4651
7925
3129
6357
7226
5836
7958
3033
5893
4465
8375
5651
4084
5366
5555
6708
7584
9026
8763
9946
6356
1756
630
1245
9980
9290
8848
4988
8614
5947
8199
4747
109
5035
6181
5385
7823
8611
228
7119
1997
383
4473
3991
7403
6610
966
5396
7110
4848
3064
7088
4688
957
6347
7718
9419
1393
6269
3531
1921
9202
2011
7526
5480
6280
7530
6756
9965
4333
7030
9536
6535
1529
2233
6425
8458
3806
8734
9822
2849
7096
4490
5510
9928
2502
3605
5172
1216
241
2065
9731
2592
877
5568
2883
1850
7220
8856
6939
9603
1555
4483
8869
103
1574
7347
7285
3635
6100
5186
3005
4196
6915
795
390
2313
8643
7943
8057
6887
7842
6176
1242
5466
5441
6367
5759
4388
2121
4689
2077
891
8246
1396
2361
3350
8567
1050
6940
9411
6644
7153
2109
4189
4794
3599
1898
4649
9630
8105
5047
2902
817
528
6838
9141
9070
8249
7248
2848
9438
9200
3782
1445
7656
7381
1397
1877
8337
2483
4253
7896
5838
550
4454
4437
6718
4148
3500
8242
6499
6561
6149
2367
1511
7056
6437
7231
584
9139
2516
4755
8944
8623
7466
6993
2104
2989
2335
8989
6793
7488
2093
7728
6725
5822
701
6518
8677
3900
1252
4089
8436
6393
9673
3443
7415
7106
4847
4561
1970
7860
1638
2061
4271
7612
5531
3179
2734
2448
7561
7385
3493
8480
4101
7580
3349
1942
9749
8714
1908
4844
2148
9829
6144
1071
4679
2260
8831
7345
1620
7717
9848
5449
5307
935
191
4637
9549
6306
875
3019
240
4690
4092
8824
319
23
6438
5964
306
1426
9467
8358
6918
6247
3971
1495
3711
6327
4408
9382
9861
9138
1781
5611
1206
575
6554
6705
2521
445
1771
7865
8388
8917
4808
2815
7835
1731
6331
5162
9143
5992
2141
2205
9635
2302
6727
8455
5543
7619
5809
628
5470
4804
9801
6274
4999
9812
134
973
4053
7836
587
2653
8491
1744
1003
5511
1766
9259
9147
2515
7265
4628
5540
8050
3209
9505
9781
1915
646
1460
73
3180
8556
7554
2590
3714
2497
549
8560
4838
4009
7048
3010
6370
8197
8142
3803
1470
2745
6
8472
9038
6916
6585
3394
3496
8753
5730
8108
8265
90
5666
2579
2658
6555
1058
9558
4143
4683
4944
2797
2738
2553
2255
8630
2613
6510
5885
5980
5144
9388
6612
2819
2420
2610
6400
427
5312
4256
9784
1225
334
1658
7809
4814
5362
9179
1227
3408
3693
1052
6704
7420
8165
823
8004
1145
7274
2236
6737
4423
3709
5146
1363
6998
7094
3510
117
1325
6695
3577
4580
116
6844
2049
5824
6562
633
4195
3454
7027
7784
5576
8208
2688
3968
6484
9548
2856
2891
4399
8557
6421
3075
8332
1034
5427
5962
9276
6172
239
700
6345
6505
9252
9297
8259
7483
1840
6820
238
6654
1056
7471
5301
8073
5552
172
5680
1086
1240
5996
9669
3141
8193
7446
6690
802
5224
3426
9167
1830
4438
7558
8997
1334
3245
2811
9392
962
2896
6251
8706
3407
5695
7821
7990
1205
8799
8445
4749
4459
3879
7994
8310
9657
6569
8473
1803
4635
4695
5521
4409
4462
2304
8237
9943
2169
7101
161
1805
9211
6503
2414
2772
1425
4941
58
8029
198
5438
7086
3131
8685
1909
9073
5122
1512
5175
6278
6989
7766
2754
9228
2251
2657
1064
6942
2378
1119
7706
4130
7145
3114
5722
8060
2338
6890
1937
606
580
2532
5593
4871
6849
9165
6459
6634
4728
554
8760
9468
3198
2272
2366
8931
3412
3070
1099
4367
432
4144
3554
7940
7678
1914
3071
6186
8297
2540
3119
9378
8936
1140
9531
8919
6589
2032
9448
8812
8984
6407
6398
1891
6232
2165
880
3024
8680
5972
7247
4989
7065
5100
3390
4672
5132
4811
5567
3675
515
361
3171
5350
9992
2746
5218
3586
6270
9877
5068
555
8641
5709
4033
6391
9309
6433
9766
5559
2751
5361
8002
8100
441
9218
2271
2586
4162
6746
7371
9586
9750
644
4475
8159
9206
8497
9730
4594
4599
8114
7887
3012
7297
7405
7840
2783
9870
1120
1382
3479
2319
1633
2895
6648
6124
3076
4493
961
1895
1624
1851
1680
1965
2696
3749
6941
1846
1708
4316
870
1055
9407
1996
5028
1675
470
8419
1069
4702
5529
8047
9973
2550
8619
3632
8992
5284
3045
5254
9790
8516
8302
4379
8660
1072
2916
932
7653
2837
1191
1065
9940
2417
8232
6173
4828
2693
3288
6691
4556
9294
6802
2978
1101
1284
7867
2010
6637
4716
4304
8247
2426
557
3255
3185
5796
1049
8893
6733
9429
6114
4950
9159
5697
6153
9697
6362
4000
5039
3804
8969
2707
7760
4588
4543
9675
7422
4275
4243
3221
8420
6618
9598
7874
7669
4381
9643
4952
9768
7524
3992
7339
828
4926
536
4569
2591
9666
4659
9077
3986
5589
9559
9938
1037
3102
3040
3020
6225
1032
7638
4971
2234
9636
8486
4919
7020
7380
4955
4414
8003
5508
8948
8103
1992
1677
928
5741
2528
7708
9898
9887
5015
9352
6065
3192
2611
2015
4063
1415
3220
7967
789
2204
6623
9688
7042
1545
6209
6493
8186
3173
2394
2767
7365
7333
5917
8188
179
4886
7519
725
1967
6573
6949
7650
4023
4347
3188
3480
906
351
2703
4797
6671
2975
4652
2843
799
2673
7017
2253
6335
9645
4876
9015
4287
1464
1207
9571
5779
2060
8504
3994
4730
6837
7111
8575
4081
6191
3680
6192
9459
7141
5910
1777
3268
7774
56
9451
8324
6714
1945
4417
8009
2265
7229
3908
1412
3859
2822
7731
4680
4566
3433
1637
6657
4230
7142
790
8043
2725
8366
1219
8876
394
900
6329
8222
7752
246
2397
7326
502
4664
806
1740
4991
8248
4994
9907
2504
657
2381
8872
2465
4772
1381
4140
6929
4131
9193
5193
1335
465
5707
2035
4345
3691
2083
1444
886
7162
2677
3523
872
9371
2153
6699
289
4154
1759
4854
226
2490
8735
3585
9343
1467
4898
1934
1600
7568
9361
7924
2103
5118
6642
1520
1676
5439
3322
5447
3387
3931
8637
9930
3032
7687
883
7146
6312
6224
8588
5632
6273
7845
4924
7720
3417
1346
9091
2722
9853
6084
8205
9546
9119
8929
9875
1722
259
4787
2615
702
6571
3184
6205
1493
7800
9490
4586
8520
2877
5413
9568
8170
4596
1878
7314
4210
7912
3048
7179
8035
8705
972
4767
323
3008
6748
4146
8851
3344
2552
4258
6077
1906
1098
931
7294
7120
6354
3910
6480
7386
6158
5065
8927
4842
9631
3862
7206
4041
2470
26
3329
1239
2129
2355
1151
7606
6217
7137
3031
6514
5668
8632
5751
8970
703
5124
1607
125
980
3520
8033
4627
5050
4147
9748
6064
6132
6884
3059
2308
675
4298
9804
1730
7407
547
9434
7348
6669
4549
5089
2715
2299
1307
1886
1648
6520
3277
9640
7185
2522
3767
3084
7331
5515
8104
3988
2687
2178
6042
3326
6904
5769
8207
7703
597
9055
6020
2957
2924
9901
6275
6267
8097
5988
7060
1688
208
2443
8684
4934
850
3089
7462
4726
1653
6130
4765
9078
8152
6482
2593
3150
3484
5753
9867
1872
3514
4285
1111
2692
2416
1834
6622
6878
426
3893
4868
4332
9226
1936
4267
2186
4348
7634
2982
6296
8315
8023
8902
5528
2152
1515
5926
347
6724
4279
2890
984
2530
469
7533
3760
3347
7782
7884
9023
3058
1350
9391
2379
5939
6807
4425
711
7426
9716
4102
85
6626
1063
8865
561
6261
9841
7510
8202
1406
5618
9658
9291
2014
7061
5130
9436
6166
7482
9756
6978
1566
6255
2929
4732
5400
6466
9483
9874
5599
9830
1005
5833
3127
324
7151
985
9461
4460
1354
3704
2776
1453
6076
4654
2684
5640
6552
994
4002
2581
5679
6587
516
6088
4715
1027
5096
6071
4751
9632
9937
4897
2646
1075
1309
533
6682
5109
922
2059
8084
5340
135
8871
7280
8651
1013
5761
4639
1794
3751
3276
3300
7379
3648
4864
1257
2835
7
1746
7512
224
2211
951
3478
3532
1022
3816
9406
1035
421
9270
3473
139
3298
2859
926
3755
896
2399
2018
154
6873
705
6635
108
4910
5336
8495
3077
772
8014
4815
8217
7767
2762
8652
4218
2149
3784
7871
800
9010
4520
1267
6005
36
352
4522
8269
9069
2199
8410
3327
9770
2727
953
3487
1772
7360
5230
5225
2087
3191
3229
9747
9446
4870
4461
6308
1009
7682
3928
8860
1401
5738
7939
4940
571
4754
3761
5115
4619
6667
9198
3927
7188
316
8829
3140
1029
5424
5673
5388
7779
5477
6419
676
7205
4227
7279
7243
9545
472
2597
9013
7622
485
1733
5657
6874
269
5574
3000
2154
7364
4743
9174
4521
9019
2704
7739
9148
5952
3916
439
2226
8447
8821
3193
3332
1532
5116
9702
6530
3993
9316
6489
3566
321
8334
7469
3342
8118
5410
254
2739
8385
3232
2831
9613
2262
9565
3860
7169
7194
3877
5085
855
8928
4155
9261
458
1561
9344
3090
6536
8542
9817
3775
7067
1946
4122
9185
429
6295
456
7571
2289
7002
8284
7927
7962
5787
9846
5145
7637
967
4208
4085
8138
2695
8091
4436
3644
43
1679
8532
2833
2216
1612
89
4248
4524
8695
2418
3737
8879
2868
6951
4530
3486
1685
1280
5713
1417
181
4019
5354
3781
8836
5416
4511
1197
936
6189
8606
4323
7772
88
9241
3722
5622
8078
6542
3570
6832
5030
2968
1384
2171
2836
4829
2074
3696
5616
5090
5867
2893
3280
4725
9488
4411
1572
6231
2022
7826
3628
4939
144
6319
5043
7949
3934
80
669
4839
2025
5595
9945
6607
5974
3362
5767
5164
8769
6976
2622
866
9196
8600
3063
169
3174
5058
8788
4670
2563
2424
6338
419
9575
7189
674
5582
1093
5444
9231
6593
3226
663
7430
5474
2464
265
4191
5747
9060
8605
7053
9322
620
160
3103
5750
4066
3181
8088
3833
382
9110
348
6019
2578
7827
6924
3307
1188
6309
3364
9567
2560
8463
9314
3216
8886
6947
8126
5259
6804
9376
8313
5103
695
5060
741
8107
276
8625
1606
3545
5152
3505
9177
1619
7843
9040
8006
6105
9668
4097
47
9414
3278
7878
8950
8994
9554
4435
9808
256
6862
1295
1986
119
7605
7249
6651
8723
1481
5919
2110
8792
1775
666
3810
7833
7455
514
2054
3882
507
3392
9753
4492
9709
9617
6932
4551
9330
6509
6967
5223
1110
4623
5908
1802
6881
2660
5777
431
5627
832
5501
7198
8810
3175
9866
8402
3660
492
5210
9764
5398
1400
5693
3978
3518
5238
1861
3030
7916
4194
5907
499
3406
848
6322
5183
1732
9599
2991
7437
525
913
497
2182
3731
5944
2436
2485
5683
2538
8635
9020
2194
6709
8452
2162
2946
7501
25
444
5687
6605
186
3133
6925
7404
9511
1438
6767
8403
7624
9858
1194
7769
5397
5776
9948
3591
3022
8274
1487
2068
9022
3534
1778
2962
4513
9525
8040
1248
4675
3501
4904
752
4067
142
9837
8475
5108
7099
843
7292
2954
3601
7513
5900
9931
9350
290
3163
286
3471
5273
2012
3741
6798
6831
2173
2949
914
6892
7174
5171
2224
933
3541
105
9380
2437
9476
998
7222
3243
3305
912
8273
1015
3013
2127
9
4949
8287
7690
6592
430
8319
2056
5495
2970
3474
8593
130
6751
3634
7688
3744
3121
7255
2293
1237
9030
7632
2320
7508
4056
5219
1251
8955
5874
206
8855
2209
4238
1200
7937
6006
1755
5403
2195
9732
2554
9584
94
1292
4112
6087
5890
2785
3941
941
9845
1816
6945
2339
3459
3645
6922
6906
8974
5630
237
7204
3495
5102
8277
840
3218
3752
4391
1137
7627
1911
2482
4658
1522
4959
2305
7281
576
2963
3466
4359
4464
9774
3796
8224
2598
9555
8683
9763
8367
133
6420
2988
2794
735
5607
1160
5325
744
2442
2023
3897
3054
9300
2531
1565
1024
1932
8457
6127
59
293
1663
5892
8634
6875
5483
6317
621
8698
1602
8583
729
679
9583
2300
9607
5706
837
2180
8253
8535
6072
5973
3754
6546
2088
227
7655
5704
4539
7660
235
5280
6059
3498
5244
7929
1795
7716
3002
8554
7492
4916
4402
4044
8934
6894
6448
849
919
8166
263
6392
6864
2500
5862
4118
7007
9331
3189
2983
2574
7635
2986
8171
3200
6814
4215
1801
1132
5456
1502
6052
8830
31
9590
3494
3838
3113
8161
6315
2879
2410
7256
1584
6934
5268
114
6257
9242
1910
2374
2808
4232
5782
2683
8649
4734
6639
6977
4602
9557
2232
8168
1439
1146
5431
7855
9101
9746
9215
4593
2724
3363
5418
917
6013
8513
6661
1912
5518
9321
1880
7590
5940
1729
9842
7500
2790
684
4117
6937
2629
6134
551
9904
570
1523
2034
2415
4477
42
9408
2170
489
7025
7825
2720
9076
9516
5135
336
7208
715
2870
7454
3439
5436
5672
2147
3296
6794
9707
3542
3161
6029
1148
6451
2769
2933
6747
4487
7858
8846
3413
3826
9820
2425
1138
9263
8638
6779
1586
7467
1498
3571
7557
7956
5046
185
7074
6594
4816
9007
9320
4068
5509
3563
4768
9591
2938
28
7564
2267
3447
1006
3573
8518
4849
1420
4030
4198
5270
1815
924
7178
6008
6753
1990
6018
7165
2493
9041
3212
8130
5127
2085
4880
35
3080
1471
6017
9083
1667
3627
5888
6408
7015
5084
6016
2659
6477
2650
4544
6810
879
3671
384
3011
7894
79
9828
7999
9608
560
616
4560
7008
8691
3400
6776
6853
3614
4775
9381
7919
8054
9086
3735
1060
2576
7478
6045
7266
3962
5860
2641
2370
1926
3092
4873
6513
155
4607
1254
6579
8958
4410
2430
6819
406
649
451
7729
1917
5504
5757
7490
376
4862
3211
1640
1976
5496
4746
8051
934
2661
7164
5324
1414
9017
8493
178
4016
6118
3186
1359
7354
5828
7831
63
1314
9634
5428
8601
6713
1289
9071
1339
1789
4175
8570
9618
9111
9984
2582
4515
6576
4286
5092
4307
763
8827
7250
5465
4900
2175
422
6387
9927
1466
9683
386
5314
4341
9275
9199
2654
9028
9650
3883
6490
1300
2514
2117
7806
1585
16
7225
4694
6106
604
8853
5479
8399
9337
7075
3736
2539
5708
532
1223
9854
9508
7802
7378
8526
3706
4856
5963
5002
9773
5949
7133
9396
7160
2356
8346
8688
2510
8990
2409
6650
9821
7811
6139
4354
722
9123
5675
7358
7016
7770
4378
6332
1848
1709
2996
2886
6617
5578
349
6350
346
8219
545
257
4050
9357
9966
6406
5300
5491
9627
1776
8998
9176
9203
7480
8499
6281
7768
7853
1726
2190
3293
1558
4505
4948
4640
9197
5600
4859
7005
7948
7453
6427
62
7829
5026
642
335
4792
2375
6167
1260
9220
738
3852
8952
5490
9112
7100
505
5810
4858
92
4327
1215
6215
3162
5905
8016
4401
4170
1563
3815
8674
3621
7293
5983
4340
4082
5535
8080
2136
6450
6598
4636
4517
7154
5629
5653
8321
5289
6277
5154
4257
3047
6230
4643
946
3610
1405
5044
999
1171
3727
8675
4129
9001
8260
4978
6795
2246
5208
5702
1008
4711
5869
5780
2871
5333
6981
9733
5451
4177
7218
3108
9114
5158
3912
9687
2257
2666
8347
9213
9735
5182
8608
7866
5005
8815
5150
9240
7184
5194
7289
5913
5167
9815
2408
5603
3726
8782
9239
6103
8814
7759
8898
2341
5231
4578
3074
7496
8466
4350
3703
2844
858
7264
2567
5392
4526
7621
5712
8957
3138
3552
6871
1501
3126
903
4769
1224
4762
1924
3851
2901
2595
895
4206
572
9256
2004
5457
8017
2600
7822
3099
7541
1087
1294
5586
6074
5538
801
8954
6595
3957
771
493
4443
7531
2638
9340
9629
9653
8661
9012
8609
9891
4426
8627
6330
1033
9191
511
1164
586
4216
223
7877
1287
3420
9365
915
2845
9336
7234
8566
7893
5685
4992
3462
9400
9552
1590
697
2599
4779
3309
7212
1868
4759
7643
3728
2064
2346
5937
1315
3798
5240
262
4798
7695
8624
5308
4467
2714
3310
809
939
4537
5654
1728
1070
6823
2803
5872
7618
202
1313
2213
6378
3719
6512
7282
5365
2412
2792
4105
2885
3783
2316
6323
6432
4372
6559
3061
4339
6985
1712
8937
9492
997
2633
2086
8489
9169
2753
2240
888
1081
9184
647
4124
7252
7909
8964
5637
374
6302
196
6907
7244
9258
5894
8771
6736
8370
6001
8276
7603
3260
1468
294
9475
6965
9156
242
9442
3580
1528
8702
5303
7907
8296
2967
5883
5445
7775
3799
7553
9287
3325
7850
7383
585
591
6092
4392
6199
981
7032
2091
7476
2834
8008
5732
9713
7592
4629
1494
6973
8798
4665
9503
2373
4202
7057
4035
7974
1253
1694
1571
2910
3587
1373
5717
5820
5819
8783
4616
726
2577
1760
435
2866
2953
6957
3565
9390
9942
8149
4091
6506
8959
6788
4496
9135
1812
3615
9348
8437
1950
9462
3814
1244
8122
2729
3151
724
5527
9064
395
9823
2021
1745
3516
9628
5503
9267
1790
1418
1922
1573
5903
4325
9428
2847
1767
4604
4575
5353
8905
7748
7210
8350
3178
9248
3533
601
4645
9104
8243
3194
8787
1131
4906
4080
4612
3770
2433
2371
836
7677
670
3081
6707
1560
2730
2312
8430
9864
5310
3375
6769
2698
7485
1864
7955
8514
6611
4110
3236
2511
7777
4252
3861
4313
4866
2229
2166
5691
1465
3427
5909
4722
3294
6101
8490
3353
5334
4826
3041
5249
3072
8918
7277
4133
2144
6738
9592
6258
5855
4590
9615
7914
9222
5670
9616
4647
9882
9671
7626
7491
7311
5207
4790
3246
3512
7683
5349
5360
7343
3943
4937
2943
4574
5959
1118
5443
1084
2937
7628
7745
3457
9379
4294
2501
365
3027
7705
3302
1711
4351
7269
9225
7783
861
5667
1786
3747
5281
2288
6563
6365
8750
8010
4820
9581
5842
6445
3721
2030
5602
2699
4486
4375
7306
2670
7913
2939
1589
3312
6806
1536
5174
9243
1366
4741
9271
5816
331
2630
5105
4476
255
4891
6966
1873
74
2342
55
3169
2750
1955
6068
4450
343
373
5178
4491
4990
3256
3894
1276
9057
165
8056
4179
8823
9116
387
7034
317
8933
4321
9509
5287
6374
9217
7988
4264
7608
7754
1318
3624
6984
7132
6539
4710
3698
5236
9978
3398
680
3756
6912
4356
8424
9052
5638
5954
8756
7633
661
1030
5440
4624
354
4929
6467
438
5993
8586
9131
6768
7689
7995
8076
7182
6720
1505
2992
7109
1127
9518
9949
7254
4008
9935
8356
3979
68
1109
9623
9589
4946
9051
2541
8121
6195
2959
6041
4547
6170
2458
9797
6541
8092
845
2353
7910
6286
6900
1662
457
4137
3540
2559
8209
1312
7038
5541
1331
2952
4671
1269
9447
5233
7073
9953
5678
2679
9922
6537
4979
3295
8633
6235
4707
8862
9585
9816
746
3626
6349
3152
3702
4365
6444
590
9761
6107
4674
3578
3389
7673
251
8179
6028
8758
8736
2005
3590
5494
3477
5523
9884
9715
5834
6926
7828
9050
7228
8451
6023
7504
5519
5887
8325
8044
8892
2839
4846
8671
8648
7287
9913
5390
5797
3083
113
6899
6375
3053
5978
9047
1214
1443
2881
2362
6762
3773
8842
898
1258
8732
4963
2115
216
3148
4420
8754
5928
9757
4737
8987
9869
1684
2640
3284
8
4791
6272
1931
2461
5968
9954
3321
5151
1261
9726
4466
4620
1226
4138
660
2238
678
6741
2731
5778
4374
6305
7183
3009
3001
4552
4027
4545
8299
710
6472
921
1452
3613
3845
2542
8604
4542
978
749
736
3485
4444
8620
2439
4634
5348
3227
5655
3437
8062
5991
539
4529
1660
5057
959
1770
84
862
3279
71
7715
9009
1355
1078
5071
9619
5272
1184
8540
2665
6771
9172
2026
860
2948
3165
201
1821
6213
4004
3618
7986
6786
9088
7377
3666
1875
200
1428
4967
8972
3016
6250
4827
3252
641
1203
9230
4212
5437
194
9872
8392
4836
153
1673
698
3984
1783
4852
2019
2908
9011
5166
7050
141
2040
9440
3111
463
3079
5756
4610
2488
6128
7443
5553
9955
6784
1643
4268
8316
9385
217
1857
1752
1697
4546
6800
7033
3358
709
5305
292
5692
3097
8182
5542
3468
6245
7957
9002
6975
3039
7815
1083
5355
2906
1628
3889
5012
7370
1587
6409
5086
7461
4510
1301
4925
4370
1090
7009
7177
9302
9941
5033
3167
2985
1496
5507
3956
609
3733
4591
8071
2708
6817
3182
1105
4161
2625
1971
4773
2161
9124
8982
4480
5803
2955
8755
7862
5596
5061
5299
5989
5784
7200
6115
8146
2756
9449
6333
4723
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment