Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Benchmarking various methods to encode 100 000 movetimes from FICS
from __future__ import division
from __future__ import print_function
import heapq
import math
import itertools
from collections import defaultdict
#from scipy.special import erf, erfinv
def huffman_table(frequency):
heap = [[weight, [symbol, '']] for symbol, weight in frequency.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
def huffman(symbols):
frequency = defaultdict(int)
for symbol in symbols:
frequency[symbol] += 1
lookup = {p[0]: p[1] for p in huffman_table(frequency)}
return sum(len(lookup[symbol]) for symbol in symbols)
def fib(n):
cur = 1
old = 1
i = 1
while (i < n):
cur, old, i = cur+old, cur, i+1
return cur
def fib_encode(x):
R = []
i = 0
while fib(i) < x:
i += 1
while x > 0:
if fib(i) <= x:
R.append(i)
x -= fib(i)
i -= 1
retv = ""
for i in range(max(R) + 1):
if i in R:
retv += '1'
else:
retv += '0'
retv += '1'
return retv
def fibonacci(symbols):
t = 0
cache = {}
for symbol in symbols:
s = symbol + 1
if s not in cache:
cache[s] = fib_encode(s)
t += len(cache[s])
return t
OLD_STEPS = [1, 5, 10, 15, 20, 30, 40, 50, 60, 80, 100, 150, 200, 300, 400, 600]
RFC_STEPS = [1, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100,
100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300,
310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500,
510, 520, 530, 540, 550, 560, 570, 580, 590, 600,
600, 1200, 1800, 2400, 3000, 3600, 4200, 4800, 5400, 6000]
def argmin(l, f):
lowest, lowest_arg = None, None
for a in l:
if lowest is None or f(a) < lowest:
lowest = f(a)
lowest_arg = a
return lowest_arg
def stepped(millis, steps):
tens = int(round(millis / 100))
return argmin(steps, lambda step: abs(tens - step)) * 100
#STEPS = 200
#MAXTIME = 150000
def compact(t):
return int(round( math.sqrt(t / 100) ))
#return int(round( erf(t / MAXTIME) * STEPS))
def uncompact(t):
return t ** 2 * 100
#return erfinv(t / STEPS) * MAXTIME
millis = [int(s.strip()) for s in open("millis.txt")]
print("Encoding %d move times from FICS (size in bits)" % len(millis))
print()
print("Baseline *: %10d" % (len(millis) * 4))
print("Huffman baseline *: %10d" % huffman([stepped(m, OLD_STEPS) for m in millis]))
print("Huffman (tens): %10d" % huffman([round(m, -2) for m in millis]), "(not practical)")
print("Huffman (secs): %10d" % huffman([round(m, -3) for m in millis]), "(not practical)")
print("Huffman (new steps **): %10d" % huffman([stepped(m, RFC_STEPS) for m in millis]))
print("Fibonacci (tens): %10d" % fibonacci([int(round(m / 100)) for m in millis]))
print("Fibonacci (secs): %10d" % fibonacci([int(round(m / 1000)) for m in millis]))
print("Fibonacci (sqrt tens): %10d" % fibonacci([compact(m) for m in millis]))
print()
print("*", OLD_STEPS)
print("**", RFC_STEPS)
#print()
#print("Lossy compression using sqrt:")
#for step in RFC_STEPS:
# ms = step * 100
# print("%.1fs -> %.1fs" % (ms / 1000, uncompact(compact(ms)) / 1000))
0
0
1133
1406
717
1421
1026
665
2157
420
380
843
3450
481
1042
2653
61526
1857
12043
1268
2999
869
2727
14647
2311
3985
4677
2397
7513
2958
912
1229
979
6513
10786
1337
6422
11685
3030
5353
4976
17329
1315
789
23098
2489
1381
1040
246
2469
296
1485
0
0
4148
1107
5874
1835
5520
3620
5176
5668
2772
1117
1844
341
4454
1965
1083
1869
4238
1078
1770
1028
512
2369
3130
5989
1829
1678
2927
2158
2863
3191
9602
1285
5461
8015
2233
1032
2137
2297
6773
5040
3781
2359
3073
3921
6407
12145
9823
8466
17768
24723
6358
1757
1316
1653
2393
4786
1795
1184
13784
1528
521
872
1474
5671
1359
1823
919
1104
229
0
0
100
100
184
100
300
100
120
100
130
100
540
100
274
291
100
1064
752
1246
514
2837
430
2116
100
1829
1169
442
1054
100
765
1706
2318
2250
571
1006
2385
1369
2368
2492
1740
1336
929
3449
934
2624
2734
2789
2596
3710
2630
798
8178
1422
100
276
294
2443
1261
884
0
0
100
1265
100
100
100
100
100
276
100
291
100
302
100
245
100
311
100
972
100
100
100
100
100
100
100
101
100
1159
100
679
100
174
100
271
100
544
100
546
100
273
100
868
100
511
100
100
100
100
100
100
100
110
100
302
100
873
100
100
100
517
100
100
100
101
100
222
100
239
0
0
619
2157
100
3156
2071
1937
1497
1266
969
1516
1469
2078
1205
1937
3093
2719
1060
1953
1158
1937
1318
2297
3790
3250
9559
2437
11246
6922
6501
2265
1726
2453
4936
1860
1408
2047
3181
3640
2317
2360
5221
5782
1725
1859
1712
656
10860
1875
1424
1921
4425
2203
1531
5860
22907
11891
3474
2031
2479
4328
100
2735
5372
1640
5994
5140
2300
2562
1360
734
4130
2579
1332
8375
1325
2937
1655
2469
3830
1609
2119
2313
1035
657
1480
2219
1579
843
2588
1297
3554
3813
3476
2593
4572
2312
1670
1859
1713
906
1861
2875
2287
2079
1568
4984
4902
2344
100
1844
2184
1688
0
0
2191
4177
1951
4198
2876
4120
5673
13873
6569
27734
14744
5239
8707
10875
1916
13631
4407
1612
4066
530
8179
5122
2103
5588
1687
1792
1454
7346
5339
3650
5315
3870
8687
3462
2921
0
0
1981
245
1134
396
3055
957
1150
230
5126
2013
3838
3151
2829
686
5798
1182
2614
1478
1683
1950
1510
4382
7486
6718
3798
6269
4462
7286
3166
6550
8333
3254
4341
25358
4220
934
7501
10606
4606
4198
1877
1206
2382
246
1510
654
19605
2494
6468
1142
3589
4393
9077
3390
7422
6542
3846
3166
1261
1038
3125
1429
3046
3262
4276
2430
3654
5894
2893
4590
1292
606
3124
6462
1992
7062
3572
871
3806
1222
1521
1110
1502
1558
525
0
0
733
1456
1824
1327
649
1334
934
4963
1683
1822
1501
4292
1435
564
4570
3795
3571
1487
1834
1703
1571
1571
1495
1391
5713
3474
4949
1187
2278
12201
1812
1271
5967
6801
1835
6366
4584
0
0
587
1981
451
2783
451
784
743
1744
1179
1141
4850
3279
1075
13472
1637
8449
1444
15947
1965
1857
5655
2194
898
185
950
7903
936
3457
9921
7350
5850
4320
1996
4564
3275
13681
931
3531
1382
2829
2084
3116
10951
1937
3237
979
5453
4923
3035
3333
5397
2238
16440
3865
902
8962
4726
1256
10217
7895
20544
1923
7638
2349
0
0
486
100
559
100
469
593
604
100
728
468
616
858
1036
639
976
406
1472
702
1609
1279
1359
983
990
1560
1224
1388
763
593
592
1388
995
1139
1162
100
1387
2403
669
1591
1127
733
884
889
2217
608
1657
2137
783
608
670
2543
1737
5897
2081
468
1402
593
1237
639
647
655
1200
1201
1521
1076
130
437
1110
2294
1970
1077
1113
1872
1735
2902
1063
1451
121
1778
1121
1279
545
1419
2727
577
1409
546
0
0
602
3213
960
6316
2101
4492
3768
6978
5238
1060
15752
1537
6010
2701
34828
4118
10975
7176
1316
7554
5554
2513
26996
1630
15574
5637
8923
1711
23390
5665
30454
1748
8392
2766
61639
2000
30557
2306
12903
7894
3871
2481
12831
1513
7032
1418
11376
2427
11987
5442
7727
1529
4508
6947
22772
1929
1254
1734
48389
8034
1289
4873
14099
2608
18281
4188
9187
3082
3197
6009
9153
3353
19266
8792
17970
4241
13863
12257
12514
2345
15922
6402
11681
4958
15412
17165
11411
9000
9100
9141
9819
12929
6961
7711
7497
5190
13034
1349
2925
0
0
1039
100
1513
1242
2615
822
2304
1739
7079
3593
5706
4647
3406
2878
10782
9102
1469
539
3776
6739
4819
15675
12276
2322
30033
2298
919
779
3551
6193
2814
12552
4103
15347
10237
29362
16370
1455
6262
4812
2228
9893
2205
2315
1086
2426
2072
905
1592
2888
2827
10795
1945
5149
4065
1111
2408
1345
1500
1281
1391
1283
3734
10355
1039
1819
734
100
1113
391
1354
1016
1997
755
2118
2606
1779
100
1364
100
794
100
1882
836
1710
0
0
1185
693
486
1354
598
1349
1421
1172
495
757
1203
6950
9069
1978
5922
4960
14199
2995
3049
2684
7499
2231
11071
1835
12121
3556
6555
1094
8591
8060
3200
3734
8366
4442
2044
7550
1521
5829
1634
13711
3121
5828
1485
5640
8252
5982
2411
4203
3987
3136
1699
0
0
1578
1507
1200
1603
1252
1995
1632
2571
1994
4682
3647
1537
4236
3940
2033
12897
2799
2856
3804
1984
5857
5688
3346
9138
2986
24434
9243
5565
4277
5875
3368
6130
6233
13062
5437
1579
5802
2694
2418
5070
18237
14627
4933
0
0
2016
411
2035
635
2162
1916
2400
3589
5254
4808
2218
2152
2965
1652
3840
3457
9839
11386
2788
1417
2835
4746
2492
6146
2101
932
3654
1479
3963
3604
2800
1506
11533
1261
7794
2494
3376
3020
5739
5777
6751
1510
1983
5302
1948
1449
1811
1035
3189
2354
2593
1661
4009
5902
4910
2339
2753
14152
7195
3090
3319
2636
2853
13215
7068
3293
6394
5771
3863
949
11923
5620
2100
3340
5481
848
5239
1474
1776
847
6381
2433
7933
3474
3518
2479
2248
2183
4559
2933
35081
1193
5613
1426
2619
995
0
0
1082
100
1433
100
575
100
539
100
203
100
203
100
224
100
574
100
429
100
808
100
459
100
100
100
175
100
538
100
784
100
686
100
100
100
625
100
182
100
100
0
0
1713
2145
2480
100
807
677
10779
1391
3055
886
12383
31851
11399
16580
18693
16942
11274
17582
3791
5967
2258
3558
1948
4919
8650
9086
8933
9739
17013
8474
21488
6282
1787
5540
77205
100
9508
10604
16698
10346
2284
11124
17302
6842
7926
6262
19593
3130
5000
5549
13626
17088
3786
11608
3842
6906
5440
2183
7890
7801
15321
2747
821
6527
2511
1903
0
0
1968
592
790
1427
1737
1055
944
1018
668
1242
900
952
925
786
969
2141
678
943
1414
864
1230
3193
1233
2485
3109
4977
10105
3952
1423
2156
1750
3606
3439
1547
15331
3215
2050
10131
9058
1124
2281
982
8061
870
1232
898
2021
765
2160
2239
1835
687
869
1430
2074
1799
1499
2222
1516
6408
4750
1480
1053
758
5665
3250
5967
2489
1701
797
2029
1664
2879
1155
2850
2471
0
0
1006
382
1033
2070
1641
685
1154
990
502
1191
704
2017
8294
100
1102
6495
1687
7251
3552
985
1408
3224
1818
16523
3661
1580
3217
1650
1547
779
10010
2994
2601
5600
3078
1008
4308
7439
1471
4934
5588
5277
1564
10454
6658
5334
4465
9578
4989
4987
3262
2688
10363
1401
4703
8777
4987
1008
1792
3019
8414
1430
967
17489
6952
1649
19915
1894
967
3251
723
1566
4762
4474
1398
2151
1688
869
1339
2305
2507
777
4919
4185
1234
2132
13302
1329
1490
490
0
0
1318
1479
2326
3239
1131
3063
720
6183
198
2439
2126
1267
3539
3201
2740
2340
3166
8733
2375
23347
10815
9092
4402
1146
2595
1380
2691
1428
2614
25921
2551
36673
8364
2080
12598
3318
2926
6218
6267
3850
3844
9443
2774
5488
14057
7863
21021
1761
3549
9539
2669
3332
2442
0
0
100
702
100
1123
100
795
232
889
1331
3074
3336
733
2004
1669
12573
2886
1715
1248
484
100
2275
1404
951
3011
100
4352
1500
1747
2137
2855
1263
451
5981
1652
100
589
2315
100
1648
1904
4768
2184
720
3730
911
2277
2099
1201
201
1170
1037
2106
547
1528
432
1466
461
3401
100
2574
1985
1123
1315
484
1131
764
970
952
1964
951
1000
639
0
0
485
913
485
3714
578
1502
531
2166
1141
1101
1453
1235
1281
265
2047
500
4740
1383
1567
335
2674
1130
2281
898
1969
2454
4703
6423
4172
1338
4640
6128
4594
3219
1438
772
4535
4212
1906
6391
907
0
0
102
1799
100
507
119
1179
100
743
101
1335
114
1998
116
3775
143
2083
144
6428
181
4998
148
15610
156
21143
172
5844
135
6811
111
1378
114
3279
120
13533
107
6446
134
3227
0
0
1442
2777
2736
992
1008
1375
2594
2020
2683
3262
929
1601
1424
1062
814
4143
4078
6296
2328
7913
9118
930
3735
14321
12622
3906
2766
6354
7358
3314
7446
10379
11902
6227
1583
8497
7940
5185
10388
1427
14075
46060
7578
8373
15026
19258
9393
1166
1105
1637
10328
1062
2528
4974
7952
1159
7353
2559
1232
1415
1532
0
0
1168
611
882
691
802
530
821
851
913
1132
4389
1712
1268
6819
13490
18727
18906
5748
2078
2974
2246
0
0
1697
3383
1614
1524
1512
5702
1557
5083
2015
7502
2775
3110
1711
2231
2748
9573
3294
1221
1767
1949
1750
1655
3245
4651
3048
17129
9649
1577
1733
5196
2334
6163
2909
2530
2092
5372
2450
1682
3510
2845
2703
5358
2228
7980
7003
7930
6755
15479
6944
25784
2196
41616
4968
13658
13042
9773
7146
5518
2450
5202
2040
5051
1798
0
0
100
1365
100
100
100
100
100
222
100
829
100
100
100
312
100
241
100
134
100
100
100
100
100
100
100
100
100
786
100
176
100
100
100
100
100
532
100
324
100
403
100
169
100
598
100
100
100
100
100
100
100
222
100
306
100
756
100
100
100
388
100
100
100
100
100
296
100
151
0
0
140
804
100
131
100
100
655
100
100
100
967
814
1903
1399
1701
1108
499
100
499
1166
100
1343
100
1434
2043
2856
686
3046
1342
2650
921
4437
904
2977
734
4626
6614
2863
100
1111
608
960
100
2236
452
3079
999
688
2106
700
499
1987
100
2179
100
1154
100
573
0
0
1045
100
486
100
393
100
1485
3172
1018
3219
1370
2969
956
3563
586
3297
2489
3422
4367
2922
1261
2766
879
2500
1551
2360
917
2266
0
0
1000
170
281
130
396
100
179
100
551
100
345
924
474
1474
1270
1923
189
611
2478
1314
2192
2781
1520
430
2051
2386
808
1423
736
427
1243
1516
4513
1439
2911
1934
725
2078
1513
3353
3843
4897
1116
924
3356
3207
3067
3457
3720
1418
2106
1996
1791
1466
100
1153
1050
748
1308
1122
1938
100
142
576
633
820
565
290
465
665
881
618
451
852
700
649
499
623
386
242
499
280
432
289
2494
852
391
873
1150
997
0
0
390
100
1559
100
1443
100
1096
998
1076
3137
921
951
1265
1278
1779
2084
1258
700
3113
1225
618
4520
1333
1326
1144
2198
2181
3142
2312
2074
3310
1756
8619
1975
438
1226
272
1834
1379
3099
1390
3431
2576
4627
3106
1085
4520
1138
2595
6270
1466
1448
1556
1053
2408
1602
2111
1612
2197
100
0
0
643
100
1247
100
1200
4234
10278
4193
3623
7687
893
6341
5774
11010
1453
9795
31003
7101
5573
9452
11165
11154
6420
3793
0
0
1276
100
1841
100
2194
100
1955
0
0
1339
100
739
100
886
100
426
100
247
100
267
100
225
100
383
100
129
100
456
100
100
100
100
100
335
100
972
100
979
100
616
100
164
100
692
100
370
100
1020
100
609
100
621
100
371
100
139
100
694
100
532
100
1188
100
464
100
476
100
782
100
588
100
498
100
500
100
466
100
196
100
137
0
0
558
1020
126
1312
162
1022
100
1292
614
1372
626
3986
1371
1793
672
4336
1434
1352
558
3325
3907
9613
1616
4146
1497
3094
2083
3516
2314
3986
2199
13971
4216
2023
9305
14791
1275
9814
2998
2884
11053
14081
12888
13569
10301
18667
3265
2434
3058
1132
2773
4287
4831
3435
6029
2584
4001
771
3774
7210
1229
1392
1206
1633
11579
2413
1732
3194
2284
1202
4516
4877
9244
1392
3475
991
5969
1933
2399
711
2272
0
0
100
2369
100
4469
100
2277
100
3187
100
1564
100
4413
100
1701
100
5325
100
5593
100
3943
100
2770
100
2229
100
3004
100
1880
100
1745
100
3623
100
1871
100
2482
100
1928
100
3491
0
0
869
100
2701
100
449
100
387
100
335
100
684
100
493
1046
537
312
1532
483
801
858
866
452
573
858
2640
1451
784
452
1751
1591
1283
327
2717
3245
2121
1607
482
2262
899
3510
2281
2933
2355
1982
2358
1155
590
2574
2223
702
2801
1794
1285
359
1480
4461
739
3729
2165
1981
2403
1263
1387
561
3572
530
1098
1435
1109
1139
435
1544
1145
1139
0
0
714
456
1662
2641
934
693
741
1134
805
1888
457
1582
2663
1324
770
1682
889
2717
1051
4575
4910
3193
1848
3422
4473
6619
1701
5760
7332
27258
1460
12226
8645
12080
2325
1102
3241
1738
819
5823
1444
2161
840
1232
3402
15727
4901
1386
13896
1520
1029
1319
717
3740
8713
1636
5154
2041
1096
2487
648
2634
2004
1668
856
3891
1004
4257
2264
3333
1904
922
763
770
2567
1901
1185
1526
3129
1931
3866
1000
3363
2713
1050
2145
1895
1553
1945
2308
2771
2173
1006
3694
1004
521
794
856
744
1208
888
488
731
2464
1724
1543
1926
952
8780
1566
1535
0
0
100
1219
100
161
100
369
100
390
100
709
100
108
100
330
100
220
100
384
100
100
100
100
100
330
100
116
100
875
100
363
100
331
100
2091
100
604
100
628
100
243
100
391
100
221
100
189
100
100
100
100
100
100
100
100
100
659
100
100
100
100
100
494
100
342
100
314
100
207
0
0
875
2837
2217
4983
8307
15628
1482
15162
5151
22682
1675
12377
1227
6336
1584
3477
826
17740
2533
7812
2923
8488
5935
13529
11889
20253
1939
22343
5033
5188
4239
2564
8546
2285
1423
6528
7806
1978
8567
1766
7232
2819
20790
25118
10279
6293
841
6400
982
2580
1147
1445
1863
2879
5381
2203
790
1932
1688
5253
4534
1918
754
2641
1391
4571
8456
1873
5237
1654
1259
3050
3468
1505
3551
1480
700
1832
2929
1912
1400
1417
713
1480
790
1373
2722
1389
916
2019
1218
1184
520
1279
1422
2068
1080
1409
586
1176
1405
1189
655
1849
559
1533
1504
1590
787
1885
1932
1409
2800
1554
0
0
17127
3999
132180
16412
39581
22967
39144
10795
3620
3358
17509
13111
8892
16140
51984
10725
18020
16187
43304
14306
20657
7510
18947
23528
67776
30545
52391
69063
14859
24659
17314
56099
29646
27536
27112
97436
33808
24386
44117
53868
29987
35976
48592
45291
29192
6740
6574
69589
23065
28094
32744
137836
20479
30847
6780
32005
9901
0
0
100
124
513
100
375
171
1057
100
499
100
159
327
100
608
100
390
100
718
100
1248
843
1326
641
390
1402
2278
617
1575
100
1622
1637
1669
985
1778
1103
453
1157
1528
2930
2262
8522
936
1142
2106
3599
3136
2232
2621
845
1185
1418
577
1860
1466
1068
0
0
100
448
100
505
100
429
100
328
3344
834
3000
1649
4781
370
2859
1309
2860
997
2938
585
2735
1075
2890
2699
2796
1078
100
376
0
0
701
2163
1943
1371
1693
4408
1262
5379
1352
1971
1603
3810
2874
2650
731
2004
731
2131
9393
7121
1262
3920
3355
10520
8352
5285
1812
155
4647
2619
1662
3218
11396
9928
6770
4510
962
16917
6940
3770
7662
7002
11536
2599
7991
8135
6069
4022
1933
5783
2103
6692
5558
5458
3044
17992
10706
3553
10135
19827
1612
0
0
1581
11078
1793
6906
1509
10203
2116
4062
4280
1938
1268
3312
1980
9375
3229
1750
2412
1219
1747
1484
1394
1625
1376
4906
4807
4703
10865
8077
4616
17593
1881
2516
2224
1922
3291
5531
2183
2250
2769
2484
1744
9390
3485
6593
3105
2453
1394
18078
1982
3594
2088
6172
1468
4125
1493
5938
3369
1922
6660
1281
3648
1579
2290
10172
1626
4859
0
0
827
432
593
100
1748
1616
1311
1299
1076
2053
1077
749
1451
689
2121
1262
1956
2000
0
0
1306
100
854
100
1430
100
750
100
1564
100
1086
100
1108
100
6689
100
2321
100
2583
100
798
100
1928
100
3363
100
891
100
2760
100
1690
100
2078
100
15640
100
5536
100
8150
100
4980
100
1625
100
1658
100
2050
100
3322
100
4319
100
1010
100
6071
100
5889
100
3539
100
2144
100
1611
100
4729
100
2519
100
1748
100
1522
100
3528
100
5167
100
1658
100
2155
100
2233
100
5450
100
3054
100
974
100
1681
100
3900
100
1396
100
3265
100
0
0
895
814
773
3019
1095
1010
1341
2091
1562
1432
2315
11951
7983
1699
1666
2515
4399
1361
2838
3680
2132
10207
5642
2826
8321
2565
4617
5258
4508
1143
9612
5498
11752
3326
2378
11756
2459
6209
2751
3895
16390
1264
3562
6080
0
0
646
740
499
890
730
370
644
1830
837
520
744
3610
559
1830
777
680
849
3110
584
4630
1462
7140
1211
1770
569
2110
863
1370
722
5400
7002
2230
290
3060
2775
8200
1222
100
552
890
735
3700
1934
5310
698
5280
918
9080
1245
2450
6011
2400
7291
7380
1973
7990
949
780
1112
2580
828
5260
1492
1210
513
6130
3641
3840
5520
4330
13094
5750
7089
2980
3282
100
1165
6740
5090
6520
2124
6060
3985
7010
1560
12900
1043
4140
2459
2430
4531
3260
5317
3710
9194
1970
2050
3740
0
0
941
5071
1114
1433
754
4001
2783
1490
1692
1925
790
1822
3050
1749
1451
3315
968
3341
1551
7504
4088
11414
2155
2843
1419
11145
2029
7708
23390
8582
19489
4223
3701
19497
16627
11775
2742
7615
7630
13869
10605
14403
14678
26332
40067
9443
12939
5111
7297
15115
15334
12758
26883
13326
5773
7893
13778
19391
4542
9330
3723
4109
11041
25590
17962
14821
1472
19412
10389
16273
13543
22717
20158
21361
5385
8985
0
0
100
738
172
935
188
976
266
697
203
787
156
680
141
2513
125
2860
312
1998
657
742
140
2032
250
7787
3203
1602
3188
2091
4125
4926
12453
1827
3328
10020
2922
7062
3453
13182
3531
7778
3234
2021
2594
2266
4500
2180
2656
1400
2875
2005
8797
2844
11844
1714
100
1000
1875
3023
1734
998
8906
1861
1516
2974
100
3208
1969
1575
3172
1495
4016
2146
985
3429
2094
1250
2204
1559
5391
648
100
1067
0
0
1324
1230
1603
4410
2948
0
0
100
452
1016
3026
1416
484
321
583
517
1123
100
1341
1882
1872
1562
517
1316
1201
1400
1903
1500
1731
1869
2605
3630
1326
669
2730
1419
3214
3068
1732
100
4325
2199
1529
3431
1762
684
1326
832
686
4951
905
2955
1607
100
2013
1486
843
1016
1232
285
1622
2814
2418
1068
983
1163
1356
1184
1154
3255
1170
1400
1748
100
1435
100
822
100
1228
1300
982
654
281
1799
100
612
100
1296
100
139
100
154
343
386
100
291
843
500
100
944
100
279
100
575
109
0
0
150
100
503
100
1402
100
880
100
190
100
352
304
1039
405
100
445
695
1714
570
954
456
1088
150
444
100
1487
2527
1577
695
1835
3165
1662
1475
100
1016
1326
1599
3904
1797
1035
523
589
1824
638
3810
2863
4065
5274
7190
4534
100
2341
1258
2565
1123
722
1273
1495
820
4316
1294
1094
789
1463
967
2143
805
1488
2040
903
1224
1636
1116
1535
0
0
100
434
100
610
100
434
100
656
100
938
100
754
1531
1446
100
1506
1168
1141
2474
580
1818
2008
1647
570
1224
1010
2240
1234
1310
1919
2199
100
1896
1950
1584
3159
2115
1055
976
1713
3946
1056
1673
1123
3737
756
1740
739
1070
2875
2352
1268
1313
3874
2349
100
2314
1433
100
756
1142
1265
1215
384
1107
878
2834
1816
1198
1004
100
1897
100
1401
100
869
100
224
447
100
1295
100
1666
1103
100
994
894
521
164
430
300
497
100
100
100
326
100
163
100
835
100
803
100
100
100
100
100
100
100
100
100
100
239
554
100
469
100
201
100
344
100
725
100
422
100
178
188
1478
730
100
189
1144
100
0
0
1854
1826
862
3157
660
1381
6698
5058
5862
2642
1620
3320
1409
2871
2912
2468
2596
2924
2333
8086
2368
2893
15613
7284
7183
17457
2686
5493
15631
4975
10146
9513
1879
13972
2726
7609
39914
5194
2129
2532
19481
5300
8366
3212
1547
19372
13749
6012
2203
5615
5992
4476
7997
15904
16461
9411
11369
3784
5575
7365
3672
5788
10909
5452
39000
7258
1431
5036
5230
7006
6808
5321
3479
4279
3953
10586
1448
1912
2117
3800
1265
1632
0
0
1476
100
713
156
559
100
593
100
515
203
550
3250
1303
1422
851
1406
1935
1485
569
1329
801
2093
1101
4407
809
1656
1339
1906
840
1047
713
1172
3097
1281
2537
1078
1837
3421
841
3625
899
4672
3845
625
1126
1359
762
1156
757
407
3070
797
3455
1171
3709
3719
1474
171
1982
1828
2780
625
3879
547
1081
1906
910
100
1613
2125
865
3063
1455
250
807
1453
917
235
440
100
1150
125
0
0
1435
100
100
597
100
1263
100
565
100
563
2059
3197
905
3487
1139
1899
2121
1004
2902
2179
2059
2889
2823
2992
1997
5246
1404
1732
1201
958
100
4357
1077
2152
952
3907
2730
1526
2902
890
1747
1948
1622
1802
2465
3019
2137
688
1685
3413
6365
2370
1747
1229
100
1091
1123
596
234
1276
858
466
0
0
406
218
639
107
327
188
343
697
100
534
936
535
100
911
437
934
437
991
312
1369
5413
1938
608
1701
531
3786
998
4704
936
4119
515
1982
873
765
1436
1156
1966
707
405
613
406
944
1513
2697
1748
124
4539
1463
4290
3551
3323
1094
827
5468
5226
5361
749
1502
531
1155
2138
2297
3448
1966
4867
100
1747
112
1107
497
1451
140
702
1020
297
370
312
147
515
530
718
129
1232
113
0
0
1909
100
1224
100
1879
100
1593
100
2586
100
2209
100
1494
100
1915
100
2199
100
750
100
6372
100
1696
100
2083
100
1811
100
3038
100
30238
100
2032
100
16384
100
8342
100
15373
100
10233
100
3826
100
5198
100
3434
100
6916
100
1740
100
2913
100
2836
100
3912
100
5503
100
2340
100
5390
100
3930
100
1715
100
8145
100
7710
100
1858
100
11900
100
3801
100
2584
100
2235
100
3558
100
2375
100
1588
100
2292
100
2183
100
0
0
1709
8189
9889
4267
5264
4419
4793
10680
6129
6447
9576
5641
9486
15163
3184
9376
8905
4642
10311
10205
2634
29212
5252
28080
10245
4772
5330
7848
16645
25326
8164
9483
7317
34601
14395
34055
15199
9673
2844
4893
20540
15837
9044
0
0
1321
1261
737
980
1514
6263
1579
1960
918
2636
1386
1060
1134
993
873
2246
2256
1192
2673
1489
1012
1604
1813
1998
1777
2916
1115
4744
2358
1548
1183
3323
2685
2280
1469
14587
3042
2571
3661
9119
3136
11916
2155
1267
506
6670
4943
1501
5046
1714
1018
7359
10561
7965
10383
5653
2154
8358
5253
5413
3693
4918
5553
10211
9114
1927
1022
2137
2750
2394
2905
4907
2355
13787
1969
1106
2803
1703
1595
2624
918
2537
1458
1514
1847
738
5520
706
1314
1545
4711
1933
1200
1672
1339
0
0
2879
2559
2120
1222
4973
3820
2298
879
2895
1833
2296
1176
2538
2886
3411
1934
6164
1885
6080
3008
5711
2164
2324
2951
5306
1186
6201
6289
5767
4619
6980
1189
2649
1195
4618
12291
4054
1257
4256
1782
4948
2574
25877
9121
4299
2996
7675
1420
6092
6598
2580
3689
3591
16484
15101
1952
1971
1255
4291
39567
4731
4244
7352
13443
3382
8122
3822
1708
8543
17357
5251
7794
0
0
1752
693
2144
754
2072
726
509
1119
3296
641
2478
627
1876
755
1805
3464
4441
828
12436
791
2590
14308
6510
1905
5260
1411
15146
1915
2220
1351
4369
3301
12418
44627
39436
18989
18889
18015
2840
8674
2395
6400
21399
8103
6285
6835
6491
8224
7555
5495
7735
22911
31893
24484
2670
4529
7980
12865
14346
5545
2943
2397
2201
2519
6916
2145
4611
11131
19842
7038
4978
2565
1983
6059
1985
5374
927
8941
1864
1455
0
0
1524
1359
1041
1093
1413
1469
1280
719
5155
2969
3687
7422
1154
10641
3714
1141
1750
2375
3389
1282
2783
4062
4588
7656
5577
3250
3917
3406
1266
1265
3956
8531
8525
1265
5302
3406
7621
813
1840
1734
0
0
1334
1062
1642
1513
1440
2068
1217
519
1002
1497
1423
2479
1366
</