Story

To celebrate the 10th anniversary of AtCoder Inc., we plan to hold an anniversary party with users invited. At the party, CEO Takahashi will cut a giant cake with a knife in straight lines and distribute pieces to the attendees. There are many strawberries on the cake, and he wants to distribute a piece containing d strawberries to an attendee who has been participating in AtCoder's contests for d years. Please find a way to cut the cake which maximizes the number of pieces to be distributed under the specified upper limit on the number of cuts. Note that Takahashi will eat all the pieces that are not distributed, so any leftovers are allowed.

In the above example, by cutting the cake with seven strawberries in three straight lines, we obtain two pieces with one strawberry, one piece with two strawberries, and one piece with three strawberries.

Problem Statement

There is a circular cake with a radius of 10^4 centered at the origin and N strawberries on top of it. The center of the i-th strawberry is at the coordinates (x_i, y_i) and satisfies x_i^2+y_i^2<10^8. Takahashi can cut the cake in at most K straight lines (not segments), which may intersect each other. You should specify the line to be cut as a straight line passing through two different integer coordinates (p_x,p_y) and (q_x,q_y) satisfying -10^9\leq p_x,p_y,q_x,q_y\leq 10^9. The two specified points can be outside of the cake. Because he is clumsy, he cannot stop or curve a single cut in the middle of the cut.

For each d=1,2,\cdots,10, you are given the number a_d of attendees who have been participating in AtCoder's contests for d years. Let b_d be the number of pieces with d strawberries on them. Then we can distribute \sum_{d=1}^{10} \min(a_d,b_d) pieces to attendees. Here, the i-th strawberry belongs to a piece if and only if its center (x_i, y_i) is contained inside (excluding the circumference) of the piece. If a strawberry is cut in a straight line that passes through its center, it belongs to no pieces.

Scoring

Let b_d be the number of pieces with d strawberries on them. Then, you will get the following score.

\mathrm{round}\left(10^6 \frac{\sum_{d=1}^{10}\min(a_d,b_d)}{\sum_{d=1}^{10} a_d}\right)

If the number of cuts exceeds K or you specify an invalid line, it will be judged as WA .

There are 100 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.

Sample Input 1

2835 100
51 3 44 99 1 87 83 19 10 90
484 -7595
606 -4986
-70 3067
3481 -4705
-3464 -3044
1329 -4256
-3512 -5340
-2544 6126
3435 7021
-7712 -6197
-3097 569
7192 1127
-1048 1879
4813 -3083
-5549 6929
-442 2382
2945 3994
6014 -7099
7351 -3206
957 2312
4759 3636
5006 2830
1295 -3571
8639 4466
1737 1871
430 1351
-1131 -7028
-9734 -306
-2399 -1120
8091 -3904
7981 353
3857 3265
1904 -9009
8580 -2444
-8069 3327
2134 -1889
6814 -7227
-179 4070
-133 2159
8408 -3895
8310 -2805
-2613 8307
4909 -6786
-4757 -1665
-5655 -4694
3044 -833
1461 661
-854 6814
-3173 -1271
-3234 -220
-5572 325
-5581 -3338
2073 -5006
422 5252
-2123 -671
1847 8702
-5892 -5104
1619 3729
-9533 -1758
-3949 3323
-4690 6069
1307 3679
692 5468
2131 1579
8492 1546
-3285 4628
-8716 -1213
6372 7303
714 2324
5838 6861
-180 -2797
5641 6136
1976 -6215
-768 -1353
3284 -3719
-6839 -979
8686 -1972
-6309 -2519
7714 6148
-3269 -2754
-3864 6951
-1476 4044
-3462 -3473
285 -8593
1045 1832
-4038 -2488
7024 -2583
581 -6553
4012 -603
1743 2227
-5344 5418
-9502 2454
-2278 3759
-3898 7095
-6842 7212
5318 -168
-1041 -8572
-6728 4202
8340 4797
8947 -4407
-4883 7131
4883 -4575
8155 -3350
1337 -3654
2731 4752
8004 581
3637 -1668
3117 2523
6308 -5224
1031 -3502
7048 7078
-6094 2876
691 -7417
-3923 -7061
-9026 293
3689 4085
1127 5962
-5618 -6061
4512 1564
-3236 -416
-9460 -1675
-1781 -1921
1000 -6263
2347 -931
5882 -1002
4695 -7875
-4233 8852
5700 -2382
2714 -3241
833 -3597
-2848 7445
-4746 220
-7733 69
4069 4537
5890 -628
-4376 -506
3673 -5994
59 1952
-3549 -3144
6102 -4773
8469 1581
-119 -5423
3140 1067
-5032 -5506
2167 7041
8073 -1435
-374 -2695
7844 -5181
-7466 -1752
3583 8122
3894 1046
4404 8547
2572 5333
-604 2975
-6043 2805
6815 -4786
-5082 -6474
2265 5421
2611 -8621
1525 -7317
886 -7918
-3432 93
2259 -2986
8365 -5457
1268 7771
6070 7406
572 5620
-6655 7069
2267 3706
4556 7775
-5495 7411
5334 -7307
-5830 -387
-1892 9533
-1734 2547
8411 4917
-3810 -9224
1231 6809
-3521 4389
-6775 3016
-2915 -3517
-4003 -6182
7243 -4020
-4508 8789
-6377 5081
-8719 945
94 7427
-4343 8041
-444 2336
-921 6102
-5733 -8028
5068 -3973
8188 3444
6691 5820
-472 4302
-4325 2035
31 4050
1195 -1493
-4449 -3249
-7105 2594
100 -7939
-131 -6275
6447 -5086
8140 -2242
3221 -2699
-2133 -6591
7061 6651
864 -2899
113 -1002
1239 5103
-1473 -5647
1996 3502
-3456 -5403
-831 549
5292 -6128
-5918 -2771
-696 1730
3585 -4084
5533 4160
2593 -9621
-7496 -3938
1734 -6794
2902 3181
-2717 3180
-512 -7886
6223 -1167
-1286 3422
1801 -6794
3584 -4937
3525 -4695
2767 6928
-5305 -6483
8921 622
-5089 -6415
-5350 5347
9501 1920
9836 -1130
9322 -610
7368 1792
-8854 684
5263 634
9745 -2189
6505 -6709
368 2849
640 -3474
5569 6104
4445 3906
5034 -7551
6811 -3802
-5521 4781
2307 7752
-1732 -7612
-2209 -4026
1744 -9669
583 1510
3002 -3923
853 -4109
-8095 -5239
810 -3038
-2391 -1461
-1660 -2831
1435 -6926
-130 -7227
-8130 4368
1509 7772
-376 -158
7070 139
-5171 6804
9864 1591
4115 -7775
835 -9598
6096 2407
-7583 -3626
-5921 -5804
-1659 4965
-7193 -1156
3016 3731
4376 5446
-1108 2092
-3797 4911
-1452 -5699
3886 -7050
5482 5842
5026 2916
3987 -8923
6021 -7861
8050 -932
545 3371
-4028 -1019
6324 -3122
3355 -1963
-5626 -2598
-2071 -5233
-2592 550
-5070 2481
7228 2359
-105 124
4905 2229
-4811 4553
-4346 -7282
4672 5592
7698 3543
5413 -394
-3083 6660
-3342 5661
1644 -3381
-8694 4422
7176 1813
-1357 -4772
4888 -8283
5421 -139
-3194 -2871
-3594 8066
-714 1683
-460 2945
7877 1689
2061 -7126
-2069 -4295
-5083 6772
1759 -5464
2117 1121
-2916 231
8877 1459
-1068 174
4440 3887
673 -8471
44 -9313
-8919 -595
325 8643
-7507 6048
-8207 -2424
2045 -353
-2108 -1003
2316 2005
4795 -8111
1063 -3218
1007 -8575
-7056 900
4002 6028
8788 -3367
-4555 -4040
-784 -9781
2002 1661
3718 -7921
1003 -1914
4321 -4046
-38 8258
-4811 3576
-108 6798
2202 5751
2000 1885
-7163 1462
3707 -8395
-600 9201
5838 -757
-8035 -5000
-4188 7193
943 132
7533 3216
-5676 -2787
-1412 -5504
7094 3408
3168 5455
4378 -617
7105 -1537
-9907 876
5938 -1555
-6648 1451
5489 6309
9755 -2135
-4082 7369
-9156 -1877
-5755 -145
5332 -7101
5097 5930
-2044 2465
-3435 -8595
-7635 1214
-1148 -6573
-493 -8289
3125 -3779
1306 -7910
-5449 -1364
-7339 -116
-2634 5518
-4164 2102
-1674 997
4578 -530
2629 9096
-6624 -5881
6782 1720
2950 6478
7929 3591
-964 -2817
-5302 2261
-732 -2244
-7592 -6213
4974 -4631
7955 601
5650 5313
8606 -4090
-2211 335
-6181 -7186
-2798 8941
-7497 -4914
-1219 2425
358 5731
-5255 -376
-3120 -6978
2113 -6864
4033 -2347
229 6090
-3875 6737
-3936 2093
-2081 -4954
-9810 -1162
2811 2994
300 2430
-5611 992
-7621 -3362
-2504 1025
3141 7788
-5949 -2616
-2778 6223
-3849 -435
2325 -1444
-8120 2179
4142 -5562
-4028 7335
2800 6132
-6529 875
1675 -8211
-5876 6727
7974 4582
616 8127
4461 -4761
-1302 9500
-8472 4445
6569 2265
9472 -2322
1605 -1618
-2176 -2973
4690 8034
9103 -2571
4836 4983
-6922 -4820
7278 -6031
199 889
9316 -2252
4889 -8138
2662 -8199
5282 -1003
418 -8764
-1991 -6508
-6103 3370
1430 8525
6899 -219
2424 -5170
4990 -3250
-2620 -6879
4087 6718
-3944 8901
-1010 -457
3324 -2628
-9166 2361
-7209 4107
-1008 7907
360 234
3069 -9372
6667 -5651
-4814 -2494
-3839 6851
5569 -3517
-2216 -2802
8980 -2023
-3643 -8503
-1495 -9560
872 5001
-3605 4014
3011 3482
-8228 4275
9379 3275
4032 6124
-1126 4767
-8680 2441
2087 2805
5793 564
2199 -848
-9136 -1667
-271 932
-3110 3639
-5886 6986
2462 2555
-3256 3227
-1772 4640
2516 4615
2178 3478
-4454 4277
-2065 -2415
4750 -6829
836 -5043
-2385 -6092
-2239 -3159
3788 -7084
-6583 -1759
-6341 -216
-2348 3387
-1122 6448
3530 -1624
6538 6413
975 2432
6379 -5109
7457 786
8243 2713
6529 -384
-2269 7019
2284 8286
1292 -9642
-4422 7329
4057 -7640
6886 -3538
4899 -384
3930 -3952
3195 -3354
-3279 -7536
-1249 7291
3086 9235
-2276 -5436
8128 -3303
-7579 519
-3463 3673
-614 4788
-891 -5576
-4160 -4908
-8860 3853
-5419 6641
4832 8500
-2453 8702
1006 -566
-183 2979
8747 -362
8536 -928
-239 -2220
-963 8477
-3760 4470
3255 1859
2617 -5734
-6633 6312
709 2688
6885 2213
-6227 -6645
-9314 733
-2706 8666
-5530 -775
7451 -3906
-6711 1164
2815 6155
855 3136
9035 -1183
3192 8991
238 9937
-1460 665
9363 2694
9777 1016
1566 3836
7143 -6240
4529 885
-4321 3994
-7984 -3886
3041 6996
-1070 -4141
2962 3508
8250 2866
-7973 5079
6502 -6373
-6696 -6916
2863 5224
-6177 2508
8144 1257
-273 -8025
-7646 1944
6089 5771
7617 4969
-835 7359
5819 972
-3802 7047
4123 -4918
-763 -8312
5294 -3728
1856 5518
-6951 -5467
6121 -5432
-4717 -5808
-3146 1564
183 -2014
5286 -8053
7086 -474
927 8709
7845 -608
3320 2680
2204 9702
3737 229
-1220 -9656
2667 3760
5364 2181
-1635 6892
7366 -5144
53 -9139
-8113 -5138
-1229 -4723
-376 131
-1170 -4474
-39 1244
-292 3468
6274 7534
-4850 2808
-7196 -3589
3185 398
728 7785
1258 -5500
5418 530
-3137 7401
7281 -263
2188 -1139
-1212 7230
-2788 -8745
-7823 2964
-6019 -4153
7851 2416
-1076 2253
214 2872
-5341 -1441
5393 -3559
746 8539
7562 5189
4413 -5006
-4447 7342
3700 -7923
-5185 405
-4123 828
-4061 -5427
-2853 -4257
5643 -3314
344 -883
9323 -1809
-6078 2332
4867 3683
6738 -4060
-7009 2420
-714 -5753
3099 -6086
-334 -6916
-7344 -329
-2760 9053
8449 1850
-167 7914
-742 13
-8496 -4251
4337 -2838
-8154 -427
387 -9469
1514 9549
2645 7455
9075 3502
-3457 -4703
4549 239
5269 745
-6607 -3646
5348 4434
4113 7276
-5566 -2818
3268 -970
-3793 -9017
-4693 3379
669 -6980
-5126 3937
5684 -2072
-6899 -148
3303 -723
2095 -5814
5454 1695
3419 5011
6407 3121
-9184 659
5377 7655
5293 -3963
-4219 8493
7339 -196
-5978 7344
8175 -287
-5073 -5033
-25 3107
4451 -6970
-1638 -1575
-2899 2153
-6514 1704
-4607 1591
8050 2620
6905 6060
-1166 -3057
2281 -753
-2096 7699
2980 -1148
233 5773
2068 -1174
6828 -792
-1543 6580
-4174 -7457
-7619 3467
489 -7170
-717 -3783
5373 6745
4243 641
7252 1058
-9190 -2247
-9416 -2747
-256 2108
381 -6646
-3594 -3689
-6119 -3529
904 3678
-987 -423
-8049 -1600
-6563 -7365
-7070 2543
-1311 -121
2335 -6854
-5264 3730
-4111 4961
7850 -1080
2609 -355
-5430 -4820
-2753 8617
-2942 4833
-4665 5771
4165 -5936
8593 4660
-3821 -6953
885 9249
6968 4048
9058 -4163
3832 -5315
-4904 3924
7820 -1596
-5325 7876
2095 -1222
-5451 -5281
-6787 7166
-810 5632
-2362 -2732
7334 -5081
-5196 2932
1756 7350
6509 -6211
-8812 -1920
-3758 4749
550 -8188
7134 6771
-9185 2315
-2752 7063
4528 5234
-3660 -3865
-126 6998
-9359 2489
1392 -1669
3700 9166
-4600 1722
7767 5688
-236 1414
-1140 -702
-3991 8769
6046 -3424
-2874 -5375
2418 7255
7874 -3193
2340 -7983
-2063 -8609
-6487 -2292
2725 -9526
3570 31
-4742 8375
-7068 2022
-3699 -5016
-3216 -3452
-112 6561
3050 8853
-789 -9576
1214 -5325
-1613 4386
8769 481
-3017 8426
1641 9279
-7101 -885
548 -991
724 5566
437 4525
-5161 -1755
-7738 3089
-2341 -65
3694 9146
5329 7214
8011 -1192
-1471 5709
8411 -4039
-7746 6246
1066 5073
-7888 293
2129 -1790
1414 -928
-6684 -6359
736 1222
1778 -6163
-9047 -2717
33 -7801
6813 -4439
-728 4463
-1126 5000
-7346 -6649
4702 -1906
-3393 -3238
7403 -4067
7152 5618
-2326 -6443
-2589 -7946
-4088 1963
-2212 2157
-2284 7985
-5065 5756
6571 -1024
-4065 -2812
-4862 1197
-6001 -1852
6689 5216
-2684 -9147
-9263 3335
-4554 5736
3720 -9281
-638 8205
-919 -5529
4170 5639
-9064 1784
-8416 -2782
2783 9514
-7060 -2094
-2528 4690
1165 8694
-5356 -7124
1663 7960
-5159 -3901
-5785 -7071
-2282 -7660
-5248 2617
7061 245
5044 3711
-3980 -6733
8077 4265
-4876 7528
-6296 2260
8082 322
161 2565
-3090 -279
-832 1236
-6759 -2850
-1481 6192
-6794 5180
7676 -566
5197 19
2591 -3862
2814 -2401
-4791 -8448
5287 5396
6962 2907
990 -2071
-3106 1837
-7690 -6308
-4417 -7419
2187 4319
-4511 6640
-5036 -1853
-4214 -3625
-243 -2039
-3260 4052
-4249 -7880
-5772 4016
-1666 60
3861 -8436
175 1207
-79 -9170
3559 -1163
3897 -1019
-5816 -5037
-1006 -1898
5111 -5956
5386 -2797
7536 -3493
-1179 2496
1355 -9551
-3066 -628
-1104 3089
5113 8458
-45 4501
-1457 542
-7946 5972
-5072 2948
6986 455
-8776 -3642
-723 2210
8735 94
3861 3200
-9299 -2920
-3560 -6600
3087 2594
4460 -91
2697 -702
3202 444
-6940 -2553
-7396 6520
634 -5352
3384 2324
6879 -4031
-4905 3089
-4090 -7325
1289 -3075
5714 -1837
-4045 -6456
-3251 -7477
5849 4238
4007 -6023
-2725 7902
4859 -158
-836 3245
7493 -5732
-1801 -2714
-1373 2145
2406 6182
-9139 1573
-1927 4659
4391 2067
-1403 -6007
3820 -7500
420 -599
-2687 4037
4569 -2936
-6743 4411
-2400 -8641
-3187 -5160
-8355 1127
1511 3013
-4832 5092
2034 -8305
7676 -6331
3044 6097
-8506 3165
-5902 4866
-6586 -3067
8032 4877
7026 -6784
-434 -6267
-3665 -2800
-5584 -5490
2675 -5147
2224 -1397
2149 3969
1127 3856
-153 3052
167 5904
-6148 -613
-4330 1165
-1335 -9902
-6514 308
1374 7422
-2521 7145
-4982 2926
-543 8870
-6976 -4774
4653 853
358 743
1859 5359
673 -8793
-4687 -6302
-5685 5926
-243 6637
404 -3953
6491 -4797
-6909 -5574
2538 1814
-4375 858
1758 6459
1402 -1422
2649 -6403
5071 6157
4533 7909
5865 -2381
-145 1678
8026 -5245
6550 -5067
4550 6275
-292 1838
8332 -2926
3767 9206
1810 2678
5351 5474
-1709 3490
-8939 4367
-3402 2890
1593 1513
-9874 -980
88 -1181
3584 -7395
-3428 -128
4464 -2547
-5556 2363
-1868 3436
-5133 1777
-3404 1021
-701 -2378
-1907 1481
1950 -1838
-6392 3262
-1739 -1944
4100 -6298
-2627 -6276
-294 -9918
-6990 7094
-1222 5131
-5191 3759
-4551 -8292
19 -850
5804 6567
-8304 3356
1689 1018
3433 4181
286 1748
9554 1983
8849 -3758
-6142 -972
6573 4038
-6164 2982
8131 182
-6911 4313
-8489 4992
4292 -2608
2070 -3151
-3448 4750
-9007 2050
3253 -2829
169 -7595
-555 -8502
-535 2346
-1907 -7017
-8469 -1475
-4849 3442
3771 3030
-3706 -3809
-6743 -1980
7758 4982
5209 -4891
-5162 -246
-3362 -2016
-3174 -7718
-250 -1954
2306 4714
-2099 -3708
371 7107
6080 -831
-8328 964
-1356 -7576
-2518 -2449
3723 -5771
3457 -3306
-1862 -4778
6770 2399
-148 2929
-831 5408
-1891 -3868
1059 690
-6764 3945
71 8655
1747 8557
-3438 -205
-4651 5495
-7029 3032
-6803 2169
-3520 -4964
-7103 -5597
6333 1110
-3098 -4225
-585 -1455
1869 9720
-2119 -8311
-2752 4662
-8570 -5061
-100 -9291
2622 -7149
-8018 -4004
-4858 4135
3345 4796
8461 -1363
2313 -175
-6735 -4323
-3304 3097
-3294 3524
7315 -4856
-4187 4664
999 -6893
-7367 4128
-6215 506
8968 321
814 3818
5526 1753
-1499 -1394
8256 -2925
-6594 -5841
-2805 -8641
-9099 1455
-3140 4220
801 -3577
3129 8682
-7798 -218
9126 649
-1376 -6759
-4469 2968
193 7928
2070 -1155
-2962 7631
417 2022
-2853 -9167
-1709 2056
2325 1631
9795 -470
8726 1460
1821 -6338
8141 2131
988 -1199
-3451 -8162
-2490 -5863
-2472 -4812
-524 -1559
-6445 -1496
62 6267
-3139 8907
9531 3016
-52 5108
2982 5008
-1414 1309
-7989 -3823
-4591 4791
3109 3279
-1422 -1569
-8380 4135
-4847 -6601
-8894 3503
1099 2302
2454 -8811
6676 -7374
6615 1729
1374 -6715
-5234 -6672
5393 7881
6293 -6643
-919 -269
-8956 2651
-8916 -3417
-4991 4537
-3770 -1859
-6807 -5860
-4791 3298
4775 -4470
-4357 -6084
4067 -2144
-5821 4219
-452 -437
5061 -4903
-7749 -1487
-6017 1398
2015 -8881
4137 -89
-4427 -1314
-1737 8951
2294 4854
-109 -4098
-9322 -1997
-5432 7913
-662 7234
-4082 -7775
-5726 -460
4958 -96
4374 -943
5630 -6899
7438 2869
-3013 -8645
-6477 -3708
5921 -1834
6533 -233
-5205 4091
1277 -6874
958 -5533
6883 4509
-1748 6888
8786 -316
3250 -8061
-9028 2740
-5805 4021
-2285 8909
-8957 349
5924 2110
3243 -340
3040 -6309
-1627 -588
-5517 -2037
-8359 -3919
-5856 6340
3724 712
-2661 2419
-5651 6708
495 3241
2314 2164
7848 -5252
-4021 -1321
7078 2630
1133 -4323
-4615 8570
-6710 1938
2111 7811
-4616 -4418
6920 -3920
-7314 -3205
-1950 1785
-2096 -1581
-5310 90
4807 2492
9038 3640
-3165 -4827
6083 3977
5709 6250
-4175 6889
-3332 2252
6587 1309
1889 6779
5609 -2808
2032 -1019
-9316 1701
-8706 -2536
125 -481
-4604 8428
634 5832
-5464 -5540
-9887 -1152
-190 -7628
-6309 4675
-2527 -2861
-4890 5435
711 -118
8875 699
-1788 -7803
-1996 4485
6857 4118
-5641 387
-3370 -7820
4184 2145
8931 -2580
573 -7035
-6680 199
-5481 190
8455 3485
6078 6442
3378 5732
-4685 -4063
2609 -1790
1712 9395
8174 1925
8475 -1026
1164 -844
-3327 -2262
-401 -8849
-7984 -5952
2811 9119
-1543 -7272
-583 -9712
3580 -6317
-6695 -4568
-1777 -4262
-8493 -5083
-1166 -1800
1965 -3847
5867 -4956
-6436 5164
4935 5708
-2597 7851
3001 8588
5427 -2023
3071 931
-217 -20
2346 895
-6586 -3119
8098 1662
1165 -4283
3085 6125
266 1193
-7057 6569
-3113 -1365
776 -3783
-1630 9712
-3918 -8821
-3946 8284
-5184 -5096
4349 -5272
-566 -7077
8090 3735
3291 -4374
8809 196
-4018 1931
1452 -3532
5412 -6057
3361 1079
-3099 -4249
-1470 4323
-5699 6722
-202 3697
-3286 -6667
1199 -3785
949 7425
-6822 -3679
-2926 7198
-4945 -4554
2495 -5712
8396 3330
1059 -1295
-4844 -7522
8094 4247
-1426 3952
-2121 843
-87 2351
-4239 -7575
-5486 -5118
-4005 7020
1852 -3343
-2028 1946
-4665 3205
3610 2769
-1469 -1219
5601 -5828
843 -7182
2316 3964
-9 5899
1551 -5745
-4519 -7621
-4765 -2295
-1238 2886
-2115 7464
5640 5285
-8219 783
-7587 3427
2798 2813
5477 7400
6140 5435
8863 -3705
-8220 -3363
-1623 -2384
7923 -68
4185 -2098
-2055 -5803
3429 5217
7715 -3218
-7379 790
-2620 -7432
4466 -4276
9679 21
5621 -1328
4413 4110
1117 647
7093 2474
-6883 2039
7334 -3345
-9719 -337
5165 7712
-3313 -6189
5603 -8107
1585 -2719
-7595 -4423
-5121 -3264
-8371 3024
-2960 936
-2841 5916
-5609 6047
2835 4424
-2712 5382
2839 5539
8911 3063
-1760 -4593
-8322 -2264
-7363 -4240
2207 -3409
-964 -4311
-4235 1011
-4109 -325
3395 3282
-7813 910
8096 2424
752 -3320
142 7968
-1929 9648
-3739 -3976
7874 2260
-2364 -8611
-2303 -9447
-532 -7429
-4000 3225
-5616 -4621
2468 -976
1348 -7687
-3368 2523
8138 3728
1142 -5545
2071 -4660
-1736 7092
-550 5128
-7900 3582
3244 8357
5501 7181
852 3066
1687 3477
4984 6633
6280 -491
6929 3004
7919 -856
5030 -8567
-7536 -256
-5452 8030
-4758 7397
4318 6219
-7028 2098
7386 -3621
189 696
5397 -7969
-1124 -9150
-4766 5145
2270 8949
-3209 -983
-3500 -6703
-7595 2727
-9386 2037
-1228 9245
5387 -4928
-1144 -6249
-2773 9471
825 -8457
3994 -214
-6103 1523
6873 -2873
-921 5905
-6131 -363
3842 -5215
-5226 1352
7856 -5562
-3552 570
1780 -7169
1943 9473
-1294 -3398
-6415 2741
-6895 -3752
-1889 4954
5254 554
8097 -3845
-4869 -1340
-4736 -635
-8454 -379
-3059 -4309
3691 740
2105 4750
-8633 1374
-768 -3402
-5957 7933
-2134 648
2935 6742
-7749 5019
839 4387
840 -4747
1592 8818
9629 -1783
-3737 -3316
-3979 -6698
-5326 -6075
-7504 3636
-5664 1472
-487 8283
7967 -4121
-5013 3499
7776 5891
-677 -8486
3072 5111
-6332 -2068
-8697 -3237
-274 2298
-6288 -5025
6446 -2815
-131 -3817
8824 1817
9983 183
5598 -299
-4155 -6736
82 5723
-2280 3544
3026 -5248
-1008 3210
-3183 -5734
-6471 -3840
8589 3144
-4883 6781
684 -4208
-3287 8030
8085 2567
6506 -2242
478 -8521
125 6460
1370 -2203
-2881 -9112
911 774
4258 -6717
-6432 5404
4835 -569
-2470 1672
3650 6398
2541 -8650
-8053 -3010
-8816 4367
1277 -7211
6504 -137
359 -9698
3402 4383
3277 5795
-9397 -610
-7570 6048
-210 8528
-4039 5441
-429 -89
2751 4934
908 5416
5723 2613
3242 684
-1981 -4368
-3836 7761
-6303 -1152
-5287 -1159
82 1294
-1224 2502
-425 5221
8627 -2828
-4666 -3571
-5185 -7640
7484 -4842
426 -2828
4026 2508
156 8911
-6410 -3140
5708 4617
-5327 -5904
6684 -5509
-7547 -2636
5840 5032
-1719 -5328
-7467 326
1787 -889
-226 7103
5126 6302
-6535 -3019
-5618 4988
-9150 3698
3343 -1957
-966 3521
-2169 4340
2486 2076
6064 -2373
-658 -1698
-970 7909
-7122 6862
3637 -1739
-7564 -6099
-3247 -8030
1780 2342
5475 121
-491 -6248
-1749 1093
8283 -3223
4888 4162
7182 3091
7451 -705
-1350 14
-5468 2269
6843 3702
3645 -629
1038 -9738
-8759 -4572
1959 -7428
-3320 -5492
7111 4710
5157 1808
1137 1523
6909 285
-3681 6348
2362 -4660
3924 8238
-5111 -4326
4445 343
-6974 -6038
2357 1066
-3666 5851
-3985 6506
2047 4292
-3820 -1389
7848 -2829
-3277 -4758
-3595 3444
2028 8121
2356 -5617
-5927 1947
2233 1463
-2068 -2556
3361 3629
-1870 -5347
-8198 -4767
2006 7910
855 2503
-8631 3995
7700 5964
-111 -1500
5567 -8211
-4784 -4601
-2297 801
8144 434
-6665 6581
6846 6223
1664 16
2412 -3984
5086 867
-5223 -6234
4934 4631
2534 -4696
-5394 -638
5597 -6604
9864 1551
5685 -2909
-2314 4994
-3545 4622
-1106 -3388
5909 -203
2506 5847
3416 6513
-4978 -5647
6997 -7092
2502 9149
-4299 6068
-6797 1900
-7249 1537
5150 2595
7557 315
1730 235
-1137 -7053
-436 992
1108 -4238
4023 -3762
1453 5863
2507 -651
6466 -1505
-2534 6435
-978 5421
-7867 1253
5599 5966
-3252 -1250
4140 3993
-5625 -6322
-908 6564
1571 -5301
653 -8344
-1727 -4453
6737 -1164
-5905 2876
4380 2240
-2878 -3608
-4653 -237
7339 -6129
-527 5396
2370 -2478
3660 -439
-444 -8947
-7171 3567
769 -4325
-4012 2266
-8372 3084
-4329 6451
5825 -5615
9056 2616
7183 -4236
-5665 -2232
2052 -4586
3191 3550
-3140 4579
2106 -829
-6686 986
3205 -2933
1378 -8127
-4935 2492
8134 3667
-233 -5761
-6400 1588
395 -5243
1135 -654
-3879 -4170
-579 1959
8725 -698
5866 307
6075 -7560
-2957 -825
-6174 -6065
-7226 6376
1284 2845
-6317 1696
-5453 2148
-103 7928
2177 -6896
-9087 -2234
-4709 8398
-8128 301
-6731 -4549
1794 -3162
700 -6484
6727 -1922
-828 4484
-1815 -9314
-7672 4926
6926 3268
-8911 1066
-21 -406
-8104 -4806
-5585 3538
9085 3993
8190 -2727
4983 -8495
7130 5652
-2022 -3370
-3289 -1025
-8959 884
-3592 9254
7957 -4696
1221 -8264
-8011 3030
3656 1110
2806 -5060
-2117 6067
3374 -7368
-1910 -3820
-1497 8659
1462 -1775
189 -3471
9584 302
-2472 5780
2809 5385
-7921 -70
4412 -6132
660 1207
-857 6035
-8506 367
1687 -3250
-3075 1690
-2005 -322
3169 -2211
-41 4209
461 -1673
4749 -7769
7407 -5791
1562 5385
4917 -7596
-872 -6358
6697 2884
4217 -8228
2420 -8587
-9078 -2223
1055 -4218
-6772 -159
-9479 2231
-2082 3066
-8365 -1206
4430 6494
-2843 2327
344 -964
-8772 407
-6464 2004
3158 -685
4780 -5970
-4412 -3872
2244 -5005
-5003 6518
7537 -6036
-7390 3231
107 6227
-347 5065
-2936 -4902
45 6678
4600 -8005
169 5361
1301 -591
-5154 8074
897 -3443
7247 1369
3987 901
4679 -826
-2945 -1865
-3890 -5228
1220 -2304
6999 1795
-9446 744
7815 4212
8586 3340
-1313 1263
-633 8299
3748 -1154
9780 -296
6493 3755
-7405 3541
6134 2179
-6319 -3348
6210 7626
724 3773
-1207 -714
4527 5800
7592 -5376
-2416 -1152
7958 379
-3094 -470
-7999 4372
-5750 -1440
-2994 -9217
-7146 -4412
4031 6196
7455 4329
-6049 7610
3866 -4052
1544 2135
9206 986
3551 2902
-3837 -2080
-1481 -5937
-6054 -5208
3225 107
7578 -3559
9478 -2056
-5584 4676
270 9208
-6391 -5948
-6510 -6459
-9561 -2191
-446 -9586
-9446 261
3527 -2008
-944 2006
-311 -2515
-6908 -1647
-1315 6046
8309 -4248
9870 -1210
8016 -4421
-1356 -2490
7823 -1074
-3566 8105
3067 -8992
-1827 -1182
2099 -2391
-5953 2574
4962 2637
2478 7294
2546 -6583
9317 977
-5652 -661
-3758 -813
-93 -6521
898 9747
6978 -1218
1073 9907
-9288 -1086
3827 -4371
2206 2758
7428 1691
-5011 -3099
-4298 838
-3256 -7701
-8150 5043
426 -4174
6895 4344
-4357 -40
5182 -3392
-9136 -1273
3402 -4554
8579 3212
7684 562
868 5309
-6309 -6986
286 -5154
2405 393
8536 7
8452 3691
479 8356
-3904 7020
951 9545
-1472 5865
2065 9357
-630 1683
5732 -739
-5294 -1535
-3039 -9064
5596 8208
2949 1406
4441 2010
258 -4524
3859 116
-4948 -5976
8753 -4310
2130 940
-3510 6624
-3682 -2013
-7440 6117
5505 1142
-8515 1993
-7842 4128
-3213 5112
-6238 -3732
-4341 -1246
4343 -7406
9381 2577
1082 -4003
1062 -2173
-587 602
3890 -2752
7195 -1933
-2310 5737
5362 4848
-501 4323
6987 -2215
5721 -2590
-1035 9826
-1141 -8175
-538 -9813
-6749 -7299
4062 -1775
-7730 2884
-6372 1214
-2442 1341
-4317 -3195
7761 -4585
6159 2767
675 9304
-5272 4719
-1169 -6089
-4999 -99
1424 5441
-6868 3929
-4020 2903
-2014 -1584
5099 2026
-3528 5223
283 -6911
4631 -1050
564 -4021
4638 2049
4672 -8377
-2027 8256
3352 365
-3209 -8306
3505 -2481
-8929 3501
-2561 5478
-5274 7157
-700 -5159
2609 -8060
-4178 2413
9193 1905
-3495 6876
-2302 1045
-6110 3669
-3180 -9459
-8261 -2792
-2229 -1665
-4242 2662
-9658 -429
33 626
2449 -7453
-6304 -4111
-1067 -3750
6894 5508
-3581 2274
-770 -9867
7176 3277
-6048 -7615
9783 -608
3114 6948
5258 4769
3803 383
8197 5325
777 -2617
-142 1315
8199 -3079
7559 455
7870 3603
-6488 -6914
-3233 4941
2660 -7554
2736 -2989
-7637 -2121
-171 -8320
-4182 -7556
-5491 -1358
8463 -880
4833 -8282
-2243 -8950
-1947 -9244
7859 -3862
6632 1588
-974 7725
1086 -775
6835 618
-410 -2461
-8158 2956
2907 -4081
24 4430
717 -729
-1221 7749
8516 1227
-5583 -6187
-6133 3398
-1582 -1803
6922 -1958
928 5543
-6286 3729
3359 5545
-2183 -7247
-1731 -6367
-2040 -1787
-48 4320
6687 -7071
-1044 -2532
-892 9947
592 -2842
-8221 -5627
4305 7731
-4743 7770
152 -8544
4452 -4083
-7757 6288
7219 5873
2279 -4649
9043 973
-6813 6692
-5295 637
-4862 -993
-185 3303
-289 -1542
6494 5671
2520 -7592
8840 -4373
8686 -2695
-4773 -6453
5154 4288
-129 -655
-4320 2378
-6387 559
-5225 70
7172 3320
686 -3983
-6711 7025
8953 -3526
536 7095
3378 7885
-5981 2197
5088 2357
-1612 -7989
5217 8349
7095 -3427
7457 -527
-52 7059
8326 -683
-8448 3425
-1379 -1860
3083 4484
3933 5052
-6989 -2968
3672 -4239
4317 -5233
3411 -2281
-4002 8135
845 -9327
969 1567
-8101 -117
-3749 -6470
3344 746
5896 3369
6658 6585
-7446 1214
-2171 4219
-6204 -3935
8639 -1384
7543 -2292
1933 2233
5267 -891
-1208 -5405
-5306 658
-8128 -5409
3948 -3023
-7820 -3930
9554 -1233
-3109 1322
1332 -1476
-6522 -668
1047 -5449
-2095 -8614
1271 -7099
-1405 1092
48 1682
802 8599
-8425 -4848
2163 -6826
-214 -5036
-4536 -1883
6217 3008
1574 -95
-252 -2698
-9367 1907
-4517 7250
-6509 1907
-2555 -1824
4235 5045
-7689 3679
-3765 -3223
-6601 -2525
2301 2823
-2564 3840
597 -9099
-225 2073
-3309 2189
-9418 -609
3089 57
-7930 2927
4052 3262
760 9223
-8764 1808
-7772 1384
-5443 1991
-6437 -5215
6559 -1521
7794 -2654
2974 2610
3054 -162
-4443 -6765
1579 903
-3236 -2974
3335 5143
3233 -1386
-9340 1656
-6457 7067
-1171 -5793
1833 -3112
316 -4658
-397 2545
-7254 5213
-3013 -9357
3581 -7869
-2092 -9432
-126 -9427
3584 -1857
-3075 -4637
-5089 -4935
-2027 -7238
782 -1338
-8618 -4982
-1479 -9046
4770 7721
7313 1194
201 3467
4850 6099
-449 -2273
-912 -2738
-625 4463
-704 -1727
773 -5717
-4191 5881
3370 3500
2706 9488
-3154 -805
-5411 -7957
2411 9300
1404 -188
-1027 8017
-2902 242
197 1112
2905 -3356
-5323 -6766
5425 -350
5854 -7801
3057 3322
2633 8183
7999 -1865
6656 4704
-3697 -1583
-355 6557
8332 -4715
5227 6322
8112 42
-4557 6207
8047 232
-6348 -6153
4393 4471
5481 4882
-2051 4421
-54 -9534
-4986 -1555
-5016 2138
-9640 -431
-1779 -4701
4894 5877
2767 3048
-7936 -4457
7466 -4055
2526 -7602
-2329 -2040
-4903 1966
2630 8729
8728 3273
-3619 -2726
6037 636
-3930 -2093
-1345 6109
3746 -979
-4667 -3141
1355 610
5431 -8279
54 -3035
4339 1964
-5382 -839
-4144 7054
6644 1572
-5956 2493
-8803 1729
7114 -2461
-4921 -2225
-4880 1526
-2137 995
-1672 -1557
-1263 8260
-3947 -5176
-2318 1981
8274 2736
-8139 2412
2223 -4418
-5230 -3158
48 4347
1313 7374
-6846 -3859
7776 1268
-2102 3352
-63 -914
-4597 -8005
8204 -4869
8016 149
-4341 5802
-7420 6048
-3183 -3326
6676 5938
6786 -7162
-5836 5837
6220 5503
4199 -5197
-8428 -936
-2759 9383
-1903 -6871
391 -5591
6245 -1237
-8187 -5385
-2674 -3775
8117 -1889
2542 239
3099 -560
-3547 1124
3224 453
4038 -8040
3722 7262
-5789 -2587
4279 -7429
-8308 -5505
3085 7164
-2197 -6002
5236 5391
2619 5559
-8089 -3859
8744 -1317
-1763 240
-6972 -2065
-3910 1334
3281 -6937
1022 2529
-3400 -8183
-5742 214
4603 7156
1619 2446
2475 2342
-1984 6390
82 -1689
-5310 5938
-4053 -8952
-8855 1340
-3890 -818
5009 6378
-6201 -5403
-1592 -4051
-2435 -333
652 1910
1966 5681
7621 4594
-6348 -1106
8693 -456
-246 404
5483 -7436
-683 -6184
-8184 4359
1668 3516
-7449 4777
2444 7383
-8066 5895
-3228 1889
-5322 4551
9030 -4244
4420 2525
1253 1535
2421 279
403 7849
-7604 1757
8491 -4328
-1675 -7426
4775 -402
-6710 -1213
5056 5517
8959 1692
-7929 4013
4284 -4536
-8208 903
-3965 6823
-1302 -5203
7995 -1746
-3664 2931
62 -3687
-2415 7274
-1373 9207
-2314 1225
8271 2920
-6029 -3654
-5616 -7291
9505 -1122
-369 -482
3386 -7623
4806 -676
5239 -1280
656 -4933
3257 -7347
-5218 1901
-1280 6146
-3355 -7707
-447 3235
8652 -4099
367 2167
892 -530
-6002 609
6463 -3469
2967 4879
-5217 -725
8614 -197
823 5937
-8968 -355
4299 8675
1073 5917
8503 -1839
2926 52
1008 -5709
8533 -4936
6469 5696
-716 1932
-2119 -9195
-2251 8233
7420 -956
-1777 -9509
-5061 1251
-1169 -7334
6103 5293
6300 7363
3199 -2237
7388 5712
6448 4098
-5453 4370
-5456 1405
7169 -2407
9038 -1500
-8019 2366
6744 -6904
6243 482
607 -5851
2765 2104
8365 4144
7869 2797
-5938 5546
-4398 -5655
-6807 -5528
554 6683
486 9166
-7259 5143
808 1637
-8960 4133
-1145 9027
-3357 -7424
-1019 -854
1332 7617
5811 4433
6013 -7537
3454 -8504
-8554 -3866
3592 -7560
6319 -827
9805 650
-4122 3382
1029 2127
2458 -1365
-6178 -869
4648 -2546
6280 -5119
592 1545
-2821 -2052
4581 -3015
2048 -53
4247 7363
3168 1212
-5061 5371
9883 1467
8584 4982
-1734 -2696
5215 -3852
-2801 -643
-6866 6767
-3962 5599
4661 -3478
-2330 -6419
-3770 -1844
4847 -8692
-1772 8439
694 -6086
-2966 -4639
3055 -5740
4656 58
-7660 -4216
-4400 481
8354 5386
459 -9973
-449 2592
-4463 -3639
7363 -4693
-8797 1134
8892 -4537
8772 -4459
-326 2504
4249 3853
4616 -7632
-3277 1021
-3341 3312
7893 -1950
8566 2419
133 4174
-3672 -6971
-569 -5469
-640 8582
3120 -473
5372 -3940
-5724 -7885
1527 927
-319 9559
2087 5124
-9913 -429
5471 -5188
4954 -2733
-6820 -2873
6112 -7099
4326 2962
2649 -1448
2794 -1660
807 7642
4853 3477
-2016 3466
5553 -1964
-9711 2024
-2990 8700
6618 -541
-6109 -6504
-5922 -182
-1038 -3726
-184 -611
-4261 -6604
-5047 -6155
8111 1105
-4045 8849
8015 -3338
2954 9072
4361 8662
-387 -1954
-9030 -318
-6143 -6777
3482 -3435
3705 7732
-7044 -6914
4425 5239
862 1195
7279 -3241
-5342 -1956
2552 -7816
-7499 1841
3766 3099
6486 -2614
-5362 -3284
4221 6116
4015 5135
3868 -1562
2567 2742
-6416 3267
-6882 -4875
-8926 -980
7787 3965
-343 -1765
2899 -3612
7008 -4454
4378 2642
-3091 -3343
-458 5488
4477 3139
4209 -208
-1689 7726
5999 2015
1253 -3344
2313 -443
1095 -3277
-3349 5578
6678 -6101
-5885 7473
-1477 4215
7408 4806
-936 -8522
898 -79
-7873 -3171
-6951 -4410
9695 -1778
3205 1578
722 -2320
-1507 5501
4511 -8542
-1428 -709
-6160 139
-5221 -8349
-1401 2309
-2985 524
321 -9692
3348 9330
-4637 -7967
4885 2173
-2476 -6245
-3554 5410
-6180 1096
-5326 -2105
-7099 6477
4781 -790
-7564 -1595
-1592 9284
-6233 -4578
4118 4409
4092 -3350
-4556 4368
-4757 -5074
5842 -4306
-1238 5808
731 2166
-7250 -658
842 -1165
-4620 -5
433 -7497
3728 7842
3179 -5256
3998 1995
2712 2422
-4556 4337
7980 -875
5741 -5605
5798 -1090
7704 -581
-343 5793
5608 7558
3678 2159
6972 5109
-8416 785
6136 6690
-1717 9161
-444 -774
5018 7308
-719 1951
-5621 -2616
4615 6617
5132 1834
5817 -86
-1012 -6671
-6368 6537
164 -2168
2399 1707
2984 397
6680 -5081
-4137 6380
-2091 -5150
-596 8486
-5609 6794
-358 8506
-2780 5389
1189 -587
6590 7238
-2327 -2971
3314 -690
1676 -6709
4081 -1080
9093 511
1154 -7353
3724 -8413
6973 -3639
-7018 1505
-9704 -400
-7674 4407
-2501 3208
7833 1816
2661 -6438
-990 7249
-1794 3437
2816 3583
-6065 3690
-4444 192
14 5466
2801 -5994
-2373 4871
-3804 6898
-2272 9551
8780 -899
3422 -2304
-5008 2599
-5793 -5327
-8560 -445
3594 -4903
-1979 -5987
5698 6801
1612 812
-3727 -4434
3126 4235
-5550 3214
-4249 -6274
-4950 -7309
683 4075
-3417 6134
-4482 -6826
-229 3953
5831 5351
-7268 -4930
-287 -8696
8515 -2226
2274 -6885
5102 7821
426 8721
-1998 730
2565 2635
-760 -3195
1699 -9652
7937 -3479
1795 -4461
-9037 2226
5828 4804
-3237 4220
-2588 -8667
4455 -821
-8066 -4858
3204 9094
2041 -8895
-7997 270
-2124 5069
-1763 -6088
-224 4970
4240 -3053
5218 6387
-7853 160
-3487 -3553
5125 -3531
-3147 -8125
-4993 -222
2464 730
3677 -3078
-2216 -6971
1869 -3536
652 7741
6251 -4728
-5526 -3260
-681 -432
9329 -483
-6237 -1080
-1848 -676
-1635 9599
7912 -5813
-2583 -5502
3984 -4092
-745 -1671
6097 804
5956 7180
-2495 1377
-2105 -1665
1409 -6302
-7951 -5463
1664 -719
-5930 8010
-7254 6425
-8740 -4382
-1562 -7409
4648 3809
-9439 -320
-5246 -6632
-5437 8028
9779 -508
388 8436
-9508 -372
-6575 1246
6217 6835
237 -3799
4271 -5613
5256 -7221
-4182 8413
1142 -424
4563 965
7519 532
-2373 -6425
1114 8176
2241 7455
4785 -1982
-5344 -2072
9370 48
-7986 5640
1102 1689
-1225 8347
3417 2665
3277 -2149
-6940 534
-2271 8789
769 -1740
-717 -8165
-6553 4814
-107 6378
-6632 6065
-2924 -2754
3405 -5425
1931 -664
2227 -2045
-8970 227
-7846 4254
-1037 3871
4694 2079
6840 -6074
3758 2852
-9324 -1579
-1742 -6023
-1 1397
-597 -2877
-6747 5466
3429 3283
-1930 -9546
-366 -8247
2023 -3135
5685 -5575
-75 -5923
4662 2826
-3802 1663
-1178 -6076
4606 -7290
-384 -8426
6498 -5488
1911 -3324
-5762 6081
2835 4233
2732 3463
-7943 5574
-8355 -1249
-6032 -7961
-6289 -4261
-4913 -1929
1215 6849
-6839 -463
-1656 293
3083 3366
-149 7212
-3620 -4026
334 1229
2528 -5304
-3190 -9436
8690 422
1009 -4775
-959 -2756
4953 7346
7393 2750
956 -4087
4146 -6199
-3686 -8811
7661 2578
-3721 -5126
-1644 4991
1926 -7706
-9019 -65
-7826 -1382
-5864 -7490
8774 3746
-8162 -547
2804 -8884
8083 -3502
6713 7100
7534 4669
-1190 8416
8155 3345
8956 1627
-6898 -5960
3953 -7248
1574 -1796
-3304 7002
-3882 54
3637 2906
1396 -543
6970 2848
-3564 -4711
3174 969

Sample Output 1

30
-1812 -1984 -9663 5131
-2586 7859 7423 -4798
193 8457 -300 2680
-149 -9041 6425 84
3329 -5601 -2055 -5156
4701 3753 -2852 -2578
-1417 -9909 -5593 -5639
-7013 2309 -7622 6652
-5296 -5647 -9646 -1031
-1275 8332 6134 1727
-6996 2724 933 4067
1134 3022 -9377 2501
6487 -7016 -6730 4775
9141 -7928 7794 -4177
-5164 -3440 -2341 -6820
-5940 2165 -1255 6089
1691 -1616 347 -8205
-7966 -6024 -2883 5136
6899 3888 1191 6179
-762 7446 2182 2919
-6843 1720 -8636 -9995
-2997 -6378 4359 -2044
-7094 2392 2381 558
-3241 7718 -2179 -1519
-358 247 -547 -5282
-376 -1900 7187 3663
7470 1828 4310 -103
-2289 7865 8712 -1962
-6942 -5180 -1909 326
3266 3617 3585 1090