In [8]:
import time
import random

In [9]:
# Set seed.
random.seed(a=100)

# Create our default list.
short_list = list(random.sample(range(1000000), 10))
medium_list = list(random.sample(range(1000000), 1000))
long_list = list(random.sample(range(1000000), 10000))

Heapsort Algorithm


In [10]:
# To heapify subtree rooted at index i.
# n is size of heap
def heapify(numbers, n, i):
    largest = i  # Initialize largest as root
    l = 2 * i + 1     # left = 2*i + 1
    r = 2 * i + 2     # right = 2*i + 2
 
    # See if left child of root exists and is
    # greater than root
    if l < n and numbers[i] < numbers[l]:
        largest = l
 
    # See if right child of root exists and is
    # greater than root
    if r < n and numbers[largest] < numbers[r]:
        largest = r
 
    # Change root, if required
    if largest != i:
        numbers[i],numbers[largest] = numbers[largest],numbers[i]  # swap
 
        # Heapify the root.
        heapify(numbers, n, largest)

In [11]:
# The main function to sort an array of given size
def heapSort(numbers):
    n = len(numbers)
 
    # Build a maxheap.
    for i in range(n, -1, -1):
        heapify(numbers, n, i)
 
    # One by one extract elements
    for i in range(n-1, 0, -1):
        numbers[i], numbers[0] = numbers[0], numbers[i]   # swap
        heapify(numbers, i, 0)

In [12]:
# Test on the short list.
start_time = time.time()

heapSort(short_list)
n = len(short_list)

print("--- %s seconds ---" % (time.time() - start_time))

print ("Sorted array is:")
for i in range(n):
    print ("%d" %short_list[i])


--- 0.0 seconds ---
Sorted array is:
152745
183236
366725
412125
477025
481850
739784
767514
808225
997948

In [13]:
# Test on the short list.
start_time = time.time()

heapSort(medium_list)
n = len(medium_list)

print("--- %s seconds ---" % (time.time() - start_time))

print ("Sorted array is:")
for i in range(n):
    print ("%d" %medium_list[i])


--- 0.009057044982910156 seconds ---
Sorted array is:
430
1652
2973
3376
4786
5919
7669
9521
9823
10213
11476
11869
13135
14314
14885
16706
19862
20957
21288
21408
22535
23946
24167
26215
26895
27364
27404
28860
29203
30783
32118
33768
35336
35593
36728
38646
39580
40761
40948
40962
41503
41505
41575
41588
43536
44218
44834
46077
47588
47649
48928
49388
49433
49649
49823
50213
51774
51795
52071
53184
54642
55005
55018
57237
61047
61109
63690
64665
64952
70045
72831
75121
76209
76726
77516
77870
78027
80295
80764
81174
83883
84047
84287
84670
85459
85845
85877
87172
87806
89451
90491
91054
91690
91838
92555
92811
93247
94568
95172
97149
97356
98922
99552
100107
102356
103426
104433
106244
107206
108781
109083
109195
111381
111972
115311
116135
116144
116439
116688
118482
118889
119357
119569
121638
121722
124734
124870
124907
125511
125936
126881
127204
128761
128985
130121
131074
131100
131664
131841
132275
132765
142672
144741
146529
146778
147291
147588
147672
148215
148544
149952
150628
152390
153624
153813
154132
154338
154774
158855
159876
160896
161808
162648
163286
163437
164222
164378
164982
165118
165952
166662
168214
168804
168953
169149
170158
170435
170686
172705
175127
177743
178470
179899
180731
181375
182964
184589
185202
186110
187129
189135
189422
191210
191588
192541
192725
193221
197756
199731
201287
201322
201998
202195
203636
203839
204877
207416
207745
210065
211519
213425
213607
213772
214418
214519
214938
215061
218817
218862
219305
219956
221075
221682
222010
222903
224258
226975
228082
229791
229809
230340
232127
233565
233922
234252
235750
237882
238708
240000
240863
240878
243246
243500
243975
244613
244759
245243
248748
250144
251445
251900
252540
253633
254720
254723
257584
257766
258886
259093
259551
260879
263421
263820
264799
265716
266558
266780
268425
270777
272437
273125
276212
277613
278401
278878
279052
280147
280716
282053
282522
283153
283948
284451
284591
286391
288516
288848
289175
290245
291331
291922
293480
294018
295204
297036
297857
298107
300413
300783
301418
301849
302080
302599
303935
304975
306016
306039
307984
308203
308824
309581
311212
312454
314269
314467
314631
315407
319256
319766
320173
321287
323907
324320
324435
324848
324910
325657
326347
328333
329727
330402
330656
335320
336323
336578
338799
339780
340309
341320
342630
344141
347842
348087
349952
350149
351252
351256
351640
353684
353759
355047
355168
355301
356412
359702
359929
359942
360359
360871
361462
363860
364550
365061
365215
366399
367138
367227
367504
368520
369533
369586
369738
369793
372794
374576
375523
376620
380631
381436
384519
384953
386095
388038
388244
390787
392608
393204
393319
397853
399045
399340
399931
400039
400716
400728
403183
404428
405824
406291
406491
407416
408026
408348
408782
409513
410490
410950
412642
414690
414728
415206
415593
415764
416981
418354
419136
419764
420069
420253
420526
421250
421550
422214
422541
422646
423010
423382
424358
425757
426260
426401
427540
427724
428467
429594
429902
431812
432769
436179
436448
438057
442674
444058
444110
444377
445950
446467
446656
447036
448883
450889
454572
455023
455462
455562
457058
458678
458704
458877
459550
462955
462981
463370
463563
465209
465913
466861
468349
469655
469963
471727
472290
472389
472528
476282
476672
477825
478093
479735
480075
480660
480733
483507
485512
489032
489529
490881
492210
493655
494931
495258
495328
495734
496585
496895
497123
497156
498615
499294
499867
500655
500913
501302
502415
503579
503970
505373
505964
506497
507053
507919
508170
512965
514456
516333
517235
517453
517822
518410
519898
521324
523147
523341
528966
530865
530908
531218
531486
531746
531992
532198
533394
533849
534865
535427
538526
540728
543259
543356
544323
544445
544609
547236
549053
549517
549893
549995
550596
550799
550851
553296
553836
554342
555389
556381
558787
558894
559742
561350
566785
568707
568831
569325
571566
574628
575748
576296
577435
579814
580114
580768
580860
581605
581989
582378
585267
585542
585935
587891
588677
590008
593170
593445
593659
594186
595814
596111
597447
598350
602155
603254
603271
604505
605238
606321
606434
606446
607169
607898
608172
609785
610988
612580
612775
612998
613591
613786
616695
618749
619032
619052
621077
623020
623363
624283
624453
624602
625603
625818
626919
628708
629179
630271
632041
632237
633173
634297
635920
638687
641409
641867
643254
643342
645387
645583
646055
646382
647640
647737
648508
648527
648895
649175
650262
650772
651347
652142
653057
653559
654177
655690
655800
655899
656745
656787
657761
658427
660285
661595
662020
663702
663801
665536
666395
667037
667228
668781
669469
669728
670408
672593
673279
673997
674687
675379
675430
676157
677098
678806
678953
680046
682445
683114
683154
685133
685438
687016
687899
688575
690162
690818
691470
691781
693589
693948
694143
698043
698728
698909
699611
702641
703818
705384
705591
706134
706549
708325
708811
710019
711141
714595
714932
715520
717686
718548
719767
720946
721964
722511
722949
723059
723266
724767
724943
726670
728565
729247
729756
729787
729824
730046
730850
734878
737197
737636
740466
740485
741236
741886
742671
742962
743261
743958
744344
745070
745194
745667
746884
746923
747492
747853
748623
749157
749463
750160
750274
752147
752671
752832
753802
754885
755086
755977
757259
760066
760659
760953
762558
762587
763185
763242
763581
763781
764491
764896
768358
768847
770240
770923
772487
772497
773199
773781
774266
775026
775804
777084
778732
780856
782299
782389
782678
783279
784136
785120
786822
789120
789188
790497
790726
791823
791921
793332
793626
795542
795844
796442
797748
798492
800587
801524
801655
803342
804213
804304
805325
806206
807090
807800
808103
811074
811400
811422
812599
813407
815399
816105
817568
818072
820064
822109
823869
825759
828857
828999
829268
830814
831619
832833
833525
833904
834316
835138
837554
837588
838234
838882
839646
840023
842673
843362
846594
848955
850983
852351
853350
853976
855520
855709
857754
859969
860378
860934
861998
862362
862619
863247
864016
864019
866586
868596
869098
870205
873768
873911
874217
874879
875214
875423
876097
877124
877464
877550
878376
879358
879655
880345
881527
882035
882604
883368
883375
885391
887094
887776
888534
890001
890588
892860
893850
893875
894782
895663
896353
897372
898087
898187
898488
902555
903181
903264
905122
905470
909242
911022
914939
915277
917156
917268
918749
922711
923924
924471
925374
928156
928556
928955
929455
929889
930628
930700
931032
931556
932606
933711
934135
934190
934212
936225
936413
936879
938062
939430
944926
945479
945638
946175
946767
946894
947223
947404
948351
948972
950776
951900
952834
952909
953466
953633
953828
953907
958164
958322
959051
959488
959829
963370
967118
969089
973571
973873
975005
975475
975543
975960
976406
978071
978281
979302
979348
979413
980153
980465
980542
981904
982210
984271
984827
988440
988681
989174
991776
993083
993799
994936
994971
995112
995988
999020
999122

In [14]:
# Test on the short list.
start_time = time.time()

heapSort(long_list)
n = len(long_list)

print("--- %s seconds ---" % (time.time() - start_time))

print ("Sorted array is:")
for i in range(n):
    print ("%d" %long_list[i])


