day20.go

package main

import (
	"container/ring"
	"fmt"
	"strconv"
	"strings"
)

func main() {
	// TODO: Optimize with double linked-list.
	fmt.Println(part1(input1)) // 3
	fmt.Println(part1(input2)) // 13883
	fmt.Println(part2(input1)) // 1623178306
	fmt.Println(part2(input2)) // 19185967576920
}

func part1(input string) int {
	return solver(input, 1, 1)
}

func part2(input string) int {
	return solver(input, 10, 811589153)
}

func solver(input string, mix int, decryptionKey int) int {
	type tuple struct {
		n int
		i int
	}

	data := parse(input)
	fmt.Println("size", len(data))
	m := make(map[int]tuple, len(data))

	for i, n := range data {
		m[i] = tuple{i: i, n: n}
	}

	for e := 0; e < mix; e++ {
		for i := 0; i < len(data); i++ {
			fmt.Println(e+1, i+1, "/", len(data))
			for j, t := range m {
				if t.i == i {
					//tmp := copyMap(m)
					//delete(tmp, j)

					// Shrink. Slow, create a map is faster.
					//for k := j + 1; k < len(m); k++ {
					//tmp[k-1] = tmp[k]
					//}
					//delete(tmp, len(m)-1)

					tmp := make(map[int]tuple, len(m)-1)
					for k := 0; k < len(m)-1; k++ {
						if k >= j {
							tmp[k] = m[k+1]
						} else {
							tmp[k] = m[k]
						}
					}

					next := j + t.n*decryptionKey
					if next < 0 {
						mul := next / len(tmp)
						mul *= -1
						mul += 1
						next += mul * len(tmp)
					}
					next %= len(tmp)

					// Expand. NOTE: This is slower than cloning a new map.
					//for k := len(tmp); k > next; k-- {
					//tmp[k] = tmp[k-1]
					//}
					// tmp[next] = t
					tmp2 := make(map[int]tuple, len(m))
					for k := 0; k < len(tmp); k++ {
						if k >= next {
							tmp2[k+1] = tmp[k]
						} else {
							tmp2[k] = tmp[k]
						}
					}
					tmp2[next] = t
					m = tmp2
					break
				}
			}
		}
	}

	r := ring.New(len(m))
	for i := 0; i < r.Len(); i++ {
		r.Value = m[i].n
		r = r.Next()
	}

	for ; r.Value.(int) != 0; r = r.Next() {
	}

	total := 0
	for i := 0; i < 3; i++ {
		r = r.Move(1_000)
		fmt.Println("val", i+1, r.Value.(int)*decryptionKey)
		total += r.Value.(int) * decryptionKey
	}

	return total
}

func parse(input string) []int {
	rows := strings.Split(input, "\n")
	res := make([]int, len(rows))
	for i, r := range rows {
		res[i] = toInt(r)
	}

	return res
}

func toInt(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return n
}

func copyMap[K comparable, V any](m map[K]V) map[K]V {
	c := make(map[K]V, len(m))
	for k, v := range m {
		c[k] = v
	}
	return c
}

var input1 = `1
2
-3
3
-2
0
4`
var input2 = `3711
-1434
1793
611
9745
6977
7163
8640
-3210
-6021
-3404
-6977
-5746
8756
5559
-9619
-1866
-9562
7336
-3121
-2412
-7053
-6967
-4095
7454
3949
1055
7965
1308
4022
359
-6990
1006
-8119
-7148
-5458
-6618
9992
-3646
1793
4309
-6088
6522
-5626
773
6529
-5447
7121
63
-7056
-4580
-5384
-7206
5015
-5324
2437
-931
-3531
-5958
-8531
0
9725
3551
9580
9777
4239
-3800
-3889
4798
1715
-1807
448
-3838
5468
3435
4854
9925
-2548
-4662
1641
1823
-3224
359
8642
-8134
8477
397
6050
-6056
-2329
247
2919
-8241
-8198
-7070
508
3345
-7737
-3458
-5900
-2956
9992
-3929
-1389
7747
5159
-9927
8393
5146
4737
-7176
8154
477
8966
-8203
-5948
-1525
-6351
4007
8372
-8985
388
6133
518
1267
9773
2714
4947
2161
1223
-5259
6322
-5186
3864
-5344
-2420
-1242
6960
-2377
8871
1518
-9880
3367
6834
-3829
7001
941
5185
3002
-3084
-7070
-4173
9754
900
6195
2130
-5964
-7878
-3
7151
5948
7665
7895
-9371
327
4869
152
-6958
-6296
8194
8123
7439
-2254
-16
-751
-6009
-3955
9470
-7791
4588
-5378
9495
2220
-1858
1527
1963
9943
-7271
-8554
4164
152
1492
-8801
-4645
2536
1122
9611
5725
9810
8110
3892
-1580
7627
1540
4122
-7754
-2150
9716
7127
9455
-6339
-5646
-2025
-2586
5523
2424
-6795
5478
242
9484
-1920
3024
9282
3932
-7070
-3920
-7596
227
4513
1143
2130
-2601
1074
-4291
5726
230
8708
3423
-8941
1027
-3335
2054
-1598
4935
9076
9098
-9976
-1600
-9612
-7150
9448
-3430
6262
-5112
-9738
8903
6967
3989
7919
-9361
-8157
2838
6866
9267
-4897
-8796
-6670
-2613
997
995
6519
-5600
-1548
8620
-3014
-1061
3967
192
583
-3798
-2890
-2239
6047
6233
-5972
1568
875
9710
1915
8620
7033
232
3833
-1292
-5711
-6597
-715
-4065
-8022
1581
-7646
3755
7937
1949
-4269
7803
-5900
-3000
-2908
8306
-5777
649
-6533
7804
-1301
-8806
4138
4022
2923
9501
3746
-1680
1029
-2401
8457
-3335
1826
9502
2492
-895
-8447
6751
-4796
-2519
-2649
5269
5864
-176
-5903
-9547
7806
-3982
9102
2374
-8895
5452
-5065
-6263
6123
4055
9971
-195
959
-2045
-3237
-9170
-7621
-1455
-7843
8085
5801
-646
7119
-1301
301
7729
3904
-4593
7799
4339
7264
611
2734
6154
3862
2713
-9613
-866
3188
9082
-2484
6786
-522
8062
-234
-7845
-9660
1297
5789
-2066
7857
-933
-2178
7206
-6504
4055
-4807
-8287
-8065
3043
-9367
-7066
2888
-547
-7988
3681
2135
-7083
-4887
9593
629
-9389
4778
-8152
4703
4526
5965
5523
-970
1699
-4042
-650
-8718
-2099
-2156
-4250
4823
-1267
1054
9660
-1510
9011
6465
-8139
-769
4040
3500
3360
-7299
3766
635
-7621
5493
8574
-7727
-4625
-2266
1380
7632
-4705
6430
8313
2205
4779
-9803
6928
9110
-6164
-6503
6285
-4434
-38
4934
-5710
7322
-8140
-5492
-1237
-8029
-281
274
6660
7603
-6250
-107
2023
553
-1339
6742
-9890
3069
8624
-8671
4634
506
-5903
7875
-8332
-8603
-9607
-433
-7442
-5899
-8164
4245
-811
-9127
-7596
-4576
-9453
-6504
-2406
7283
5984
7702
2991
-8341
-5793
-2952
-9463
867
1082
8990
4741
-6387
-67
3772
3932
2446
9514
4070
7338
-4634
-8774
579
-7621
-3342
9672
4092
-422
-6056
4502
-281
-2633
1616
7322
1641
-1866
2188
-9607
-4265
-3395
2112
7505
-3274
3926
5881
192
9355
-8975
-9799
5615
4961
5862
-8966
9161
-6568
7096
-9547
5168
4871
5105
7509
-405
8359
-61
5177
-9230
4772
-4277
8922
6834
-1224
-8463
-9651
7449
-3979
2919
5817
-168
-6770
-2367
2220
-2373
-1798
-6918
-2319
-9646
3677
3783
-824
-5958
991
9581
626
-5542
-168
-4514
8471
9315
-5256
8625
1951
8054
1467
-1692
7030
-9811
4351
-4503
-3983
3625
5593
9576
7627
-2095
4053
-458
-522
-1838
-6086
-7957
-3073
-7032
-2301
-1879
-8940
-3929
-5143
9198
5136
-3503
-221
569
3258
8969
5137
4466
1198
-1875
-7001
-8401
-9628
-4376
6368
6899
-6998
-6268
-5578
850
7758
-2836
-3617
5199
5857
-915
-4008
9964
-2042
-4576
702
4350
-7378
388
-5676
-2485
2237
-8245
-3345
3039
-9985
626
-6423
9599
-8799
1249
-9322
-6598
5068
-3124
-4186
1393
7608
-4406
-7980
-588
-6723
28
-6056
1908
-7477
-2009
-4253
8781
7499
4501
1728
5461
604
-735
9829
-2972
9601
-7072
6440
-9937
-3971
6880
2082
9716
6638
1172
14
5047
-7490
-9798
4022
6741
5366
-8177
4941
1765
9473
-8059
-9316
9990
-4018
-6433
-7806
-3095
-2871
3495
-7505
9062
-6506
4805
6931
9992
-5401
5894
5628
2473
1826
-257
-5631
1538
5608
-7503
6411
-9362
-3265
-6574
-4470
-7029
1915
-9432
-1257
1948
1131
-3303
5011
517
-6743
-599
-6787
-359
9250
-7051
993
5770
9742
-1802
2514
5247
8838
-3919
-5189
8633
1211
2514
-2848
415
7978
-8183
6431
4257
-3348
2552
4703
372
73
2872
9685
7138
-1985
479
8810
7952
-8495
2764
-945
3249
1141
-3655
-1048
1503
-5303
518
3755
-5365
-7401
-5034
7222
7108
1213
5847
-8774
7389
7066
3532
8243
-8940
-5596
-2759
-396
262
2765
6705
-1114
2942
8483
7333
639
8388
-2879
6452
-1414
3180
-9251
-8615
7207
323
5863
9321
8551
415
3285
9107
-2295
-4844
1194
3020
7871
6974
-3971
-1879
730
6215
5238
2375
-2887
-7060
3696
2288
7999
1008
-2604
-12
1572
-9604
-6650
4753
5562
-8574
6115
-5266
-3122
4575
6406
-9340
-3121
5
-7167
2984
5484
6640
-2095
-582
-1572
-3949
-3198
-2734
-678
-7252
-931
5301
357
9194
-3664
3194
1949
-409
3983
5376
691
7083
-4065
-3167
-1577
7589
6096
-2066
9945
423
-1591
7136
3371
-8023
8236
-2649
584
-9400
4925
3767
-330
5121
-7338
-4365
8840
6691
1018
1092
5364
7778
-690
-176
5411
5873
4854
-8838
-4143
-4521
-1137
-9568
3975
-2602
-7136
676
626
4196
5565
3024
1623
-1081
-8027
-8253
-8941
7800
4077
-4431
8085
2124
-2527
8478
4817
-6855
-5003
9819
-4330
5057
7358
915
-5578
9566
7048
1831
-3216
-9236
-4071
-7120
8054
9425
2345
1313
6317
7739
-8791
-7157
3937
2519
-4901
1980
644
2935
7185
4961
5301
9346
6224
-990
4575
-1129
-633
773
1058
7851
3763
1464
2571
-9677
-5903
-9733
-9637
-6130
-906
-7169
-7492
7623
5015
8791
-5596
997
1729
5803
-9880
-1827
-7477
-3695
-1855
-5844
951
-1308
-9072
-2121
851
889
-4721
-1702
-3080
3897
3588
4934
-9203
1391
1157
5174
8574
-5977
-5997
7825
-215
675
-5499
433
2487
-1054
-8648
6515
8334
6210
-9425
-7491
5792
1169
9664
-2879
-6345
-477
-6811
9285
-4518
-4570
-4393
-4295
-4784
-7331
-5499
7942
-8716
-8666
3618
-3329
-5269
5158
-3111
1364
5881
946
-5567
-4697
-3771
-4498
9075
6550
6940
4231
-6577
-3060
-2420
522
7435
190
6505
-3623
-7004
-781
-3727
-1146
5944
8825
-1895
-4140
9279
-3614
7233
7233
-4876
891
-9660
-7910
5322
-7419
-8810
-1475
5454
1586
-6445
-7575
-6967
-3111
-719
691
2533
-8488
8141
5978
-7069
-7577
-7817
-2433
-234
-5006
-4003
-2207
3983
-9447
5253
7489
-8276
6165
9979
-761
-1920
413
1216
7524
3485
5748
1027
-3944
9178
-7503
-5183
-5837
155
-2172
-5760
-1392
9780
8117
2990
-8109
-957
2716
9952
7231
-7349
-4267
-7922
4495
-4294
-3036
-287
-9228
7448
928
-7979
5085
-1548
4251
-2890
-2962
6705
1865
7988
3426
102
-3580
-7268
-4071
-9380
-2991
-1534
6295
-5009
-9790
3014
2060
4993
601
232
613
2734
-40
-2889
9221
4125
6276
2558
5630
2566
-1528
-4939
5724
2481
-1730
9748
-1866
3285
5422
-4484
6903
-6205
8041
954
-4355
-7368
47
4682
-1781
2929
-178
-6152
-4825
-1403
7060
8230
-657
5159
-2642
9824
-8739
7726
3024
1888
-4570
-654
8662
-5534
9430
-2901
4911
9268
6763
-8092
5680
6795
-6934
8951
2452
3868
6988
1226
9773
-2945
-1756
31
946
8195
3345
4145
-2351
5770
1478
7702
-2846
-8432
-5033
388
3749
4955
-811
-648
-2751
-6161
-6176
-4548
-3406
-810
9895
382
2810
-9821
-1580
-3165
9123
-8168
4994
-9169
-3531
6951
-8312
-3920
-8401
4685
-7347
-4143
-7456
-3073
-1941
-2991
4869
-6238
6053
-3146
5455
-6707
1663
-114
-7397
9291
1172
-8819
5199
6567
7041
7861
4052
-7495
2556
901
-4955
7329
-5239
8633
9411
5767
-777
1517
-5687
8028
-1506
1432
-8671
-9602
-9926
6289
2770
3899
-1985
-6435
1308
4040
1702
6436
9203
4439
4933
-5098
6578
-2578
-1598
-8105
1420
-4571
9726
6471
-3754
2803
-2198
-7789
4853
-9174
5407
9303
8929
-5515
5213
8664
1607
-2957
1508
5715
520
7462
-1092
-9948
2012
7736
83
-7140
9862
7104
-6979
-4954
-5495
2038
-7918
-4301
-6187
-8581
6051
-427
-5738
-578
-817
7352
7795
-8735
7438
-7993
-8979
-4552
4229
-8688
1793
-5668
1564
-3500
-6301
1308
5024
-8677
-4795
8150
-7918
-9138
-1180
9949
-8946
7380
9611
-7456
4467
7861
-6337
6298
704
-9424
-2188
7978
8708
-3897
-1362
-6442
791
-2555
-6936
-6423
7779
247
-3367
-7323
572
8727
5136
3959
6906
-7768
-7490
-5764
-3187
8153
-5600
8718
-2676
9779
3775
4165
-9733
2578
-5150
3895
-2995
-4395
-1078
-5606
-106
-7329
7919
-5115
-4576
-1007
-7252
-2660
-4746
8157
3002
3461
-2312
3932
-1453
1116
4999
-4006
-5515
-8769
8151
5342
-1580
-8360
7336
6060
-844
-6322
9271
-1793
3328
9739
-7769
-4358
8013
5338
-1836
-1932
-8203
2327
4772
5916
-6560
7310
-4777
-1817
-3026
-9075
-6937
-2349
-5038
7001
-2188
-8514
-8613
5247
-6890
-6351
-3838
3862
959
8729
1297
-1434
3892
2047
4772
-7940
-2907
8729
-3819
-8460
-4148
-4066
-2949
5188
9412
-2941
-6577
6215
-3020
4706
1032
-2383
-2734
-5579
2679
8955
-3422
-2527
7233
785
-8288
4941
-7461
-7259
456
-8232
-8613
-6083
1704
-533
-234
7362
7963
-4624
9350
9198
946
-8642
4059
3193
5086
5931
8908
-7621
2815
-741
1908
8890
-7620
1459
6457
3098
5798
-346
9476
-3788
863
3556
-8979
-6777
9094
-8241
-4222
1875
1308
-9602
7322
2813
1263
9743
2222
-2897
186
9558
8959
4196
4176
-7421
7865
-3310
8362
-8613
-9418
-4799
4309
3833
-2002
8791
8850
9209
7499
-8241
227
-9930
4991
-6118
-7477
-715
6846
8163
-405
639
830
4358
5483
-8983
-9280
4070
-5828
8089
-5130
-8810
994
2356
-6221
-7004
4040
2643
639
-1866
-6144
8729
9640
2229
4235
-9832
3328
4302
-1901
8797
6283
8117
-6187
6379
-2329
3047
-5100
-7039
4432
-2977
8236
725
-3940
-7074
5675
-127
-8878
3756
-4256
-9781
-4558
1413
-1584
2923
3914
7147
7898
7352
4653
2716
-2646
9501
2693
306
6686
6662
275
1164
9551
4809
-1166
7722
-5783
-1873
-9438
4060
4964
8362
2887
-3940
4197
-7487
-3368
-6171
-5689
-6376
2061
-7964
-2173
-9072
-2135
-2431
2661
-8884
-3187
-3510
4696
9542
-2736
8965
361
5894
8633
8613
-8133
-2879
-7268
6414
472
4374
-1616
9391
-5978
8220
-7802
-3430
5602
-2340
6895
-2646
7340
107
132
1517
7864
2965
-1605
-110
-6702
-2420
-8328
-190
-6763
6352
8838
4350
6964
-2613
-5781
9831
1938
1488
1855
-2949
-5636
1622
-8554
-6176
2979
-653
5301
-2144
5602
-8316
-8354
-817
-3630
-7349
-5499
-5802
6500
6893
-1159
8479
-2002
9323
9266
-3913
3346
9689
1321
2558
-1544
7047
-1339
8322
-9569
-871
-3874
6131
3755
4839
528
-4204
752
-6077
7576
-1045
7089
3607
9492
7307
-313
-4180
-1160
-3207
-2103
-6985
959
-7866
-6754
4712
-1075
8241
9902
1436
3711
-2977
-3892
-797
-9172
-3459
-8232
5843
4467
3975
5879
4063
9368
-6155
-3247
6558
-135
-8502
-477
7083
-4005
-5114
-1755
-8152
5694
4325
3436
-3618
2813
958
-2412
-8794
-5081
6283
-9030
5614
-7782
-565
-8149
-8951
5175
5953
7645
-4826
-5308
6622
8943
-2938
3367
9211
6032
-4557
-3387
-907
-2430
4954
1793
5628
1082
802
3895
2580
-8234
8441
6922
8542
-3113
-8637
967
716
-7922
5300
8591
2166
7623
-6808
7972
-352
-2300
-9504
-7517
-5075
-9860
1211
4060
-6032
-3681
1622
-6721
-682
8062
-6863
-7887
-6064
628
3655
6701
-7062
-9087
277
7999
-7752
-1146
-5231
-1085
5949
-6936
-2145
8143
7645
-2950
487
1545
1869
644
8545
-7474
-2000
-6263
9780
-7036
-2411
-7168
1850
7438
7262
-7496
-220
-533
-479
5533
-608
9674
-9293
7025
-7095
-4817
-5576
9153
806
2449
6917
-6775
-660
-7557
2991
-4429
9016
-1180
6302
273
-4345
-3834
-1906
2112
-6212
4007
-4470
9113
-5014
2229
-2932
3556
4485
-7576
-5948
4590
2233
2863
-287
-4003
-755
-403
-6405
6060
8959
-4838
8542
451
-9672
-3945
-558
-7749
1601
-8366
-5948
-6254
39
9074
4744
-8902
7417
3622
-9992
-7554
4716
1656
5159
6357
-5841
6505
2423
-2698
-2158
-4620
6534
4974
-9850
7907
5801
-8139
9608
-7577
-4187
-5570
-8215
8954
8372
360
3959
2345
-3704
7468
-5020
5177
-7190
7524
-3550
-7623
6446
-6391
-6825
-8839
-5170
-7494
-9758
6238
7207
-3040
1029
-4408
9329
-5948
8426
5816
6906
6470
7767
-8469
7361
-1143
-5375
-8240
-3650
1527
4497
-5609
1908
-3535
-3217
3047
-220
-650
4181
3937
5420
4848
-898
1010
-7881
-6337
-2855
2566
1214
5965
1231
5314
8349
-5545
-9122
2664
9161
-391
-4283
4736
2276
3028
-5188
7980
-3036
-6295
5288
-4550
-8187
439
-2936
-4736
-7031
-4395
-2364
-7351
2375
7800
-915
4830
-6033
-7933
8608
-9429
1434
9930
-4902
2130
1909
1331
6352
5587
9930
-4736
-3318
2919
9074
-930
3941
-2698
-1403
-7737
4388
-8833
-3409
4270
-2209
4291
5736
-715
-9515
-2239
-7557
9492
-9353
9075
-3210
8271
-8173
9949
3625
9358
2261
-3718
-1929
-3618
1154
953
807
8908
-2107
7958
-3932
-3036
-1080
2979
-4214
3814
-7258
1499
5625
-6319
4924
3347
8243
-6647
-6224
-6703
520
43
-167
-2371
-8324
5110
-7776
-1231
-5208
-8637
6766
2868
1973
3711
3755
5001
-950
3745
-4733
423
2772
5879
7519
-6609
4934
436
-9374
-8251
-3960
-9546
3024
4938
8149
-5117
5633
-2145
-5386
5105
-5984
-1901
-5474
-8025
-2252
9515
8463
-1732
-2329
8890
1771
9328
-2055
-9811
-4256
-3665
1586
3478
7715
6890
-3399
-6469
370
4096
-2600
-1814
2251
-650
-1233
-1161
-1129
4697
8631
-5222
-9094
-542
8372
-780
2145
3780
1711
1572
5047
8128
6623
-6337
-5834
-3732
5350
3711
-4193
-3368
-9222
1569
-4442
-1435
3301
-729
-3080
2619
-8748
-3332
5711
-3320
2666
4597
-6284
-1093
7417
1752
-2594
8567
-1120
-6944
-2017
9082
2923
-5826
-9911
-5378
-9792
6069
5466
-1965
3114
-8119
-6646
5417
-7994
8123
-673
-9587
3543
2589
-7870
-9234
3017
-8353
2334
-1901
3077
534
8141
-1182
9574
-7204
6395
-7045
6195
-6989
-7672
6003
-4186
5582
7821
-4574
-2207
1622
8871
9524
-8405
4542
-6345
242
-714
9107
8268
-5949
4461
6246
9919
7915
-8774
6125
-5086
538
-5576
4871
6860
5448
-2441
2580
6271
4956
1752
914
-5674
-8769
-2380
-4071
-904
-6494
6389
6803
2734
-4498
-3465
-5033
-8775
-8762
6997
4167
-4373
-4576
8162
-3335
2820
8131
5433
-3523
-7007
6838
-6322
2629
4871
410
-7183
-4704
7533
7811
2846
-8900
-100
256
1195
-2941
-5500
-2464
-7054
6763
2242
-7181
7498
4579
4057
-1755
598
-9175
8969
-6861
2390
3025
9110
7125
-6981
188
1540
-9285
5767
-2449
5322
6931
-6169
-9993
4197
-3137
1023
9198
541
-7206
-3881
-8590
-3920
-7195
2936
5571
7357
-2762
4133
6666
-5533
-1348
2196
-7205
6516
9091
4284
-2301
-1703
4531
9663
-5671
8875
5557
-8853
3010
7194
8495
4059
7608
6860
-3618
-4817
-4746
-587
-3859
4325
-7401
-6954
-4521
-4434
-6104
-9332
-8786
4645
-3046
4657
-8469
-1029
-9524
9618
-7342
-4630
6788
-3654
1217
-1508
7795
-1538
-8312
-1120
1998
-592
2437
6283
-7983
-8975
-3036
-9966
5230
2846
7489
3209
7409
-1146
409
2155
-6112
2449
7149
1329
-2107
-2566
-8379
4055
-8095
-8501
1973
6311
3401
9205
-4526
5131
-3571
5166
-2343
3995
473
-2761
-650
-8800
-518
8478
4057
3589
-8341
-3516
-2857
-4299
-4453
-8707
7126
7871
8617
6951
1616
9419
-2936
-2830
5247
8246
3068
-8857
619
-4148
-1671
-7225
2728
1634
-3571
3932
537
7664
-2909
-3800
5159
860
-3512
-3920
-2465
-9509
-5113
3904
-4578
-9127
-1728
-4723
-9168
9581
5131
-1941
6446
-4217
9664
7469
-8232
-3020
9123
-8645
-3945
9171
-5911
9486
-2439
9507
2043
-7798
-7075
-1423
9277
2166
-9687
-1633
9328
-9408
-8369
433
7104
-2938
1559
4031
-4198
5979
-4133
4741
-1551
1353
-1862
-5933
7182
-1165
-8022
5769
6813
-8025
-4434
2395
5146
5198
-9599
8893
8262
-7215
-6913
-1340
-6440
2398
-1200
7524
-2312
-5765
6544
-8288
991
4830
3163
1003
6134
-5392
-1357
-7066
3893
-1895
-3339
7736
8626
5853
-6612
7338
8162
6818
-8803
-4281
-5225
-7338
-3502
9162
-9241
9953
5131
-2890
952
-1807
1283
4598
4712
3783
-7005
8959
-4733
-9182
-5578
-3762
9551
-7893
7450
6625
-6646
1973
3947
-7119
2519
-6703
2229
-5364
50
8851
8939
-8783
-2290
643
6226
-5118
7454
-1339
8708
155
5362
8047
-8460
3824
368
-6965
8867
-1307
4278
1081
-5529
7592
6414
-1746
-6641
-8615
9526
7850
2975
1214
-7266
1152
-8198
1709
-3617
1425
7628
-5134
7700
5482
5695
168
7188
5174
-4843
5255
518
2700
-6937
-2887
9321
-3650
-6854
4593
9
5152
480
3703
-1715
6795
-9719
-4287
7937
-2294
1323
-2890
7589
4845
4125
-6913
-2356
-6927
4040
7067
-1616
4991
-6537
-1280
7839
6563
-5760
-1766
6457
-7474
5439
-6071
-2705
-7253
-4164
-2500
403
-5848
-3856
-9992
-7626
-6402
5723
1284
-4348
-2114
-6032
-3
-5416
4169
-662
1468
4693
7841
-2769
-6751
4374
7389
1883
6340
6810
8289
3285
-8211
-167
1796
9945
-9524
-9017
-4255
7264
3503
-1526
2928
8875
-6763
-4083
5863
8834
5621
8255
-2158
-7769
-3717
4901
1538
-1434
8472
-5598
-1261
5675
-754
-931
-1901
-7157
6669
-3863
-1438
-664
-6124
598
-9003
6166
-3982
-8594
-2845
5794
5777
-7119
-1588
5767
-4003
1531
7322
-3597
-9055
-2693
-2058
-167
1659
4994
-6157
3135
8650
6220
-3913
-6056
5259
7231
-6255
5338
5187
8141
-120
6504
-5344
2047
-3320
-8460
3601
3146
4270
-8320
-1281
-811
9000
3214
8782
3501
-2271
6033
4988
8709
6515
5789
2338
2152
8514
-3982
1118
7722
3914
-3758
1761
1284
5219
-5122
-1838
469
8922
-573
-1176
1604
1898
-6004
7937
946
-4073
-1269
7336
614
-2682
-7762
5772
8469
-8060
-9560
3525
-8267
-2290
6290
3168
-1866
7087
-1598
-9598
691
3209
-7582
2480
-2957
4883
-6918
7976
-4909
1254
5553
7045
3859
1722
-6531
3812
-7621
4079
8469
-3634
2473
5227
7107
1860
2645
-2438
-9280
7479
-7211
4265
-4160
-2786
-4710
-6715
1223
-8126
4131
-1813
-3427
2127
670
-8035
-239
-4981
-5324
-6034
5878
373
-7190
626
-22
-787
5019
6240
-9743
2713
67
-3618
-7955
3247
1761
4961
-2816
2651
-6263
6573
-3003
-2916
7722
-1671
-795
7744
6905
-6131
5301
5010
9177
-9865
-4300
4031
3464
-6336
-3719
3608
5159
-6726
2249
-3830
469
-6086
7014
4604
-580
5963
5712
7170
4087
-4010
7126
-8848
-6064
-301
-5902
4778
9222
-3073
8966
3755
-2718
9517
3371
-6361
-5823
-5505
9916
4070
-4737
1531
-8308
-3571
-1358
2647
-1724
8741
-6100
-4690
377
-7146
-7534
-8811
5259
-8401
6380
-6185
-6360
3433
-5500
8430
5094
-2528
8430
-3570
-4707
-8325
-6003
-1397
-728
-3897
-6658
-2092
-327
-1984
8470
-443
-1634
2753
-4145
-7519
4234
-9899
4187
1908
7894
2533
-1176
2425
537
-5595
4060
-5490
1143
3745
-4360
-3688
3401
6889
-2419
5531
-547
-7342
2923
5768
1376
4218
2311
8533
1376
-9373
1908
4308
-5868
-7164
6257
3724
7865
4513
663
1356
8542
4370
9277
2944
8922
-8175
6229
7956
-3329
990
-5721
6544
-5600
-6034
-7294
6685
9139
2896
1058
3946
8867
5602
-2971
-2559
1826
-3284
-1634
7801
935
-4849
-433
8277
-6979
-4969
-6671
-6856
-494
-1580
-1650
-4152
-8479
1603
-7935
2611
-1722
-5828
-7620
-8946
-8503
5102
4924
-1696
1304
965
-7001
-7626
-481
-2692
9266
-8157
7627
-1428
8470
-4699
-2025
-7671
9161
-8223
9787
5455
5406
6469
-9623
397
1392
3235
-9334
1526
-7079
-8386
-7554
-8552
-4066
-4173
6491
-2830
-7169
-9470
5241
1320
4475
1549
3663
7499
285
-3187
5950
7880
5425
6290
-5341
-2294
-2211
6874
1496
-3550
-8098
-1497
-4825
244
6046
-8990
5748
-2577
2047
-2367
-4738
-3859
9728
-6940
4934
6976
-613
-3787
5448
5151
1577
-610
1887
1141
-7215
9350
-6039
233
-4032
752
-6626
-7298
8154
5046
-3435
410
-205
8084
1482
-567
-5146
2195
-1616
-9568
-1932
8123
-2577
6457
-5534
-9613
1807
7327
8326
-9821
-3317
4474
6903
5858
7628
2451
-9216
4054
-8360
3285
-9167
6677
6616
2388
-9814
1792
-2698
1066
3631
-9798
-1029
-4472
9146
-3913
9184
-1012
-329
-5072
6397
-6086
9384
-9429
9668
-8345
9925
5668
-1072
1331
7795
2607
7207
-409
8709
1872
-474
8430
9382
4041
-2452
-1321
-3514
-4313
-8611
7966
3646
-475
519
9502
-7020
2859
-5680
-5534
4422
9234
806
-1340
4359
2797
-7003
-7446
-5524
-6757
-5527
-2845
-6225
-7372
-2706
3600
6084
-6990
7162
-6463
5947
-6839
9393
3123
7712
-9115
-1123
5136
-9797
-3232
-2011
7475
1883
472
9346
-5920
-2689
4245
5487
-7532
-2104
4363
-4576
5725
-38
9919
-3170
3167
3813
-8637
2863
-4169
2344
-6671
-7458
7944
-6070
5953
-3387
6412
5411
-2163
7001
8345
-8359
9917
3030
8362
-3503
-8662
3443
-1110
977
8875
-2534
-1029
-5655
-8343
5298
-6490
3532
1726
-4936
-7225
-933
-5982
9410
-7010
-2295
-1328
-7150
-5851
1957
-5305
-8407
-4053
3030
9112
-4985
951
3980
-5868
769
6853
-5005
-1887
-1368
1354
8595
-3544
-9491
2620
-1363
6029
-1077
2868
1792
608
2222
-1566
-2250
4991
-6997
9627
-2085
4162
1635
6411
2075
5777
3755
-2957
-5324
-7051
5803
1297
-8539
-6268
2393
3618
-9088
2543
1614
3179
-2580
6889
-6258
-6816
1031
-7401
4166
791
5658
9780
-8274
2010
7739
4559
7438
-7629
-8302
5158
-2480
-8152
7406
102
7185
-2453
-8276
7848
1988
-6575
-5983
7999
2776
635
-931
5980
-7074
-4219
-9930
-485
-3434
-4939
7942
-1771
4142
-5492
2229
7903
5777
705
-3096
2628
-6433
9
8781
6347
-4818
-1714
-4477
5203
-5401
-4347
-4119
4712
1194
-144
-4588
-8469
-7993
-7413
-3052
4991
-5887
-5397
-1563
-5308
-3198
-8715
7937
-9481
5878
4399
1887
-5114
-9811
-2145
-8784
-6393
-2971
1095
-7974
-9086
-7544
-6573
787
5910
6660
-365
8141
114
7389
-4337
3525
-2689
4379
-2871
-8268
8735
6919
7549
-7761
5087
2668
-4217
-8774
-8409
6745
1449
1662
-7558
-8671
-9414
-3750
-561
-1241
4689
7931
-4065
5166
-3274
6673
8352
-4688
7915
-3184
-4741
9572
-5050
-5034
3532
-2673
3883
-7511
-7190
-60
-8766
7163
3898
6651
-555
1726
-9646
-811
-5002
-2815
1622
-2620
-2368
-9447
8756
-9952
-5853
8528
3145
-5680
-6095
-5515
941
7245
4929
-239
-5846
6410
476
1936
8842
4469
-3571
-7265
8626
-3483
6123
1908
4479
7106
1196
3887
-2431
-6787
-4408
9476
4022
4294
5842
-474
1100
6951
-9156
-4066
2251
-6005
5668
4060
348
5166
-9081
3653
-3142
-4817
1188
-9529
-3042
-9710
2676
-4186
8583
5716
-12
-143
8139
751
5495
2224
8704
-5143
-7357
4585
8390
-7962
7310
-6057
-2890
-8650
3975
-3913
-7553
-6829
1055
629
-8611
8704
2935
7627
-9636
8237
4830
7730
-7655
3693
744
-6423
1973
-4760
-3551
6505
-9297
-7125
8391
-2273
9608
-3999
-6216
6055
8592
-1582
-8419
8289
2493
-9850
-2918
-6064
-9897
-7001
-6319
-5396
495
9351
9646
3328
-9086
-3388
6552
-7472
-9380
-2095
1908
-15
9725
9769
-4410
-8460
7601
4976
1524
-4765
806
6520
-8086
-4407
-892
-1562
-8212
8102
-234
6233
-1020
5582
4988
-6551
-1241
9351
-5714
-5747
-7899
-9870
-2890
-3913
2511
7825
-1465
-5458
7473
4096
-4430
-4939
476
7030
-2994
-8146
-7263
661
1232
-2233
-6533
97
7162
4189
-135
-5844
5187
1278
-963
-9151
-1673
-5986
2161
6311
-8801
9912
9777
9154
-9145
2647
7626
8937
1228
-8757
-5173
-7789
-9764
1054
2556
7067
9098
-3105
9155
-7274
-9837
4657
-2534
3569
-8219
7542
5177
5297
9
-3614
-215
-5086
1871
962
4432
2925
4003
-1554
8430
5935
-2406
1796
-2107
-8534
8139
1049
1320
8646
-6546
-437
-9202
-433
9581
3458
-7286
-9449
-9657
2075
3302
5266
7683
4946
8426
1947
360
-6902
6245
-866
-1621
-2173
8955
8710
314
-708
-5663
-6808
9355
-68
2935
-1510
8228
7839
-7523
3423
-8753
8567
5802
-6835
769
2358
9338
5767
3977
2902
-5747
7700
7081
-29
-5149
-3788
-9280
-3283
3759
1970
-7950
-6991
3768
-4724
-7381
-5308
5825
-6835
-2815
-2030
423
2965
-7233
3751
6165
-2705
8908
9410
101
-4065
3175
7406
4580
1003
1225
914
-1582
628
-4472
-4724
3553
-573
6519
-1624
1698
-2144
-2145
-3654
-1112
8042
3814
7047
2061
-8355
-7476
5177
1823
-8537
-6779
2619
-7861
8423
5891
4934
7204
4092
-3393
8747
-3929
-9623
7446
8513
6929
-4579
-1702
-1920
-12
-5849
-459
-7169
-5275
-4636
1706
-9933
-2960
3171
-775
8709
-6770
8710
1223
-1340
4201
5
569
5769
2578
-6729
-2294
-4822
410
-9339
-7782
4289
6685
6810
-6170
5866
-577
3689
-7195
-1000
-8000
8157
5716
168
830
-1232
4460
7608
-6435
-6784
1686
7150
-4131
5333
-4720
3959
9200
7104
-2494
-4581
6774
-6573
5625
-7150
-6763
-9054
1119
534
3436
-5378
469
883
5733
4060
9775
-546
-5342
-3241
-6049
3551
613
-3809
9220
9641
3302
7151
5485
7589
-1614
7608
9161
-776
1159
-898
-2281
-9803
6657
-2738
-9169
9559
-9988
-8287
-2465
-6784
4699
-2248
9748
9285
7934
-1879
951
-6856
-6395
5238
9321
1907
2224
7492
6763
-3537
4542
-3745
2845
795
8610
-6154
-2281
6673
-5500
-8564
1464
9495
-6511
4007
-8979
7972
-3088
-4897
2649
-5127
4395
-5982
-5977
8188
-1231
8271
-7132
7672
6311
9110
1601
9709
-4707
-4006
-3198
8426
-437
5109
-7887
8085
9072
-1263
-1442
-9811
6380
-3528
-9507
9884
2764
-3473
-1566
1908
941
3985
4703
4803
2484
-7762
-2736
-5747
-2480
3963
-4081
-7381
-7367
6805
2246
-3010
6502
-327
5263
-4033
9856
6298
1000
-7181
6709
-4583
-3584
-9489
8991
4118
8583
5733
5599
-9838
7618
2313
1813
-9951
-9479
-1321
-7598
-62
627
3480
1482
7999
-3747
-144
-786
7262
8504
7449
3339
-374
-1770
-680
-722
-910
-4837
-3611
-9607
-3482
487
802
80
-930
5868
-5337
9476
5802
2038
1908
9911
-4279
-1844
5455
-2526
-251
-4003
5528
-7980
4138
7806
-3170
-8211
6040
-4919
-8188
-8887
-5141
-8314
4735
-530
-6726
-9667
8545
-2938
-896
7339
7149
-9895
1032
-3531
629
6338
6242
6686
-547
-8140
3389
6257
-1592
2880
-8616
-7776
9782
-3096
-2782
-591
-141
-2319
2643
-4291
6268
-930
-8837
2633
-7724
6508
3380
9037
1058
5999
-3332
-3600
595
-1582
2278
-7792
-1286
-7070
-6626
3242
7627
-8094
-6461
2143
2943
-6940
-8144
-4895
-9651
1092
-5428
9241
8066
-5982
7136
-775
2327
9695
-5762
-4360
-1920
-2490
-9470
-2195
8062
7295
-372
5405
-7791
-2780
7207
121
-239
-4231
6238
-3224
-3968
-5143
-4095
-3286
9273
-4470
-8594
-7749
-5780
4032
-6339
-5143
8210
-4990
1081
399
5863
8150
8608
9171
9506
875
1074
8483
-6503
-437
292
-6444
-6610
5314
8228
7464
4752
5686
-7086
4661
-220
-1814
7483
-6797
-9674
-9325
-7157
8430
-6296
9172
2451
-9236
-8870
3809
-3494
-735
-4751
7119
7438
-6212
-871
7069
-5384
-2793
4954
-7490
-4323
-8174
-3823
2321
519
-2038
9470
-2941
-7074
3711
-8241
-7258
8782
-5081
-9083
4639
7489
-3732
-2181
-7835
-3341
6892
9551
8925
7295
6627
-1837
1055
-9241
-6009
4286
-4300
378
-8197
-8710
-9750
3949
3866
6834
-580
5241
-4842
3772
-2092
-533
-811
-8206
7739
6060
1677
2910
7435
23
-6320
-7394
8574
687
-4875
-8854
959
-2586
9601
-7146
-2762
4427
-7854
-7832
-4081
-9363
-9236
9177
-7276
-1722
952
8924
2639
1718
-93
5959
-786
9945
-5826
-5072
-659
7855
5622
9846
-5239
-8027
-2448
-8157
-495
1538
-4131
-5333
1869
7090
5832
-1673
6269
-4200
1353
-3005
-8393
8355
4075
-6743
-6274
8182
-4634
2222
1872
275
-3038
1292
4072
9271
-8496
9112
-5147
-5094
-1612
-5341
-8152
39
3195
-5501
-1730
-8789
-5308
-8719
7067
-2301
-1562
-1006
5338
-6030
6606
1788
-3425
4830
-9875
-1768
-8536
6050
-3149
-2359
4954
-2114
3963
8483
9831
-2682
-8462
7841
7867
-5677
-4377
-1422
-5122
-963
-9438
8089
-437
8220
-4649
6452
6173
9228
-8940
-4299
-5817
-3198
6337
3500
-4969
9140
255
-2446
8430
7293
2613
-7794
9691
-4005
-3919
-7951
-3466
8101
2032
-5441
-3461
1308
-6062
-3060
6327
-2367
-5094
7138
-6990
4311
-4164
3171
4171
-671
-5435
7043
9538
1129
-8941
-6074
-9688
537
-4430
-5736
-4552
3123
5628
9868
-9236
-3874
6055
7942
-4969
456
-8152
4749
-8110
7627
2154
-957
4164
-5518
5562
-7600
4555
-6871
-2872
-5113
3443
6616
-5458
4588
-3727
-9475
-5747
-1884
-4395
-6573
3709
-3342
-6778
-7442
5863
-2314
266
1416
9556
-372
1367
9685
7530
-469
7347
-7394
5818
9458
-3570
4845
-7970
-1256
-1392
2275
-1549
638
-5780
2260
-518
-3263
8545
2180
6446
-578
4028
3809
-4355
-4817
-1639
7996
9686
9349
-5350
3576
6887
-9882
-7678
-3043
-7461
-9222
-3719
2798
888
973
2590
-7413
-6795
1612
-5578
-4300
-8836
-9389
-7854
5060
350
2909
-522
3826
-8945
-8266
6101
8293
2705
9681
2296
1842
2751
-8481
4294
4476
5350
-5375
-9285
-7728
1627
8595
8104
4377
-4297
-6918
7004
1983
-7789
-2207
8214
4805
-4117
6897
-8960
9827
-4581
-6721
-8463
-9431
4651
5950
3700
-6331
8650
737
95
8727
-2251
-2681
575
8270
-3165
-8784
4432
-6903
3526
-2018
-6389
-4297
-2293
3704
7895
-7621
-1895
2073
-5006
-362
6357
6677
-5364
2845
285
96
-844
-1665
4701
691
-5141
5553
5726
-9912
8854
-4507
6931
691
-2204
-2635
7844
-2374
-4171
-4696
2484
2768
2789
-2207
-3890
5031
4536
5653
-1598
-5903
4333
9642
5884
1548
3553
-1502
-8632
-1177
7762
9907
-664
-6873
-7575
2248
-4472
-144
5562
-8300
4405
2388
-6690
-484
-5576
9349
7804
-3772
-7790
-8897
2352
3701
9413
85
-7309
6235
-2995
-6693
3039
2887
7319
3544
571
-2328
-8807
-106
-5515
9689
-6405
5553
-9
-1333
-5687
9927
-7997
-7310
8762
-5132
8741
-265
-2735
-5887
-2353
-3111
1104
1483
655
7575
3192
-8138
-6806
7207
9448
2508
-9599
2802
-8801
-8858
-278
199
6609
5675
5010
7510
-6521
-3929`