第142回【Python】平方分割
現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
Python をゼロから勉強してみよう、のコーナー 142 回目です。
そんなにお酒に強い方ではないのですが、飲み会の席なんかでは酔うことができません。LunaSaki（嫁）と二人のときは、ほんの数杯で気持ちよく酔うことができるのです。誰よりもたくさん呑んで、酒豪だねぇとか言われますが、本当はちゃんと酔って気持ちよくなりたいと思っています。
それでは、今日も頑張ってみようと思います。
平方分割
https://paiza.jp/works/mondai/query_primer/query_primer__squ...paiza くんは、長さ N の数列のある区間に含まれる要素の最大値を K 回求めたいのですが、与えられる区間の要素をいちいち全て調べていては時間計算量にして最大で O(NK) かかってしまいます。
そこで、paiza くんは 平方分割 と言われるアルゴリズムを用いることで、この計算量を減らそうと考えました。
平方分割とは、次のようなアルゴリズムです。
1. 長さ N の配列が与えられたとき、N の平方根 x を求め、配列を長さ x の配列に分割し、それぞれの配列について目的の値を調べておく。
（分割で得られる最後の配列の長さは必ずしも x になるとは限りません）
2. 調べたい区間に完全に含まれている配列についての 1. で求めた値と、その配列以外の部分の値を全て調べて、目的の値を求める。
この問題では、長さ 10,000 の数列 A について手順 1. を行ってみましょう。
10,000 の平方根は 100 なので、先頭から 100 要素ずつの最大値を求めましょう。
K
A_1
...
A_10,000
l_1 r_1
...
l_K r_K・1 行目では、与えられる区間の個数 K が与えられます。
・続く 10,000 行で数列 A の要素が先頭から順に与えられます。
・続く K 行のうち i 行目では、 i 個目の区間の両端の要素番号を表す整数 l_i , r_i が与えられます。
期待する出力
ans_1
...
ans_K・i 行目 (1 ≦ i ≦ K) に区間 A[l_i] … A[r_i] の最大の要素の値 ans_i を出力してください。
・また、出力の末尾には改行を入れてください。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ K ≦ 100,000
・ -100,000 ≦ A_i ≦ 100,000 (1 ≦ i ≦ 10,000)
・ 1 ≦ l_i ≦ r_i ≦ 10,000 (1 ≦ i ≦ K)
入力例
3
74769
-62958
6542
-93191
-6767
-5945
65384
-97133
85447
-80479
10143
32154
-19276
8255
2733
-64387
-35338
-50818
-53711
-76302
55090
-70049
-15703
33613
60309
-65932
-88854
64740
99070
-69104
83800
-50548
-77339
-83144
-13179
83974
69015
-41526
-39415
-89667
-93106
-58861
-62437
-95980
86724
9816
92219
-25096
86161
-67156
84426
-23504
-74287
2461
-21948
32069
-86265
-79450
-4874
17271
24776
54973
63173
7199
-27630
-31710
19021
2634
-77767
25772
67903
13279
-18292
-60086
40197
-15910
-11082
-80722
317
98331
-61585
-80403
77464
15359
32603
46799
-42809
-93890
-32446
12102
-68239
-90340
-85213
-87302
-24104
-69961
76037
-80638
-3349
-82803
50480
12036
-60900
89626
69504
37776
-8917
27326
43513
-4891
19666
-4136
4089
92567
-29853
32913
17525
84381
-84795
32265
-9573
-66246
36448
52583
-25510
-59884
39117
65490
14563
62808
17863
6574
10439
16681
-18173
-15669
89770
80562
-46769
22201
-74959
5727
-75588
-79466
94865
73757
74224
-63184
66
38201
73449
87632
86531
34169
59242
-99253
4613
89549
-77560
96944
89757
28548
-89857
-55772
-81136
-51889
99686
-98152
-22480
-15267
60649
-33669
-97778
-49620
-77489
-97500
-5628
-68997
-5302
22973
6935
-80684
5607
9608
-34662
95767
41831
36379
-41757
-58724
-25830
55393
-51382
-26471
48556
-74951
24969
-88141
96714
40775
26425
4018
-64579
-58203
-86170
87576
11287
-66881
6117
36810
-74779
-71601
-4544
8483
-49447
1193
62748
65014
-76914
46882
58673
-10303
-29397
-51186
-344
25512
18542
-57837
-23724
48917
77330
40067
97400
89088
-35233
-9992
93757
91646
-30481
14483
-72597
-51517
52932
18036
-99084
-22380
-41903
15292
-68816
-55747
-6417
-66645
-63083
44506
-82672
-33092
6250
83019
36162
-67022
9266
61443
57368
-54111
24939
56733
-91229
-15694
36791
-20320
93665
83779
25697
-33371
-89962
24159
81665
39460
-36376
96519
84533
-89696
901
-55862
12994
-66716
-52380
-14396
53374
-68143
96997
-75874
-77897
28609
-44453
30888
-49951
78991
-34299
-73704
-75281
-11651
-52777
38420
-48869
98349
-47840
25512
-82407
-98783
50524
90949
8535
-5361
41987
1847
-6146
12026
68515
-63669
-91570
-62623
-61720
44930
-28967
97716
29571
19855
-52050
-22149
-62580
-9307
-16323
-88453
-60010
-42656
82244
77867
-49921
-76571
-188
46108
20137
97241
-37532
33369
2736
90607
-26718
41061
-23547
41364
-40467
-87906
14669
-48274
65656
-209
30275
-24575
28610
57597
61009
45431
-81615
54382
88478
-51939
27083
-39576
41667
58135
-70274
24229
27959
79069
60607
-73980
-62616
9351
86354
-20399
82780
97165
-44943
-80606
-98041
-22931
-92158
-34094
26554
70433
75877
10438
-30444
-88936
16840
53158
-45847
30974
89423
73894
-16228
38866
96628
76311
97069
66329
15447
98202
20492
-30467
70629
-2562
-18814
25683
-30747
81598
72304
-21793
13940
90457
33168
-54647
39302
-60655
54047
77763
29238
-34732
58908
-15470
-83960
51693
550
1850
25011
-480
9506
46249
-69177
-29727
-44220
2388
-58528
-29556
35439
-98225
-15432
1716
-18583
85810
13074
-71383
14565
-45643
62049
5944
-22197
-59637
51940
15192
96323
-79374
1400
27208
-55723
-55572
10482
21328
66451
78126
-84229
-44261
-75300
-73523
36032
44230
27397
30317
-14020
-17753
38399
-74534
21390
74034
-18804
-39800
-42971
-8011
6110
-29206
38203
71678
-617
-22108
-76477
-74569
-47827
-15341
46638
-89997
-41318
-58236
-8849
9039
80537
-1210
63258
-23113
-61776
-1324
-64725
-49092
90538
-55645
-75268
58649
-30356
-37841
-49023
-99378
-18533
-64134
-3452
-74981
6015
-98257
-38368
-30910
34101
41220
-31487
65408
35010
-40829
-26813
-29266
74991
17192
74630
-98689
82185
83378
-15774
-98913
20097
-527
62338
72610
62413
55546
21014
-34043
-72066
-31172
47216
95846
43831
-38177
-65686
-4312
92605
-7700
94743
71792
-22754
66828
-50463
79461
80895
-70826
75712
4162
-96475
-20796
56018
44507
-53583
88530
70396
-6125
-94885
-42451
-11522
-34726
-10501
-63109
-1010
55355
-18910
64056
-48571
-28763
-99244
62398
10070
78480
-22995
-60545
-30449
-39400
81807
26943
-41225
-11610
45217
-84798
-30363
-51252
-17682
-48936
-89761
-25518
97318
-46699
19196
-30983
-18874
-76194
-3512
1344
7465
-99277
-77972
-59368
-89934
26408
-48144
50523
-47215
-43134
6728
53586
31851
-61980
-61473
55848
-20040
-93840
97976
-5335
-16212
15092
26281
82468
-79615
-72033
44115
97382
-77516
-19845
-14682
66611
-97776
-82859
-76798
91708
-68382
-31574
51535
-22410
92042
27814
94493
31509
4001
-54215
54780
-52762
-82960
75515
88801
26804
-98660
64984
-50801
5380
16950
-86077
-54202
81244
-45437
-26731
80807
29273
-55996
-56295
-7638
53788
10552
25327
-71167
-77098
-26097
-86150
-16935
-68592
77792
-95549
-45066
29552
-61795
-32239
29806
23817
-71359
-70380
58881
538
-63161
-27583
-64178
8751
-68947
6787
80578
-71916
-30037
-36316
-69618
65734
-7551
67037
89674
27132
54634
-44408
-56690
46293
18521
-64849
-16106
-78795
53717
-10140
2213
70922
-57536
78063
15821
93089
-90649
39711
-74830
-66052
-32882
92996
-69235
45085
-64349
-54600
-36350
-70465
-96911
-51630
-52342
-99848
62349
-22563
-83232
82
14158
63821
-88161
-49185
-82925
-9191
63873
60431
50465
-30854
98004
-17440
-36949
-49549
94511
-34279
42141
65429
92159
41143
-66320
86667
93928
33583
-68271
64661
24656
65511
39372
-90829
27930
44101
28648
61542
-75583
46712
10390
-61550
96188
7790
-70252
36831
-7399
26498
-20627
-83053
14126
-35864
52985
9711
34302
-27056
-61535
-29953
-28554
-66295
-76710
16749
-67426
24593
29481
-36649
57563
-44604
19122
88799
28080
-33446
-85750
89400
-80023
-97667
-51064
94713
6351
-98122
30192
-54241
-60232
-89563
9278
78964
37806
-68742
-55432
41282
66727
26188
20596
2034
20498
80831
48883
62540
-32458
-80150
12155
-71145
-92572
39602
-98882
-42893
50672
28809
5112
19004
-30289
73768
-76206
-66362
70256
-70975
-25922
-66703
27154
-26873
-26105
56798
-1263
-19061
-23196
-4114
35703
-25575
-45243
11164
-90631
28888
-38003
-72751
-28509
3348
20549
-1472
22871
80448
56494
51855
86256
88367
89927
-52947
-88622
-43522
-89008
33656
-13748
7894
85391
10359
8470
-71868
90469
-24473
21061
-59798
48141
-97175
87503
70117
-80009
52059
42384
50165
-28205
-99806
-11920
-35430
-10742
-62143
-87866
-46811
79357
38100
-5989
-18691
-36817
-98485
96561
80435
-30568
43178
52476
-26694
-81487
-27447
-38311
-18154
27636
-16040
-34745
-9459
86169
-77626
-99965
-50740
40813
78103
-79613
34139
13209
-69470
-59989
-49878
15937
-12111
2635
46297
-80614
8529
-78605
-51490
-15780
54258
-79323
-6913
-51546
-16992
34210
-53239
32412
45947
15428
-62421
-91021
-41238
-92538
76896
-83414
44137
52833
51384
-54178
-16067
53823
-51243
40973
49409
-12549
83718
-90592
-97654
-2253
35085
-26682
-54965
79876
39592
23947
-64054
37924
51088
-91012
86012
-68461
-39107
-47571
48433
-2777
-15867
-58897
77821
-4512
-37323
-64671
-45580
34043
16079
28857
-60578
-35817
51045
-53125
-7861
64518
-53025
797
11165
-34282
7363
71946
-23653
-93317
-87822
-12579
-90813
-92463
40435
63887
14927
-99828
-17491
-43020
96143
-62713
-17410
-51398
91922
-57656
-17281
-90958
-1008
-21201
-4245
57031
37991
-10878
-13205
-82756
47943
-97296
52266
37688
95413
-37527
65563
61572
-92162
-62898
29023
13350
22081
-42737
28197
79324
-23333
-45242
-9409
-32700
86838
46139
-55072
88886
-14849
-62922
90027
-52190
54211
-55024
48051
72466
-82561
-44082
-82265
78877
-71090
-28317
-56984
-28662
3756
-62619
-3223
-28425
89225
-48099
2966
-82502
-80489
-27128
-92678
-80770
59697
-60612
18836
70724
64828
35638
45056
53136
41285
88430
7681
79160
5248
-98957
77816
63286
-20892
55552
20777
9918
97044
-1902
-13416
-27104
-1293
23238
76336
-11719
24122
55802
86541
88790
-84889
-81889
-44545
-44094
30239
62554
31585
27930
99852
-64685
-89881
90320
-11999
85067
53111
47803
-73056
65242
74985
43913
45157
-86610
-31687
-5593
-79553
-21764
26674
-61867
-21494
68586
83747
-34515
52295
13487
-12643
-6663
-61017
-29
49118
-91819
67008
-74157
90828
57569
-19499
-43442
54563
24735
75997
-98647
76903
-7048
-50606
-80386
-50373
-4343
-70131
-30977
31583
44993
-2669
-93129
-97019
-52714
-2065
-71902
-94545
-36470
-22365
98578
83283
-64966
-87823
-79778
20394
95379
-82940
-48603
95689
19113
27671
-9654
29532
-71954
70396
-46459
70523
-50413
22854
-76107
-52936
42654
-86881
-24919
80576
-76793
59429
-19390
55811
34300
-56531
31500
-37734
71716
-15340
53614
-19053
-38633
-4595
57458
82174
5933
-3724
-79530
-45465
56507
23498
92619
80371
86251
37913
19047
-5741
-66349
53382
-12237
-76080
2739
-87809
-92065
-5210
-90756
-89628
-39261
73690
-37697
6424
62482
21232
96864
82913
-85842
-58439
-94676
28105
-51450
49059
83165
-87980
-96183
82336
-31591
81721
9825
-31269
-60436
-81262
3598
-56229
-57729
56505
-23506
51566
39257
86044
-77405
-9069
89697
59176
-30445
-46940
70595
-7312
-72222
22132
91654
-70895
69164
51900
-98904
-97504
-17132
98233
45804
61414
54151
41551
64581
95679
-90161
91283
-72140
-96225
4147
-32779
9263
12467
7434
70039
64492
69799
-14507
-10469
70745
-17198
75945
-1038
-32060
98513
-55435
73072
-4496
-42392
-47166
-4156
55028
11210
21360
-38097
-56130
61828
-88943
75744
8005
-5195
49574
-30325
-31673
-62116
62688
-56159
26121
12772
-66450
-57177
7939
21425
55106
94307
2277
76709
26423
71531
92606
76106
11386
-42573
1311
15756
71671
62892
-42291
-6003
-79136
4882
18564
51719
71227
-18599
42140
31192
-45531
52914
-15292
-87033
-38072
-32259
44491
67939
-75858
-51943
-3266
-85721
-35757
22878
32599
-80023
-78001
70948
-43671
-59467
-90198
-94692
-96944
5043
-82098
-46570
59880
-8874
-50162
-61975
-9185
-9668
64568
-39869
69938
25462
79996
-88973
-39573
-84801
37955
-53612
-8483
59595
4118
-52439
26749
-32145
71370
-83092
1284
23184
3505
92289
43946
-99498
-88319
99205
-6382
-56026
53342
-32838
84908
5668
-44744
98675
23455
90093
-38318
8841
-94807
-70333
62126
-38389
-44439
79153
36689
-17265
-9862
58488
-82207
55273
25101
92959
92031
-63687
-79250
22945
4538
-71568
-57235
50878
-32820
-20768
-99735
5386
-31782
71925
-88330
-91917
30930
32117
-71877
95742
-43254
68946
85495
-37114
-85682
-30915
36113
33557
45532
57360
26285
-48392
-11797
-23417
20054
-88126
-61279
75933
97676
-46274
-14308
39405
45290
18619
64295
94900
-10076
21966
-93703
27381
-34137
-20204
59577
83112
36796
92413
78146
-63710
82215
-78615
-30669
86581
49940
-64693
-22814
-71936
35320
9394
38319
1414
13885
10047
-83759
93314
-74152
78579
4623
57273
-41196
-71548
-45419
-38411
-71410
35904
42420
62471
-54205
-74246
-32189
47602
484
-3067
19728
51872
30107
-3958
-89819
-77624
29015
-8129
35152
-13794
32446
-6887
-19670
32012
23147
39198
74394
1042
-66447
5248
-82735
52970
-91796
-61009
78671
27914
25630
40428
35846
-19662
85322
-12755
27708
-89826
-95405
-77910
63507
26715
-95591
13418
97942
-12225
-52765
80561
-41845
-18520
37645
-20544
-1521
46752
2353
-62964
-56524
-28647
6100
-49772
50108
-84629
-68166
6561
85210
30617
21760
-76720
-29902
98067
56447
-72190
51868
44691
10038
-4801
62354
79908
-26119
-82532
96564
54412
-21808
93025
-49982
70149
-84682
35603
63948
-682
-31806
11161
-17972
37632
52266
6215
58883
-39350
87284
4706
10877
-96047
16793
16374
-85936
23258
-61913
72776
-70722
96154
-6198
-20539
92549
-50587
59317
34022
-65785
-83166
12920
18806
-29798
3541
-64658
98365
28235
25548
-55137
58784
44325
-76012
-78305
41799
-36496
-28882
-81331
-74805
-17754
-73436
-62546
3483
7924
-15562
16589
-83288
90390
20302
50342
98692
-80048
45873
89525
15367
-56060
-52703
41689
-55542
-67706
-85442
-92571
35860
22120
-13565
45560
29221
1496
-34047
-67753
-57509
22411
86151
62995
-12561
43959
-36669
89617
10585
-31576
-15632
77883
-1791
33198
79588
-81870
-57584
376
60148
-58894
-12838
-68497
-70111
2532
-89548
38782
-97518
80483
45041
22494
-77131
28598
-40240
59861
39463
74969
-87162
-93955
95411
57649
58640
-72863
37869
17947
11165
52129
46058
43682
97370
-43670
-58888
31755
43279
-79597
43842
80654
73481
-77987
-98363
8487
-76284
-97569
-80104
-88968
24044
2220
11572
-81840
43111
85798
-56891
59883
47693
-63591
-83895
-70660
25622
40964
47294
64591
8402
65442
69724
-29769
-98628
-86189
35540
8176
-54412
-42860
-93742
-74454
-17089
-39275
15397
-89650
-86665
88819
10315
41832
-40578
37091
6187
50760
-93043
6445
-39063
-2369
12745
-69643
-27386
-4005
-44439
-56428
-24468
46613
-4205
98476
85132
83325
55158
25519
-8220
51813
58661
-53166
-66965
12922
-49413
85466
-32051
-76419
57660
75586
-58856
39585
-61289
54145
-80900
5840
81842
-88787
13588
-77256
35596
42215
21359
33993
6664
-66612
-60372
51203
24979
-88664
62940
-2685
85386
-76235
81578
92787
60832
64085
-57856
47859
11157
-78259
-64629
71341
-22415
-60083
5953
91037
-64030
30111
7782
-56491
-93905
81183
-97610
61846
-64339
72805
-35839
72112
38166
63540
80577
99324
40298
17872
-55141
-47763
-85357
-66041
69056
-79420
60158
73812
13258
-28742
79615
57911
91845
-52503
86904
30192
98122
-52350
-47782
-82147
99118
-35521
-45159
40743
92353
-89391
19319
70621
-86465
-55754
-28597
-87690
37840
-16966
85039
-98152
-74527
-44574
17364
91446
-66654
40257
40475
-66782
-94225
67921
85130
-15940
4098
68521
-66300
-9996
-20226
-72458
-8776
97080
76664
-31071
14515
64529
-78248
18985
6193
-93480
95481
-2419
-17277
48406
96084
72242
-18743
-36275
14670
-68900
-70250
4264
4376
-86098
42193
2493
71824
34650
17705
94135
68217
25471
92295
15433
82595
-30823
58332
-60617
-2250
37503
55958
-76911
97445
54063
27663
58654
-9451
67295
-52745
95400
36535
-27975
26374
92973
63086
94891
-54141
-9303
-19400
-65389
10236
-51073
-6207
-83563
-54211
89318
13246
85559
-7415
1177
-13707
-76844
-40198
25650
81074
-18208
-40029
54059
67479
-28247
42547
16473
97084
57658
49552
40184
-86292
-20486
-36381
90922
29098
59425
16168
77728
-99806
-63195
68444
47261
-3423
-27287
-44656
22968
46778
14989
97918
82653
11308
-81810
-5198
99548
-3808
-39912
-2637
23837
-47736
-19102
-55677
-34769
-56799
45892
-37625
-53133
57348
9335
50934
21824
-28572
-98568
-42260
-55480
23742
34505
-80702
45060
16046
66209
-89704
14634
-56289
4841
23651
-95059
47807
47654
-71313
23009
50053
-96178
-84494
10062
91667
48501
-29806
59327
-74607
38222
-29152
-18738
-53724
-26006
-81921
52040
-29119
58943
-67512
-23670
-81428
-62535
27590
-8216
12721
-59924
37270
-39534
-60486
542
40083
81417
-31227
-89273
84545
-97592
-70827
-46677
-19660
65495
91945
-25240
-41618
-34049
-54140
68606
-79894
26061
87175
82400
-6663
-1311
-94788
-36975
32434
-69546
49133
30245
-25293
11636
6845
57743
96109
-73503
10483
-22417
-33139
34360
-27081
-16718
-29706
-13234
-11796
88779
-12908
-10024
45566
79324
20816
-65075
84877
62981
1318
-63977
-32409
64628
35559
65271
-31162
71948
-97831
-92858
60581
28316
68846
8989
-67802
-18168
-16183
-60647
63146
-78899
31144
-53948
-48892
43021
-27483
-43403
68222
-80712
-40833
27858
-77153
-91347
-37227
84292
15378
-6949
-72722
78109
13023
42046
42934
-92915
-50988
-87836
64846
14724
37987
41564
-41721
19933
48608
64741
18169
49223
75534
-57509
-89903
-28245
-65129
77478
-61482
-57203
95761
-87329
-68325
59797
85451
-9250
-59863
71080
-61135
-6605
-85694
-33642
57485
-57545
75293
29570
16975
-54436
20485
-14278
81723
-61967
13676
-94398
6328
46399
87789
28185
-7998
48012
-46227
-95306
-94726
-19833
-42994
66914
-70000
-73774
87968
52399
54684
1437
-71223
-10736
-4321
-8327
18658
35666
-21500
80741
88349
81309
32574
69230
12115
8665
51809
-81573
-64760
-74718
69914
-57335
-65095
63208
-3292
71484
-84301
16944
-16883
25045
36545
-63979
-71430
-17068
69804
53862
48032
88479
38557
-84340
-46519
-85662
-30273
-68397
-56209
54996
8293
46640
92599
79021
56108
-8387
-53474
-96152
19316
40869
21447
32008
23249
-52416
91232
20307
-53631
-16224
79747
-39570
-57812
-38575
85570
-35152
60343
32446
55869
82824
-32634
20910
-50783
9094
-70119
-35132
-85498
46933
-12318
1586
-14608
-55443
-2081
-65540
-9490
41333
32824
15702
-87826
-84551
-32644
-21565
82652
57896
55607
-87980
-55093
-15131
18310
-55237
-81216
-58096
62648
-53907
-6393
-37485
-25761
20109
-47775
44001
-84878
28749
22585
-71108
10922
32128
84733
-97621
-48811
74005
43729
-83291
89231
88381
-51255
-53862
98485
-80576
-37947
-23360
-83290
-66890
-60812
86529
58731
74726
-25191
-97843
-7877
70209
-9892
-40802
-26145
9254
7351
-7611
41268
-50188
-81117
2650
-76688
59137
7789
-64495
-3484
83459
-51107
-51031
34474
62321
412
-3575
-52353
93593
-55246
-62670
-69109
81548
57216
69988
98383
90582
-98878
36977
99053
-95075
34138
-34361
-72219
-48778
47175
-14392
-52994
-2505
26495
-29043
-70892
96181
-89139
2832
-47583
86277
-20665
79313
23858
91177
-39864
48502
-9653
-59270
-78126
-80202
-38093
-58453
61202
17369
-91683
-75552
-65526
-42888
22207
-87022
38035
-87334
-44857
-28226
-22762
95131
54906
-28597
-79650
-85706
-43061
53104
-79476
-4420
-31633
4951
-51504
21643
73808
23947
50871
34805
66282
-28036
17589
-26288
-53503
-86837
39379
66917
47787
33071
64760
-85494
-46165
-38957
-80250
51869
905
-83074
44964
-85100
11867
5942
4295
5124
50967
26990
97589
-29229
45146
5009
-12079
14562
-49735
-12858
-93351
92574
48153
99732
-30544
76967
-45313
-79583
-85050
67706
-70176
-66361
-47514
50285
94142
35766
-56463
-86712
60739
18899
91
-96132
42586
2301
-79205
-21654
-8026
74568
-48064
65332
-14169
10446
95066
-21572
42130
-96725
51991
-87457
-17729
-25793
-38214
33092
62999
-60294
-32858
26682
88729
-59003
60090
-76098
-28241
31466
25264
-16358
55616
83702
59403
7614
83941
43137
-82961
34303
24233
-20170
24261
41562
-37159
-35952
-49189
70368
-41933
-16119
-83459
-36092
-34902
-8635
-98487
49758
18671
35563
-22671
21544
-91599
-72673
-37419
-86629
-31093
-73123
6467
-2210
19771
-64527
-60097
84384
-80370
61103
54862
83368
72121
74522
-20175
-72128
-48744
69321
-22938
96405
36797
9769
-65036
-7900
45923
66958
83166
33575
-1922
108
81734
-99117
37906
-38079
85175
-69181
17610
86239
-77200
50147
75214
-22534
77054
72726
-40547
63913
40755
34216
-10836
-38743
-41403
-47332
83961
26216
10758
-87857
-46940
-73782
-42609
92137
67728
33892
88603
59243
31578
-67258
85277
78803
79799
56590
-82583
-10549
-76812
-39453
-99863
-64780
52107
25503
-45596
2480
-76578
-77171
50189
-3720
46192
19819
52282
41965
-66554
-18507
-79787
75342
39662
-75863
-4787
21079
59334
-7482
32416
78210
26565
39765
66461
50766
7000
61544
80814
42687
30663
-90918
-35583
-62025
-3563
32662
9782
61674
11901
70942
67387
-53554
-81872
-10727
88149
84544
-16447
27759
32466
81067
-51914
-31253
-17866
-77462
-24048
-53760
7788
-24413
30223
7700
-18958
53577
11213
-30533
10327
-81282
-20275
-36313
-48496
-53998
-67254
-28082
-22521
75113
-56957
77631
53472
-98085
-76220
-83814
93852
-25646
-19316
41950
-46199
94224
68059
-61400
51698
-34595
41506
31450
62504
41124
47436
-45201
-53515
51238
28491
-83484
7123
34967
56461
31922
-23609
62461
20949
54504
-22886
-94717
16994
19667
-97014
61009
71612
-25299
-11455
3157
-97404
71214
-17735
82126
72644
94993
26492
62950
78917
20602
68557
39083
-41629
-13513
40309
-78485
62898
-63548
-53207
5659
-35484
-11160
-9692
92440
61766
-85933
-67048
95629
17754
50269
44579
19273
80480
-28951
-9482
48868
22455
71378
-86860
-6228
7370
-54994
-75377
-89230
-98170
-12669
17360
99748
22646
-19106
-95398
85975
82464
-27100
-69886
68629
-88196
13730
59031
98050
35788
98366
26627
78269
64491
-16583
-51839
29881
-2911
-989
12490
-50303
-25186
34121
-79274
-91630
-51226
83883
30600
-68189
-45812
-37294
-5454
50645
14134
-94756
12626
74957
-19816
96526
48693
-79375
67580
-83717
61140
81715
7090
-13519
-39251
-44382
39669
66392
-18367
-82808
48839
69630
-43950
-99352
-57543
-7653
11613
17855
-44479
32907
93971
-47931
-18707
-33786
85138
-65032
-47029
24277
-56352
23850
-69641
-73802
68263
-81597
-52314
55007
-17810
55983
-95678
-80441
-92238
79753
-72415
-80882
-61213
-64441
3553
-87696
-15275
54099
-42311
-6336
64019
9375
37924
-81166
74896
68153
69470
-82730
98060
34343
3249
4541
-66519
-52573
-66546
46712
3842
-32198
41095
-64622
60496
49511
13582
81480
-45250
32005
-6190
28420
-33150
-73730
-26469
61736
-42973
45147
-60003
-25582
-6236
-36744
-90869
19565
-18575
46957
38259
25855
-47452
5959
71623
-926
-43842
84665
-12221
-95877
-78653
-83977
-39868
-51226
-64503
-29484
-31055
-76333
-63322
60207
-26141
-61074
47708
63758
-77679
-15262
-81055
-82621
67406
40208
-58046
-67411
59073
29569
-83912
12215
57604
-16886
-4193
-38805
96641
-90183
-86686
-97933
1142
-73658
28967
-93779
-31002
-50769
-95013
28066
-42070
-50061
-45879
-61285
-88283
-36916
94592
-89910
95984
-65413
54698
-28496
14921
79964
65646
12309
18855
-29942
-78275
-43809
-11382
-52729
-52875
-99640
-95995
-84774
17741
-96741
-41133
-24537
69913
-76728
-51395
-33588
95631
96879
26653
-58038
16659
-4357
751
-94216
-25520
4470
-83103
81483
10384
-90486
18636
-81240
-5097
49631
-47588
-38072
55824
99746
53393
28609
17840
-49779
-4084
6841
24471
-87932
9198
-54781
13524
-77732
93646
-99756
26613
-38550
22492
-10441
-35762
-96309
9049
-3567
20448
-35930
40745
-14554
28656
-29487
-72356
84712
-55504
59110
66100
87317
23374
-36837
27386
-43471
92602
39970
-78048
49314
6555
24670
57921
-80978
-97681
2515
-57112
-31429
80966
-38861
72165
-70191
-1936
-63603
-89077
79290
13274
-88047
85374
92480
58954
1315
67931
-20724
88747
31489
45692
43668
-19972
-65498
-16954
-63890
13412
46400
-41209
-4964
69374
85912
80295
77943
77722
35226
-4303
12358
-9618
6838
72126
88634
-62493
-36566
-78869
60521
-71750
73872
63937
-27583
40665
52595
-48190
-34218
20331
-31554
-17135
5556
83350
37079
77472
51275
45413
93547
-76759
44718
-40200
47972
-80038
-43486
-40243
-5077
-51678
-70528
93745
-52167
60928
70478
87648
-43282
-25318
-35788
49484
74173
88781
16456
-16077
43170
-97474
-57846
-65448
-94631
57554
14642
50175
53009
-13475
53534
-26574
33404
14698
81591
23603
-1753
59432
-93482
86107
7898
-5510
-85480
-51476
20987
95473
-39679
15917
-38981
29786
-62768
32950
8339
52269
1102
52976
-94335
-69278
96950
63980
-23238
-46688
93435
34312
26363
46009
-31106
87658
-7399
-72273
62749
-25687
32767
-59204
-84456
16290
40829
-97674
-59114
35087
42360
-43779
13084
98035
-99688
45630
-1724
51769
66557
-56638
1401
80300
91787
6318
-54365
30289
64483
-37233
84231
-98022
70637
-75874
-21191
14961
-80212
-75422
6155
40977
-47593
8898
-60380
-55073
-72024
18210
-87773
-14057
-36080
79623
-31239
88095
51643
-80207
-96154
-67774
16877
-39241
-51340
-88743
65032
-75514
-4908
-47769
-14109
-96926
10248
-56998
11932
64322
-16868
-44632
75320
20436
1150
72375
51757
59308
-97243
54090
-19896
42948
-96420
-90391
63219
-94807
42820
38113
-59384
66137
-44720
14978
53854
-2959
-91223
90018
97229
-77128
22259
38252
23523
56228
-24359
35661
-64096
-169
74338
-24514
-94971
-56465
-53412
-77946
-80762
87785
4582
61815
-33316
31620
-21802
-31562
-15653
-39459
-21130
32660
-39281
-56891
7077
79576
-51647
81402
-10026
1737
-91551
-31454
-38206
50479
72704
1248
46215
-13136
-1534
59674
50019
-70409
85227
-21597
11288
-81752
-22003
71667
-19158
-74876
-30722
1128
-35805
79872
-3179
-16081
89141
-66273
43565
-56169
55609
82536
-65083
-14911
-52292
-5503
-36582
-382
-87428
33981
-34207
-18000
-26821
13579
88041
-51065
-38000
-32267
-88340
-99110
-71504
72216
-43414
34774
38902
21329
-53458
97488
53877
-24696
-23040
61807
-30988
-9277
74728
-94976
-4
-27984
-73868
-80284
11057
67098
77448
-42945
95673
81559
22301
-37148
38954
-71454
50449
-80872
48217
15565
7600
-32479
41990
-15576
24976
75798
-77932
-17683
98060
19494
-15870
89257
84322
-64362
10041
-78071
-76350
-38063
-5274
31539
-1690
-19410
44124
-6073
64411
-33947
55033
-872
-9789
-34617
10301
73225
-13709
-39120
-40650
-43063
-88878
-37428
94996
-93000
61987
-14274
-23434
-56861
-2921
12392
14919
19487
-22642
47569
-92282
-46198
53532
19113
19447
-23774
19822
41258
-18922
53829
-78352
-20839
88948
481
-81057
-6311
98464
-93558
3217
24290
-30813
-911
35879
5341
-30232
-66380
-65665
-36523
-28301
21638
86791
-67592
-2201
61354
69229
-48622
75571
19637
3057
26760
35213
68177
63544
65195
58347
81079
48076
11580
-21056
-46996
5117
49011
79675
-70272
-82246
52409
34445
-63686
-60240
-6254
84902
-54054
-37754
95544
83619
-30097
1261
-71731
63254
-65112
-13269
-54496
-91091
-54087
92067
-79763
7738
-74899
-14042
35284
-74959
41299
51630
-99052
-45151
21770
85701
77188
54211
-31652
-79045
-94375
32191
-91013
33271
-17123
-84058
-27891
67279
-42635
15634
67885
-92150
44243
44419
-76209
-40094
55037
32395
41279
34830
85388
63660
82373
52357
-41777
95143
-95841
63911
34952
35444
-32078
-71943
-79573
-40349
-26299
4143
-15298
95688
53154
-11782
-26202
-36886
64799
76022
-16419
56464
9803
-81173
37330
93978
22370
50268
-56496
6843
65771
-19273
-95980
38042
-30406
15590
75381
84941
87428
-50831
96395
-8695
-3407
-22501
-792
-50977
-64471
50691
-10963
-98157
47737
8346
-65459
-76316
773
89927
-27200
-75912
91691
99543
-73464
-93881
31733
-5073
-57489
45226
-65372
-49930
47691
-69230
75583
-25081
-64039
-52920
70110
-22279
-59
-64690
-10774
-21067
-25030
-44456
98226
-65639
-98083
19740
-10728
-26872
-70865
-67809
36261
-1631
94237
25444
81259
44104
-63302
4250
98658
-265
19720
79596
-38841
49516
7600
66102
-1206
-58937
26846
-57257
42811
6169
-16720
74141
37143
12031
-75423
9528
10754
52822
-78414
73706
-67173
-59613
-47985
-76400
-25635
-39296
85962
80905
-75004
-27761
53562
11959
-70059
-50897
63715
23248
-31642
48620
-59925
-74280
-75313
53199
67074
-43229
-73872
-43744
-43857
56471
60371
-43934
99876
-22953
-44197
22614
56629
7560
29330
-73115
88544
-64185
-5546
-10160
-34800
-14040
-13234
-30760
-27695
-62853
-7981
-67301
-38170
-89457
21808
-3963
-82836
98770
-19258
-94046
13185
49683
-93051
25277
23472
-73897
24389
17651
47578
5010
55795
-24990
50422
-22485
-90323
79035
12938
8867
91015
-7825
31832
76598
-93662
-60129
-38936
-7693
-67753
90305
-83285
20725
2489
-79045
-97053
34818
-4507
96903
18463
56888
12343
97660
-30754
30381
-31336
-28210
-97991
57058
5987
-43102
-8234
2405
-99032
-606
-96693
-77952
38652
71053
-88868
-96600
-3004
94423
-99186
-9139
-38570
65953
-70248
8716
40735
49194
-86269
-30539
-20935
73938
54346
8834
-14534
-89752
-74188
-10682
72664
-11144
56322
-26207
43556
31396
-33483
19530
5188
37157
80758
80598
48156
58871
59443
-15962
-27754
29412
76055
79442
-15929
-53540
5799
40594
29602
-51841
46292
-81229
1590
80204
95298
70623
34010
-62221
35037
-34401
-38678
73846
-57384
-89438
92134
78224
42634
73241
-91858
45050
-84350
-13608
-17492
94822
-67342
-42161
82842
-58075
54318
-80005
-65926
93896
90889
-49814
-79500
23257
-12943
64918
-80819
49676
49420
-5939
-17562
63369
-30330
-80118
20136
-600
-99976
-65099
-24554
-26640
78672
17909
9447
-69642
28419
-36520
32087
35088
68740
-46869
26070
-91585
47874
-83103
-37166
-63126
-50338
-59429
-37606
517
-82970
87645
-71493
44906
4946
79575
63287
90672
-80918
15404
29930
-84281
-25279
-87320
-77106
-95664
84286
-58627
24327
-27099
-27696
-44888
-62563
73276
-56556
-89296
-30253
-32262
-53736
73871
-65099
23229
-78793
82241
-27920
-91644
82334
59095
37288
31744
-84674
-70558
-49865
-80584
-75392
-76197
8010
-83125
-83800
21258
43381
-9824
-58014
-23853
-3753
68898
-68228
-53808
-22045
-32238
39443
41369
-58871
20955
-68805
57000
31403
48701
-15572
-10225
-91957
-68080
-63881
-86271
87486
88749
-48270
-6815
31580
2196
-29994
23446
22500
-47620
86662
-53566
355
13324
16863
-18299
56801
-21629
-41431
32267
1693
-30446
79728
44722
59154
-22789
38664
-2231
84650
-29862
21490
-23419
-44964
-1042
-29082
-22954
46873
22545
33962
34395
-58388
-72808
41876
-27123
-99104
-83928
-68538
92746
67794
-81603
39268
97688
-71427
57476
42620
-11253
77830
68641
37917
-19873
70936
-68385
36586
97490
-76930
21648
3484
19172
5984
33695
6898
36162
-94723
-15535
-19141
-89533
-1864
44798
42057
-11985
79936
-69027
-94694
-30638
-5269
94031
84040
-98334
-43701
-8740
6662
9585
24689
33081
70487
2746
85822
53794
-7365
17391
-1836
-20522
15735
92690
-23761
60849
-88116
23491
49723
-35394
85906
-80522
20687
-22365
57941
-68594
-89354
41664
-67626
-86860
-82983
-8212
-96868
-30830
-7292
-71842
10826
-74165
-71340
-40070
-93637
39686
66427
-76376
-61155
-6650
2385
-29534
-59950
68685
-11127
11821
99971
-81688
92601
91678
76218
35786
37281
-59267
-59941
82214
-13899
81028
-34925
89872
-56185
-19402
-95127
25231
16901
18185
92134
46686
-69056
22488
-84084
56516
-31235
50670
-66929
38606
-7338
-42718
76684
-43560
-66832
-98239
34933
-31649
16649
36353
89584
89652
64105
-32793
-95564
-48762
-60421
24066
82403
-64542
85012
-44782
-78724
51323
-5852
10844
-55501
28932
91747
-84386
-1848
-16046
71093
11403
70621
76448
-77355
237
63002
-46982
59818
71113
-82749
-97408
50678
4677
-90292
-60023
-16032
-76075
-85458
-69573
-32559
-58315
-4636
-83452
-48079
29465
-38113
-66651
11645
-81727
-48809
-48174
18386
-13465
4129
-88820
-45455
26256
-52137
-35659
-35957
-89083
-16767
43350
-39700
-283
-41555
-63746
26488
86780
-52725
-31306
-53372
-26851
-16547
97100
-30448
-97143
50447
-32957
72375
-58544
-73041
13735
-81786
18259
5841
-92650
98154
19696
-8984
-61058
28516
-77518
90593
50252
-82397
-74091
93414
-36802
41523
-73397
-11968
-62501
-67421
-24811
79921
-35270
32132
-6315
75518
-42257
-95620
84227
1511
-3935
99149
-60764
-50166
-65836
18523
57910
74909
-51973
-88383
-96969
-72794
-45944
49596
51447
25060
-13039
-14544
-41498
36030
-60858
55905
68217
16813
-55680
-43263
99845
59429
32951
-20238
-19415
-31430
62470
-86409
4532
99818
85772
30130
13226
-23313
71657
-72764
-31647
43125
-35124
-10403
80736
46712
-21329
48087
-4467
9796
-21516
63897
22833
54026
57524
-37669
-81315
53083
-41767
-71153
-48182
48958
-26594
11928
-78457
1834
43358
26537
72677
58338
-18229
95035
78377
-51341
-5159
-39894
77232
91923
60887
67716
10393
77552
-89555
-39122
21382
72119
-83245
-37070
768
-80817
-49078
-6479
-27248
-92365
-47232
-28225
58230
-47917
-56897
-7963
81467
-57711
-14820
-36131
10724
-23648
72105
24337
38589
82990
-57547
-95261
72325
78184
88981
93342
-58634
20596
49084
53364
-99713
-5154
-44797
2604
95517
1102
-53119
-88166
40225
-90039
-93821
-43289
-36071
-13387
46873
-8888
66551
-45397
9853
-48392
-19803
-58888
9879
14207
-16007
90740
-86058
85718
-16894
-31655
4641
11248
-213
-63301
-30918
37485
22090
34722
51952
-36287
11497
-45548
96483
-7818
-9804
71286
-87143
-46729
84385
-72364
-66516
51784
-39251
41400
36511
74383
-99011
40157
-47326
-31180
-64770
-72603
16721
43878
-72379
-50357
-76040
-61432
-64415
-18024
-80257
72151
70161
8361
-84601
-96667
-102
13988
-83837
-36851
-4054
-56473
97971
-93308
62082
-98750
-82409
-83611
1855
68177
-9602
54358
45841
-21721
-53806
280
12810
-15540
53094
-3822
-91023
-27235
41002
63829
-77743
-26683
50195
-18193
-87795
-99518
32020
-50235
-76952
39481
45425
19308
73772
59915
63881
44084
7832
-58601
89932
40888
39937
75792
38449
-20143
-73810
-44587
-73144
-74541
-54602
-18196
34710
-61707
94434
59099
-45323
-61914
41201
60701
-80569
15422
-37930
-22798
16621
69957
62845
-4622
80020
19908
-19566
60834
80305
71872
-43793
-2463
55110
82979
44160
83047
-21134
-84746
21977
53354
-2928
-1932
94071
-27525
4993
64383
-77294
-71583
53642
76629
31826
3653
86447
12643
-98487
-49522
54536
-66109
-84833
769
-11102
-42137
58146
-31001
-2024
32403
22544
31144
-23120
-58648
71165
-60742
78479
18455
-16945
64312
-51411
-31187
28196
-5885
-1092
24257
-22108
96722
12860
95090
15362
36326
71516
-44908
70716
11992
69414
70360
5669
-90065
33556
-15477
46322
-70055
-22437
43426
57439
-74284
-15124
-11071
97587
-48315
-33677
-79546
27679
-63136
10795
-57843
-64003
31917
-65836
-93030
52671
-1973
-67881
37813
-77249
55118
-91455
-76789
-36845
12206
-15572
-36836
-94372
-59083
-84131
-39402
-67182
-90340
-48987
68340
-59879
-47194
59641
-4017
-83057
-55342
97281
-52704
-55214
34223
-12207
74336
-13173
-92139
-13811
50194
-10750
938
5701
-87064
15036
-44746
37071
-73249
3792
-831
26139
-95161
69682
14635
-60828
90031
2164
35901
81050
89877
-3224
12907
96775
36198
33853
-26818
-80742
22551
-95974
-74032
53208
-56873
73065
-50998
91739
53086
27474
-32082
-35024
-28386
77354
46710
-18486
-47288
-13214
-69372
19061
-46408
95112
76150
83798
-2659
-45354
-38896
46531
-3745
-42985
-58718
-72558
-33449
70508
61517
33296
55743
76798
57068
-86945
-39802
95709
4156
-28773
-1160
75438
92409
-22518
-42336
98457
-77108
-75040
61129
7227
7103
-68831
-80657
-3745
28553
-32098
-16117
-43688
63658
62945
57093
-67884
82829
90976
97117
1530
93440
9204
70344
-74647
7320
2640
-25790
-13713
-21793
-3834
12815
-95243
33912
90827
96183
-93740
-58250
-74871
-90203
-24206
1101
-67847
34255
-11541
80534
92746
-11785
74694
84613
86592
21190
-62230
-544
-48616
10097
2143
-42214
20339
58484
89944
-18966
71433
-12870
59605
-53502
36939
-89400
7610
-19865
92580
-18927
-7146
-40755
32727
-56354
14337
-6258
-22562
-30615
13093
63533
-74107
13695
10046
-62224
-31515
81080
23134
-86786
58817
-24090
28131
-75599
-66887
-33656
-78721
-79237
97893
77396
66323
83878
35532
-19840
34584
-95349
18177
-50448
45461
9264
-19475
-21753
64542
88182
78920
8831
-44660
7993
-22759
30165
4249
22218
-72443
-24103
-49412
-62119
64621
9541
4893
-26559
78763
-20096
52739
-53535
12293
-75177
-76857
-874
-71367
21665
66471
-16338
4532
-93307
8476
98287
-16080
-97057
44520
-7904
-81198
-28885
-23562
-82604
22445
14795
-59640
-22542
-73777
-5325
-2117
-63836
55821
-59335
94401
31683
-34423
20470
19285
-27977
48913
-10419
74149
93356
-43651
-3327
-30945
-41448
-61987
52493
-71015
-13458
3085
24986
99935
-80561
-82286
-77371
58972
-63639
-88914
83628
-14458
45975
-54218
-61173
-27177
14399
-83389
-45536
-35633
-1563
-47675
-8123
-84045
-79852
57945
48831
-91122
-55554
84217
14068
-17514
47211
68578
66377
-70283
55644
61836
26802
-21146
-89734
-25189
75808
97957
-65682
67633
44247
-64355
-82815
33794
38962
-6013
-17707
-46185
-48489
60244
72683
-76224
41357
-10448
-56095
9311
80119
-19182
70444
-36120
67882
-40998
40988
-74121
70229
27633
-93563
-4200
-83221
2079
-94170
-6692
73054
17975
55878
14811
-90435
-1580
21459
18932
-52435
-25588
-99758
-99643
-71411
94749
20313
93432
56044
26773
17017
-87428
-54017
-37859
-94268
-2971
81212
-70125
48446
15543
26587
-20061
49984
98221
-49354
59301
49674
29321
-45682
-59348
-8713
-29313
-47996
-43396
-74446
-95377
-9539
-99996
22518
-73953
-40349
-37237
39810
75323
12791
81244
67265
-91945
-84551
-58003
86071
-703
49317
41400
-58270
-13276
-78342
-56667
2328
70025
94352
-88823
-96498
93985
-3438
80569
-93399
-66278
-77906
-95749
33594
-62398
61052
-77792
78179
-85615
9773
-25596
27841
-40391
-48875
31508
-43867
82569
67467
24761
-23859
76066
-75217
-98374
-6206
-65496
-15837
-37749
97224
-5138
-34928
59784
69516
10794
-95257
87220
-42975
-9718
63665
88619
-53005
71717
-98304
98634
10342
40326
14724
16716
-60914
-45681
60438
2998
71232
28468
-30113
-44378
-90871
50982
-21341
-4200
-97687
-77878
28100
-60073
13218
-12145
29159
-29271
2503
-26088
69758
78786
-72304
-69948
-43328
32952
-22023
-66597
25108
-14745
-13815
29750
-77547
36039
-29668
70022
-78541
9054
-18832
-99216
28431
63815
-86980
-96019
-79192
5128
3969
-23702
-31100
-48793
69849
4994
-8237
16892
-5690
-87672
-86746
-7204
-92874
75670
-60789
62483
85475
12336
25603
-23245
-99796
39929
29121
42910
706
26271
-41480
-61959
-20239
92125
-94818
92502
-6895
-27114
6402
39752
-76108
-83237
29551
1955
-27773
57659
-12689
33772
-64373
-86870
-28288
-77984
-42880
-36334
24248
-6265
55751
-99790
93392
24370
-62998
23949
-68824
-61696
-16023
32735
88897
-75029
-70403
14908
73093
-31975
-77995
48414
-28530
25541
-15751
-78459
74130
57551
-98535
85580
-64621
-31038
-70461
30841
50162
71114
50386
-91093
5618
-16303
67634
2379
-97750
-31717
-43608
84443
-46986
62518
99902
42670
-22166
77135
-83619
-42616
-13215
-49477
-4162
-42254
-59160
5675
59500
38080
-51927
50732
-11593
-65527
34286
-17489
94222
-20928
37878
76976
-78800
-41428
-41355
-94968
65736
-48876
19110
-11778
-30836
53665
-4987
-84542
7744
-30775
-88323
-72472
-98880
29028
-52966
80305
28717
-98597
-93576
-8465
-26050
48334
-63642
14698
-22235
97992
75546
-66417
8947
80326
-29075
-48698
75184
-44353
-31725
29743
18072
47271
-96410
74878
-65461
-75029
-84905
64431
-16220
-32313
58489
84470
70876
-63036
-71012
-23499
-40578
-65220
70787
-70412
8764
-78937
15874
-47031
-72985
96372
-49201
36505
-13191
40158
80317
3686
53718
-96516
-60763
78353
-31613
-80482
26064
42118
18067
62185
-79521
-41424
66127
-19044
-10866
15095
77087
57083
45954
-28295
41931
64350
95926
66530
28537
30224
97922
24559
51385
-96940
55463
21121
-78761
-37866
-28862
91587
31246
5706
51687
-59940
-27046
-5856
62396
-54742
-80438
54111
15386
-66799
81247
73876
-56971
-53531
-90729
23481
-28537
-74008
74376
424
76419
28802
-16976
60788
-41407
-24004
86377
-18546
42301
3182
27112
41313
2325
-96398
72440
25151
2950
46926
-58582
-63738
-10686
-34182
-3651
44661
-92935
79239
-34507
87785
3017
23685
7932
-31573
18311
-64453
-27134
-7664
-11976
57230
39867
-99078
25897
66275
-96902
44623
40533
-73563
69815
-45917
-75764
83086
12747
-16309
-22255
-31193
-71482
17652
25595
92069
-55444
-72544
-8286
79803
5892
-29387
74195
44028
63283
-79391
35309
13800
-12933
-60123
-58709
-82728
-25658
26245
67941
26224
75232
4164
-45786
-64059
-80277
-97066
-41403
-24919
-7848
-63491
-54427
-21023
-94769
-31235
60495
-54096
-42613
67836
95060
24497
-78280
25483
-20041
58740
-10019
56575
-82940
-24556
72174
-59066
91275
55332
59808
-18533
-14088
-37230
21199
-33482
-2697
-58206
-43678
-66592
-96385
-82119
-98445
-74310
88041
68691
-26484
36864
-52233
83443
53521
88961
15282
63676
55891
45622
67481
-55657
-21071
-15207
-14665
96576
-57438
55503
10602
41818
-37025
46333
55477
63320
-25244
-1465
45582
82556
67202
-16860
-43522
-68349
68701
-51397
36606
99972
-13401
-38626
16833
-22349
65016
-84227
50466
55276
38964
44589
-58506
74477
71466
44420
-69038
-32991
15396
53582
25540
35402
14285
53225
-68530
-34139
-15362
52834
87273
31262
5825
-63319
-75976
-90605
66954
94338
-11664
34910
-91459
-78487
59511
-70466
8289
7914
25474
-4883
71060
-20233
6243
-26444
85843
48980
-56698
-76023
-92371
62428
-92698
73870
38609
11261
35214
-54913
93682
-55490
-99127
25540
70870
29026
-93013
-76348
-25174
39064
54803
-90760
94087
-76747
2761
-5030
42576
94390
2738
-99277
63800
-6666
-31611
90482
97167
-78788
-56855
18974
48270
-68903
80662
-72023
-92485
35172
-7360
-59769
49587
77529
-14107
96661
-99848
18359
-55076
-31319
-46588
-65234
-86929
72437
72437
-92362
44514
25706
-91744
-4208
-40365
88905
-68349
58340
72380
-81664
63618
84721
65703
17554
82775
42533
30702
33419
-94006
71524
10741
-56082
-15755
68277
-58715
-82741
28622
46807
30273
-37295
-12026
82588
60139
-32974
-41374
7325
-58052
-692
-89162
1771
88417
-41191
64152
68140
-37800
-22754
3791
-25687
54028
-56018
-90071
-93030
-73121
-14923
81954
54890
80727
15749
11586
44193
26473
-38818
-95761
-93990
-65482
31149
-52369
55932
-38189
-34872
-25388
-89154
93870
-21240
25957
19713
3205
-24424
63995
85420
55753
32177
-93846
77947
99149
54507
15810
-87825
27645
81576
50642
-69328
34245
88359
14630
-17734
-69241
81115
26099
-23211
-13895
-11854
-84477
84906
82782
-51983
23959
-77637
26092
75610
63548
73353
-2329
-53467
82605
-22513
-61712
-74960
-49890
3332
62162
-93270
-22420
53056
-43859
-97380
82731
11282
9586
-91339
75835
-63237
-93036
96617
91152
-90683
-6468
79581
72092
-8877
43046
-36447
-91224
-83491
74827
-97083
-82278
91204
-6188
85521
-84998
-22240
-75823
73555
31312
-1195
61415
-55700
-39996
35915
63360
-45154
14758
-70978
81730
-13223
31419
4043
-41043
11815
-46540
-10476
-30765
-75587
18048
54664
46563
95454
7980
-71893
-83677
-77228
-53919
66568
67252
-95985
45872
-31569
-49737
-72985
-84231
-24484
64866
96902
-63163
-7458
-26405
80941
48375
-34547
85022
-6373
-22695
22308
91072
-51105
-44999
70086
-87204
86938
28315
26109
-58591
7693
-43264
-65406
27898
-50539
-20995
63974
-44387
-95789
-4949
-45407
13233
-86866
-35875
-23462
-40098
61404
52096
-49082
-95895
-3708
-47720
-27498
43196
30351
-77155
42550
-27052
-16777
95053
41629
10834
76856
37367
87752
26452
46540
4765
75862
-91497
-69988
-42999
-58127
60916
25240
-40683
-18177
50960
-96521
-96087
74534
75384
-65130
8149
57802
60962
-19152
64616
-69340
-83577
-52847
97715
94474
-972
-60877
-72804
-14670
-24523
39436
84680
-21092
-64206
-88464
-55274
-92095
-79516
38839
-23793
88664
93008
-29747
31205
15772
11764
-20034
-83724
83568
97213
47769
24089
-96955
58699
9134
31568
28893
59438
63928
52983
-54258
-69892
-82061
-90494
40899
38422
-29770
-90220
-47161
65007
43386
-30647
64909
-60014
-76570
36940
-50286
610
-60194
38722
-93434
93004
-74299
31845
-54622
-65200
44556
-5323
-36436
-88348
-32549
-76185
39274
-17581
91662
-81381
-55170
-74301
69612
-16095
11827
-3409
42734
17813
14909
-11142
34431
-66048
1228
-81192
-74072
15234
-30342
98377
32350
-34406
-18780
-33510
76132
61520
72479
26477
2511
33658
30707
-40573
-4249
-62517
15022
80681
-14558
-53863
-59501
-17455
310
-40964
-51597
23665
-9692
-44922
-80792
29572
-14917
-40884
46469
-41851
-80066
20440
-68169
27072
-44759
-71081
-36254
-86830
-14282
87736
-69269
-42105
57919
-1453
84815
39076
-87369
-16919
52334
86453
93160
54471
-23780
36703
62875
18810
65437
-90971
32480
53425
-14514
-65545
-4062
19679
75330
-4386
64594
5951
-15956
-83151
92915
47378
94268
-42522
27610
4527
23160
63711
10408
-94693
63191
91747
-16876
38091
-35412
10794
54405
-68619
-25611
-7244
-36148
-74475
-62071
23607
-12078
83325
-30419
-55645
76963
-56138
11963
-32004
-49583
-28051
-80514
93608
-18703
-15565
-11870
3295
-96166
11740
-4596
47791
49324
-8909
60047
-3315
-60766
-89037
42207
-78012
78586
-8667
-61453
-7255
-42832
81227
-33288
-42997
83350
-17488
96379
96555
-88081
-48652
52795
-12291
84928
-63503
487
5463
-71931
92597
81197
93450
1438
-88838
-34988
-41339
-46768
92342
81346
-50171
-10791
-82125
75546
-11334
1939
-63572
-91138
54819
-14252
82748
16131
-51730
-38378
94958
23822
23852
65017
36234
81755
-91990
-4745
74018
29470
416
38652
32105
77513
-91998
-30728
38777
-90250
-89488
59426
-34441
86175
42703
84350
37751
-88569
-95918
55428
33540
-74169
44132
64703
-42763
18335
84783
-84229
-23011
-78339
11391
-62199
33704
293
88869
-13207
-88748
2917
13509
-76128
37655
-80718
70557
28441
-37610
-66505
41191
6885
15949
-97001
-97437
-10760
99340
71683
21057
-46043
-20426
15096
-5554
-2389
-52150
-60745
-70413
-49478
69444
-16273
-77966
-48204
-55071
23568
47122
-28001
96300
65780
-67518
3533
35342
-68156
47180
98238
-89557
68018
-18895
-53443
-5414
76259
-73621
52924
64065
-17044
92791
37262
2146
61614
4631
57201
-81011
-45917
-20413
23184
-58241
-41133
-61560
59526
-58149
-76946
6569
-91982
15564
-41968
-55046
-4926
52729
35742
-15313
27488
-10715
64758
88588
85333
-67160
-63965
-61104
-51429
23828
75411
-93324
65955
-35299
30789
43817
71883
40437
-94074
-34437
-7959
14376
-66082
25131
-20523
-94866
26081
10634
-18617
99778
70060
63442
35448
-8803
61586
63134
82126
48003
-91779
-17705
-97940
-7609
-79426
-76645
-64327
83944
80814
-57753
20342
14031
-67553
-86703
-44213
66696
-12651
62864
31402
6099
-82439
4480
-66543
-45929
13608
62901
78310
10675
-6659
-97217
51379
-31899
-69060
-84839
51834
40378
13652
29804
19058
2562
-60925
43094
22308
67752
64975
56833
69551
-63545
22063
-13569
-21618
-27187
23561
87803
46556
82647
80880
76715
-89584
-32120
-45573
-27671
48015
30241
33142
16632
-62679
45644
16685
-70193
-4687
20458
63619
-7899
-13827
71461
5178
17821
34411
6885
-3661
38148
-81249
-99860
-29710
-92553
75812
73567
19019
-61705
83764
75987
-49326
-81034
-15968
-81740
-19712
14503
-53247
-75593
46128
-92893
-74367
-27621
-42264
-79131
67321
-58231
-1352
-61240
-71028
7587
97775
14805
58959
-21341
60837
91447
17838
8115
9771
-19091
-66974
-27615
79244
365
82047
-70202
53248
74595
-77721
-60810
84218
15518
25829
10677
-40545
-97356
-73772
20633
-98434
-60730
74271
-76854
-70439
-13782
-3272
72488
-34923
8288
61768
-92945
-58129
-16315
-77370
-82726
-44172
-32045
-54670
58367
89611
6119
-64143
-76296
23931
82393
-50660
-16486
-96687
-35358
-41193
-46893
-62428
64123
-81140
-81019
-46184
-65018
529
-21439
96314
-45395
17098
-59101
87511
-64601
14310
-5424
-847
-41041
-51447
-22662
28215
-48654
-57482
-9130
-59211
-15602
15284
90378
63673
-79374
95380
50693
64350
94186
-86756
81706
51220
59078
-53522
51309
74542
10470
-55046
-35067
-96903
91647
-24204
-36538
35530
-3448
-84683
87639
-35341
-33408
26413
-38146
8665
45308
19329
8781
-13064
-11419
41282
98245
-83017
-98454
52991
66545
8016
-40779
19556
-4851
-73135
-58409
-86813
88516
-5765
-86652
6595
-71047
-25044
-15683
98845
21569
-44249
35626
-50952
-30838
-46079
12288
-66138
-35710
51826
-31504
19604
78562
-37741
-9522
65645
84688
-59961
-6550
-18744
-17137
-40895
13490
50608
-23971
44455
64815
-56390
-42157
33726
8575
63714
2079
-91969
-45432
97844
-48329
-38943
30204
41083
-63025
97150
4909
68886
-91252
95224
71696
14522
64193
-85153
7345
24845
7465
462
-98085
19062
-92219
-9144
34989
99615
6578
78821
-29549
-73858
-20415
28460
83737
-64464
-55470
65865
32952
-23776
-35677
57829
-6
-88040
-52570
-86096
-88612
24768
53713
64064
72369
10231
-18857
41355
-46636
40182
62103
7862
-34828
94004
94507
-32614
48106
-10963
-95644
-4405
-68649
25907
-47289
82474
56625
-64850
69738
-14230
-9896
-82935
-80632
-55768
-92124
-98453
23614
-3716
-73583
-95887
-61626
7467
34354
-77344
34134
56615
-79989
-49354
87890
-57532
-39162
7498
85038
11749
63693
-97416
87347
40445
-16899
99862
80980
-41635
-42919
4765
82109
76946
-18589
-74433
3697
-71795
10562
31734
32432
-78783
-45803
-98035
-87156
72120
-20337
32225
-78466
-60093
31493
-44880
-33878
-24460
-33315
14933
-12608
-23875
-59099
-16430
11164
16958
-8312
54652
6114
-4969
47141
-71046
-300
47195
-21984
-15717
62098
23422
77509
82091
-29102
65779
29526
38602
66242
39270
28859
-73124
9756
-10443
-85572
-54773
70704
-63271
40901
55804
-14497
86632
63618
18870
-85186
15706
83715
6860
72523
-4080
-92836
-88030
78650
55977
76778
-37061
-41682
4901
-54524
-51103
-22571
44329
27327
-31189
12343
-52585
93685
3395
-11428
14976
-83711
-96363
76721
-38757
16847
-55204
38470
-14457
-30013
23718
96816
16747
-8513
88196
60082
65912
-69681
-695
82236
25891
80670
-12754
-25616
9697
92460
85426
4714
-35071
56673
-39525
-69516
-46206
48260
47673
63935
93751
-99970
-21929
-74530
-95943
-50813
-18018
-59319
2181
89935
-24876
79818
-87637
65564
38533
38999
-87639
82822
21805
42275
-56592
84308
37510
70647
-78890
-64686
-20272
36435
-40291
74091
57896
-28027
48548
-64545
63293
50213
-5815
-87068
-99571
-78932
-80736
-28352
-2587
-93546
19798
69295
-82688
-65471
-79664
84450
-89504
-65553
37770
-62628
-40422
-7586
75118
-21832
2652
-58206
-67947
-43590
90222
-80772
57015
-9178
-70810
64381
91185
-69367
2346
-5804
96398
55044
-60791
8632
61426
59063
-19973
-86439
91474
53462
-36482
-13955
41547
-25881
-66908
-43266
70121
-58114
-57351
-23954
10101
10619
-15239
95386
-55394
-71327
37645
33112
40510
-43701
-63201
67487
85484
-80404
-87427
12970
81255
70875
80703
37097
62940
-79748
71759
-38178
-23149
-33975
73014
-49615
-74516
-31776
60850
24688
17690
-60799
5089
-41735
-24263
38151
-57877
19511
-21294
-34096
-74201
-36218
-64155
76039
13281
18604
-72609
-8416
43398
-4273
71989
23748
-14991
84363
-27818
8617
94081
-96546
95967
-84631
75512
49400
49351
-28682
-74147
62022
24691
-10180
-35655
37441
-17642
78970
-32148
68947
-43780
-99960
-16600
98390
89593
-92900
89886
-80475
93965
96852
-49534
92902
-62878
-65573
90730
-84355
4680
58520
-20483
68737
93652
87048
97680
-24471
96171
55057
58168
-43898
90096
-19597
-94639
34003
52338
-6523
8136
-71165
67772
79295
-73699
-64306
-13152
-41238
1054
86508
78529
-89602
-81095
-70897
-44322
25770
57176
59068
20723
71471
19168
-44061
77059
-13613
91551
-89470
-17792
-79002
-72379
28945
53483
16459
35378
-39712
20293
17307
-17367
87642
13602
62412
-36913
-32004
74608
-69406
-55470
-48590
71111
90950
-1070
70667
-52414
-45141
-52069
55981
48037
-20966
-81654
34338
66747
-7947
-74243
-10967
-10612
-42472
45510
-68983
59268
47811
21351
95637
-64185
-68080
-42623
-89101
50718
-92285
79752
19166
8600
-94480
74820
25645
-51295
-23187
-50890
49931
52469
83927
-91210
-35622
60899
70997
86165
93232
1983
24878
-67147
-33454
93317
-12804
-25019
85005
-84074
4903
88461
-53414
36338
-20471
-842
47930
68487
47713
76133
-17220
9245
-78776
49099
84866
-15179
-89738
-95938
2159
92485
-61405
-36802
83300
-63410
88271
-45232
69432
34940
25486
90527
-52844
99211
-5692
-73897
-31416
-40317
32791
-45732
5766
-6001
-34781
23319
7983
13036
-41354
-75735
42929
35917
-47123
-41586
-84916
29373
17429
49806
43416
-30721
-75443
-49425
31271
-8754
-61013
19126
-81912
-95619
-43605
26191
28439
-10320
85022
29677
5143
-3165
34516
87963
97257
-83533
81801
-6429
-40183
30354
12666
29361
-19716
95310
59559
61791
81423
92462
-83779
46173
-74540
13128
18527
-26110
-36777
91190
-55825
46297
-68215
-58809
-61327
-47998
77755
-67382
-62312
86540
51500
-59803
-7494
-20474
-47559
22028
-2451
-86726
73620
90700
39602
-60630
-17522
50291
30190
-20321
82203
-68399
-37969
-18502
88528
-57325
-93930
78366
75579
-44575
35115
-91092
16574
64376
19556
-9080
32827
-66518
93588
89494
-36116
23090
-66692
53932
7924
-62364
10915
84840
-66660
-95204
26632
32330
-33080
97071
-90832
48198
77661
-17017
-81747
-29893
-18894
17379
83302
-19436
52414
76754
-11989
-22528
-74220
-71476
-76644
-5454
-52321
57357
16635
59405
27821
-93411
49793
84216
-73051
77589
92710
-93157
-88149
-2697
39628
96369
-68530
42430
-46643
86723
83455
26335
-79762
96555
-37616
-31572
-18606
59059
91828
37425
51568
46386
-98779
-47225
-64775
-26670
90222
76042
84650
7111
8178
-42946
42587
18697
-96450
-1779
-21984
-40642
54628
78529
-13589
57035
75360
33857
1864
72886
83105
-19822
2302
-75905
-12863
30159
-1143
52249
-70238
-73996
-50409
67528
-73940
-50166
-30238
-93264
-76213
34277
27384
76403
41254
-46669
-6041
60852
-57763
-24831
-58523
-26126
66620
68328
38847
36699
75927
30566
-52660
-56183
66253
45393
-7248
-48795
-48487
-49028
32599
-76846
-55626
-69071
-29836
70854
51227
88897
-58723
1383
-71356
-41613
43302
-9559
4808
-73272
42561
75379
-81082
-47099
23159
7820
22154
8304
-38102
20744
44910
88301
2429
81337
76597
87866
25776
52416
-97856
44681
84191
97398
-14267
26335
-56315
94988
65747
-42314
32541
-57707
88258
12905
58406
-40881
35290
-13921
-44794
6455
-34302
85947
-49454
51399
86475
-77062
12353
78178
-6366
-36231
89820
-19334
-82229
-52531
78204
-77091
13032
83369
67666
-66245
4332
-25580
-29441
84449
-8154
3052
-48813
-6424
29817
-90310
-84640
-12725
44175
20686
-67199
-3812
-87810
4644
-65341
-22007
-32566
84204
6655
68761
-68970
-31017
-88675
92851
-49556
-15968
-41123
-49733
77554
-99776
55583
-38684
-74293
-6415
-6516
-99496
-13836
53434
50501
74320
6563
96084
-38079
-32024
42065
41611
-89662
-73029
-56896
56787
-5732
43119
-73124
81808
87474
24273
-9246
-900
-63546
-5611
-22841
-14430
80517
-51790
-1843
-4513
-7477
93368
-66378
-69169
-51042
-15704
-36202
-72549
71454
67230
-87556
92041
-55437
-41252
67899
-16690
37708
20811
-68411
-12119
80064
-54130
-91129
54545
60556
-7208
53065
-40965
-38465
79762
-23997
-15479
79916
39198
33424
66779
-60934
72556
20576
73870
-40127
34280
-38637
10964
-58451
-31297
80925
63920
53768
-25201
16572
-76817
29163
70134
59777
-41992
22171
-49481
88148
-47905
-73418
-25335
11499
-52377
13142
-91014
-77092
-6987
-98247
64579
-80477
73041
85210
30153
-89757
-46810
82434
-93738
-42527
47400
32409
-1113
94788
-6521
-3828
-5000
40999
-97513
-5222
-56708
63926
24599
1088
-51124
-96227
-79931
-2951
-70113
-70417
16337
-80396
-54799
97003
-99645
38538
42503
88763
-30229
2897
-59407
-60767
96715
58021
55685
3506
58718
82813
745
-63193
98331
15026
24773
939
63325
-58681
36387
-43633
43311
91212
-51042
-44072
22545
-90957
79797
35351
96502
-1485
-85929
17566
-75252
43764
31597
28775
-43715
24903
55423
-47214
-1112
-39983
-59034
50735
82282
-30308
39085
19097
88779
-50164
43223
-43956
19368
10837
-59812
-91806
81806
28748
-22040
17047
69302
39437
23209
78181
69076
-86827
39218
-51891
-97677
-96047
-61356
-4773
-89754
48352
14652
51845
-81846
12603
-51634
23224
76649
53303
58743
35146
44766
-18533
-81504
-67506
52197
-49999
-94418
-81345
31089
14201
-13245
-34391
92126
91715
-5429
-88134
97933
-44471
70841
33981
-85464
-54833
73662
-75226
9384
-9475
-28855
-64772
-22240
-14811
70704
2646
-26167
-75791
-20712
-92743
93861
-96272
-21070
-63377
37718
51469
-85835
-9726
81703
10726
80391
-11293
36376
-32350
14131
511
-13380
-19908
84808
82308
21639
-37439
-59542
50346
54561
-7300
-82234
-15942
-26330
26599
-9137
49655
32279
93816
-89500
710
-54317
-40050
-22502
-91391
89189
-22341
-39944
-76208
-40123
72417
-4484
69970
-62999
62949
-57086
-62220
58434
30758
31667
-12125
-8575
36488
36044
13067
-13296
-60500
-83834
97909
-52128
-61808
26354
4398
-72979
-43258
44491
15190
78999
-81427
-80739
22064
96067
-27275
-41679
-34713
-45105
92375
90391
-98943
-47156
59830
-83318
93389
-1128
-88600
-6571
45703
-49892
-29741
47889
-33538
7703
61130
-89170
-45567
33785
-66115
-20402
80628
-93734
-76190
85741
37810
54488
-73166
-84467
-97746
9687
13459
70625
-7329
-18229
-58007
-66206
97734
-96750
63606
-64935
90497
41564
-9399
-38108
-98468
-59610
-56497
29854
-76793
-54198
73680
-24092
44271
30644
-76076
-45897
-95959
-20718
-99426
-78624
77133
4729
84306
-99540
-32151
-25442
-95331
14211
23844
72415
74519
-52202
-60345
-71914
12245
-22012
-4117
-18131
-8557
55063
46426
-3580
4173
41683
35960
-34874
61285
-24951
-80634
-61054
59770
-60500
37606
-38240
-23208
97500
-6578
-80570
16566
19495
15843
62770
10468
41441
5096
-27971
91940
-61748
-1200
30636
77417
-38287
13097
5948
-68538
50655
-92964
-25910
-82464
-13540
-80139
37551
74914
83274
-29658
-9634
84923
76250
15959
88714
93145
16294
-32985
-19474
-99873
-19160
23532
68674
-47979
-13136
18062
38708
-44797
54382
31805
-41582
77692
30780
-63202
-82248
7732
58081
-51712
99768
99948
39279
-86725
-86646
74083
32591
-47782
-89320
68940
-52169
76168
41514
-91919
55453
69435
94280
90685
10050
-73952
1477
37821
26529
76658
-35300
60085
-61168
-68406
60611
-11926
29515
-29609
-14454
-57042
72277
6869
-97945
-14559
5461
-20898
-79884
-15755
-35961
-96563
95592
26588
-25596
-19270
1191
92654
-77395
87432
-35865
35688
-21963
-31679
12609
7189
87816
-67495
93527
-21468
-95492
-33324
-63993
10550
12190
-86603
-87048
10471
1528
33142
-14467
-76453
-96763
1897
77567
-85524
14921
37540
-14581
35808
-80941
28974
99182
-18140
-66034
-47174
51522
86906
-81138
40752
83705
-86489
94832
1214
-98268
9864
-38042
-68911
7697
76929
-37257
-26972
-96987
-33939
-62805
-46669
78363
23770
10921
-53686
-21912
21565
23487
-43026
20174
-93136
69728
-87137
-10598
-54698
-21451
-79863
-46380
46711
62171
-92695
2760
-99014
-54375
-79672
-83122
12731
72329
45013
7643
8651
72061
-83111
-45635
-50272
28278
-31800
51947
-57884
-22874
-62230
46136
-12380
-33221
-55223
-91157
74763
-85887
-94382
34755
-71439
-69220
9149
4557
-47824
38104
-48851
37616
4938
63778
20373
93092
-60642
17755
57010
-62778
30453
-93620
-91044
-88644
20205
-37861
-45499
-76
21582
32028
-44015
-55379
-39858
3147
-17609
28672
5766
7356
-89044
-56179
8600
27001
30682
41376
21083
92174
37612
15700
-50616
-20228
-65773
92962
-55445
-54040
-79380
13960
-79483
-88072
-3509
52762
-40229
-80382
-30724
-82473
-25275
-99589
-78587
-74156
-60430
21362
-46666
5970
-21773
80834
65590
-73211
-57252
-66465
-94407
-84549
-87209
-48645
20032
10702
57487
68472
-91263
-34102
-74020
25417
76700
-31416
98987
-37473
-5328
-27741
35002
-28084
-53037
72073
83480
-8090
-50446
-22218
73456
-49255
2788
-85152
20940
-32793
-7367
44945
-34118
-77885
97830
64074
7260
81104
-39742
-36810
70135
-47688
-29180
1934
-21659
38402
-43060
-79069
68201
92178
62156
5295
-5687
11145
-42516
986
86185
74758
-47160
-81441
70396
-57277
-82658
31588
66200
78291
-79144
-62347
-8401
48971
7352
22580
-18966
83623
75988
-53027
-10127
-81652
25579
-16045
-92020
11264
46789
96992
-4758
-49579
-70011
66305
71905
44952
-74749
-31131
-60567
94845
87712
47599
-12049
-25307
-99986
75286
-79347
-61447
93685
-74996
-66664
-20577
20843
-17412
-56813
27028
-67250
-55060
-29071
-20364
39497
45310
26460
-68840
-78952
-82012
-71383
6911
96349
70399
17272
90745
-58292
-65880
-84366
99271
-17201
-5629
46582
91394
59870
53734
-8838
-31899
38069
4257
-73183
-33867
44176
39787
-50522
84696
93892
-64016
12425
64584
-74123
-7169
-57379
-52749
15937
29420
-31277
-6581
-34089
-74683
12535
73165
55836
-56446
-97867
-75654
14106
-92619
-79556
86533
-99819
-71197
-59156
43633
-7439
24950
-19575
50778
29075
99562
-30292
-45823
5145
-79100
-14382
-89839
31431
-71899
-91713
51209
11444
-75293
-81829
-69979
19427
-84381
-10306
-25280
70486
12281
-15247
75426
44277
12328
19854
-22974
87887
92113
-11552
71553
-19308
20756
-74886
35616
32614
-94024
-95195
-87901
-89806
-42294
-94787
32617
-76763
-46587
-69018
71824
-25896
41187
-58381
20090
-95381
-31018
-35779
-48019
25364
-48311
85658
-12148
2677
-9417
-76870
-27845
-42450
98594
43133
47682
80345
54866
88784
-11276
-33101
-82327
-83519
-62660
77046
-59024
72899
-76483
-85082
-53422
7279
52124
26104
-4470
-64241
-64648
-25023
-44743
-36492
-26974
39604
1534
3302
85880
-84523
72702
-57309
-54938
-32928
61182
-77480
35439
46286
-26887
79605
-38291
-99076
29481
-53365
57783
75068
-15219
-37573
61805
-67535
-3861
-54635
2169
90849
-59045
64836
-61324
-9263
-22853
95352
28960
-96065
-50882
-85643
-93823
50828
-8220
-80307
-78309
10344
-10347
26829
-54780
-20825
7882
7599
-90564
54200
-15810
-81973
90221
24588
40890
-86421
-56870
21289
65971
1299
-63300
63436
-98248
-65794
-90703
1757
99983
97908
71322
-15570
89170
99771
73612
-12474
86298
-79688
-27526
-70687
-82625
9100
-67910
-44197
77207
50523
-77779
-5023
40489
45210
32057
40032
39803
21198
68936
-5169
30871
71541
13587
-48737
-74562
54503
-34118
29934
-41702
28471
-49624
46699
-7212
34029
-18618
37685
-89420
-60200
44808
23258
16854
-36816
-84529
-97406
63439
-34732
20671
-53405
36831
75894
82906
-47100
-80211
23071
48387
54595
65170
85668
7947
-78410
-79275
51164
37505
-85686
33080
19338
-13076
99430
34003
-34325
-76856
58057
-33636
16109
3862
-21435
-68923
88821
-50675
70551
-13613
94834
55688
-8019
18813
-27912
79519
58708
-24437
-58982
50764
-28383
-10546
-61585
-4734
-99926
23290
61837
11846
-20282
38309
78147
-5697
-39604
37248
-36631
19381
13613
-17351
-54088
-98502
75149
22357
9746
95826
-81164
-30931
-39227
-5929
5021
-98639
2299
38339
-56035
-35356
-36393
-42689
24697
-9634
-60997
-72306
-24500
15617
-24419
-97804
18249
-55369
62109
-55436
-60206
32741
61286
36042
-60834
-58078
-50239
69428
-98291
-68138
-54100
-59637
-31765
-82522
7047
63901
36514
-86266
44878
16004
31370
57859
32025
8369
-46883
-90310
-74077
-17221
-56433
-20309
-3714
-5024
20363
14433
17910
-47709
9085
-27371
4789
59557
67831
-67684
-22621
-31665
-64635
-57354
-38849
24617
-59713
-72873
99414
91866
13883
61763
-21910
64131
-89500
3813
33269
45905
65066
66631
-22838
-26447
-12415
96854
-24223
86987
91530
64466
-28738
42610
-86382
58536
79861
-58918
29147
91110
-31565
92380
-78710
-32492
17185
-5705
91725
48793
46390
43676
73793
56623
6961
42083
8424
20270
-55435
-69446
-3015
-78952
95473
-89902
73066
23993
-53766
51620
37453
38806
49704
-30812
-98148
-88763
73290
79229
74177
88298
58970
-45801
23254
-67300
82259
49314
88570
-83741
-96136
-34395
-51670
-73137
-30186
69944
10855
25546
-79500
-42414
-7891
48183
26413
-48246
-69404
-67069
25440
-10113
30075
61573
-29458
-84954
-8614
-33319
-81943
-7241
87560
75433
72783
34933
-55078
2955
-3174
75573
58951
74891
-26928
-60676
-97622
-96658
-94463
-82349
33517
730
-31130
1261
44305
77155
3261
-23229
99595
33454
94635
-498
-75490
-102
-65716
-93186
-5679
92142
-7160
9632
-47294
-48218
23134
-77989
81656
44331
70445
55522
15636
360
72569
56965
-16165
49574
-23082
-57644
79786
-15051
43843
68583
42036
26950
-54324
51554
96803
11705
8435
76925
-64585
-12432
-3693
1031
32862
-90257
44307
80308
97635
-992
-56188
-48460
-48990
-75621
82089
-77913
-40369
-49307
59472
56046
-37129
19517
-72280
31104
-49194
93351
97909
-54931
-65647
-33622
67848
-80552
25120
65163
6147
-75184
-16868
-43178
-23580
79245
46765
-65943
76077
-80198
11514
29593
30808
85504
9101
63764
71154
-36035
-34247
-69918
-84915
14146
-41532
-95645
87010
33593
-35762
-61299
-25504
-16447
-98243
67181
-43334
-2201
25515
83990
44948
53483
-62186
-15989
54293
-13603
-34531
-76657
28619
-74703
92996
-3397
-48447
-28621
-55467
-89284
-3407
25803
94279
-98177
35122
38260
-22289
-38411
11567
-72641
-44944
-54053
25885
-12729
71551
-51211
-71458
78904
-10696
-6632
17974
-84551
-83739
65293
66507
61948
-10668
-52166
-47595
81360
-42730
40303
-67239
9817
6746
-17936
60640
-74561
-67177
-84148
-60808
81871
9712
77303
48338
-20336
-45838
30770
-48057
43738
-12179
-67402
8604
61491
-61458
42221
80262
190
63091
28823
27047
69139
-23843
61047
72242
96160
17381
-95288
-53794
60224
-24518
82340
20384
-78530
-27485
77988
-84602
-10196
95656
41299
43549
-98710
-77889
34707
94398
29422
98174
77101
62341
6762
-48329
1003
31999
-43123
-48165
-65894
-32709
-9623
-4337
-44425
-93170
-87953
53877
-2219
75966
77119
-70137
41359
-19881
31449
48705
-97620
54441
30274
-42949
-99220
79389
-78042
34057
38572
78685
65129
18705
-48764
-11084
29628
69003
50715
-81234
-34561
43082
-2506
-87628
-62915
-57843
72565
66663
59261
84553
88953
26931
-39117
30149
34957
-73816
5865
-50885
529
27424
-57867
13006
-35901
81706
40434
16246
-11088
-39497
-44466
32216
-99338
-43833
58927
55176
-75028
-36683
-4994
-11085
29357
28881
21711
-50186
-680
53697
-53819
-33100
-8797
53701
-61097
-72163
43971
69849
-48918
-87407
-44789
4890
-79982
45364
98469
30498
59865
-94787
-34445
85678
-9059
-12504
14468
17873
-54711
86239
-38329
59413
77838
-74118
-52725
98226
-31061
86581
90401
59524
-55641
-66856
84784
-53347
-42232
-57569
20968
41771
-60206
-32232
75099
-62643
-35871
-37226
5361
-89696
-35479
35468
67925
-36371
57623
80418
-56611
27854
-5788
-336
40010
70476
93064
90283
-18853
-79482
5197
42217
65619
-69069
36329
26213
1637
92114
75751
-78167
14177
-93612
-41809
-88775
84658
-79780
15962
14491
2321
-3421
13333
26613
-20119
-42019
43247
5432
35480
-25693
-56592
5938
96169
-29263
97440
-44598
31377
-40963
53977
49216
-66934
-42809
-27818
-64209
67681
-98748
-6396
-50168
-7934
48882
5464
-78423
8090
61323
37759
51867
59495
-69327
-14559
60463
23499
70403
23098
-68407
77724
44424
8332
-26760
60140
-72057
-29151
-7929
-23966
83291
3880
-32031
35960
45131
45143
64032
-74290
81303
-55602
19048
8343
30932
65638
94512
33932
54918
74959
-23435
28593
75448
-21004
-46247
48542
-30805
-87321
-4819
-78745
49581
-88708
43187
45006
-12342
-80543
26905
-84550
-27417
-41583
63324
-12620
20751
-46299
63157
-8462
43501
-3242
-61143
25544
-94508
81405
-35812
51271
76095
-45682
42799
-18090
-4744
-60710
68556
34144
-11975
78311
-19563
-81059
-58508
-99642
-68064
-171
16968
36496
-60676
-25421
-81686
64525
-30365
11181
-40211
-59524
83402
99744
-88711
-70301
-85523
47208
76089
-50748
-85019
-68067
17394
-49945
-56079
-92663
6358
-20184
83698
33425
40243
53079
91279
9161
-53864
-96770
53175
85277
71192
-91592
-15867
80367
2908
24314
-40978
94372
-42131
-14420
1084
-6712
39686
77062
-71004
93798
61802
76908
-12049
61721
-43098
-49098
-36786
66739
-85936
-97167
-11220
-57727
-82976
4892
-29453
72118
-80575
-99468
6508
-94821
7636
83920
50174
-52355
96088
99637
-35982
72071
-11293
73419
79929
31109
52291
-68018
42401
-18900
-95852
51441
-72603
-22182
16852
40555
28296
52627
-77083
-86125
44308
56980
11383
-40521
-80672
84976
10643
67408
20874
25921
-50490
66020
78529
-40321
-87129
49670
97548
-55230
-72889
-75355
-12205
-86870
24950
-49269
24807
58501
-98102
2247
-46941
-49778
-18086
84428
53530
-44130
-91561
24241
-83614
54332
68657
72026
-86158
-73629
61814
-13163
31800
-57394
-5690
42045
21244
-4224
-62313
9191
-82825
29698
82588
-12905
-2736
-18836
5592
-19382
-56702
-9990
-84575
-76991
-65078
-93472
88872
32157
-81144
37988
10673
35555
-45631
11009
-16481
-35
-45826
-73103
-10182
2692
-71677
-23114
-47127
-64658
-63186
-85573
16293
41787
90682
-233
-88043
-68596
-72580
-20231
-57579
-84453
-21675
-76868
80010
-61714
57030
-16875
87018
-81435
93870
76408
-62074
32999
-39288
65107
70616
69926
93263
-43621
31470
-28589
-75933
7326
8392
53806
81104
-88792
-28204
-99651
31076
38523
-94191
-74515
26404
-47175
-79349
-76688
11295
-12006
63948
80760
-61545
-48923
40924
50289
79510
-72254
97777
56097
-10021
-5160
-88647
39569
-50935
-62497
91164
58341
-52219
-11762
-65400
-46101
-21216
87365
-65468
49324
-19450
-64192
16812
-64445
-93840
38509
44861
66669
79143
69116
-64853
4995
-13147
63458
50631
61749
-73493
54479
33522
-17461
53871
5273
-65686
-21294
92842
56190
22495
78268
46370
-34140
-73786
-86361
16617
-51934
-10920
-62809
-16799
-42078
4439
26269
55047
76896
29356
-93678
-33316
7984 9087
8855 9824
8228 8478
出力例
99983
99983
99948問題の指示通りに書いてみる。問題は、区間が含まれているかどうかを調べるコードをどう書けばいいか。
Python
N,K = 10000,int(input())
A = [int(input()) for _ in range(N)]
sqrt = int(pow(N,0.5))
if sqrt ** 2 < N:
sqrt += 1
range_max = [None] * sqrt
for i in range(sqrt):
s,e = sqrt * i,sqrt * (i + 1)
range_max[i] = max(A[s:e])
for _ in range(K):
left, right = map(lambda x: int(x) - 1, input().split())
ans = A[left]
now = left
while now <= right:
if now % sqrt == 0 and now + sqrt - 1 <= right:
ans = max(ans,range_max[now // sqrt])
now += sqrt
else:
ans = max(ans,A[now])
now += 1
print(ans)LeoSaki（旦那）は短い配列を作って紙に手書きしながら、考えました。調べる区間に、小分けした範囲がまるまるっと入っていれば、小分けした範囲の最大値と比較すればよく、小分けした範囲にまるまるっと入っていなければ、一つずつ値を比較する。文字で書いてみると余計にわからん？
VBA
Sub query_primer__square_division()
N = 10000
k = Cells(1, 1)
Dim A()
A = Range(Cells(2, 1), Cells(N + 1, 1))
sqrt = Application.WorksheetFunction.RoundUp(Sqr(N), 0)
div = Application.WorksheetFunction.RoundUp(N / sqrt, 0)
Dim range_max() As Long
Dim temp() As Long
ReDim range_max(1 To div)
ReDim temp(1 To sqrt)
For i = 1 To div
s = sqrt * (i - 1) + 1
e = sqrt * i
ad = 1
For j = s To e
If j > N Then
temp(ad) = -100001
Else
temp(ad) = A(j, 1)
End If
ad = ad + 1
Next
range_max(i) = Application.WorksheetFunction.Max(temp)
Next
For i = 1 To k
in_ = Split(Cells(i + N + 1, 1), " ")
left_ = Val(in_(0))
right_ = Val(in_(1))
ans = A(left_, 1)
now_ = left_
Do While now_ <= right_
If now_ Mod sqrt = 1 And now_ + sqrt - 1 <= right_ Then
ans = Application.WorksheetFunction.Max(ans, range_max(Int(now_ / sqrt) + 1))
now_ = now_ + sqrt
Else
ans = Application.WorksheetFunction.Max(ans, A(now_, 1))
now_ = now_ + 1
End If
Loop
Debug.Print ans
Next
End Subindex を 1 から始めているので、細かい調整が必要。これも短い配列を作って確認しました。入力例の場合だと、0.0 秒未満で終わるようです。
最後に
紙に適当な配列を書きます。平方根で求めた値のサイズに配列を分割して、その最大値を配列の下に記録しておきます。適当な範囲を決めて、左手と右手をその場所に置いておきます。左手と右手の範囲内に平方根で求めた値のサイズが含まれていれば、下に記録しておいた「分割した配列」の最大値と現在の最大値を比べます。
比較が終了した部分は、左手を右へ進めます。左手が右手と重なった時点で終了します。
分かりづらい。しかし、こうやりながらコードを書きました。
引き続き、よろしくお願いいたします！