--- 0.09043121337890625 seconds ---
Sorted array is:
29
174
316
373
424
705
762
786
830
1017
1189
1456
1767
2001
2115
2123
2241
2259
2450
2459
2462
2765
2775
2776
2807
3152
3183
3356
3595
3678
3863
3892
3975
4016
4064
4090
4360
4772
5280
5355
5875
5916
5956
6060
6385
6483
6493
6523
6599
6874
6916
6955
7008
7093
7331
7332
7537
8164
8266
8312
8388
8557
8604
8717
8860
9034
9274
9314
9430
9458
9553
9588
9593
9597
9808
9891
9911
9944
9954
9990
10174
10204
10252
10426
10757
10770
10945
10977
11019
11031
11380
11507
11510
11658
11694
11757
11794
11875
12006
12116
12170
12191
12210
12344
12415
12430
12688
12711
12746
12752
12768
12819
12885
13022
13116
13389
13457
13680
13809
13818
13822
13897
14208
14498
14506
14510
14615
14624
14626
14671
14928
14935
15079
15152
15172
15195
15317
15387
15415
15681
15796
16008
16051
16118
16196
16267
16332
16386
16429
16450
16889
16979
17002
17065
17068
17344
17514
17556
17606
17632
17863
18069
18131
18220
18406
18479
18545
18650
18653
18787
18912
19120
19284
19307
19326
19393
19398
19411
19539
19652
19734
19859
19878
19919
20185
20245
20382
20493
20536
20552
20569
20611
20846
21024
21034
21297
21418
21490
21667
21823
21831
21926
22007
22020
22030
22150
22160
22208
22281
22380
22442
22523
22543
22677
22969
22979
23076
23229
23364
23373
23399
23533
23814
23816
23857
24100
24318
24447
24660
24731
24753
24942
25018
25269
25310
25366
25467
25593
25636
25697
25963
26029
26071
26272
26499
26510
26555
26672
26676
26835
27014
27132
27550
27626
27631
27788
27809
27989
28221
28403
28567
28610
28937
29077
29222
29244
29258
29337
29621
29712
29807
30138
30158
30514
30612
30684
30950
31094
31139
31167
31302
31330
31431
31575
31616
31799
31831
31861
31877
32088
32141
32144
32228
32409
32511
32558
32608
32658
32703
32708
32822
32876
32941
33091
33369
33511
33607
33658
33825
34039
34083
34113
34131
34329
34668
34685
34741
34826
35151
35174
35391
35616
35736
35885
36029
36051
36237
36473
36477
36542
36552
36623
36640
36650
36767
36893
36971
36988
37130
37232
37433
37498
37556
37565
37575
37701
37710
37763
37947
38041
38137
38271
38305
38325
38511
38523
38570
38642
38660
38678
38903
39061
39125
39182
39189
39365
39371
39433
39480
39659
39691
39943
39962
39984
40015
40021
40075
40121
40225
40478
40496
40698
40741
40789
40838
40866
40880
40947
41015
41064
41131
41153
41157
41169
41217
41599
41764
41824
42009
42016
42292
42442
42496
42511
42571
42610
42653
42683
42687
42925
43045
43239
43423
43541
43649
43708
43826
43902
43906
44119
44253
44405
44585
44723
44784
44824
44916
45433
45446
45512
45555
45719
45822
45824
46031
46457
46491
46755
46770
46854
46994
47052
47164
47211
47217
47421
47459
47471
47516
47536
47557
47638
47756
47810
48031
48461
48653
48704
48729
48983
49050
49334
49401
49539
49546
49728
49855
49903
49932
49950
49993
50075
50147
50225
50330
50371
50402
50601
50652
50686
50688
50697
50708
50765
50776
50789
50963
51263
51336
51376
51397
51404
51486
51529
51591
51632
51815
51838
52050
52062
52102
52127
52269
52505
52542
52597
52681
52683
52880
53150
53186
53193
53227
53238
53585
53595
53629
53660
53755
53831
53850
53868
53898
53918
53981
54019
54042
54163
54198
54344
54405
54564
54786
54825
54868
54872
54886
55064
55351
55365
55370
55456
55491
55520
55543
55560
55592
55604
55616
55702
55726
55732
55760
55769
55883
56007
56069
56587
56593
56687
56718
56759
56946
57052
57302
57312
57373
57578
57657
57833
58207
58209
58246
58352
58537
58556
58919
59014
59068
59191
59242
59270
59324
59346
59355
59356
59462
59598
59893
59901
59978
59998
60090
60206
60433
60604
60696
60911
61055
61162
61220
61539
61766
61806
62069
62228
62266
62319
62337
62408
62409
62445
62486
62744
63033
63059
63258
63273
63304
63402
63596
63654
63666
63803
63964
64028
64244
64260
64279
64282
64403
64409
64521
64717
64749
64893
64943
64996
65312
65477
65493
65549
65553
65588
65700
65743
66069
66180
66277
66308
66513
66729
66937
67018
67323
67738
67858
67922
67992
68004
68074
68098
68198
68235
68333
68402
68552
68620
68846
68864
68869
69038
69228
69277
69285
69584
69595
69687
69696
69700
69853
69882
70074
70099
70149
70421
70602
70672
70688
70718
70754
70938
70977
70988
71007
71209
71381
71425
71472
71834
71889
72112
72141
72328
72469
72544
72657
72870
72941
73165
73205
73667
73698
73706
73967
74354
74506
74507
74916
74923
75108
75260
75377
75463
75470
75722
75798
75992
76059
76077
76165
76395
76431
76869
76913
77086
77101
77146
77164
77245
77280
77334
77349
77507
77680
77713
77901
77943
77952
77990
78084
78111
78517
78536
78622
78660
78812
78964
79001
79151
79156
79472
79525
79882
80124
80195
80330
80334
80352
80462
80504
80746
80798
80890
80947
81001
81123
81352
81490
81511
81523
81728
81897
82041
82062
82098
82128
82244
82538
82587
82725
82758
82826
82944
83196
83212
83307
83517
83590
83643
83752
83947
84077
84125
84156
84328
84555
84656
84745
84755
84795
84883
84946
85197
85198
85695
85772
85826
85878
86165
86181
86252
86350
86357
86478
86578
86764
87042
87069
87218
87420
87437
87679
87825
87883
87943
87976
88035
88132
88274
88522
88668
88703
88780
88914
89027
89287
89505
89620
89625
89671
89673
89711
89873
89901
89954
90057
90174
90311
90366
90529
90544
90671
90774
90814
90854
91062
91110
91192
91210
91402
91510
91848
91864
92008
92054
92101
92153
92173
92226
92382
92408
92435
92552
92570
92671
92932
93159
93334
93381
93540
93600
93629
93764
93810
93880
94028
94058
94094
94271
94277
94351
94450
94480
94551
94572
94804
94902
94919
94965
95075
95108
95210
95223
95400
95514
95538
95703
95838
95955
95985
96225
96476
96686
96792
96880
96936
97161
97342
97581
97931
97968
98174
98213
98248
98273
98369
98418
98437
98689
98741
98916
98957
99048
99212
99278
99281
99302
99337
99352
99367
99393
99436
99502
99852
99865
99964
100147
100291
100368
100487
100541
100599
100610
100637
100871
101079
101085
101270
101326
101336
101487
101658
102045
102066
102093
102122
102177
102212
102284
102297
102458
102665
102793
102889
102898
102954
102979
103106
103382
103510
103551
103643
103653
103733
103758
103977
103990
104011
104024
104052
104063
104097
104098
104162
104188
104218
104352
104412
104502
104569
104646
104803
104839
105096
105208
105496
105564
105585
105786
105923
106038
106097
106161
106320
106492
106577
106609
106741
106754
106848
107108
107223
107287
107325
107449
107451
107614
107762
107914
107923
107971
108003
108103
108136
108247
108275
108333
108451
108478
108710
108724
108746
108911
108935
108963
108972
109028
109080
109112
109210
109240
109285
109405
109715
109784
109852
109892
110046
110047
110065
110253
110269
110371
110674
110716
110752
110778
110784
110845
110912
111067
111391
111483
111513
111537
111608
111659
111680
111690
111821
111892
111979
111980
112000
112173
112189
112378
112407
112475
112490
112557
112604
112745
112945
113117
113153
113202
113394
113637
113726
113748
113769
113831
113955
114003
114336
114387
114515
114537
114576
114724
114837
114944
115080
115275
115415
115459
115478
115645
115867
115878
115932
115961
116031
116454
116590
116677
116688
116848
116966
116996
117032
117036
117041
117277
117396
117399
117428
117483
117546
118005
118111
118190
118226
118258
118323
118428
118476
118569
118990
119038
119074
119187
119230
119382
119572
119619
119627
119638
119808
119910
119980
120416
120425
120489
120502
120542
120720
120925
120998
121078
121192
121206
121304
121375
121398
121565
121674
121822
121874
122275
122483
122542
122555
122682
122839
123039
123040
123046
123074
123082
123139
123149
123241
123397
123490
123659
124023
124278
124434
124469
124648
124655
124806
124892
124930
124964
125002
125111
125218
125256
125259
125459
125551
125646
125674
125857
125945
126065
126209
126421
126479
126893
126905
126990
127112
127272
127289
127554
127564
127698
127716
127835
127870
127919
127993
128083
128163
128202
128250
128262
128369
128467
128564
128577
128718
128766
128817
128969
129022
129034
129052
129278
129454
129466
129559
129656
130084
130310
130370
130429
130556
130615
130651
130865
130966
131071
131184
131243
131267
131373
131439
131608
131648
131728
131849
131926
132041
132106
132278
132334
132457
132465
132675
132869
133013
133234
133318
133392
133592
133649
133773
133801
133861
133890
133966
134061
134101
134330
134388
134485
134789
134875
134913
135139
135219
135234
135269
135343
135370
135482
135792
135798
135836
135858
135929
135971
135972
136064
136096
136147
136201
136314
136418
136702
136927
136982
137076
137094
137119
137298
137360
137414
137491
137725
138120
138301
138317
139065
139162
139310
139457
139459
139539
139624
139719
139822
139848
139925
140016
140021
140041
140050
140093
140315
140567
140628
140636
140753
140760
140864
140921
141120
141227
141229
141629
141775
141831
141911
141934
141958
142045
142227
142308
142314
142425
142500
142670
142693
142717
142744
142817
142851
143023
143041
143167
143180
143216
143369
143526
143689
143734
143798
143863
144038
144231
144334
144344
144561
144648
144666
144669
144673
144740
144747
144847
144998
145043
145118
145131
145145
145330
145593
145603
145660
145687
145764
145918
146402
146437
146601
147038
147064
147368
147398
147502
147512
147518
147539
147577
147621
147736
147747
147777
148007
148118
148140
148167
148241
148272
148404
148412
148466
148551
148714
148846
148906
148930
149022
149047
149187
149221
149265
149402
149525
149542
149557
149631
149705
149949
149950
149976
149981
150047
150049
150224
150231
150263
150350
150486
150504
150546
150588
150604
150689
150848
150952
150987
151028
151393
151503
151626
151709
151729
152141
152155
152226
152230
152422
152439
152633
152940
153319
153541
153625
153686
153801
154145
154284
154484
154486
154596
154615
154679
154775
154921
155005
155038
155074
155075
155136
155282
155491
155545
155611
155726
155758
156380
156485
156503
156581
156619
156666
156703
156725
156768
156804
156968
156994
157065
157223
157256
157343
157516
157598
157684
157709
157738
157789
157791
157835
157872
158014
158090
158277
158639
158962
158968
159032
159303
159706
159746
159759
159775
159908
159962
159972
159989
160059
160211
160461
160469
160551
160561
160687
161091
161104
161254
161438
161483
161506
161558
161597
161770
161810
161879
161893
161976
161985
162101
162132
162242
162266
162435
162531
162564
162684
162860
162907
163172
163175
163673
163881
163884
164012
164094
164168
164200
164237
164698
164699
165018
165072
165118
165129
165139
165152
165276
165310
165332
165355
165390
165411
165589
165819
165822
165867
165893
165929
165949
165966
166041
166059
166123
166141
166222
166310
166470
166719
166928
166940
167006
167073
167401
167517
167564
167588
167627
167735
167960
168053
168110
168280
168302
168521
168620
168720
168739
168743
168899
168947
169032
169151
169187
169188
169347
169351
169376
169478
169622
169665
169697
169764
169818
169913
169991
170106
170274
170407
170500
170570
170725
170734
170801
171018
171438
171456
171777
172041
172170
172265
172362
172533
173002
173105
173148
173330
173340
173587
173782
173788
173887
173931
174009
174015
174127
174147
174162
174272
174307
174556
174629
174743
174855
174858
174971
175012
175105
175261
175264
175488
175549
175632
175644
175698
175700
175786
176014
176251
176265
176415
176454
176554
176568
176624
177037
177196
177212
177299
177381
177388
177567
177577
177715
177752
177866
177941
178343
178387
178402
178416
178770
178815
178865
178872
178913
179105
179281
179367
179389
179409
179491
179530
179533
179814
179854
179922
179929
180039
180104
180118
180160
180176
180239
180255
180279
180281
180293
180465
180498
180556
180629
180781
180854
181005
181057
181130
181247
181294
181304
181396
181449
181471
181529
181660
181922
182367
182370
182482
182517
182868
182942
182970
183010
183046
183083
183112
183182
183331
183359
183370
183488
183527
183610
183764
183814
183954
184197
184425
184818
184902
184907
185016
185114
185530
185655
185715
185870
185879
185895
185926
185979
186126
186147
186175
186316
186343
186448
186498
186508
186743
186950
187188
187242
187388
187393
187475
187738
187771
187868
188078
188088
188236
188270
188313
188452
188601
188654
188671
188680
188748
188839
188847
188988
188994
189003
189247
189680
189733
189936
189949
190072
190096
190126
190212
190432
190515
190699
190827
190998
191017
191041
191086
191337
191338
191786
191854
191858
192025
192078
192097
192166
192177
192181
192283
192574
192597
192764
192987
193114
193221
193247
193318
193412
193570
193650
193697
193717
193898
193933
194045
194106
194155
194351
194362
194397
194732
194825
194976
194993
195023
195134
195251
195274
195328
195588
195642
195707
195929
196165
196434
196469
196482
196511
196574
196688
196872
196930
196948
196952
197072
197123
197241
197258
197712
197714
197749
197765
197780
197812
197884
197889
197962
198059
198122
198174
198347
198361
198426
198732
198769
198944
199066
199152
199215
199222
199246
199400
199478
199726
199732
199959
200111
200204
200495
200506
200675
200705
200750
200760
200769
200947
200970
201086
201165
201247
201301
201328
201407
201548
201693
202058
202135
202187
202216
202273
202383
202385
202398
202506
202518
202527
202791
202889
203037
203128
203147
203209
203234
203235
203321
203335
203341
203379
203443
203513
203667
203672
203710
203795
203823
203867
203886
203889
203945
204020
204070
204080
204183
204314
204317
204406
204594
204615
205045
205311
205449
205567
205571
205709
205802
205825
206041
206043
206198
206452
206470
206473
206760
206788
206803
206891
207040
207097
207153
207218
207311
207327
207361
207544
207687
207760
207779
207882
207956
208040
208056
208197
208249
208263
208468
208586
208593
208656
208724
208833
209003
209055
209069
209131
209158
209253
209337
209398
209579
209593
209717
209727
209879
209992
210010
210034
210075
210239
210251
210276
210319
210388
210473
210499
210505
210512
210620
210936
211611
211826
211846
212136
212161
212333
212389
212396
212460
212507
212539
212679
212857
213131
213279
213530
213590
213688
213930
214121
214198
214277
214392
214470
214490
214584
214592
214823
214828
214850
214884
215031
215038
215046
215181
215317
215386
215644
215799
216659
216802
216920
217083
217154
217192
217205
217282
217421
217700
217750
217940
218068
218198
218480
218500
218607
218630
218731
218769
218779
219078
219081
219190
219231
219289
219394
219494
219647
219741
219809
219824
219846
219875
219882
220454
220629
220789
220845
220917
220953
220967
221001
221418
221539
221642
221824
221847
221857
221916
221994
221999
222066
222136
222254
222405
222499
222726
222980
223007
223066
223213
223234
223325
223346
223441
223488
223732
223749
223769
223874
223916
224050
224261
224813
225014
225076
225256
225442
225599
226372
226443
226516
226638
226719
226730
226755
226967
227001
227174
227478
227636
227676
227831
227834
227870
227905
227923
227962
228005
228038
228167
228292
228379
228384
228594
228695
228808
229039
229233
229495
229619
229729
229793
229852
229872
229924
230016
230071
230252
230260
230310
230313
230333
230437
230809
230857
231139
231153
231180
231283
231336
231383
231473
231626
231788
231862
231892
232006
232225
232341
232420
232462
232466
232467
232534
232621
232685
232724
232766
232818
232879
233089
233090
233157
233170
233218
233279
233435
233452
233513
233786
233888
233889
233937
233969
234102
234117
234167
234181
234313
234329
234968
234978
235015
235066
235174
235720
235790
235976
235998
236009
236090
236269
236407
236721
236795
236959
237048
237125
237162
237251
237357
237446
237856
237911
237946
237950
238034
238165
238328
238714
238858
238874
238898
238915
238931
238975
239161
239370
239509
239590
239650
239681
239750
239754
239846
239848
239857
239858
240036
240485
240501
240696
240766
240908
241072
241140
241300
241318
241586
241589
241727
241728
241890
242105
242137
242233
242357
242539
242561
242640
242668
242693
242706
242952
243310
243425
243571
243893
243933
244085
244089
244123
244501
244518
244909
245014
245038
245145
245317
245426
245515
245601
245833
245848
245931
245940
245970
245980
245987
245991
246044
246110
246118
246235
246290
246443
246479
246589
246731
246783
247447
248071
248143
248203
248338
248446
248480
248492
248553
248631
248638
248783
248827
248832
249338
249354
249378
249476
249856
249885
250344
250379
250388
250416
250780
250901
250928
250937
251068
251296
251340
251569
251826
251913
251945
251968
252016
252031
252040
252100
252602
252652
252818
252882
253204
253211
253496
253528
253687
253710
253738
254210
254211
254241
254315
254427
254477
254570
254642
254700
254931
254965
255038
255052
255245
255461
255481
255482
255530
255551
255570
255813
255836
255855
256039
256168
256527
256678
256685
256689
256731
256959
257077
257119
257153
257184
257250
257252
257285
257360
257799
257826
257888
257938
258084
258085
258086
258157
258176
258213
258276
258327
258336
258375
258450
258743
258863
258877
258919
258976
259069
259077
259153
259200
259346
259523
259524
259527
259590
259693
259731
259757
259812
259959
260108
260268
260274
260293
260353
260571
261004
261113
261147
261182
261246
261488
261546
261599
261672
261740
261766
262010
262076
262086
262131
262178
262224
262268
262285
262415
262471
262609
262755
262887
262904
262935
262995
263069
263160
263256
263316
263390
263524
263618
263810
263944
264072
264811
264812
264896
265045
265092
265181
265182
265268
265294
265366
265380
265431
265573
265706
266046
266054
266078
266204
266218
266226
266236
266281
266549
266642
266846
266848
266989
267048
267083
267126
267191
267209
267322
267874
267914
267917
268477
268604
268694
268876
269230
269285
269299
269320
269410
269452
269462
269581
269640
269696
269870
269988
270097
270210
270279
270366
270405
270545
270741
270788
271119
271156
271202
271431
271434
271451
271549
271733
271736
271754
271883
271964
271988
272112
272127
272189
272277
272407
272415
272516
272788
272906
272949
273095
273160
273372
273383
273504
273526
273763
273859
274075
274208
274241
274310
274359
274431
274484
274641
274652
274670
274881
274942
274976
275119
275126
275130
275205
275241
275262
275625
275692
275711
275726
275767
275772
275816
275923
276070
276094
276134
276303
276482
276518
276526
276630
276674
276813
276985
277205
277335
277352
277440
277453
277591
277593
277862
277958
277985
278054
278293
278294
278456
278592
278597
278633
278638
278987
279139
279165
279230
279379
279420
279499
279610
279664
279901
279902
279978
280004
280088
280250
280416
280595
280624
280626
280629
280814
281007
281357
281393
281423
281482
281854
282224
282340
282445
282522
282706
282729
282769
282784
282926
283026
283040
283068
283090
283140
283244
283275
283405
283437
283610
283676
283880
283917
284039
284165
284241
284407
284414
284419
284485
284691
284712
284892
284954
284975
285194
285210
285317
285334
285422
285446
285587
285646
285656
285716
285787
285846
286251
286322
286433
286452
286731
286769
286851
286974
287047
287141
287299
287356
287626
287777
287792
287808
287809
288025
288032
288087
288187
288210
288246
288326
288374
288378
288380
288444
288446
288668
288797
288810
288817
288921
288934
289319
289346
289440
289481
289593
289784
289832
289837
289855
289879
289980
290080
290164
290179
290210
290260
290274
290286
290298
290299
290355
290485
290637
290718
290773
290801
291014
291021
291023
291041
291114
291279
291493
291633
291678
291690
291703
291740
292208
292706
292751
292794
292839
292869
293004
293194
293246
293247
293446
293522
293704
293776
293787
293913
293947
294186
294294
294441
294594
294663
294769
294816
294931
295061
295082
295199
295333
295379
295391
295438
295483
295497
295500
295551
295723
295731
295751
295970
295995
296081
296122
296223
296382
296428
296539
296603
296659
296745
296749
296761
296775
296841
296939
297064
297067
297096
297155
297217
297395
297411
297573
297694
298036
298189
298198
298274
298304
298311
298532
298567
298810
298823
298863
298869
298935
298963
299077
299104
299205
299239
299247
299530
299702
299862
299970
300210
300218
300308
300419
300493
300532
300614
300688
300719
300754
300787
301264
301293
301315
301345
301532
301613
301629
301696
301770
301778
301791
301798
301872
301999
302236
302391
302520
302669
302671
302987
303051
303329
303468
303540
303755
303815
303819
303859
303903
304100
304147
304157
304190
304212
304270
304455
304572
304735
304738
304767
304898
305078
305147
305215
305231
305420
305615
305807
305876
305894
305954
305958
306271
306288
306298
306322
306332
306392
306418
306422
306592
307083
307152
307260
307266
307342
307347
307368
307431
307620
307625
307785
307846
308107
308191
308211
308233
308242
308256
308336
308339
308411
308509
308536
308604
308605
308613
308789
308987
309415
309550
309578
309605
309834
309887
309911
309958
310342
310386
310422
310680
310895
310947
311074
311089
311183
311312
311417
311444
311514
311519
311598
311790
311863
312123
312168
312216
312285
312322
312332
312405
312411
312458
312465
312826
312845
312862
312948
313026
313100
313134
313254
313364
313427
313563
313879
314009
314047
314115
314118
314348
314484
314538
314650
314884
314915
314946
315001
315027
315124
315241
315289
315350
315371
315390
315392
315494
315623
315746
315828
315915
315996
316233
316355
316431
316478
316559
316759
316964
317006
317107
317194
317296
317658
317743
317868
317989
317991
318064
318215
318228
318302
318381
318407
318590
318948
318987
319004
319092
319099
319247
319296
319404
319969
320003
320209
320225
320535
320541
321119
321364
321688
321792
321867
321870
321972
322122
322231
322244
322362
322403
322428
322473
322633
322691
322696
322710
322713
322868
322946
322986
323007
323108
323132
323324
323362
323803
323930
324147
324222
324282
324379
324440
324510
324523
324639
324658
324667
324719
324898
325299
325344
325367
325376
325455
325477
325538
325663
325704
325722
325723
325758
325813
325857
325963
326039
326059
326064
326117
326243
326271
326537
326572
326772
326829
327069
327145
327158
327247
327391
327492
327530
327575
327620
327630
327724
327893
327961
327975
328076
328174
328217
328284
328360
328374
328481
328561
328658
328732
328754
328808
328871
329079
329112
329123
329135
329197
329465
329740
329843
329907
329981
330050
330211
330285
330303
330397
330403
330482
330529
330574
330600
330705
330760
330975
331098
331445
331541
331584
331675
331787
331789
331873
331926
331969
331979
331996
332048
332188
332208
332262
332537
332734
332948
332959
333016
333095
333142
333187
333283
333430
333506
333689
333852
333928
334018
334044
334141
334275
334653
334701
334762
334788
334829
334964
335001
335033
335100
335200
335332
335457
335528
335643
335679
335798
335885
336040
336159
336246
336298
336395
336405
336709
336746
337013
337166
337199
337323
337360
337403
337681
338089
338122
338124
338378
338470
338555
338581
338807
338849
339014
339158
339410
339485
339491
339724
339842
340339
340359
340391
340432
340622
340858
340878
341017
341036
341053
341098
341234
341279
341286
341287
341400
341450
341514
341628
341734
342141
342153
342195
342355
342366
342370
342662
342759
342911
343056
343069
343079
343115
343167
343233
343266
343300
343415
343438
343546
343556
343669
343841
344298
344307
344321
344639
344711
344739
344748
344986
345030
345031
345168
345179
345299
345508
345578
345767
345940
345970
346059
346072
346133
346364
346501
346756
346816
346849
346891
346994
347015
347113
347250
347374
347739
347746
347811
347872
347879
347959
348041
348114
348296
348320
348499
348599
348715
348726
348781
348892
348956
348961
348977
349222
349236
349304
349402
349468
349580
349594
349596
349630
349661
349773
349841
349902
350147
350164
350464
350527
350569
350819
350937
351042
351232
351293
351317
351428
351704
351816
351894
352017
352146
352159
352227
352243
352401
352561
352662
352781
352824
352941
352942
352960
353331
353484
353485
353500
353703
353762
353785
354086
354508
354735
355016
355120
355156
355165
355253
355288
355544
355566
355602
355617
355904
355910
355933
356246
356253
356256
356262
356279
356292
356295
356366
356377
356490
356606
356848
356857
356881
356900
356905
356959
356997
357009
357011
357094
357130
357194
357297
357666
357677
357732
357773
358037
358095
358112
358117
358196
358222
358370
358472
358547
358695
358724
358780
358815
358854
358948
359034
359178
359242
359251
359254
359352
359418
359420
359445
359573
359880
360022
360064
360161
360280
360480
360501
360529
360618
360704
360778
360839
361019
361162
361291
361336
361355
361893
362162
362197
362263
362475
362524
362595
362642
363090
363120
363144
363198
363241
363317
363458
363471
363474
363794
363959
363987
364047
364068
364160
364162
364213
364229
364238
364241
364247
364302
364357
364527
364592
364696
364737
364814
364908
364918
365195
365462
365533
365692
365755
366036
366075
366133
366441
366466
366498
366533
366548
366693
366696
366765
366893
366896
366946
366968
367386
367482
367529
367670
367747
367797
367920
368069
368070
368084
368226
368525
368600
368855
368888
369030
369084
369369
369394
369594
369657
369671
369741
369759
369782
369966
369988
370060
370185
370294
370297
370424
370471
370489
370498
370515
370576
370585
370625
370804
370979
371006
371103
371185
371210
371238
371261
371569
371618
371656
371658
371746
372057
372166
372205
372236
372506
372521
372557
372617
372707
373063
373196
373208
373243
373328
373410
373485
373544
373554
373660
373676
373705
373768
373812
374012
374098
374109
374146
374244
374360
374466
374576
374628
374652
374698
374726
374775
374781
374952
374960
375107
375145
375161
375188
375289
375486
375577
375669
375785
375824
375963
376367
376461
376762
376966
377087
377121
377228
377322
377353
377384
377777
377952
377989
378022
378242
378302
378319
378354
378362
378383
378514
378528
378715
378825
378890
379008
379105
379195
379338
379394
379455
379549
379652
379744
379861
380319
380392
380485
380892
381084
381206
381270
381473
381578
381611
381629
381637
381971
382068
382105
382284
382437
382449
382467
382492
382555
382606
382640
382812
382849
383141
383423
383449
383543
383680
383727
383824
383837
383983
384141
384257
384275
384435
384462
384605
384857
384908
384928
385092
385169
385244
385304
385364
385515
385623
385811
385944
385961
386192
386234
386368
386568
386641
386668
387224
387272
387506
387569
387603
387675
387794
387824
388023
388116
388275
388570
388614
388677
388696
388742
388794
388947
389063
389109
389279
389534
389660
389661
389675
389936
390073
390339
390400
390417
390451
390470
390962
391055
391195
391821
391862
391874
392005
392294
392376
392463
392655
392840
393150
393299
393382
393563
393646
393698
393811
393932
394016
394305
394354
394686
394704
394795
394829
394834
394884
394957
394985
395115
395136
395254
395259
395535
395546
395612
395651
395761
395981
396089
396111
396408
396673
397088
397191
397662
397732
397873
397910
397950
398497
398574
398731
398892
399423
399464
399599
399623
399647
399738
399825
399952
400014
400081
400093
400245
400365
400400
400440
400563
400587
400799
400913
400934
401181
401183
401483
401721
401757
402052
402096
402105
402215
402418
402420
402536
402722
402735
403331
403363
403490
403533
403542
403553
403632
403669
403830
403957
404104
404293
404415
404523
404572
404746
404838
404857
404862
404883
404996
404998
405023
405178
405241
405277
405349
405373
405454
405686
405778
405932
405961
405974
406019
406134
406167
406401
406410
406642
406903
407012
407034
407110
407150
407159
407248
407275
407382
407534
407624
407994
408080
408146
408156
408480
408724
408775
408890
408940
409035
409038
409089
409176
409384
409445
409471
409670
409819
409824
409937
409942
410060
410143
410163
410202
410553
410559
410653
410765
410766
410901
411159
411188
411290
411360
411385
411400
411437
411438
411442
411484
411577
411647
411726
411734
411735
411832
411933
412149
412207
412232
412477
412479
412570
412598
412688
412812
412934
412957
413026
413064
413241
413478
413508
413528
413700
414002
414227
414262
414353
414480
414526
414808
414865
414932
414992
415002
415005
415127
415164
415192
415275
415324
415344
415750
415767
415827
415904
415907
415963
415974
416018
416053
416233
416244
416266
416382
416602
416720
417089
417355
417374
417419
417536
417562
417580
417752
417901
417918
417998
418130
418287
418290
418316
418528
418586
418673
418678
418887
418897
419020
419184
419185
419233
419328
419493
419660
419757
419849
419860
419931
420071
420090
420187
420378
420413
420432
420444
420680
420689
420807
420859
420909
420923
421149
421215
421219
421240
421361
421375
421417
421436
421550
421715
421967
422118
422331
422398
422427
422532
422538
422569
422653
422924
423034
423407
423503
423702
423754
423829
423979
424001
424026
424134
424323
424396
424425
424532
424536
424549
424568
424614
424767
424791
424863
424868
424899
425018
425137
425234
425248
425289
425377
425378
425433
426196
426427
426443
426447
426518
426749
426786
426876
426953
426974
426977
426992
427003
427006
427011
427069
427220
427252
427277
427288
427407
427461
427498
427525
427707
427827
427970
427986
428057
428253
428362
428374
428663
428673
428755
428893
429138
429284
429296
429317
429332
429428
429581
429847
430014
430121
430343
430390
430480
430491
430602
430724
430829
431063
431374
431409
431411
431450
431658
431916
431938
432046
432062
432144
432359
432417
432840
432934
433301
433422
433946
434001
434029
434386
434400
434474
434561
434773
434781
434847
434885
434912
435004
435027
435033
435047
435067
435172
435207
435362
435464
435600
435731
435782
435826
435834
436036
436061
436117
436436
436604
436685
436797
436829
436916
436947
436953
436989
437180
437185
437388
437438
437516
437633
437876
438075
438182
438230
438365
438654
438723
439058
439186
439289
439347
439372
439492
439653
439668
439671
439690
439716
439718
439996
439997
440218
440240
440263
440327
440434
440587
440598
440623
440726
440804
440911
441183
441363
441439
441658
442031
442415
442503
442530
442622
442693
442775
442778
442919
442979
443075
443159
443330
443438
443679
443949
444020
444049
444150
444301
444399
444421
444450
444522
444808
444821
444872
444914
444975
445063
445140
445191
445195
445259
445320
445471
445524
445644
445782
445870
445990
446068
446418
446462
446482
446497
446540
446640
446739
446960
447106
447140
447239
447452
447491
447661
447992
448152
448161
448235
448248
448328
448488
448553
448603
448706
448819
448841
448883
449180
449217
449365
449412
449701
449744
449800
449815
449835
449841
449844
449894
449940
450026
450216
450286
450536
450819
450841
451142
451247
451259
451397
451418
451527
451673
451700
451726
451738
451755
451871
451926
451954
452136
452383
452419
452435
452669
452675
452714
452847
452992
453150
453168
453240
453411
453446
453644
453763
453771
453806
453814
453834
453990
454237
454305
454413
454564
454646
454833
454852
454869
454956
454983
455013
455022
455039
455392
455453
455488
455501
455532
455679
455773
456135
456179
456192
456363
456400
456470
456497
456737
457157
457184
457309
457416
457440
457459
457579
457706
457763
457894
457941
457953
458362
458376
458395
458431
458437
458483
458534
458586
458959
459185
459273
459490
459529
459589
459670
459752
459926
459978
460008
460035
460064
460115
460410
460490
460508
460526
460536
460621
460900
460910
460961
460977
461023
461098
461126
461194
461206
461217
461249
461414
461856
461858
462029
462035
462394
462493
462759
462851
462992
463141
463158
463581
463754
463897
463971
464302
464313
464544
464682
464735
464829
464847
464932
465195
465344
465364
465399
465469
465530
465558
465584
465684
465696
465725
465751
465755
465817
465974
466020
466039
466108
466138
466259
466298
466410
466556
466640
466668
467011
467261
467339
467358
467362
467662
467710
467721
467809
467858
468045
468324
468346
468356
468394
468404
468481
468490
468544
468743
468969
469063
469176
469253
469278
469288
469345
469498
469565
469567
469645
469722
469759
469786
469937
469992
470071
470457
470662
470789
470889
470913
471094
471119
471202
471289
471545
471570
471636
471741
471766
471832
471983
472059
472173
472266
472435
472509
472819
472833
472839
472908
473048
473167
473273
473432
473527
473719
473758
474071
474216
474226
474456
474492
474562
474567
474663
474919
475420
475554
475636
475728
475856
475898
475921
475973
476108
476167
476329
476575
476788
476806
476906
477167
477254
477345
477398
477831
477849
477890
477908
478113
478139
478192
478288
478362
478386
478491
478499
478549
478588
478614
478854
479006
479026
479072
479145
479225
479233
479266
479518
479566
479574
479576
479606
479725
479834
479853
480028
480143
480168
480649
480660
480829
480897
481036
481046
481148
481300
481472
481537
481797
481881
481978
482120
482202
482205
482379
482471
482540
482554
482612
482645
482855
482858
482955
483179
483189
483246
483371
483425
483467
483516
483524
483544
483561
483768
483882
483929
483994
484005
484036
484111
484317
484430
484635
484679
484753
484874
484929
484958
484991
485197
485350
485365
485418
486058
486074
486101
486163
486183
486184
486329
486407
486581
486652
486667
487035
487136
487175
487237
487393
487589
487657
487673
487689
487816
487841
487987
488129
488130
488233
488447
488586
488694
488895
488963
488989
489026
489135
489161
489199
489291
489297
489348
489452
489507
489529
489567
489575
490310
490413
490644
490656
490676
490686
490853
490999
491572
491652
491696
491747
491884
491981
492060
492095
492393
492404
492583
492608
492869
492902
492976
493164
493191
493227
493322
493380
493386
493458
493691
493707
493966
493998
494035
494403
494467
494720
494722
494910
495163
495324
495629
495878
495962
496062
496089
496166
496190
496341
496406
496665
496689
496770
496773
496995
497276
497288
497303
497345
497393
497458
497681
497903
498037
498057
498129
498257
498328
498376
498585
498591
498655
498864
499069
499488
499742
499829
499920
499945
499954
500041
500441
500478
500496
500583
500638
500658
500789
500820
500853
500988
501006
501008
501137
501142
501169
501198
501245
501364
501532
501691
501921
502047
502141
502156
502230
502244
502442
502657
502940
502958
503010
503043
503052
503160
503164
503166
503167
503192
503208
503314
503491
503667
504125
504179
504198
504235
504406
504510
504511
504572
504589
504638
504651
504698
504705
504755
504919
504932
505060
505189
505232
505309
505504
505561
505626
505697
505737
505757
505765
505786
505971
506015
506105
506381
506388
506519
506522
506526
506531
506570
506749
506807
507150
507220
507226
507638
507661
507812
507820
507981
507993
508091
508143
508328
508447
508836
508976
508982
509114
509143
509317
509478
509530
509535
509606
509621
509655
509745
509975
510038
510073
510165
510235
510352
510364
510407
510466
510469
510483
510907
510975
511051
511102
511108
511189
511217
511314
511629
511646
511858
511974
511982
512061
512238
512269
512273
512483
512489
512660
512698
512702
512789
513222
513418
513606
513829
513830
514154
514529
514534
514914
514987
515204
515337
515370
515426
515603
515754
515802
515958
516127
516139
516154
516199
516260
516467
516514
516543
516574
516629
516828
516915
516933
516938
517004
517157
517271
517352
517577
517732
517839
517872
518098
518394
518435
518574
518695
518705
519151
519255
519325
519464
519510
519520
519568
519715
519718
519743
519769
519827
519904
519916
520121
520317
520330
520458
520462
520505
520566
520769
520806
520972
520986
521123
521170
521191
521250
521263
521366
521490
521513
521578
521624
521643
521695
521841
522026
522027
522134
522168
522185
522360
522379
522435
522498
522550
522584
522711
522851
523008
523043
523079
523097
523168
523182
523266
523296
523321
523574
523684
523692
523722
523906
524020
524058
524093
524210
524393
525072
525585
525591
525622
525661
525754
526106
526171
526215
526343
526382
526411
526456
526638
526804
526874
526924
526955
526963
527171
527189
527362
527365
527574
527650
527723
527725
527828
527848
527875
528062
528079
528290
528330
528332
528460
528537
528561
528904
529091
529101
529213
529345
529647
529653
529681
529766
529806
529994
530036
530062
530067
530083
530140
530176
530383
530505
530588
530619
530899
530927
530993
531030
531100
531119
531234
531298
531300
531370
531489
531571
531820
531854
532212
532229
532231
532247
532263
532293
532334
532429
532625
532732
532990
533323
533412
533484
533501
533600
533625
533642
533676
534037
534132
534144
534162
534216
534380
534476
534557
534610
535027
535047
535159
535551
535643
535896
535920
535928
535947
535950
535978
536079
536109
536221
536369
536636
536647
536772
536787
536835
536925
536976
537136
537171
537253
537342
537414
537422
537732
537929
537939
537994
537999
538087
538133
538322
538333
538339
538367
538473
538485
538596
538637
538699
538801
538871
538965
539097
539314
539366
539589
539706
539915
539963
540001
540066
540177
540335
540354
540623
540741
540812
540850
540950
540982
541274
541305
541318
541459
541567
541572
541594
541717
541951
542209
542226
542269
542402
542485
542546
543126
543407
543549
543663
543784
543997
544090
544126
544147
544392
544430
544433
544458
544637
544654
544704
544830
545242
545418
545754
545808
545872
545955
545959
545971
545983
546041
546360
546402
546499
546551
546846
547335
547444
547530
547624
547796
547820
547918
548062
548285
548359
548603
548751
548865
548943
549052
549120
549267
549300
549328
549376
549503
549530
549559
549585
549628
549707
549879
549906
549918
550378
550391
550495
550746
550975
551055
551210
551281
551283
551578
551601
551630
552129
552155
552157
552335
552388
552404
552588
552642
552808
552861
552995
553010
553079
553102
553182
553207
553295
553428
553507
553532
553544
553675
553884
554488
554576
554587
554740
554837
554921
555027
555076
555086
555170
555173
555282
555368
555404
555418
555425
555464
555492
555554
555731
556241
556349
556370
556542
556586
556637
556787
556807
556850
556857
556998
557148
557216
557269
557299
557531
557572
557592
557833
558124
558125
558364
558372
558381
558465
558502
558648
558735
558739
558899
559119
559133
559291
559311
559459
559606
559671
559974
560089
560136
560318
560426
560949
561041
561113
561465
561705
561741
562042
562060
562368
562474
562477
562558
562697
562732
562761
562847
562870
562874
562917
562941
563040
563129
563184
563522
563560
563647
563730
563734
564059
564143
564536
564640
564657
564824
565437
565438
565510
565539
565544
565648
565731
565882
565884
565998
566031
566085
566351
566578
566629
566655
566664
566712
566978
566991
567043
567085
567090
567229
567335
567544
567601
567687
567861
567961
568004
568166
568225
568395
568397
568413
568447
568466
568600
568684
568712
568801
568810
568872
568949
569078
569355
569405
569482
569724
569775
569835
569902
569912
570221
570330
570463
570536
570661
570709
570769
570959
571049
571324
571363
571531
571596
571940
572064
572066
572246
572262
572270
572271
572322
572400
572444
572465
572546
572574
572578
572651
572871
573240
573294
573443
573503
573519
573533
573566
573687
573694
573732
573930
573947
574153
574245
574516
574582
574585
574605
574778
575044
575233
575234
575261
575291
575353
575415
575474
575545
575564
575660
575695
575711
575715
575740
575749
575832
575845
576202
576225
576288
576471
576473
576505
576532
576586
576596
576692
576834
576932
576964
577038
577170
577242
577287
577421
577442
577511
577564
577606
577760
577820
577919
578024
578278
578613
578643
579125
579129
579165
579453
579467
579472
579589
579672
579692
579807
579948
580039
580137
580202
580228
580255
580330
580396
580399
580412
580436
580501
580549
580602
580647
580932
581017
581018
581230
581242
581276
581352
581392
581967
582013
582019
582395
582620
582799
582842
583050
583473
583509
583601
583702
583710
583718
583767
583865
583898
584091
584292
584456
584488
584656
584717
584915
584923
585152
585173
585182
585248
585351
585368
585481
585497
585542
585875
585999
586301
586458
586464
586501
586537
586729
586756
586820
586910
586996
587082
587091
587365
587682
587683
587755
587763
587940
587960
588230
588366
588459
588522
588690
588721
588818
588857
588924
589022
589095
589119
589268
589501
589503
589623
590053
590131
590196
590282
590433
591009
591036
591057
591082
591164
591262
591457
591481
591492
591765
591796
591814
591841
591987
592032
592430
592462
592490
592524
592616
592642
592704
592731
592848
593069
593083
593102
593115
593183
593280
593308
593667
593712
593811
593865
593877
593954
593959
594052
594174
594598
594629
594803
595273
595287
595344
595574
595634
595684
595691
595724
595791
595925
596297
596368
596410
596481
596576
596635
596716
597226
597305
597349
597408
597549
597693
597754
597783
597816
598055
598342
598525
598764
598768
598802
598850
599044
599270
599298
599395
599452
599672
600101
600103
600104
600138
600194
600205
600236
600445
600460
600603
601215
601561
601591
601597
601697
601756
601764
601876
601926
602076
602204
602271
602415
602443
602478
602899
602966
602994
603028
603107
603201
603302
603396
603449
603503
603529
603566
603756
603841
604032
604042
604147
604328
604643
604831
604929
605150
605180
605224
605340
605405
605526
605660
605663
605700
605730
605800
605923
606162
606500
606700
606840
606852
606853
606867
606936
607105
607538
607784
607878
607881
607951
607954
608128
608133
608436
608523
608585
608614
608972
609054
609139
609358
609384
609583
609600
609802
609969
609978
610072
610103
610112
610128
610313
610403
610435
610456
610531
610540
610594
610630
610722
610758
610934
610965
611006
611029
611117
611206
611288
611388
611502
611516
611551
611817
612288
612306
612311
612357
612391
612428
612629
612725
612760
613134
613222
613227
613251
613284
613304
613413
613588
613789
613833
613878
614176
614554
614643
614748
614844
615017
615030
615042
615043
615044
615167
615284
615318
615399
615436
615737
615743
615808
615983
616217
616242
616311
616417
616464
616608
616681
616779
616836
616838
616968
617155
617439
617629
617676
617845
617921
617933
617943
618088
618110
618387
618487
618538
618558
618563
618575
618627
618647
618710
619109
619193
619240
619474
619483
619505
619532
619744
619757
619778
620091
620260
620294
620448
620488
620812
620905
620917
621061
621068
621097
621149
621246
621332
621521
621615
621740
621802
621842
621874
621978
621986
622012
622156
622521
622573
622600
622797
622851
623201
623768
623981
623999
624016
624148
624182
624226
624249
624374
624699
624831
624858
624871
625078
625193
625402
625434
625450
625519
625586
625615
625733
626030
626239
626275
626307
626368
626377
626392
626458
626579
626645
626664
626685
626686
626916
626952
626987
627107
627176
627393
627477
627600
627617
627713
627991
628006
628016
628037
628167
628195
628200
628379
629072
629081
629101
629107
629114
629123
629154
629209
629217
629241
629275
629281
629496
629586
629768
629919
629960
630041
630220
630232
630382
630520
630534
630743
630933
630969
630984
631137
631170
631251
631277
631305
631317
631414
631459
631514
631523
631532
631614
631635
631730
631742
631996
632033
632289
632296
632459
632592
632616
632637
632913
632979
633150
633156
633309
633401
633435
633556
633607
633624
633633
633807
633828
633898
633977
634124
634370
634462
634467
634726
634772
634880
634915
634927
635187
635278
635372
635375
635502
635514
635778
635784
635873
635928
636048
636097
636138
636276
636339
636343
636358
636640
636678
636756
636810
636826
637058
637217
637219
637529
637539
637571
637574
637591
637818
637851
637909
638022
638052
638153
638274
638687
638702
638797
638854
638959
638969
639021
639086
639112
639290
639318
639441
639503
639686
639711
639764
639844
639846
639929
640130
640179
640365
640449
640485
640550
640618
641121
641162
641283
641297
641322
641327
641397
641427
641434
641496
641684
641704
641724
641765
641913
641923
642038
642106
642107
642292
642294
642390
642433
642467
642506
642593
642709
642756
642895
642896
642903
642993
643015
643226
643297
643320
643801
643817
643901
644116
644237
644238
644363
644621
644679
644723
644847
644928
644996
645024
645038
645050
645256
645439
645493
645505
645574
645625
645875
645894
645967
645977
645997
646154
646222
646250
646479
646485
646514
646652
646676
646766
647280
647305
647357
647471
647571
647625
647776
647785
647803
648219
648423
648437
648476
648748
648771
648924
648963
649059
649434
649455
649532
649550
649617
649662
649797
649810
649835
649873
649915
649930
649935
649961
649987
650027
650048
650058
650067
650132
650289
650417
650625
650740
650993
651003
651067
651215
651254
651451
651460
651667
651892
651902
652206
652225
652331
652357
652420
652600
652663
652677
652844
652884
653110
653163
653294
653309
653809
653829
653932
654268
654518
654527
654644
654689
654712
654807
654843
654948
655007
655246
655258
655300
655355
655571
655594
655854
655865
655867
656026
656065
656181
656212
656240
656267
656286
656454
656634
656687
656740
656755
656772
656788
656791
656847
657154
657368
657401
657498
657524
657554
657574
657626
657667
657678
657680
657801
657802
657806
657978
658535
658577
658607
658627
658642
658750
659158
659175
659225
659360
659390
659711
659763
659818
659826
659861
659899
659949
659961
660001
660090
660115
660401
660424
660425
660468
660550
660640
660643
660691
660774
660838
660852
660911
660954
661005
661065
661233
661284
661386
661589
662124
662132
662213
662232
662245
662336
662469
662600
662684
662808
662851
662963
663107
663358
663432
663442
663498
663673
663820
663946
663958
664266
664273
664423
664443
664460
664636
664727
664785
664810
664848
664866
664925
664993
665268
665407
665555
665607
665738
665897
665915
666131
666184
666360
666499
666507
666731
666799
667121
667151
667161
667191
667250
667361
667378
667441
667481
667570
667662
667737
667824
667952
668069
668223
668283
668287
668322
668427
668441
668445
668535
668600
668750
668755
668978
669111
669239
669263
669265
669307
669377
669463
669566
669575
669663
669751
669799
669888
669933
669956
669978
670171
670225
670241
670301
670633
670672
670759
670770
670855
671043
671045
671058
671154
671192
671264
671407
671443
671528
671653
671689
671959
672060
672072
672143
672270
672275
672296
672370
672382
672437
672455
672467
672495
672520
672639
672878
672893
672911
672918
672926
673070
673114
673218
673271
673279
673483
673555
673594
673668
673678
673717
673932
674006
674291
674400
674477
674588
674663
674764
674809
674947
675005
675082
675372
675406
675440
675521
675808
675918
676150
676204
676234
676364
676480
676517
676552
677001
677019
677045
677079
677127
677155
677296
677299
677318
677390
677456
677466
677542
677574
677605
677650
677661
677669
677872
677931
678130
678215
678295
678406
678428
678497
678504
678576
678643
678761
678770
678777
678824
678960
679061
679164
679179
679430
679581
679610
679622
679897
680124
680179
680259
680284
680392
680708
680783
680888
681012
681107
681589
681592
681783
681813
681892
681893
681939
681990
682022
682028
682114
682217
682244
682372
682588
682620
682699
682718
682969
683000
683155
683169
683205
683247
683336
683535
683579
683841
683846
683968
684011
684016
684068
684137
684148
684229
684398
684410
684429
684431
684552
684643
684761
684777
684782
684784
684813
685007
685220
685236
685272
685488
685509
685640
685789
685853
685921
686153
686265
686274
686430
686684
686725
686793
687014
687352
687466
687479
687509
687618
687720
687770
687816
687892
688107
688339
688569
688618
688770
689067
689093
689179
689356
689480
689490
689591
689631
689670
689672
689723
689825
689879
689919
690303
690425
690595
690821
691034
691071
691572
691624
691708
691731
691753
691816
691889
692044
692741
693010
693033
693130
693472
693564
693667
693738
693771
693778
693779
693899
693939
693963
694263
694409
694475
694506
694629
694639
694674
694728
694777
694833
695009
695140
695186
695202
695347
695408
695419
695435
695510
695607
695666
695720
695878
696049
696250
696442
696540
696570
696619
697012
697070
697467
697534
697556
697592
697596
697604
697634
697751
697753
697864
697955
698029
698093
698124
698181
698202
698205
698293
698349
698350
698427
698479
698788
698883
698938
699117
699120
699158
699194
699277
699311
699494
699612
699649
699652
699714
699933
699956
700150
700247
700355
700406
700480
700889
700907
700937
701020
701192
701208
701239
701260
701278
701302
701412
701545
701575
701709
701794
701852
701896
701974
701988
702006
702056
702205
702234
702467
702591
702624
702640
702919
702970
703157
703208
703294
703548
703893
703991
704044
704148
704187
704290
704331
704376
704426
704493
704571
704589
704602
704660
704706
704719
704891
704967
705018
705164
705258
705265
705487
705674
705814
705913
705966
706003
706015
706035
706052
706059
706350
706425
706544
706669
706910
707008
707041
707111
707378
707429
707518
707707
707816
707954
708007
708020
708028
708091
708148
708183
708285
708333
708347
708403
708513
708688
708796
708910
708912
709061
709127
709177
709257
709360
709488
709640
709687
709818
709997
710014
710351
710368
710480
710708
710722
710762
710809
710992
710996
711023
711028
711043
711051
711078
711240
711522
711559
711670
711788
711859
711944
712214
712315
712316
712340
712468
712475
712483
712492
712548
712637
712676
712687
712738
712771
713132
713160
713333
713366
713386
713511
713564
713627
713678
713710
714289
714316
714340
714557
714586
714789
714827
714974
714976
715211
715291
715349
715366
715374
715611
715671
715703
715736
715777
716025
716027
716071
716161
716213
716278
716445
716464
716709
716769
716781
716825
716929
717152
717165
717185
717207
717248
717273
717463
717526
717593
717849
717895
717897
717944
717991
718034
718125
718371
718397
718440
718501
718526
718556
718633
718900
718934
719240
719258
719478
719493
719510
719588
719612
719651
719685
719709
719811
719830
719845
719937
720036
720055
720246
720286
720571
720632
720651
720874
720949
721048
721111
721113
721149
721164
721183
721317
721415
721568
721577
721667
721762
721810
721851
721996
722033
722044
722253
722257
722311
722331
722457
722458
722517
722548
722579
722846
722891
723061
723190
723270
723334
723387
723398
723420
723445
723454
723492
723629
723636
723683
723708
724091
724360
724485
724507
724512
724520
724587
724702
724956
724968
724974
724988
725143
725179
725423
725445
725507
725602
725706
725787
726059
726147
726180
726181
726188
726296
726308
726356
726481
726559
726578
726667
726900
726995
727103
727217
727239
727258
727259
727359
727566
727656
727789
727869
728128
728433
728523
728900
728923
728931
728963
728983
729207
729223
729351
729381
729492
729620
729690
729732
729883
729890
730279
730435
730500
730552
730793
730796
730954
731029
731054
731072
731119
731142
731193
731323
731330
731803
731813
731838
731897
731927
731936
732082
732096
732409
732649
732777
732933
733032
733067
733287
733311
733390
733467
733581
733671
734103
734285
734320
734358
734451
734599
734629
734659
734720
734842
735086
735146
735176
735214
735320
735331
735399
735462
735513
735699
735836
735840
736095
736302
736412
736532
736576
736648
736799
736895
736947
737094
737124
737344
737479
737590
737730
737870
738118
738203
738224
738448
738470
738484
738569
738716
738860
738957
739145
739265
739324
739453
739814
740249
740286
740508
740678
740777
740786
740950
740972
741154
741197
741252
741278
741483
741486
741566
741671
741675
741891
742297
742301
742405
742492
742504
742817
742959
742981
742983
743020
743175
743233
743275
743305
743381
743478
743523
743602
743694
743802
743815
743895
744065
744135
744143
744234
744244
744478
744492
744710
744747
744754
744773
744787
744888
744964
744983
745051
745146
745152
745285
745295
745348
745533
745671
745825
746088
746233
746238
746482
746514
746585
747102
747138
747240
747266
747269
747276
747364
747397
747422
747444
747486
747650
747684
747759
747844
747871
747878
748013
748179
748208
748209
748525
748539
749018
749044
749084
749146
749187
749291
749557
749672
749822
749917
750181
750187
750264
750276
750582
750643
750726
751081
751086
751140
751392
751616
751622
751644
751763
751772
751869
751902
752011
752041
752060
752177
752265
752372
752389
752428
752549
752635
752721
752777
753351
753436
753481
753785
753916
754022
754069
754104
754130
754433
754473
754573
754711
754731
754827
754911
755024
755080
755211
755336
755337
755384
755508
755571
755919
755941
756032
756286
756436
756449
756494
756538
756574
756702
757017
757216
757338
757345
757378
757379
757578
757655
757945
757995
758325
758458
758580
758876
758884
758888
758892
758915
758968
758989
759150
759308
759316
759481
759551
759667
759875
759942
759951
759981
759990
760401
760535
760787
760838
760963
761032
761145
761235
761297
761311
761474
761531
761681
761703
761713
761797
761866
761958
762049
762064
762109
762179
762328
762422
762518
762764
763049
763069
763100
763132
763146
763191
763275
763543
763636
763639
763653
764002
764072
764077
764199
764647
764662
764734
764742
764952
764964
765018
765036
765050
765127
765143
765167
765245
765366
765389
765548
765601
765616
765679
765692
765734
765848
765857
766033
766078
766174
766313
766383
766394
766395
766399
766411
766412
766513
766589
766623
766629
766673
767162
767237
767359
767375
767395
767472
767729
767760
767780
767802
767829
767831
767969
768151
768230
768478
768479
768487
768544
768670
768815
768835
768861
768902
769013
769048
769068
769086
769118
769313
769368
769737
769789
769840
769869
769934
770070
770269
770442
770501
770541
770565
770575
770621
770733
770737
770803
770834
770962
770977
771001
771024
771205
771228
771231
771371
771377
771416
771445
771577
771606
771759
771791
771877
771893
772037
772229
772257
772322
772323
772454
772621
772624
772633
772654
772921
772972
773106
773164
773557
773614
773615
773718
774047
774092
774166
774275
774329
774432
774609
774676
774734
774829
774909
774927
775002
775043
775310
775415
775440
775517
775861
775955
776002
776105
776294
776367
776452
776683
776688
776737
776749
776928
776937
777420
777466
777554
777616
777625
777680
777885
777926
778179
778266
778363
778371
778504
778512
778525
778605
778607
778629
779138
779173
779294
779428
779523
779534
779580
779605
779695
779706
779837
779861
779881
779998
780003
780005
780025
780120
780152
780181
780298
780308
780421
780432
780661
780662
780687
780826
780964
780969
781248
781250
781348
781392
781693
781876
781919
782027
782101
782348
782373
782379
782383
782412
782475
782617
783043
783160
783244
783293
783415
783459
783670
783717
783953
783984
784228
784270
784351
784390
784414
784470
784506
784526
784668
784740
784848
784926
785085
785154
785199
785272
785312
785435
785583
785675
785729
785735
785922
785924
786067
786198
786205
786375
786519
786615
786729
786736
786878
787101
787139
787179
787347
787348
787377
787395
787617
787686
787701
788047
788197
788424
788789
788937
789086
789134
789225
789237
789290
789457
789597
789615
790033
790136
790314
790376
790397
790439
790635
790721
790853
790932
790965
790989
791001
791288
791363
791408
791596
791783
791792
792054
792243
792433
792455
792762
792831
792863
792895
793139
793291
793334
793531
793697
793885
793905
794027
794071
794172
794188
794259
794374
794426
794571
794582
794584
794739
795003
795107
795172
795256
795264
795272
795381
795393
795564
795819
795851
796135
796137
796151
796256
796285
796316
796508
796514
796623
796628
796689
796691
796875
797069
797209
797210
797338
797400
797414
797422
797765
797809
797936
797948
798031
798147
798259
798282
798373
798445
798609
798721
798884
799095
799140
799278
799281
799344
799401
799578
799620
799626
799720
799827
799838
799882
799887
799972
800042
800081
800523
800536
800539
800687
800775
800834
800889
801175
801286
801337
801451
801507
801544
801662
801688
801917
801921
802165
802293
802402
802442
802450
802593
802901
802902
803143
803284
803412
803449
803717
803722
803784
803914
804117
804202
804299
804447
804600
804732
804753
804817
805030
805035
805036
805127
805134
805194
805257
805384
805462
805474
805478
805553
805807
806062
806131
806185
806371
806382
806727
806868
806926
807034
807063
807169
807322
807447
807579
807637
807677
807681
807714
807779
807819
807843
807869
807969
808167
808241
808321
808724
809014
809229
809249
809287
809309
809364
809569
809752
809814
809854
810196
810246
810529
810535
810553
810607
810721
810826
810839
810922
811156
811319
811458
811469
811621
812039
812112
812130
812661
812664
812866
812868
813081
813707
813738
814022
814057
814080
814091
814129
814171
814203
814234
814248
814257
814349
814515
814620
814827
814851
814880
814894
815198
815298
815309
815358
815380
815608
815701
815782
815880
816008
816225
816231
816458
816476
816502
816553
816574
816594
816640
816782
816830
816870
817013
817022
817088
817231
817241
817308
817377
817525
817616
817681
817875
817909
817912
818165
818214
818226
818318
818695
818749
818932
819002
819011
819281
819310
819346
819575
819635
819646
819738
819742
819748
819867
820065
820088
820098
820313
820581
820597
820848
820865
820976
821131
821159
821202
821490
821559
821580
821599
821601
821614
821642
821844
821887
821941
821996
822078
822361
822436
822731
822910
822915
822970
823165
823222
823418
823510
823666
823706
823717
823792
823803
824107
824182
824431
824610
824837
824849
824859
824874
824938
825086
825113
825406
825410
825595
825653
825842
825853
825859
825937
826303
826389
826423
826610
826661
826688
826721
826781
826841
827069
827070
827231
827237
827278
827533
827592
827886
827929
828322
828345
828390
828430
828462
828557
828629
828733
828902
828933
829041
829096
829259
829316
829349
829458
829508
829665
829911
829960
830111
830200
830251
830338
830413
830584
830615
830677
830742
830823
830861
830959
831043
831059
831067
831173
831204
831229
831461
831510
831512
831657
831661
831958
831998
832458
832586
832717
832736
832794
832817
832873
833026
833159
833231
833378
833419
833446
833474
833550
833634
834091
834145
834183
834208
834304
834471
834482
834517
834581
834818
834898
835021
835051
835176
835304
835360
835474
835510
835599
835635
835642
835742
836119
836201
836449
836481
836517
836575
836917
836973
836981
837286
837616
837642
837779
837785
837862
837907
837915
838262
838301
838337
838363
838391
838430
838678
838797
839085
839185
839220
839231
839348
839383
839544
839666
839776
839840
839869
840273
840326
840560
840796
840808
840884
841362
841560
841575
841815
841905
841912
841980
842196
842224
842260
842378
842575
842616
842676
842732
842880
842905
842927
842965
843021
843065
843142
843314
843339
843419
843705
843707
843887
843892
844008
844245
844248
844510
844650
844741
844939
844980
845115
845182
845365
845382
845520
845609
845683
845855
845887
846025
846528
846585
846728
846833
846994
847005
847064
847127
847146
847267
847327
847334
847724
847773
847878
847900
847909
847974
848246
848340
848346
848516
848585
848591
848636
848737
848916
848926
849112
849145
849224
849273
849455
849529
849666
849741
849797
850109
850288
850301
850308
850366
850534
850543
850755
850784
850848
851007
851026
851034
851053
851111
851181
851410
851539
851585
851733
851978
852159
852387
852391
852431
852534
852554
852716
852967
853009
853177
853204
853242
853328
853381
853539
853567
854010
854575
854692
854824
854867
854946
855372
855739
855788
856253
856282
856294
856709
856740
856794
856803
856826
856919
857219
857366
857658
857773
858347
858404
858406
858475
858514
858531
858734
858815
858991
859048
859098
859106
859300
859369
859505
859614
859656
859680
859893
860098
860157
860226
860269
860327
860511
860829
861052
861094
861108
861112
861152
861229
861236
861279
861582
861866
861955
861999
862035
862056
862152
862373
862399
862557
862672
862878
862946
862992
863017
863035
863064
863298
863311
863537
863549
863739
863864
863887
864026
864096
864104
864308
864378
864411
864483
864509
864567
864851
864959
864996
865241
865304
865388
865453
865540
865643
865804
865809
865888
865993
866129
866220
866225
866429
866761
866831
866975
866993
867035
867069
867567
867961
867993
868004
868296
868355
868505
868768
868923
869018
869073
869172
869213
869245
869261
869433
869617
869656
869815
869938
870343
870354
870481
870529
870582
870690
870703
870806
870929
870995
871041
871101
871239
871288
871346
871419
871426
871432
871476
871515
871536
871859
871865
872095
872203
872362
872506
872534
872552
872683
872713
872785
873123
873221
873256
873260
873277
873413
873442
873555
873583
873658
873724
873981
874162
874317
874442
874493
874548
874578
874581
874678
875445
875473
875494
875839
875997
876106
876255
876305
876320
876505
876939
876956
876979
877041
877155
877235
877251
877379
877520
877663
877705
877970
878143
878169
878199
878304
878381
878443
878444
878467
878712
878811
878868
878922
879391
879407
879548
879561
879587
879793
880054
880056
880148
880169
880190
880302
880403
880568
880614
880952
881054
881105
881341
881441
881485
881496
881678
881849
881862
881901
881948
882049
882151
882269
882358
882450
882578
882587
882605
882645
882653
882660
882782
882816
882987
883012
883146
883152
883220
883248
883337
883495
883523
883596
883612
883720
883781
883889
883893
884134
884200
884204
884708
884754
884787
884911
884931
885006
885095
885567
885912
886123
886217
886249
886339
886790
886838
887026
887098
887184
887297
887364
887382
887453
887537
887759
887839
887974
888089
888114
888240
888451
888576
888620
888721
888792
888842
888847
888957
888975
889159
889170
889206
889236
889324
889623
889733
890065
890132
890171
890175
890345
890405
890475
890492
890664
890676
890733
890776
890953
891103
891457
891487
891538
891808
891878
892068
892085
892185
892190
892413
892415
892500
892566
892642
892687
893099
893106
893142
893206
893300
893689
893873
894052
894070
894098
894465
894597
894645
894661
894667
894962
895066
895273
895330
895499
895571
895773
895925
895934
896014
896165
896420
896433
896566
896905
896991
896992
897042
897046
897055
897237
897302
897433
897636
897678
897747
897797
897847
897891
897933
898126
898147
898261
898335
898337
898395
898437
898617
898789
898841
899479
899495
899669
899686
899762
900295
900492
900754
900819
901415
901487
901777
902042
902107
902132
902195
902233
902273
902369
902400
902600
902611
902623
902630
902643
902869
903105
903196
903201
903314
903670
903767
903836
903870
903883
903993
904002
904034
904092
904154
904173
904206
904226
904232
904429
904645
904772
904784
904804
904827
904980
904985
904998
905425
905512
905653
905789
905837
905853
905917
905975
906082
906110
906237
906266
906406
906508
906537
906557
906717
906851
906884
906948
907028
907092
907198
907449
907628
907638
907731
907779
907876
907884
908077
908089
908271
908377
908381
908434
908456
908473
908502
908538
908710
908773
908860
908988
909077
909189
909260
909428
909531
909663
909664
909672
909673
909680
909843
909880
910078
910312
910421
910666
910746
910769
910830
910901
910918
910983
911047
911261
911306
911351
911358
911509
911553
911570
911633
911719
911791
911809
911907
912175
912319
912362
912844
912855
912895
912913
912967
913004
913015
913025
913206
913320
913418
913429
913533
913579
913584
913608
913648
913822
913856
913903
913943
914027
914029
914069
914076
914210
914244
914534
914745
914800
914865
914962
915118
915313
915452
915519
915610
915775
915835
915916
915971
916200
916233
916242
916258
916300
916372
916479
916557
916598
916661
916688
916810
916944
916979
917009
917223
917296
917311
917445
917461
917637
917692
917955
918018
918112
918374
918387
918619
918809
918891
918952
918986
919004
919028
919065
919115
919645
919894
920185
920202
920220
920372
920420
920423
920476
920556
920765
920778
921001
921037
921070
921160
921192
921229
921471
921737
921763
921801
922016
922249
922272
922673
922761
922796
922799
922859
923044
923067
923110
923120
923427
923489
923544
923554
923640
923736
923779
923813
923979
924203
924228
924351
924444
924496
924506
924569
924585
924649
924736
924893
924909
924921
924925
925071
925085
925088
925253
925258
925318
925575
925696
925834
926011
926154
926179
926185
926301
926315
926471
926526
926576
926891
926899
927165
927185
927330
927449
927623
927702
927790
927811
927954
928001
928036
928077
928111
928267
928422
928443
928480
928589
928675
928748
929033
929165
929199
929297
929342
929862
929890
930103
930131
930142
930223
930224
930479
930502
930548
930639
930807
930829
930966
931038
931087
931146
931175
931191
931352
931372
931393
931452
931536
931564
931677
931711
931719
931873
931908
931955
931999
932005
932205
932391
932434
932482
932498
932625
932644
932648
932673
932692
933018
933169
933205
933301
933321
933349
933442
933691
933735
933750
933765
933845
934008
934024
934253
934360
934386
934389
934439
934453
934487
934800
934843
934879
934940
934972
935042
935080
935397
935452
935525
935569
935579
935687
935717
935857
935942
935973
936557
936677
936717
936780
936866
937255
937347
937359
937517
937594
937736
937884
937940
937989
938044
938082
938103
938111
938274
938552
938575
938579
938608
938722
938841
938875
938898
938958
938971
939038
939060
939137
939267
939494
939531
939666
939681
939690
939771
939797
939927
940004
940051
940108
940139
940190
940429
940435
940509
940517
940573
940595
940629
940652
940659
940766
940874
940967
941048
941064
941084
941338
941703
941748
941837
941922
941947
942144
942333
942554
942623
942711
942862
943119
943322
943434
943598
943609
943629
943669
943724
943777
943796
943806
943859
943901
944039
944152
944224
944344
944377
944426
944437
944592
944797
944984
945080
945115
945218
945382
945469
945487
945523
945765
945928
946144
946251
946440
946480
946524
946707
946818
946986
946987
947065
947153
947255
947332
947436
947568
947574
947598
947599
947629
947648
947733
947855
947997
948010
948058
948351
948467
948585
948723
948794
948816
948906
948910
948963
949072
949087
949113
949197
949236
949279
949377
949427
949676
949688
949710
949785
950061
950121
950225
950323
950433
950443
950534
950594
950607
950714
950739
950782
950803
950808
950870
950874
950892
950993
951024
951037
951160
951461
951465
951532
951767
951803
951833
951856
951882
951903
951957
952002
952162
952340
952430
952522
952749
952806
952846
952884
952886
952938
953145
953192
953580
953591
953610
953753
953758
953828
953871
953996
954027
954030
954040
954296
954499
954860
954908
955097
955172
955191
955220
955248
955279
955415
955421
955479
955502
955656
955814
955932
956207
956329
956376
956389
956452
956527
957012
957044
957147
957239
957326
957618
957622
957694
957723
957732
957806
957811
957878
957886
957924
958108
958405
958661
958663
958686
958784
958786
959091
959103
959377
959427
959487
959779
959984
960215
960328
960391
960478
960627
960723
960724
960763
960892
960920
960927
960978
961029
961058
961060
961173
961270
961300
961318
961323
961473
961520
961522
961705
961840
961878
961885
961995
962019
962069
962197
962254
962342
962486
962506
962686
962704
963109
963149
963248
963312
963351
963382
963544
963673
963748
963870
964050
964117
964359
964466
964544
964651
964695
964740
964830
964871
964986
965087
965197
965434
965761
965874
965930
966279
966312
966496
966514
966692
966733
966923
966995
967038
967150
967376
967588
967620
967775
967812
967870
967982
968185
968331
968332
968378
968473
968498
968591
968694
968821
968983
969137
969140
969302
969394
969488
969553
969559
969734
969753
969976
970172
970340
970394
970405
970476
970552
970734
970898
971270
971578
971658
971666
971670
971691
971712
971786
971819
971882
971928
971959
972005
972034
972107
972127
972233
972280
972310
972503
972589
972607
972805
972854
972926
972972
973002
973043
973158
973197
973243
973353
973356
973427
973587
973641
973762
973848
974064
974402
974486
974530
974688
974766
975177
975192
975251
975449
975582
975656
975795
975817
975883
975907
975917
975963
976027
976109
976117
976186
976212
976218
976284
976418
976456
976583
976751
976793
976810
977132
977137
977264
977288
977483
977504
977585
977615
977649
978121
978139
978155
978197
978235
978245
978530
979173
979341
979353
979551
979582
979735
979738
979764
979806
979946
979969
980240
980345
980628
980640
980641
980655
980723
980754
980848
980849
980899
980948
981131
981154
981288
981305
981314
981350
981439
981676
981694
981699
981782
981867
982099
982100
982228
982254
982313
982365
982476
982493
982506
982573
982681
983165
983173
983291
983435
983503
983506
983531
983551
983609
983733
984031
984221
984282
984307
984387
984411
984481
984493
984550
984592
984802
984924
984928
984934
985017
985036
985136
985309
985333
985563
985572
985707
985726
985755
986065
986173
986349
986386
986672
986718
986924
986961
987092
987104
987211
987297
987395
987422
987870
987888
988088
988330
988397
988428
988567
988669
988698
988772
988809
988841
988977
989146
989248
989252
989277
989312
989438
989547
989603
989689
989828
990192
990435
990586
990799
990877
991055
991066
991314
991356
991708
991716
991799
991975
992046
992058
992314
992329
992463
992467
992606
992675
992679
992737
992766
993037
993041
993359
993420
993485
993543
993573
993678
993742
993816
993948
993961
994097
994449
994720
994762
994887
995051
995055
995171
995180
995284
995429
995449
995501
995668
995757
995776
995836
995875
996301
996352
996392
996418
996492
996789
996866
996900
996944
996978
997032
997037
997167
997168
997267
997275
997401
997472
997566
997665
997737
997781
997823
997830
997985
998107
998129
998229
998281
998514
998912
998982
998985
999094
999179
999240
999247
999343
999409
999412
999428
999430
999752
999886

Can you figure out why it runs faster or slower than our other sorting algorithms?

Heapsort compared to Insertion Sort and Merge Sort: Mergesort has the same average time complexity than heapsort in the average and worst cases O(nlog(n)). When comparing both, execution times over the short and long lists are very similar with close to zero time in the short list : 0.00016 s and 0.09s in the long one. Heapsort compared to compared to Insertion Sort has better timings when going over the long list. In this case time is multiplied by 1000 times. Insertion Sort algorithms have a time cmplexity of O(n^2) in the average and worst case scenarios compared to the O(nlog(n)) in the heapsort case.


In [ ]: