Page 1 of 1

11563 - Introspective Caching

Posted: Tue Dec 16, 2008 11:04 am
by kengood
after tons of WA, I give up...
can someone provide some testcases?

I have:

Code: Select all

3 4 9
0 1 2 3 3 2 1 0 1
2 3 6
0 1 2 0 1 1
2 4 10
0 1 1 2 3 1 2 1 0
and output:
5
4
6

my algorithm = greedy , remove an object that will not access again, or that will not be access soon, compared with objects in the cache.

Re: 11563 Introspective Caching

Posted: Wed Dec 17, 2008 5:14 am
by SerailHydra
Your answers are correct for this test.

My greedy solution is like this: when you need to remove an object, you should chose the one which will appear again at the latest.

Re: 11563 Introspective Caching

Posted: Thu Dec 18, 2008 5:06 am
by kengood
do you mean:
cache = 0,1
object incoming = 2,0,1,1
so 1 will be removed?

one more large testcase:

Code: Select all

20 10000 10000
7940
6669
4049
5661
8373
322
5
2700
2980
7522
5349
5399
9007
8648
7167
1115
7065
7541
2886
5759
5842
8385
7968
8335
680
9666
2459
3722
8317
0
0
0
0
0
0
0
0
0
0
0
0
0
7853
482
8757
7965
97
9051
3057
742
4726
3133
5808
9183
8269
2345
4457
1277
2334
2234
8944
1546
4071
9922
3124
4122
7906
8698
369
767
5291
7529
2656
915
8666
4574
8115
2024
2928
3052
7736
5094
1291
2016
7412
9329
587
6804
5229
9150
6622
3714
1390
9593
8848
9919
5513
1774
8134
9427
6079
2344
7768
8049
5698
2112
9290
1500
9068
2808
4947
6299
4176
8919
169
8483
3450
7166
9298
1531
8244
7674
2245
4076
1210
5655
8330
3884
8094
2000
4226
2410
7530
5760
4150
7256
3772
739
4310
7546
8147
6986
3454
7195
8051
8739
6312
9913
4234
2355
8629
4522
9786
8316
4174
9511
4168
426
1817
8314
4542
4266
8052
5108
9403
3070
1398
2868
6440
7011
7069
2430
9535
1059
8406
2095
3783
2369
9193
4852
4901
5973
6474
6235
9527
7609
164
726
719
6567
9523
8269
2962
5737
798
854
2944
1772
3855
5337
3517
8441
9424
6909
8713
872
107
6781
6113
8304
8408
3230
3891
7169
9929
3885
4893
1486
8389
761
3289
3557
1379
2597
2599
8100
5063
1844
9935
9362
7272
5284
1297
7154
4273
3877
9186
1100
2660
5202
1846
2440
4481
308
4808
4734
4719
9407
6050
5367
5678
3503
5757
9619
9803
4859
207
9167
6030
6918
303
5310
1474
8186
2921
7360
9825
9312
2198
9230
1404
4842
6153
3679
7962
7505
3693
9639
8634
1579
6688
88
150
5797
9825
5609
8875
8659
542
758
9898
5766
8294
165
5546
4207
7358
5984
3454
5877
7169
5640
967
1294
2798
2282
196
6587
1452
5067
456
8022
9037
1601
9435
8544
2333
1758
6650
9126
7189
8962
421
2324
2045
1631
6200
6703
5017
8813
9412
6747
2078
7487
6947
9507
7672
7808
897
4244
8074
2141
8878
1487
8611
6289
8182
8752
2383
5685
3974
1432
783
2068
212
9508
7826
5104
513
3791
8710
6641
5826
6582
5891
4736
2313
5344
3145
7173
5140
6313
9908
7200
7564
4930
4875
7558
2605
9687
3238
5589
3845
4546
8138
2132
1480
3473
2007
7219
9415
6431
9014
3447
2034
735
6806
8237
3437
1071
2039
2358
2876
8286
5275
6604
9526
7789
8817
7360
2729
39
8999
1157
921
7846
5543
3606
3605
1957
4291
3531
8768
5680
4638
4093
9467
3675
7945
1230
5454
7767
9611
9990
4676
2815
2360
7871
3690
1246
4751
3647
4762
8892
5561
5569
4877
5673
5362
8482
4252
2381
2911
3671
6568
9971
3584
7276
8493
9190
6662
7214
9175
5052
6355
9980
3776
8592
7369
983
985
7188
6573
1808
8562
5161
9005
6968
5913
1397
693
5626
7101
3316
6396
3832
1279
8360
5632
6252
9214
7451
5905
203
5089
1272
6526
7676
5409
7406
8307
1183
112
2527
7894
4954
7625
4377
9403
1178
565
7015
2546
5645
4296
9158
9408
4455
6702
1702
8776
7885
8297
556
3966
2939
8255
5084
4619
3477
7848
9632
6038
7659
3991
4298
2193
9446
2824
4252
5341
5168
1048
4540
8326
6883
5678
2036
5118
1111
9924
6132
3410
1787
9145
277
6137
7177
9146
2711
1813
66
12
7694
7255
4791
2254
594
1618
4751
8478
8800
4918
1890
4010
9824
797
9205
1040
679
5240
3634
7359
8585
9847
3565
6290
717
5093
4814
343
8636
8090
1040
1199
7614
7875
7673
7278
7276
9105
5755
1573
206
674
7838
6835
8534
2966
445
4472
7081
2125
4790
3160
1259
296
2316
9949
8172
4442
8635
4452
2897
5766
6983
6809
6214
867
2574
5346
5375
5007
7495
3701
1625
1710
8144
561
314
9745
7280
6516
2350
9610
9948
2387
1328
9505
5107
6710
8354
3046
8656
4364
6624
6943
2751
1577
425
9167
3758
5136
6480
6122
3492
661
8434
6221
7724
1039
4897
6106
4189
4425
56
5058
9993
8020
4169
2093
9866
380
5888
8249
9208
3634
8083
1250
3128
4848
2672
6498
7794
2279
2338
3935
9848
1453
4455
912
131
484
5807
985
2405
6120
5934
6941
7979
3572
1717
4734
1010
1211
5823
2489
3850
4153
6868
5111
8458
8768
6442
7812
2262
7463
4685
7194
7964
2646
9621
787
3134
1389
5895
5021
9417
3529
4210
6384
2897
5348
2087
1707
1865
2908
4058
1453
5867
7895
9896
4937
6946
9918
7225
5503
7562
3301
6646
3625
2505
9769
1530
6625
7923
4761
7081
5999
8686
8089
6838
2603
8892
1359
2933
2254
344
5271
487
4792
4144
4180
1036
1840
4402
9503
4422
8115
9046
5244
8255
4318
6330
2766
4625
6213
2341
7196
1892
6535
225
1671
3429
3103
532
9015
3217
2708
5952
7036
5390
1244
6030
1352
9394
7692
7229
91
421
4709
9004
4637
301
1995
4933
1376
7546
657
2995
9455
2917
6134
8542
9787
5160
2022
8511
988
5275
7947
7815
7009
2237
3581
5078
1083
1112
2431
8025
8258
1581
2346
4592
3407
9759
138
1578
7384
288
675
4355
9230
6495
6573
8320
1000
6282
8016
2953
740
2310
3132
9004
7162
3413
3863
7449
3694
1175
848
9658
1018
409
7394
6695
4943
3057
183
718
5796
6578
9859
9702
7122
9392
7860
8685
9119
8493
3799
6048
4882
4407
595
975
7998
1294
755
2091
6577
3531
9363
7594
1557
4831
310
7749
7942
8385
4517
9965
6299
9216
899
3172
1268
2973
6747
5854
206
9728
9727
2649
1348
4261
8518
1661
3080
8469
1965
5122
2089
9618
1291
1910
2516
7969
4073
9161
5061
2951
93
7547
3365
3544
6048
8526
4221
8605
9744
1266
5319
1375
6435
8739
744
3166
7967
4524
3506
735
3185
2928
3992
8575
7207
2083
112
6923
240
9770
200
4572
6
3905
2892
8787
7118
1737
3390
9662
8593
7438
1410
2232
4913
307
7501
4741
1838
6967
232
9442
5687
7948
26
4398
720
3277
9809
2816
8744
3025
7941
1572
3519
4864
6928
6241
5638
148
5527
3017
6772
8924
2452
5872
1700
5126
8583
5398
6488
542
4240
2118
2370
6173
3794
93
7174
1852
3573
5546
6084
8956
6885
4589
7864
722
4405
5831
3453
1141
9069
1152
3281
7632
5856
3377
6962
2923
3169
7230
4623
6829
4735
4235
4763
1867
3121
8299
5337
4124
3648
9662
9169
1883
1378
3788
7133
1555
6839
3234
2034
6328
3927
2639
6388
8978
5754
9420
8946
1459
9283
2053
5831
160
6881
5509
2322
3390
8944
5775
9552
4590
5803
4127
1662
6956
8608
402
3494
9541
5162
1610
1497
1805
3862
5813
7040
2547
7218
1309
8696
2042
3404
1309
7914
6384
8077
6295
4470
2303
8368
9879
2226
1104
7319
3538
8763
5365
1004
28
6257
8492
5411
5172
4736
2323
2166
9827
8664
5269
7918
5474
1622
5816
7325
9130
8046
9299
9473
5553
1924
6928
7243
4825
1144
6800
7185
3975
5736
453
9668
4669
5980
1350
5265
5328
317
1697
6932
9962
2689
1613
5998
2213
5519
5163
8420
2629
9009
5375
6241
4077
1099
326
1394
4468
3105
9645
8313
6093
6580
2006
8749
2528
4085
2133
7692
7203
2224
8729
9851
2757
1971
4706
3287
3235
3505
2515
8998
9407
4850
9646
4676
5663
5888
2664
7944
419
3025
353
3
7357
4881
3459
6655
8100
4260
3382
5265
1161
8067
7515
2550
5745
6652
9903
9335
994
6110
9493
319
4011
2137
5494
956
3137
9921
1957
4337
1226
9561
4703
6391
6271
3826
3477
3138
6142
1875
6372
121
3314
9113
6286
4820
7817
8708
3426
8955
8614
3862
9791
3263
5784
6330
5306
5284
9242
2159
6349
620
3776
5166
4554
4070
196
96
1672
2633
8137
6690
1054
9694
3694
9262
4134
1669
6236
6077
141
699
4920
4887
3909
3811
350
1444
5016
8599
6553
4145
1608
864
4734
4387
8117
3477
6125
6935
7586
8054
6593
2784
4468
3804
9456
445
2253
1993
1182
9681
5321
9793
8272
3538
5013
1481
343
5318
4528
7438
9017
3513
2906
551
2208
9579
4764
3464
4655
1797
4545
6543
1997
6984
5431
7540
7237
3736
6108
9460
9423
3838
1278
3950
2736
9925
8826
3619
3285
8367
1485
6610
8922
3220
5778
4890
1917
1921
2836
3741
6552
9485
1617
5825
3715
7618
6588
4065
9952
6417
6349
9999
2788
2657
2850
4607
7848
1239
8564
8423
32
8628
7885
3084
6690
131
7806
413
4064
7963
6443
4462
9074
9173
9364
7512
9051
9948
6525
3270
2813
2775
2641
6432
551
7489
8582
9734
7208
3171
9049
5731
6470
921
53
1951
6103
4554
9366
3636
2502
54
9329
7088
8254
5404
1376
8213
3066
3972
6878
5746
6897
1186
4993
1962
1549
2050
7420
9996
7160
2731
837
629
8112
9328
6000
451
5365
5232
8708
3676
952
3925
4357
3327
7815
9944
6458
2519
123
3913
9876
9459
8523
7723
6997
9561
8061
6397
2728
851
3014
6929
7598
457
5558
1094
6106
6300
7283
4500
8754
4311
5849
9271
388
820
5038
4885
2431
7165
509
3923
1712
1463
9791
7858
2504
8928
1361
3645
7282
4893
1057
9040
652
3129
7513
7167
8001
8829
1316
8168
9296
57
1401
226
6237
8494
8412
4097
9453
5327
2153
7827
9397
3749
5192
4021
1972
5447
364
7491
2897
6987
6871
2851
5490
2850
2768
709
5163
8476
623
198
9910
4352
2013
1030
9326
5711
4365
5399
5004
3597
8018
4097
7442
4130
3961
1233
6172
1264
2398
5529
599
3427
712
9165
6031
627
56
2601
3588
9752
7775
127
8321
1020
1137
7101
2368
1594
6290
3221
3455
2456
7217
8047
2611
7103
1583
1695
7600
85
1947
8020
3350
5234
1830
8175
859
2270
4125
2972
4118
979
6033
7911
5539
5172
7883
4116
9776
8432
111
8608
6561
7144
8925
431
5746
2640
6640
1343
697
2008
8352
9121
4355
3226
8159
6941
3434
6449
4876
1592
3257
957
7230
2294
638
1943
7716
8074
1809
7159
356
4262
1315
730
4836
2054
4879
6181
1710
9922
2653
7527
2848
7664
9309
5042
9221
2956
4895
2152
1295
4631
949
3462
2566
8387
4380
9410
7003
9179
541
4036
2240
5697
4757
8777
9500
8294
4372
391
2939
3204
6763
8447
585
1515
4972
5049
5227
1009
9771
9761
8897
8455
777
5106
1737
7547
7793
5284
1174
2407
1228
3385
2724
6450
424
5605
4085
3065
3888
596
6469
9277
6968
7190
4390
2186
7486
7044
2013
8256
1963
7939
252
5305
3774
4280
391
8613
7684
2879
7097
6926
9323
4442
2195
6129
817
8573
6242
8535
7589
607
5943
6351
1051
5936
1035
7735
8566
7623
5764
6211
1976
503
1099
8180
5069
864
231
9754
9248
6584
2113
9805
5491
9371
9463
9315
7222
6201
8827
1600
7371
7390
6960
9197
2029
3672
6917
3603
5942
4791
5943
5920
9442
391
1998
4833
2630
3590
464
5210
3742
7370
9040
6310
8216
7458
8519
9989
1418
192
9645
3367
1284
3855
644
5420
5861
5533
6498
4638
7126
1120
6331
1028
4402
8973
7541
2630
2110
1899
4276
6773
4967
8122
7907
8283
3169
6074
6636
4738
4347
9344
4092
5799
7765
9958
252
2578
5805
6320
6798
8614
7736
3614
3411
5395
1555
4805
2598
5964
9051
3568
6425
8061
5456
5442
2537
9835
7125
6873
5133
5323
118
7818
7573
1714
6260
985
5614
6765
6582
6457
7929
8484
790
1873
1393
8722
8641
7353
6759
4643
6266
7966
4839
3620
2094
2501
7151
3752
9068
573
8877
1501
7016
8155
5932
5829
9595
5424
3848
7959
6564
3835
7317
9759
9929
5559
9585
3492
3079
6709
9036
4464
4256
2189
6031
8321
1841
6377
7317
7898
2250
9414
2860
2760
1500
1912
2553
5654
4826
594
6127
8033
9830
4015
4382
1633
779
6127
34
2240
1849
5168
4302
1398
611
5662
6237
25
7768
2137
7646
9338
9459
1553
8955
9706
857
9315
6335
5912
4124
9330
5977
4384
7186
8538
2806
8971
9438
5147
3422
3812
216
3879
99
5905
7555
9963
1875
5420
7058
9525
6317
7420
5736
1767
5873
8636
6088
3317
7825
9183
7387
9551
2800
3678
8580
8895
9999
7029
9533
3375
6418
7027
451
9238
8653
657
3297
6178
5914
6307
5912
4617
8058
6628
3588
161
6384
3967
137
3980
7625
3583
3581
4054
9574
4411
4267
6667
5678
8856
2081
8119
9285
6100
6059
9095
1076
6448
640
7336
952
6999
2796
6197
2997
1536
4328
8065
325
4657
6933
8299
8006
3869
3042
9754
3980
2028
6708
3874
3826
374
8519
3548
2168
575
2521
5141
7582
1053
4732
8880
7717
497
3660
1329
6500
7669
97
6696
8810
4170
8745
7766
6734
8081
856
2015
7812
9303
8815
657
5833
6742
7442
8089
7132
5461
8593
774
9358
4768
6808
6578
7467
9853
4072
6780
5359
7104
5846
4006
2405
8356
7330
4309
6295
1379
4287
1270
346
7783
1873
110
2415
1213
6396
8624
7409
9085
1099
5069
6161
131
3811
9632
5544
9096
1831
5245
2881
8060
3907
7698
5148
8404
3237
3255
4945
8040
7726
8958
3421
5212
6134
7678
5133
7912
3658
3303
8926
9005
5688
3470
2066
6809
9606
2386
7686
5701
6740
62
5630
5617
3648
918
9106
3502
3166
3312
3105
6354
8693
6367
772
199
74
7044
7597
1395
9738
968
2478
4342
5184
2601
7960
4577
9818
2687
9753
847
3968
5893
415
7899
7597
9352
5346
99
2207
6602
1334
8602
4381
9520
5466
1262
7680
1743
650
7950
6758
3385
7941
7352
1347
8452
7528
7692
643
9138
7757
1394
793
8184
523
1717
5673
9959
6467
4659
7614
2434
6880
594
4211
7748
3816
3216
7251
486
2814
7924
7080
6283
1509
4211
8012
9411
3272
7813
7000
1797
9228
9223
9983
5378
4891
4179
8405
2421
8243
1564
8537
9739
6996
8578
4941
8269
9046
5705
6775
3847
3448
6636
3281
7068
1767
2413
2155
1369
8594
6445
4325
1293
6202
3294
6093
4613
4357
7369
28
1827
8663
9347
7368
6610
1914
8146
5149
6858
8212
7428
8506
3512
7234
4146
9160
8865
4017
8574
4431
9994
9479
7071
831
7286
986
2922
4272
9480
4525
9184
9618
6686
654
5048
6035
1987
5019
8885
9257
75
7819
65
8344
7894
8206
7776
8707
7232
4774
3281
1790
8961
1783
4522
7556
7989
8169
6926
3465
2688
4564
247
4417
2642
2316
4364
168
9142
2277
6313
7488
6500
8199
6542
1171
5206
2972
382
7265
7924
7304
4566
5026
6494
7075
7291
947
3017
7390
4825
2244
5486
3500
7683
2889
8057
7293
3294
1841
9494
2207
8495
7366
8938
8945
8905
9814
5025
7484
4936
3562
5248
5662
9642
4107
8338
896
9101
6600
7013
4830
7579
6733
9659
2477
3937
3682
2381
7501
4073
8046
9626
3116
9849
7099
4495
9987
7462
6775
4565
598
90
2672
8787
7635
839
2409
9567
3799
9527
7441
2601
8827
6599
7008
5029
1287
3076
3791
8284
4396
5782
4092
1132
8474
4783
72
8061
7594
4294
7528
2473
922
6291
9524
4604
6011
5324
8414
6482
3843
1127
6466
8047
4341
388
9951
413
1807
1248
2453
23
8301
6224
4127
5043
9943
7116
5483
4705
3519
2652
2210
6324
3382
1908
8905
5570
2374
726
9622
3418
9791
2467
5550
3542
1565
8008
2428
125
2582
9512
7824
4550
2503
788
2321
1628
8851
2716
6789
9896
6930
4753
2466
7768
4828
9270
6876
1017
8105
153
3289
8544
8875
2527
1594
1876
6111
1955
1026
1889
9448
953
1690
8713
7915
2344
4892
6563
8685
2266
6799
5257
6264
5329
5418
499
3193
1018
7390
1488
8450
134
5911
8829
5425
8404
3183
8410
5746
8798
1579
7457
7604
7118
8102
2441
1399
7568
2961
1161
6076
6712
8719
2647
5008
1694
5712
8535
5983
2442
5270
4446
9048
4965
1715
741
7786
3185
6478
2328
5187
6485
8661
9935
6297
1296
9407
7624
7889
9073
5790
1121
5373
7349
5340
3654
4497
123
9999
5392
5785
1329
5189
1789
2760
4818
8033
9762
5827
5624
1944
9157
6043
3759
6648
334
8363
6839
1301
4875
9434
100
9725
2995
7188
296
9014
9685
9347
7805
1672
7716
1851
3754
1485
725
7225
5513
4558
6070
2793
9456
265
3630
1724
9703
410
9269
1763
1499
5566
1484
5487
2029
4917
6586
476
5897
544
9750
3188
4891
6081
2767
7763
7167
8588
367
6440
7095
1223
901
558
4560
5107
4041
6924
7854
7819
8273
4264
213
9783
8425
908
8047
7754
8998
6379
7385
8125
8568
6469
8579
796
3419
6784
5425
7308
1074
455
4003
5163
4165
9736
6756
9828
2702
2186
9980
5481
9262
8014
786
2864
4610
1973
8326
9376
2888
1691
4459
2422
6403
4098
2971
2253
6763
4598
9409
6178
1052
5918
6610
7547
7257
2152
1823
3500
6036
5319
5770
1747
2492
7732
5085
3663
5911
9190
5488
414
4296
1285
4179
3037
982
6899
826
5936
13
4513
853
3000
7194
8539
5978
7001
7249
9337
3914
3854
5654
4539
8468
5772
3563
9760
5367
7984
5536
8813
5905
3815
6486
1865
667
2574
8837
5892
2825
2188
8192
6386
830
3567
6028
3954
2425
1301
4211
5533
3496
1311
3264
6923
9377
8813
7102
7142
2136
9757
9475
2962
906
8773
7613
3186
3572
6410
823
4043
4022
3327
6033
3554
7601
8140
5898
9761
6446
4938
7459
3380
7147
1383
8862
91
3479
998
5020
9945
6381
7914
8084
3125
3451
5981
6983
6912
8119
8447
9259
4529
6536
4778
8185
5592
2451
5544
85
9133
8200
9198
4672
4332
7762
6209
5704
7388
9232
9342
7900
9350
709
3174
8212
9630
9918
1556
8152
8033
5808
2981
2612
4375
4872
1984
7840
8781
4233
5181
738
9191
2066
6866
3840
8663
3958
1476
9379
676
8278
1950
1187
2887
8759
2408
2490
8211
3220
5973
9744
1004
2824
9218
3425
5116
6096
5108
2887
4704
1428
4435
7511
873
1324
6330
6500
3495
7406
3300
6475
2604
9788
4799
8403
7514
9365
1015
3009
2231
2441
3155
6061
4693
4912
6041
8957
6932
6885
7954
7611
2931
1148
7649
6001
9596
1699
1404
6419
9742
1053
972
4732
7370
8639
6682
6417
6897
8492
2859
2729
2247
6315
6089
6246
9740
5541
6786
6680
7020
7158
4891
5696
2602
3517
499
5033
3041
5623
520
9714
1060
7648
2972
9087
7635
9783
3308
416
8428
5923
3997
3926
5125
7296
6335
1775
7306
8604
5259
2393
6270
1775
3587
8066
3227
744
4259
1778
3776
7156
9465
9260
2308
945
7398
5599
2183
2414
9659
1088
9523
6155
7167
7813
318
7147
9229
5288
831
21
7033
3278
6121
8743
5818
313
5159
5747
229
5401
7818
2648
2778
2155
9600
8443
6900
7380
4226
9971
8072
9192
7787
2878
807
5785
5134
4724
4043
4619
3420
3921
3266
4002
3656
1023
7530
8140
2537
3014
3144
5103
7183
3016
4026
7506
9903
2687
8020
2552
8785
2691
1744
4044
138
548
8259
8024
8347
5420
317
2899
8627
8819
7532
385
7224
601
9434
803
8385
1686
5066
6219
666
9581
6890
2806
9413
6121
1468
6763
2277
444
4079
9034
7269
9953
8079
1509
2663
9451
875
3567
7396
6732
9044
8514
1175
1963
9087
5150
2376
4563
8654
6431
6725
8054
4584
1772
5451
6008
559
2715
4735
4602
6382
184
4519
5938
7548
7108
501
9260
146
3798
209
2831
9770
9019
6599
2006
5906
8447
700
2086
3139
7370
3626
4253
1861
9779
9590
8607
2383
9150
1109
1789
6051
4903
6816
1293
3465
6757
559
1239
5351
1842
3511
2474
2069
222
7399
4424
8724
5737
6419
1500
9443
5288
4508
542
3326
4781
42
5008
4091
5120
2510
2678
3686
7905
399
8577
5181
9010
48
282
7191
1324
3606
7994
3646
4799
2796
9991
3250
6856
2330
4811
1851
5929
1543
1182
2771
2951
1369
2649
8818
2342
5892
4841
413
8460
1084
790
6947
5420
3409
6295
1091
1178
5954
4678
2853
9566
248
4181
2181
1128
8400
545
951
2534
3981
7506
2150
1304
5052
879
9721
1824
8249
7790
252
9234
3807
7685
4193
5915
8486
3121
4535
7912
1698
385
7543
9990
7033
2906
5152
3435
3274
8079
3534
4862
3245
9580
6362
8303
7523
1595
3321
5058
9242
4458
7135
8520
8565
697
2238
1684
2112
5739
4695
8358
2244
253
3192
6481
5519
1686
4959
6636
4381
4852
8473
9490
7592
7153
3167
6591
2282
790
6266
6277
8232
1101
9441
4447
5322
2854
4538
32
9578
8734
8927
3298
7882
2832
675
4966
7001
5221
690
8496
6470
3540
6737
3558
2306
3669
575
1183
8385
2031
2580
1393
8617
6915
6895
5716
3614
3149
4820
6633
2479
4921
2930
4526
4709
9203
8909
2949
2947
5810
8455
4637
8209
7201
1144
6958
5673
5400
3428
2389
4024
2392
6089
4696
8864
824
2985
1806
5130
2041
4620
4798
6053
1922
4922
3028
5755
3287
74
260
7777
7427
7640
8484
1969
400
5472
5055
2540
1012
5556
7398
2426
9551
3151
2401
764
3668
8628
1615
6831
3678
5030
1517
8390
9055
7421
4789
7248
2034
7645
2043
3067
7304
382
5646
8711
3364
3507
834
617
7309
6202
4011
4260
4121
3983
998
5825
6462
730
9523
1144
1421
960
6544
7529
3750
9482
2719
2295
4590
2599
1378
6569
2077
7440
5860
6168
2811
9463
5344
2101
4523
9787
341
7580
1354
8192
6863
1707
4363
5300
304
2991
9344
6911
9386
9961
648
9962
9513
5909
2719
5278
6118
3283
8834
1503
7242
4026
693
8960
2165
7119
8269
8039
6746
961
3540
4302
2725
5888
1876
2402
5320
3842
499
4022
8974
7155
514
410
9014
2446
8659
2484
4900
8862
2884
549
7756
6043
7539
7262
3983
1370
5104
8881
5702
8455
2118
2208
5123
8355
9097
3535
4354
7305
9313
8915
5878
8043
804
7168
2133
1685
1416
5915
6748
6339
1081
4555
3986
2955
8680
3475
8992
4363
1767
1186
1132
2206
9510
1211
2445
3644
4388
8490
8352
7958
8026
8277
7349
8266
4073
300
4621
1674
9239
9301
5511
1569
1923
1063
442
4861
9389
9588
4795
8796
4172
8866
1476
6659
7966
3078
9478
8475
7989
1166
2885
4754
5114
2845
8651
3605
3682
7216
8432
8191
7604
3321
8090
567
6938
3792
2916
2770
5738
8206
4640
5965
537
8904
3798
8516
695
9395
2860
5435
8181
4510
5210
6841
143
3551
5647
6224
6284
4474
4266
8292
7410
9300
4382
7953
3867
1161
1213
3127
3208
4966
2860
4758
691
5450
7893
3587
4106
1770
1851
7515
7541
1530
5478
1631
9642
6593
9588
6673
1373
976
7818
3078
9425
3343
6040
4747
7844
5410
8654
9027
9433
8376
5252
6934
8966
8974
1728
9874
2037
5537
9319
6287
3394
5717
1354
3877
4087
2960
4766
6547
8338
6764
6736
6479
5370
2099
5176
1917
5147
8051
1795
8413
2701
7730
421
3132
8691
8956
6164
3086
9447
59
5449
9496
4451
4263
2399
3314
4326
6180
2572
8123
9507
2198
4550
6767
2979
7855
3981
9927
1876
6436
3950
7076
7664
7714
7980
4669
6066
3724
8308
8211
4441
982
8411
7085
3106
6385
5677
7020
5020
3809
1637
2075
2924
7085
1936
6627
2618
1930
3713
4990
1561
4843
4016
7232
7495
1680
4214
7852
3153
9227
5436
8353
1059
1943
8445
2353
4644
899
1254
9692
196
2487
9341
1445
4075
9831
887
2914
8948
1600
573
6093
1747
6174
2973
5526
3815
1679
5333
2465
2927
6328
2651
4282
5267
771
3593
3071
1936
8717
2506
4350
1609
9115
9735
5242
5807
6988
1407
1368
6492
8709
5809
6273
1167
1625
8115
6775
4814
1785
7779
9565
1718
9564
584
3741
8237
7961
2560
2102
1199
1476
6613
2047
932
5170
7781
7883
6521
3309
1334
3424
8849
2112
4154
3669
3213
1087
3028
2292
4801
8171
7090
4290
2123
9936
6553
357
2615
5156
980
5368
5629
9813
5855
7979
3951
6593
3146
880
5131
5097
8373
2281
9432
2834
7775
1586
3286
3922
7851
1352
9781
9878
2498
4045
2801
8947
5356
3451
4324
9127
8439
2601
9841
7165
9267
5577
5429
6461
9759
1836
8837
3539
8812
4870
2942
2380
7950
8004
719
9625
1182
66
6822
1102
6367
5716
7185
9287
7821
7881
1924
221
793
1149
4212
388
7854
1415
1220
1884
3598
8070
4042
3925
3821
4412
9364
9604
9438
8657
9529
4451
6437
747
9607
9833
3099
7472
988
3038
528
4861
7567
561
3754
9802
3517
582
9896
2226
4758
9872
1761
4801
5170
9244
1289
6368
5170
5375
2215
7218
9807
3213
8470
8327
9461
518
2401
8183
4062
8001
1408
6516
1922
7286
5471
8988
9013
9675
5143
2367
3059
2222
6890
3922
1180
7290
5583
6131
359
7336
5607
8769
3403
8428
8368
7739
301
2994
481
5785
3311
8487
5217
1864
3909
6817
2084
1565
8321
1511
7791
3175
6192
732
7221
3460
1428
9239
5682
9700
8967
3938
4429
4975
5601
8014
8646
584
9099
6406
4127
4637
3919
7714
3481
2569
6365
6345
7859
4457
5138
4839
6399
7644
4864
5066
5305
6254
4945
7955
465
6042
9198
2970
3458
2642
1513
676
7203
8810
7151
4918
797
3900
5958
6001
7777
1862
7522
8409
7148
8231
53
4757
6609
3603
8761
7040
4859
9900
8708
8904
3569
1559
3604
5614
1783
4172
2464
7780
8699
826
1885
886
2032
8957
2122
3253
3839
1360
5170
8366
2556
9729
2611
7615
2420
4667
7500
659
3472
3011
8391
7045
4193
860
9242
818
5738
6121
7202
6405
582
3064
1211
5231
2153
5714
2051
250
5152
16
1857
853
9267
8788
8057
4965
4448
8583
1471
8211
5926
6628
9788
2593
7658
3776
3672
3695
8433
1249
8014
804
4577
6249
8535
5096
7001
6848
3523
2238
6874
9894
763
4870
853
7
4895
3925
7455
2497
8845
1946
7682
9266
628
24
8387
976
1085
8792
2240
6501
2289
9438
6956
6719
4469
6316
2940
3004
1465
1354
4185
8871
4531
3637
8925
6643
6774
4529
7529
4025
3740
6271
1573
4316
7109
2813
96
8450
2469
6066
3301
2048
3255
9894
7897
8173
9712
9261
6415
1235
4157
545
1888
1378
5890
6399
9827
5986
1449
435
9415
2384
2450
5476
32
9945
9247
3037
5928
4773
8727
4851
3130
2246
1238
3254
1752
606
6811
8884
5808
5174
6266
9214
9826
6826
8499
9688
4105
8935
8044
7546
5033
9002
7231
3020
5739
4164
8006
3538
9947
4576
349
8213
2422
1914
4852
1499
6131
6639
6210
3527
53
9524
5348
9895
9941
1867
2970
4647
7183
6773
4395
139
1162
6073
6375
9154
7303
2246
5140
416
3184
8042
2879
9649
8289
5852
924
7793
9164
196
8450
604
7521
6526
613
6053
6828
8590
6576
1969
1542
3931
7616
5424
1287
7207
2900
1713
5038
3919
3733
5356
5745
5189
6331
2136
2859
2585
3846
3830
255
6511
1786
5908
8693
7500
7849
4518
3168
171
6626
221
7420
5310
1539
6023
8226
4979
1139
5746
8451
4238
111
3503
431
6012
4659
5993
5568
7149
8262
1811
6790
7151
9892
1295
6979
2570
7117
5940
5469
7384
5419
664
6231
924
6423
4969
7438
8265
7781
5209
9660
5755
3522
7018
2958
5656
7724
3152
6082
1828
5060
2287
9482
7888
5932
6130
329
9746
8375
3282
6160
2990
1241
6270
9253
9808
4622
4481
3545
3924
566
1983
7654
8774
4865
1918
7110
6027
8542
8800
532
6807
7130
9627
9278
7923
957
4007
1973
9002
983
9032
6480
8626
9641
9772
4343
6692
2299
7844
7562
2238
9396
9432
6769
5998
7545
1197
1016
6688
9468
1408
5534
1840
4517
3610
5778
6553
1945
8977
2891
2240
2440
4195
1170
2537
5152
7469
362
5889
6775
1408
2381
4767
9764
3790
9543
8305
7817
7468
2838
7173
4668
4970
3922
8443
875
232
9352
3363
8781
6832
1840
8731
7736
5993
8854
9551
4464
4711
959
6824
3249
9144
7737
4732
7220
2050
3952
2899
806
6246
2276
5029
3848
7724
4226
6759
2962
4685
4940
2830
942
8732
6607
7683
7938
1466
5636
3268
1156
7239
5242
7370
4355
9988
8849
7442
6360
3017
7927
6404
6655
691
2742
8180
6923
3435
1608
3560
9658
3434
9215
5676
4412
5000
5846
1960
8167
5502
2348
935
4440
638
1384
7550
9742
4695
8300
3102
8348
717
8154
2219
3459
2986
7187
9758
4409
5601
8359
6400
1851
2276
4060
3074
8912
6334
5621
929
218
4457
3033
515
6402
2080
8336
2897
3134
2810
7483
3167
3913
9795
7646
2588
8228
7115
8266
2860
2414
2774
6299
3795
2708
3033
8227
2575
2490
6075
1891
2339
5698
8233
4810
6982
8941
5353
7085
8461
6358
2492
1512
8728
4929
7727
8661
7641
1300
1416
9770
493
3755
7393
1490
2557
4368
3783
2236
8900
6348
5806
7327
3762
8858
7633
3016
4483
8340
8533
999
6426
4027
8294
6654
6269
7239
4545
651
8326
4785
1092
1841
3689
9853
2980
6380
4460
154
6963
3755
6268
1352
6741
6917
7864
9813
926
7529
6839
9732
1205
6331
4308
4908
1233
5778
490
9995
3618
8919
1372
8565
5920
3666
1059
8144
1048
3406
4619
122
2568
6304
7548
2699
1960
7928
1671
8833
1880
938
3515
6451
2365
684
6886
2170
692
4603
8510
9012
9731
3811
9784
4298
7468
3696
8086
483
3767
3569
7379
211
5633
3701
9451
8025
37
372
3797
4175
857
3835
5324
5319
7077
2396
8789
9161
5060
6206
7926
1024
9111
2287
298
8960
783
607
6300
3722
5422
4683
5437
7189
5292
8792
3707
7127
5661
9646
2712
5002
3471
9177
2487
136
3599
2478
5229
693
5365
2078
4968
8642
3569
4180
4234
1497
4581
1858
455
1444
1805
1774
6310
2600
337
7338
9450
759
6091
6555
3009
9320
221
5913
5950
1174
1293
7543
3656
763
8412
6150
8987
6822
9316
314
4513
7171
3087
2129
1730
2794
4658
9496
7035
875
745
5891
806
798
6826
9938
7286
7456
620
6784
1143
7244
365
5211
2670
4118
8321
7015
1398
5623
7367
5591
2529
9274
9074
6921
5480
2314
3232
5331
3383
5250
9189
2926
3015
1889
585
270
8461
4928
8176
7060
3642
7469
4193
6766
2782
4835
9977
3121
4967
1907
3103
6495
2254
6295
1228
2144
4780
4035
5001
8700
3571
1356
8626
7666
9148
3377
279
2349
4354
1844
2026
8309
682
4455
4085
9203
9266
6547
662
7799
4212
4450
5048
9784
5813
1545
8281
8380
1915
7379
7727
8047
640
8164
7561
8375
9176
4743
7682
1474
9665
2397
6088
7394
6105
6820
3120
6315
6396
4470
8635
6766
3059
2760
5747
7969
4515
4555
4373
9122
7420
2585
8381
1565
3685
7996
2489
8116
3146
6160
6007
9343
1808
3955
9320
1147
7144
2677
8023
2032
396
69
8712
5880
9297
7870
1956
8189
7906
4662
9211
6904
6376
1336
6542
7075
404
9695
5283
5633
3884
883
3744
1259
3101
2392
327
3781
6868
5514
8032
6393
452
5677
7567
3178
9810
4447
8038
263
8301
2422
9992
8980
2417
6753
3953
3779
6977
7958
1402
1617
688
8743
8618
4647
8165
7658
2864
3604
3638
800
6551
620
9856
9276
8005
5760
7889
8167
2544
9917
8703
2462
7826
8542
3967
8124
6238
9330
8665
2214
3961
3122
1173
4119
9003
6700
4843
6378
8748
4361
7760
9789
1732
9007
506
6302
2622
4090
6086
6542
3692
3714
4785
1760
1743
4637
3764
2260
4749
5508
8352
7266
7702
6822
5197
6957
3330
5263
4633
7633
9827
779
2119
4853
4718
5737
1055
2362
8165
4439
7976
368
1782
9662
7540
4255
5483
8555
6495
8448
4861
3874
3960
5043
3488
865
9310
2065
7387
1450
7093
8000
2065
9638
4381
1381
4473
4870
2147
5378
4003
5024
893
7597
6641
2042
1696
7364
7765
7819
4409
3749
7092
9052
8051
9026
3652
1544
5662
7681
5042
8999
4129
6570
4982
6089
9888
5613
5883
403
9088
1546
556
1405
5031
7122
9278
9723
3348
848
9896
1941
7000
8713
3945
2679
7330
5675
2669
2985
9854
6217
7285
8922
6740
2398
4299
4378
4121
224
3746
4213
1543
8697
676
628
1417
2943
7094
913
9084
6408
3640
2891
3989
4315
6570
1627
1167
854
468
6262
5839
5590
7652
8558
1366
6201
1150
6934
6717
5001
6421
976
8060
1369
2339
3802
449
553
6923
821
825
3229
8822
5086
3514
4586
7864
6839
8319
1332
2776
4234
8792
606
1529
1811
4791
9677
1214
5721
4432
8894
9059
5924
1411
6692
5485
5276
2146
4165
9124
9044
5173
6015
6223
3161
1067
3116
9905
8284
5853
9297
8290
5541
207
1353
3228
7969
1332
8869
7061
5893
7477
7459
261
7846
8019
6689
2458
8804
2056
8012
571
1747
5365
8987
7267
4802
7228
4547
9522
3485
9417
8431
9333
1235
1879
672
443
191
3405
9835
3800
6794
5779
3210
5167
354
6167
6363
9910
3095
1055
7245
1018
6653
8385
9879
4812
1679
2491
7739
7337
4233
9441
7937
5010
1214
2664
3968
8134
2527
8769
77
6219
5709
6817
1886
3313
4805
1220
1545
2322
3365
2600
2494
2143
739
7767
8353
1852
1739
7799
8180
1886
7344
6000
4630
7813
3339
1323
5664
4806
101
9723
6439
5280
1403
5696
7569
963
6640
1199
575
5804
5058
4202
822
9241
1874
4420
2826
3680
5144
6504
1093
1674
9221
262
3707
4224
7538
2294
6006
872
1387
7753
8572
1860
3156
4236
6995
2512
9296
6121
9950
9576
289
1725
7002
6905
7563
5333
3629
2490
8961
9002
980
6251
1752
2341
3467
5017
3269
2664
8873
9546
6790
1669
5579
8214
4531
2528
3864
3595
5980
3529
2223
6082
3178
391
5074
9960
4071
9152
227
6895
1387
9404
8095
6599
1523
6594
4404
4580
5529
6732
8508
3551
583
4177
4608
8184
9894
9011
9718
2582
8576
7408
4527
7782
4666
3446
2391
3711
9003
104
650
8042
8149
1793
3771
676
8565
2629
4784
4564
7611
5120
998
3065
6488
4369
9761
4901
4102
3953
113
9763
906
6784
5203
9988
952
8963
4615
4422
4614
883
7094
5836
9311
9194
4197
3813
721
7311
2042
2818
5390
5858
5466
7609
8488
7054
2293
3885
9286
7559
6698
9827
1704
220
78
2963
4370
8789
2638
8450
8810
2966
5357
3274
4880
4235
2754
6606
3162
9343
9854
7731
199
5598
7610
8838
3482
9202
1319
1807
7280
7065
3711
2229
4106
6153
2518
9274
8447
6126
4055
1181
9461
95
6848
9361
7416
4569
2630
2284
3036
7281
2823
5899
170
8393
3454
9381
8516
7942
8508
7769
3021
9866
9322
4292
670
6381
4368
7452
6066
7823
4353
1585
4447
7997
7948
3470
1536
8602
2976
6389
688
5478
7501
2873
7107
6558
8418
5049
1753
7938
6011
1597
4069
8483
1641
3543
2396
8115
6919
6444
296
3418
5790
2535
1952
3938
408
1398
8233
1103
8008
4284
1300
8750
4779
5316
5230
5883
6524
4155
345
5265
6067
9761
1816
5763
2835
1890
6417
9115
2621
3205
9457
4207
4000
6586
2731
3243
2695
5478
7459
4280
4427
1804
2816
7461
7949
7057
3063
7189
5452
9965
6376
909
6638
1632
1834
8436
2953
5322
8668
7150
7123
6450
5398
4083
4123
494
9721
565
4526
8876
183
7382
17
2450
5736
700
1853
7224
7828
9979
2491
3058
707
1813
8109
1250
8215
6958
5714
1794
3920
7358
6212
5093
1018
5841
9305
9249
8976
8980
7013
5146
3015
8853
9701
5745
3727
4122
1590
9224
332
2910
5280
8108
940
1903
7285
3354
4553
905
9830
7894
7497
6392
8939
4410
6647
1941
9787
1594
3420
4097
5902
6455
9280
2785
4938
6601
9098
5532
2821
9274
6059
3006
7114
7350
3226
5219
5081
8654
8901
7351
8185
4154
1987
8254
920
1307
9841
9369
2523
6363
2957
4539
6873
9655
922
2998
9791
3054
2162
8453
421
8185
5022
3680
2828
4810
3703
7424
6536
5959
4770
3017
598
2703
5948
135
2078
8583
5191
9484
647
6957
9215
3254
7504
977
4236
8030
4717
1930
642
8776
1182
5871
9894
3039
9032
2300
1538
5353
4209
7500
1725
1181
8418
2323
2274
8747
6456
541
5511
2625
7865
263
1746
8306
3867
7615
4749
9102
6376
7356
6057
6766
1741
5139
6526
5426
2123
1325
5016
7006
9710
5092
4887
781
7794
8252
2716
840
6647
453
7370
9772
2402
3864
4168
9758
5603
3534
7312
2621
9471
8311
9291
2849
1523
5911
2188
5557
8089
4103
3652
5103
9020
3295
4924
9246
4699
609
4110
5850
1859
7301
8676
9550
6354
5060
6908
4084
5792
4655
1743
5423
8047
1270
5906
7806
3499
7952
7176
6511
3689
3553
3557
5919
8829
5326
4179
8709
5883
2634
2095
6087
2337
4559
2966
1809
6681
838
3861
7343
3533
9512
5547
5962
6903
7734
2052
6666
1988
7716
2679
6601
5691
5338
1379
699
782
1239
1255
9602
9650
131
9503
4296
8807
9976
5707
2726
4878
3130
727
6354
2202
3439
5650
4799
1990
3771
1669
1112
5436
4212
7471
3639
8904
7949
3653
6316
9073
4159
3610
1321
9853
9450
5650
1255
6066
5473
9483
7352
3516
8614
8433
57
7379
6508
2746
9069
3329
1917
1377
1249
3689
415
2658
326
3750
3172
1330
6601
4168
4830
3409
4341
1316
2613
4514
9088
9794
3771
6997
8630
5341
9419
4477
8652
9693
787
1250
4594
747
7595
3852
5001
1447
5446
7471
7524
7800
4203
5629
4027
4206
6901
7324
1146
3686
4447
3426
8764
7414
7467
5703
7755
2508
9596
531
9876
7513
7910
3643
4339
427
9778
4456
864
3403
2065
3434
8707
8758
4785
2820
2070
7450
5006
8624
3820
5899
1808
8301
6246
405
1637
9704
6397
3336
7642
1988
5953
1574
6298
9801
540
3942
1009
1524
5975
8630
7226
5070
7067
4213
6645
7526
3252
4482
9641
8531
679
5547
4708
8690
1955
6302
3530
6214
8737
8150
1125
296
3682
2724
9977
6759
1207
9494
5094
4773
5902
3484
3175
1906
7836
6888
6142
4740
5089
2976
8826
4660
5721
1825
5936
7362
5553
4270
657
3463
9414
1681
6087
6752
8615
755
7519
9534
6572
9885
4241
2709
6671
5349
8789
1026
5756
1048
6428
8122
9005
9544
7254
1379
1982
6088
2902
7272
1600
3148
1589
9225
1253
5154
9283
5194
4738
74
8665
1474
3105
7315
1718
7099
1356
1926
2819
4096
1411
381
1435
4304
4357
4762
3976
4492
9442
6460
4875
4870
5617
5748
3559
5100
4111
4030
136
514
3622
6517
9138
9996
3072
6655
6003
7972
4776
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
9310
6362
62
856
8200
4806
6029
2409
6223
8852
1
1
1
1
1
1
1
1
1
1
4417
1236
4191
7615
4028
3029
9241
6648
5053
1880
1057
6639
6378
1059
894
8937
3307
4149
4167
1266
2826
8440
7189
2616
8596
1300
309
3550
8261
9581
2367
5491
8786
5072
7718
8159
1034
9301
7538
1835
4578
2286
7484
8134
315
2499
2654
6316
2952
9486
547
8392
3087
2210
2359
4642
7460
2322
3104
2675
781
3024
949
7144
454
1231
6661
2442
839
3854
6526
2257
1318
5293
4121
5627
9887
5461
176
2545
3842
8661
7910
7088
3398
3314
320
94
6748
626
348
5545
6254
1871
3709
4701
4054
8462
1819
3207
9434
715
1558
9275
3797
6709
5713
5610
5037
1914
1495
6651
3725
9957
7141
4135
4133
2039
1404
4319
845
3813
8236
4641
4917
3037
5208
5881
9129
8792
8216
8512
8652
2626
1237
5175
2286
9498
391
421
9984
6737
8227
5334
251
7910
8016
2416
4246
9145
6448
3334
7809
8097
5584
5367
2118
1680
3177
7735
9095
5777
6415
299
7059
9709
3334
4325
1329
5232
8839
2155
7686
9391
5717
418
4796
5415
1542
4758
163
868
7472
4389
4838
4699
7227
1478
1619
6184
5813
3316
7881
8840
9146
3288
4037
176
5883
1975
8705
1063
4150
2319
9248
7416
3109
8487
3185
3271
7689
3486
5361
175
2081
2340
5738
5474
4615
6332
3244
307
5398
9037
1542
8448
4624
5482
325
2186
8983
8419
6544
5100
6550
2578
2577
4538
3889
4190
2716
1044
8260
6375
4829
9115
1958
4209
1397
6671
8057
4030
4696
9243
6368
1642
3110
549
1145
4897
9704
3782
5488
8673
1972
7984
3353
1749
970
9998
2854
2512
9059
483
3074
8907
6820
3620
7972
8719
4248
1980
6927
9791
3751
7940
5791
6434
8645
3435
3113
6484
8386
5267
8141
3425
1583
7467
5881
5993
3925
6290
5830
4514
6668
261
6339
6163
1300
7257
8808
8987
146
178
4259
7262
8036
6089
1399
2883
5134
2686
9697
8903
9006
1939
3688
2577
6429
7214
5400
3934
6153
7453
4544
6034
6849
9291
3295
2440
6899
7021
9499
2234
9551
7146
1843
9516
4654
8297
2978
6681
817
7920
3872
3264
4885
759
5855
1262
255
2715
3168
1859
4849
4817
5768
2783
3633
3218
7120
3066
1693
851
3645
6263
2970
4073
1598
6869
9925
5295
2220
9777
3351
9100
3728
3410
9733
8444
413
2201
5870
5224
5068
4786
4733
9388
6502
3983
6907
7396
374
3851
4878
5248
5560
2494
843
4762
4311
7358
6025
4351
9488
5117
9143
7612
9759
8110
5258
3450
8545
960
3449
5665
4833
6037
7376
535
4740
1905
4662
1178
2961
3185
2929
4247
981
1043
9029
6331
360
8940
3294
7550
4803
8216
7897
3050
4325
8513
4787
8546
808
9582
5408
1719
7565
7562
3037
1598
2552
1760
971
9938
3276
818
4638
6714
2876
1851
5269
570
3935
4960
9084
3106
5239
4433
469
4828
4522
1105
1279
2484
3752
3034
6978
5264
4400
4832
7803
9469
6948
6793
4413
4145
3770
2574
9242
741
764
2576
6066
4758
8226
3993
1904
1572
519
2381
3867
7967
7155
6219
3135
445
8534
3779
3414
8028
7686
6904
605
4879
9402
7605
2030
1541
7950
2602
4215
6727
9824
4459
3777
1774
4900
7655
6951
5112
3952
3647
9120
1076
6854
789
2143
7549
6815
984
5287
7050
7888
9029
287
4155
2808
1581
791
9681
5276
3530
5810
1393
9784
2538
9974
7613
3313
3678
1272
7292
1323
462
6197
1940
7147
8211
1350
2112
174
2565
9776
3495
2981
4951
1451
5742
8328
1176
9192
8963
9323
8753
4318
3025
7621
5855
6635
5186
6527
2028
953
2504
4266
8677
7502
8727
4062
2639
3701
161
3317
4846
8507
7291
2071
8063
1500
2559
5016
3423
1005
9049
7911
3256
2195
2921
9824
6354
1566
2950
5117
993
5193
180
2323
7073
7899
4997
4419
8166
1341
223
4651
621
3167
3974
4101
6637
5611
8409
7197
5966
9968
228
7349
9980
9786
698
152
7599
4590
2261
208
2761
7292
677
4162
3261
2965
8081
8163
5357
5408
2211
8280
147
6561
880
416
6737
4157
7228
1363
4664
3435
5466
1799
1627
3728
3250
6735
8037
9986
2489
6348
5820
4922
7861
5388
1941
2944
7316
1766
5234
3
5588
6249
9259
8995
2051
865
6412
8829
6560
7579
1438
8763
5022
8198
887
6766
5752
2866
6302
3258
7635
3165
4417
6707
3971
6786
5570
513
6959
7013
4838
3829
9080
2204
9043
3453
2499
295
1394
7522
7463
2900
5918
4550
4487
5516
7933
2385
5443
2897
3699
2424
7062
1727
949
2234
3966
6496
6554
4183
8485
4210
457
4150
9323
4040
5071
3665
6612
3591
9592
6149
6348
4023
6268
8183
2223
7338
1783
3865
6892
654
6619
7580
5130
3682
447
3669
2830
6824
2969
6912
5343
5631
4613
2312
3168
5576
8457
8079
8066
1897
7403
2095
7192
1605
6479
3585
4758
6070
8125
4849
1387
7317
2477
1200
5878
4590
9274
91
5742
9618
4500
5697
5698
7885
5158
5925
8381
6052
5599
6838
6809
2965
303
2898
3719
8650
4442
8841
296
4775
9864
8388
4897
8042
5546
6258
8380
5371
1083
2593
7300
685
5588
1091
9787
2054
7418
3127
2064
5812
1959
4459
539
2708
560
2126
7527
595
9581
6248
3450
9287
382
1131
981
6513
7309
4733
8814
5636
6986
3888
6428
4012
8830
896
620
5548
2312
9557
6112
6899
3144
5196
8645
693
1598
6873
3591
1494
7836
1582
1356
5787
8926
4631
2426
1375
9047
4844
5947
8401
5114
5829
6144
6462
3363
190
4031
6256
730
2788
5565
7328
5118
29
5774
2306
1523
5829
4333
7084
2070
9519
9523
5379
8134
441
1170
9853
7981
6451
3643
3772
604
6961
9271
7037
4735
6343
2976
8065
4785
8525
3885
7251
3623
1283
2363
2843
7498
8455
5884
5258
7895
2186
727
6115
9020
6917
7049
2886
5457
3161
868
4425
5435
2246
9221
4444
2768
1355
6334
9284
2828
3249
6286
42
2024
9848
2994
1058
9113
1923
675
9942
8748
331
31
482
4850
2570
3292
3728
3722
2491
920
3499
6267
2009
2819
594
5650
4366
8441
1311
2282
3213
8780
3581
5041
7663
233
6282
1087
2630
6277
4296
2711
6215
4340
443
9132
2228
7480
3384
8356
3479
6762
1887
766
5434
9460
5168
7995
3141
8334
5104
8868
7018
5795
2916
6037
9577
1268
4826
1133
7214
7418
8184
8548
3003
6323
4699
4902
7578
4570
3461
7299
6720
4505
9756
5387
4418
2774
8381
3239
4848
8905
7195
9085
4429
975
4673
1489
7764
3913
9618
5407
2252
7918
3936
2259
336
5950
3404
8522
5147
7380
2192
7142
1371
4406
7106
8376
5409
3010
8712
3775
1313
3804
5870
5650
5610
6377
2193
9183
8733
2956
3355
1532
2475
9089
129
1265
5578
1811
6042
5151
6530
1716
8569
4561
8809
4806
9078
5231
8485
2194
701
4397
2987
9585
4788
857
6835
7360
8828
4263
74
3617
2039
884
8097
1624
8770
6294
7134
2334
7970
7726
684
6120
2472
2296
5154
4928
2708
7396
3866
3966
4221
1344
9551
5525
3043
3353
3845
5223
1645
8938
2976
389
5950
537
5402
6698
4466
5230
7292
5430
2428
892
2846
7881
2692
931
5624
5956
8755
827
3214
9278
8338
642
5446
245
8929
2335
5114
5010
7950
4426
1066
2484
8373
2908
253
4113
1852
4870
8265
9280
336
4245
9422
3008
7726
5094
3299
1670
3097
4782
3260
3548
3768
2204
2973
140
8284
6116
5587
9921
1882
1268
6736
6668
3107
8034
2429
4862
2539
4039
1260
3292
5160
2087
7406
522
3291
1572
6139
4100
4519
3056
203
6001
5334
1504
296
5882
8426
1309
9825
9998
1115
9240
1065
5694
5901
6114
4364
4441
2216
3719
8409
2161
240
3985
6961
5841
6876
847
613
5992
2749
9458
5561
4422
3869
3286
4742
3678
609
9537
6603
504
1342
550
1434
2909
9027
2562
1959
8345
7697
3966
1365
3483
2279
8311
991
7043
8789
9103
2978
2976
177
7109
6631
4831
2778
6797
5337
1456
5299
5670
5863
4567
1508
526
1205
9466
6277
1925
6438
4031
5606
4685
3926
9026
1089
1757
3355
2190
6418
2720
257
3468
5003
4279
6198
4864
120
1569
5555
338
9572
3108
4109
323
2113
8939
2316
2539
5142
5899
6433
886
5068
7497
525
5027
2381
9283
3524
793
3468
7371
1492
9234
204
3415
6745
1527
4833
2690
2947
3303
5246
6162
8945
7856
6410
9973
744
1409
6609
3698
579
658
1757
796
5656
8251
1075
9941
7699
5230
9330
2350
1794
3548
4289
4144
332
876
9912
8513
1290
3893
4759
536
924
619
1027
898
6630
4906
3609
4683
8009
68
4175
6708
3259
7381
6658
4855
5143
7302
1322
8758
2180
1621
303
2339
423
330
3885
7514
4445
261
1696
5217
9526
1865
3528
3699
4787
2778
7086
4584
729
9388
1688
3472
804
2691
8024
597
6880
2363
5895
2507
2626
6396
2208
8945
5135
8912
9946
6346
578
9373
2024
583
2051
1162
7617
1784
7251
744
3909
3279
9894
2424
2349
6968
3864
914
980
9330
9658
9477
6905
753
4329
3808
3109
3753
9814
6782
2365
9651
3779
4926
2794
7569
6063
7321
6981
3639
8560
2963
6006
8910
9042
2515
5781
3777
9438
2203
2165
9604
4757
4989
7177
1295
7207
704
5810
410
7563
1792
8770
4909
319
9134
7126
9953
1361
7468
206
3639
5190
6423
1016
4751
7688
3896
1804
8601
2299
1579
467
8028
7653
7051
1951
2083
6167
5515
6524
5317
4839
8161
8067
8686
9160
2925
6598
3403
383
9240
3280
9174
5617
2717
7180
2377
2377
4476
8740
4332
8645
9223
5890
698
4484
14
9012
9050
9680
3166
6227
1913
7768
8403
5759
5521
9899
8399
9047
9670
227
7966
1117
3279
5466
4809
9216
455
8605
3238
9655
9758
5605
6855
6085
2922
2861
2208
4948
7396
4786
5847
6125
4934
3918
6971
5666
2731
4265
7718
2815
9066
5157
4062
4217
6723
5382
7324
5832
5401
3679
3466
6861
7021
2805
1728
5252
2141
5388
7626
391
5373
9638
5276
8083
9915
3496
2501
3609
953
6814
5020
8564
3633
6815
6843
6425
6307
4597
7585
3327
8361
865
8973
723
7352
974
6702
8669
4020
9171
6181
5658
2474
3048
4976
6864
4677
3539
1750
8390
1290
1578
2669
6920
4509
2592
6978
608
8937
665
7966
7930
9126
572
4209
2136
9522
2404
9680
5014
5218
684
8378
8606
1254
9356
7867
5540
8137
1434
6452
90
9458
4369
5821
2528
5583
6895
1894
1087
578
6215
2204
7497
6416
3310
9688
6639
388
9514
4774
280
746
254
8524
9965
7879
5707
9967
4516
759
2941
9197
3123
3827
4491
6090
12
4928
1012
8325
1035
7214
6883
1903
9242
6055
5330
7916
3890
3323
8124
8404
9760
881
6622
9126
5563
1034
2338
7870
8821
8138
7819
1039
5005
6136
7098
5877
6832
2619
4787
925
5264
1450
7179
8425
2506
5224
5596
2480
5069
5660
2802
2252
8601
4618
2073
9360
7397
7320
3788
4721
8228
6680
1268
1712
290
3152
8926
9423
7130
6119
5040
229
5687
5303
6896
167
5452
8945
4159
3565
356
3302
8671
8479
2988
3982
5500
8291
6512
9929
1063
8830
7781
2403
3187
1101
5396
3709
7108
7061
411
86
5228
4389
2217
1855
3880
950
2883
9384
8425
5872
4476
4961
9118
2227
3432
1355
5949
3897
8550
9659
3651
1468
919
5134
592
8452
133
8329
3404
5618
2825
5958
1406
6253
8650
2203
7609
5492
7132
1053
8215
5877
88
389
8059
5630
2498
1534
3814
2524
8090
9202
4503
3508
9565
4865
4912
203
95
4721
4233
8685
9343
3479
4207
2992
6440
2515
1763
2449
9142
1185
9965
9636
2440
6581
3146
3928
4011
7093
9596
9624
4577
6047
950
10
4203
3747
4003
9153
4719
2979
8617
6460
71
1924
2156
5912
5636
7174
9137
233
2620
2170
5274
390
3397
2559
8984
6543
3668
3493
7656
724
8515
7188
777
7254
9835
5299
3788
2942
7313
6410
5660
5978
233
8057
6862
1817
8085
6758
8190
4685
9025
1205
2392
7226
5246
1959
3485
1432
9281
5820
3087
5619
2273
5151
8514
5404
2508
2457
5476
1052
5030
4957
1131
1738
9110
2915
8542
1366
5554
6119
8895
6368
8644
7842
5004
2365
6630
7168
911
5110
1556
7362
3339
1743
8390
5087
1430
5000
9629
3334
3379
6190
497
9062
3668
1884
778
6973
1750
3750
7746
1544
1105
285
351
594
2463
4715
7448
8344
4642
6243
9356
1493
9189
9027
3578
9987
492
970
9662
5467
5414
1551
8683
5228
4574
6622
8208
3516
6631
8024
2220
9618
6899
6998
926
2350
3185
2641
6374
6976
122
7843
5930
7153
8959
5446
2409
6972
5213
1570
1875
8571
7813
8994
7669
237
8747
8566
3184
9346
8634
5186
7431
6395
8855
6384
5390
5387
8027
3449
1035
7711
6915
4087
6616
6182
164
4007
7653
1352
3938
8227
7239
9861
9125
8023
1714
8397
9475
3658
9724
7841
2200
1357
3607
1156
2237
4097
9210
2695
2259
1284
4316
2325
5726
5107
9568
749
8270
2748
8879
2743
3989
7075
328
307
2385
5568
5652
4395
3113
6151
3450
6354
7102
5025
1905
1446
5470
1040
4155
303
5309
9476
5571
8608
3865
3700
6181
5144
8418
946
4439
6567
8728
2998
2349
8317
2320
6527
2489
2945
9609
7514
9147
8448
6055
7868
6975
6308
3620
5156
7577
9248
5878
3971
134
8551
736
9145
3116
6377
6933
3961
7429
782
9388
3855
9694
4130
9542
9099
6297
3739
434
23
5437
8525
1464
47
7160
4326
595
7737
2848
6490
8657
3718
5301
979
3371
8982
4714
3324
4316
9468
3230
3870
2781
7681
5884
9657
2485
3484
4536
3468
3108
3380
8926
4519
9588
7093
896
5286
9911
8532
7559
1071
3233
7894
40
711
4207
1283
7806
9498
6388
96
4101
202
8216
976
2130
6032
3232
5324
3539
6178
8780
2928
7558
8304
5504
806
6512
5693
2273
6842
8660
6935
1077
9495
427
5990
4237
7929
3757
9878
7434
4585
6343
7614
7703
3610
4957
890
4880
9223
7821
4814
3356
8268
6866
305
936
5092
2021
9297
9597
2612
9192
9390
8122
51
7038
1279
9975
2665
1459
7722
1051
5630
4766
9347
5101
9723
7957
3955
6443
7263
9463
9680
5156
4267
1077
9134
8607
2255
4865
7425
9315
7434
9723
6521
7510
1619
847
8802
4346
5601
4723
8927
4314
2347
5516
8609
1733
4132
7720
3181
2408
7385
3602
645
9575
7278
9641
1584
657
4769
9890
4367
145
6548
1409
8854
1664
6625
4387
6800
1083
7963
4278
8051
5634
6450
3652
8592
1405
3548
2517
6866
7067
2482
9912
947
5964
5199
2287
2046
2706
9527
8395
9005
3206
2464
2094
289
9160
5634
9716
6110
4682
3866
6080
8853
6228
1948
2304
2677
2847
6190
8380
264
7648
5753
350
148
473
3320
1664
8260
122
8492
1756
1222
1539
875
6939
9429
7477
5478
3112
6887
8444
9990
6945
6599
4370
9313
831
934
8143
3125
8661
9410
9515
4576
2569
6543
719
6189
9929
1238
8652
1341
8114
2893
1933
5321
8386
4607
5987
6159
2230
6650
1385
3054
8622
2736
9039
8658
2327
7552
7255
8802
7224
9435
8691
7809
7053
1155
9515
685
6863
7397
7541
5466
3347
4297
8476
9894
1134
2896
6386
698
6838
6290
6854
650
5993
1944
5436
7286
5338
4951
1528
3080
7908
8495
5714
1377
9210
1358
2670
5138
6745
5537
5228
9434
1684
5213
3079
5069
5633
418
1286
9279
9549
1720
9533
1515
8693
8915
3451
1369
9567
7560
7645
6729
5941
434
7911
8157
729
6643
1287
9782
3676
5649
790
4316
6733
693
6717
2246
6787
6700
274
6526
3965
977
8675
6039
2842
2495
3745
3513
7005
9035
3528
935
4606
3023
189
7392
3655
6725
6364
5334
7362
544
6903
7312
4113
6295
5274
5775
5986
1515
1803
9071
671
2067
4829
9120
179
9376
5874
5744
9218
7596
3404
81
8413
850
7303
9369
4232
2742
5856
4538
3890
9417
9669
3423
3873
2329
6104
4200
9955
7870
4874
3694
4128
2957
568
8467
4433
2004
9662
5165
4230
6283
1218
5466
8981
3478
5358
7487
3236
3672
5574
139
9268
8719
7274
6177
4927
5318
5728
8028
512
6292
508
2659
3877
9943
1451
8117
6088
2706
4525
6602
4962
9781
2003
6754
1169
9779
5736
9144
7228
4370
9797
8170
65
908
5732
3340
9180
4148
7986
4421
2089
3325
3407
4991
2236
2056
5139
1111
8460
2587
4656
2201
4572
7370
1844
9169
9109
351
8690
9907
3591
7423
7565
4832
9089
9467
5540
7668
9530
9020
6587
7640
3816
5021
8717
4023
5332
4967
3220
1822
5709
8006
9842
5607
4137
3837
6997
2067
6245
944
2174
707
5804
9112
6226
4995
5350
7451
3446
1895
3844
3079
9704
2005
2028
5481
2534
9803
6484
4744
7164
4693
7692
2129
1084
3537
1806
5679
2953
4657
2767
7136
129
3281
595
3774
1522
1836
1656
8711
77
8822
2112
9460
8205
8829
1073
132
1726
2204
9973
7351
3080
5086
4519
8941
4958
6884
6881
2603
173
7869
7519
5912
5768
367
7802
9875
7748
7482
4360
7581
7509
3487
2503
8596
8213
7815
8852
1135
1394
980
2477
8304
2266
9960
4870
5975
2503
8132
2197
4749
7346
8823
6245
8317
8264
4206
6126
469
7241
3819
5962
2399
7402
9727
457
183
2782
4753
5084
7658
1461
6718
2872
7752
9657
1716
8838
9647
4071
5739
5667
3600
5129
351
7915
2815
5386
7627
4999
1516
3227
5990
3197
3170
2905
707
3163
4858
6223
8599
2377
5403
9258
2471
2588
1014
1363
3346
6106
7446
9180
7306
3187
6620
42
3308
8106
5631
4666
7736
5571
3774
365
3225
642
2820
3471
2254
6475
6605
9742
2231
9030
860
8837
2533
2754
9299
2919
5597
6681
1159
5680
8915
6357
523
8936
7426
1975
9729
3820
6852
7600
9857
8224
8660
1851
9647
9164
6389
2379
125
8201
9060
3971
5603
6518
4794
2562
8858
3510
9389
7568
7628
2822
6831
3128
8315
1712
2708
6949
9396
6770
5705
16
1579
3645
6303
5267
9489
2233
5605
3296
8304
8218
9364
7400
8212
6263
2078
8459
393
2814
9510
8342
8028
7301
9201
8755
6836
4703
8035
9041
5980
9183
4003
6332
4067
6445
2077
6389
783
1419
8249
2089
6225
9654
1463
340
4521
5493
3725
4972
7083
3222
3042
1300
8793
3398
4534
4321
1387
3291
5010
15
4932
8807
5991
9211
8212
7118
9586
8487
8073
7831
180
8055
7874
8721
3208
8196
9493
4617
6952
9862
2958
1758
8227
5941
6834
3391
5940
5060
4007
499
1708
2699
4551
8316
1189
5583
6166
5073
4821
8818
1966
542
6842
8637
8557
8463
3063
4420
1514
876
3636
7967
7870
5927
9305
2044
6135
6429
8994
7416
1169
3816
8403
5606
3744
2311
6730
9244
2081
604
9071
2004
6108
2956
1908
6096
9324
4904
691
1919
8383
2179
8148
2508
71
2885
4911
877
3649
7513
2112
8679
7947
3018
5748
9097
9503
4149
2040
2368
2152
7973
4662
8377
6801
3925
8841
8908
8493
7241
4334
3690
261
2550
8823
1639
9849
1622
7432
7108
9139
1911
3907
2246
3044
2758
8902
5717
875
2862
5295
1343
3695
3572
9429
7001
1536
8558
9135
546
7233
5772
7145
2443
9255
1075
8641
1455
1354
2942
4357
6319
4131
7645
56
1290
2971
7089
3207
4361
9733
5463
2146
2187
2387
7181
1033
5306
2772
5061
8215
8299
7759
587
7704
3176
6827
1930
2077
7865
1728
7908
4321
2617
7703
504
9534
8099
9452
9560
6088
5295
9662
7155
5654
1795
3054
4681
5407
9601
3432
5969
3954
545
5387
7334
3632
1928
1624
1156
8541
9009
3353
1267
8108
7686
8813
8391
3836
8053
2585
242
3916
8760
9362
5996
105
1252
9937
320
1141
1564
9465
6897
8516
1613
7802
3089
4447
1713
7961
9993
8266
2761
4121
7887
1221
2459
5785
9576
4448
8916
387
5606
6444
4965
2742
5563
2881
6192
1780
9472
4323
2921
9467
2597
9961
3297
89
2403
2443
8963
2660
5032
3714
8780
9480
4905
6931
6249
3952
9078
5695
686
6098
98
6580
7641
8507
7254
5671
3919
6856
4941
1518
363
3636
5186
8960
7119
2157
1224
5930
4820
1094
5796
5961
9671
7310
1038
4149
7525
8977
2421
6702
9132
9711
885
9570
8282
295
4329
2443
7957
1593
7027
6592
543
9335
5604
8702
765
1136
9256
4041
8510
6499
8147
6816
4530
4183
1907
6574
894
7891
6045
8436
7845
4888
6461
9203
8730
5399
1437
7599
5715
6764
4680
8357
6481
130
5861
2468
61
8253
4724
5645
9281
8655
9225
8915
3621
3696
5894
3476
5304
2079
4056
3685
2866
910
1618
3449
6508
449
1621
31
8963
7470
5331
418
5293
4730
5898
309
3668
5614
9978
470
2861
7071
5444
7526
8855
459
6657

Re: 11563 - Introspective Caching

Posted: Thu Dec 25, 2008 5:19 pm
by Laise
I think that the testcase is incorrect because of value 10000 in the list of queries (2686-th line). Read problem statement : "The following a lines contain a single integer between 0 and n - 1 (inclusive) indicating what object is accessed"

11563 - Introspective Caching

Posted: Thu Dec 25, 2008 5:27 pm
by Laise
I try greedy algo, but wrong answer... =(
Can someone tell me how to solve it? Please, help! Thanks

Re: 11563 - Introspective Caching

Posted: Tue Dec 30, 2008 7:53 pm
by bourne
I am getting WA too. Can someone who got AC post some test cases?

Re: 11563 - Introspective Caching

Posted: Fri Jan 02, 2009 2:58 pm
by Jan
Try the cases.

Input
Output

Re: 11563 - Introspective Caching

Posted: Wed Jan 07, 2009 5:08 am
by kengood
THX Jan!! Got AC!
The algorithm I mentioned is correct, just my code goes totally wrong...