Problem Statement
Fox Ciel has a map of some underground ruins. It describes the position of several jewels and their values. She wants to collect some of the jewels. The map is a rectangle with width W and height H. It contains W*H cells. The cell in the upper left corner has the coordinates (0,0) and the cell in the lower right corner has coordinates (W-1,H-1). There are jewelCount jewels. The i-th jewel is located at coordinates (x[i],y[i]) and has a value of v[i]. 0, 1, 2 or more jewels may be in the same cell.
Ciel starts from any cell in the top row (any cell whose y-coordinate is 0 and x-coordinate is arbitrary). She has a super drill so she can move down any number of times, but she can move to the left or right at most LR times. Moving up is not allowed. She collects all the jewels in a cell by moving to that cell (or starting in that cell). Moving down takes timeY seconds and moving left or right takes timeX seconds. Collecting jewels takes no time.
Calculate and return the minimum time required to collect enough jewels so that the sum of the values of the collected jewels is greater than or equal to goalValue. If she can't collect enough jewels then return -1.
You can calculate x[i], y[i], and v[i] as follows:
x[0] = (seeds[1] * seeds[0] + seeds[2]) mod W
y[0] = (seeds[4] * seeds[3] + seeds[5]) mod H
v[0] = (seeds[7] * seeds[6] + seeds[8]) mod seeds[9]
for i=1 to jewelCount-1:
x[i] = (seeds[1] * x[i-1] + seeds[2]) mod W
y[i] = (seeds[4] * y[i-1] + seeds[5]) mod H
v[i] = (seeds[7] * v[i-1] + seeds[8]) mod seeds[9]
Definition
- Class:
- FoxSearchingRuins
- Method:
- theMinTime
- Parameters:
- int, int, int, int, int, int, int, int[]
- Returns:
- long
- Method signature:
- long theMinTime(int W, int H, int jewelCount, int LR, int goalValue, int timeX, int timeY, int[] seeds)
- (be sure your method is public)
Constraints
- W will be between 1 and 1,000, inclusive.
- H will be between 1 and 1,000,000,000, inclusive.
- jewelCount will be between 1 and 1,000, inclusive.
- LR will be between 0 and 1,000, inclusive.
- timeX and timeY will each be between 1 and 100, inclusive.
- goalValue will be between 1 and 1,000,000,000, inclusive.
- seeds will contain exactly 10 elements.
- for i=0..8, seeds[i] will be between 0 and 1,000,000,000, inclusive.
- seeds[9] will be between 2 and 1,000,000, inclusive.
Examples
5
8
5
7
10
3
1
{979, 777, 878, 646, 441, 545, 789, 896, 987, 10}
Returns: 5
The map of the ruins is as follows: 3.... ...5. ....7 .9... ..... ..... ..... .1... Ciel's optimal moves: Start from (3, 0). (time = 0) Move to (3, 1) and collect the jewel whose value is 5. (time = 1) Move to (4, 1). (time = 4) Move to (4, 2) and collect the jewel whose value is 7. (time = 5)
7
8
10
3
10
3
10
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
Returns: 29
The map and Ciel's optimal moves: .1..... ...*... ...3... ...*... ......7 ...**** .55.... ....... ....1.. ....... 3...... ....... ..77... ....... .....5. .......
7
8
10
3
14
3
10
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
Returns: 59
Note that Ciel can move left or right at most 3 times. .1..... ...*... ...3... ...*... ......7 ...*... .55.... .***... ....1.. .*..... 3...... **..... ..77... ....... .....5. .......
7
8
10
4
14
3
10
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
Returns: 42
Now Ciel can move left or right at most 4 times. .1..... .***... ...3... ...*... ......7 ...*... .55.... .***... ....1.. ....... 3...... ....... ..77... ....... .....5. .......
497
503
989
647
100000
13
14
{7613497, 5316789, 1334537, 2217889, 6349551, 978463, 1234567, 2345678, 3456789, 1000}
Returns: -1
Watch out for integer overflow when computing x[i], y[i] and v[i].
1000
749613275
1000
1000
7500000
97
6
{224284427, 617001937, 294074399, 606566321, 202762619, 419798101, 200613401, 640663967, 417565817, 170000}
Returns: 3780225876
8
9
7
7
10
18
100
{41884472,12157709,27035,4,32539550,0,6,2433401,8,4}
Returns: 626
9
54
6
10
21
94
82
{893,551314117,847,3617,139,381,7514759,888,1000000000,10}
Returns: 4816
9
5
7
4
13
61
75
{2,43324,1000000000,79,6472341,6091893,882004,524,903693620,6}
Returns: 469
5
9
9
9
19
15
91
{610394320,80247,344599168,9471771,19245,22,811356,921,309116,5}
Returns: 712
5
9
4
6
18
92
32
{754,43800587,7458399,533741389,1000000000,805533,1000000000,0,66,10}
Returns: 404
5
4
3
8
6
15
47
{6369,40642411,3,887780608,55510210,8458333,7,88386415,90553,4}
Returns: 201
976
2
7
12
28
65
62
{450517557, 51959703, 447774107, 400048580, 912095657, 291882786, 137735210, 92757747, 554728763, 23}
Returns: -1
1000
12
1000
1000
7500000
97
6
{224284427, 617001937, 294074399, 606566321, 202762619, 419798101, 200613401, 640663967, 417565817, 170000}
Returns: 12561
997
17
995
998
3184139
87
37
{327959433, 360676241, 526788121, 788596894, 595969736, 649342849, 415684002, 958752113, 78835789, 767540}
Returns: 520
1000
1000000000
1000
1000
7473616
97
100
{224284427, 617001937, 294074399, 606566321, 202762619, 419798101, 200613401, 640663967, 417565817, 170000}
Returns: 92951076772
1000
1000000000
1000
1000
7473617
97
100
{224284427, 617001937, 294074399, 606566321, 202762619, 419798101, 200613401, 640663967, 417565817, 170000}
Returns: 92951076966
806
1
898
168
227783
60
15
{77, 4, 20, 36, 8, 87, 68, 97, 25, 898131}
Returns: 0
806
1
898
168
227783
60
15
{26428234, 39023649, 48438974, 48184797, 53628483, 85494843, 61515341, 21741954, 90897736, 617006}
Returns: 0
17
5
547
323
518031
68
30
{43196363, 34387857, 44829946, 82812801, 49021145, 76417926, 59041654, 11086732, 92052898, 218905}
Returns: 30
656
3
868
977
101442
40
53
{76576285, 32720773, 43234950, 67627692, 69659153, 44772512, 93856468, 96906129, 66075540, 971818}
Returns: 0
665
4
12
365
93147
91
28
{88413528, 59102411, 23804961, 19616825, 48748654, 49174170, 12371555, 60863369, 21681619, 925124}
Returns: 0
761
1
617
967
467814
83
91
{11241782, 59584991, 21459406, 65961368, 75728750, 27361003, 36854451, 80613637, 28697378, 114051}
Returns: 249
613
4
610
424
367129
31
17
{18119037, 67649307, 66738392, 53368345, 69360406, 12768582, 70026978, 38866222, 91313373, 921559}
Returns: 34
141
2
92
486
635884
57
57
{47877116, 73782350, 49337308, 94190065, 43451940, 73470575, 1746974, 79937350, 48032742, 613814}
Returns: 57
402
1
515
172
541226
30
6
{21763147, 65810612, 16454928, 88741899, 70834116, 89231641, 13171010, 37087947, 46586675, 342170}
Returns: 0
488
6
170
942
44355
13
48
{25090725, 29488570, 83410090, 4374991, 20571986, 28161791, 48007499, 70450079, 93500689, 24618}
Returns: 48
866
1
22
684
793889
41
75
{85109071, 58056393, 57962695, 2259465, 34107168, 86707247, 78919379, 58170899, 50983554, 958466}
Returns: 0
337
2
251
440
656692
16
100
{74350692, 75440814, 30526089, 70125087, 81937745, 75351327, 55543268, 96107476, 66836465, 271813}
Returns: 0
313
4
331
573
255464
27
47
{43487041, 63337834, 71316718, 94182891, 61885597, 53469280, 62477711, 61612570, 9008465, 480135}
Returns: 141
484
5
845
548
397654
53
60
{57044770, 83049279, 53841695, 4602590, 48060510, 34638607, 63107619, 6846828, 5571116, 405874}
Returns: 120
164
3
991
501
159389
54
37
{72350008, 61698337, 25671478, 83286003, 58613539, 98919657, 68713336, 59971999, 78874851, 304840}
Returns: 0
873
4
55
394
785041
48
55
{23745415, 32908439, 24915759, 34359391, 55789392, 8188957, 78916776, 63117736, 61254203, 872945}
Returns: 55
791
1
198
30
520931
1
68
{26814317, 62939748, 93929213, 91772543, 80606957, 9426543, 50075323, 5533232, 72153770, 762910}
Returns: 0
633
6
682
597
243300
16
36
{46262956, 36209851, 16845557, 34952041, 85073956, 31182358, 29915781, 1891164, 50674397, 486817}
Returns: 0
345
2
162
792
384506
50
19
{14521145, 60652485, 14641588, 8518486, 82491299, 1757215, 38044558, 77693491, 66519356, 449847}
Returns: 0
972
2
197
25
535473
1
26
{94948283, 99504990, 62131785, 71739371, 29288887, 82121433, 59459588, 51577625, 41323599, 629816}
Returns: 0
663
3
784
732
816877
39
87
{81893653, 14970304, 51348102, 83698348, 84089102, 80777152, 62206033, 52285488, 29969914, 690299}
Returns: 0
761
5
911
501
401747
62
12
{17665347, 74783055, 40482297, 43091262, 82385279, 67064887, 77925165, 27876639, 6296751, 539999}
Returns: 0
49
4
297
510
440702
29
72
{11096096, 74625122, 91253290, 82008543, 84081729, 14643264, 28001644, 41034246, 15363445, 439874}
Returns: 216
953
3
52
521
263156
7
64
{25362362, 87958197, 78043714, 26312506, 75644540, 89118513, 28119001, 725754, 17122962, 858696}
Returns: 64
547
3
843
780
104757
45
26
{68501631, 86178107, 1214784, 19991437, 39786117, 55978767, 9965179, 24981435, 76142289, 621633}
Returns: 0
194
2
664
554
286154
4
3
{60915714, 69973630, 73971525, 27894101, 36094565, 1216907, 35799096, 85075073, 42216462, 650560}
Returns: 0
383
2
179
416
622043
65
78
{7994706, 28840945, 30625648, 63252796, 50745781, 36640796, 3513928, 78589774, 28251421, 234187}
Returns: 260
852
5
371
992
201076
28
64
{72190105, 18164480, 41644463, 77890002, 70585877, 12818112, 16429220, 39873932, 35733227, 30961}
Returns: 592
91
2
271
570
719353
15
91
{28386345, 53875794, 2540977, 87568490, 99536532, 86335375, 20156281, 61046633, 87690660, 126385}
Returns: 91
900
4
826
120
289648
93
58
{54315904, 93096035, 41049613, 83002802, 85799619, 51221747, 63578847, 67655462, 66807143, 721896}
Returns: 58
363
698519861
423
999
427657
18
48
{17567865, 11571189, 55278467, 22514516, 96848496, 17334926, 5639716, 45391307, 39829296, 322737}
Returns: 442944504
704
839450888
144
928
852637
94
13
{20974483, 26074844, 17368639, 12635640, 80603104, 587578, 12796099, 28833777, 28364699, 5107}
Returns: -1
817
400893001
826
604
506069
60
48
{61185851, 34232995, 33394346, 89293075, 82483713, 77849839, 821963, 71597052, 56724001, 502393}
Returns: 178103760
150
36923246
894
80
461421
6
17
{20542930, 35168522, 60212890, 45918065, 8291790, 94101734, 52299284, 7803570, 80231028, 819224}
Returns: 1442450
995
412375804
94
406
434327
99
36
{67655247, 55899475, 60869118, 39659790, 40908526, 35059505, 26569364, 71227838, 97677402, 122154}
Returns: 2263939326
637
96368238
566
420
721134
77
70
{65602705, 1395420, 21500865, 29230817, 28219874, 9537282, 6127925, 82267279, 48924042, 908388}
Returns: 58674084
295
779740318
66
818
626701
28
74
{30095969, 38988722, 8190623, 48161014, 24452294, 30838416, 48209281, 86497063, 84643789, 874498}
Returns: 1201529564
630
423610530
646
593
266283
25
20
{33487846, 48402359, 7332568, 30922025, 74221210, 41412646, 88226215, 75355837, 22790177, 593563}
Returns: 45140520
951
338770378
320
998
808051
98
64
{36386364, 35449815, 88322358, 23475028, 72069535, 94221293, 97265210, 46449432, 13456217, 389844}
Returns: 277768334
43
777006030
840
668
949641
49
72
{58640859, 47245058, 67189102, 35215493, 29419294, 75711749, 64901589, 52317712, 39109171, 121101}
Returns: 1554732483
726
732050059
36
48
184664
80
63
{81241333, 91110343, 66747124, 66257630, 9702486, 27108928, 73579036, 75963771, 77422799, 196575}
Returns: 2563289554
860
223457418
154
572
67818
4
85
{45491122, 59144434, 86920863, 32959175, 27092617, 97847944, 33674352, 3636158, 95938169, 319}
Returns: -1
604
886239487
75
242
249
77
26
{98524219, 66941027, 98681597, 44129953, 86879449, 73074005, 69057054, 68879171, 94847950, 598028}
Returns: 156667966
862
588928894
518
918
9065
66
30
{83977355, 85868136, 59272951, 20751555, 19625778, 98621114, 34508559, 94141828, 94840184, 899909}
Returns: 33850380
237
88647323
105
19
613275
76
60
{57010054, 70121032, 53251714, 2568155, 90569361, 60620951, 29275669, 73969546, 67311923, 437863}
Returns: 16919040
992
573029529
480
52
957674
2
18
{30399562, 18694303, 53842056, 58920757, 5399694, 42398153, 6173429, 52144513, 20492266, 722921}
Returns: 136078828
700
951092158
141
17
775462
80
13
{25747526, 39632942, 30847219, 56326161, 5175392, 63325560, 18851178, 7919225, 95313236, 407232}
Returns: 527821554
651
101073190
385
59
917975
58
6
{60809786, 86427734, 18398434, 67198250, 58890867, 11185562, 40111496, 58505108, 55212643, 50551}
Returns: -1
71
330265987
413
824
408043
45
1
{90384054, 89183744, 26267456, 93288755, 39991195, 83446539, 67906439, 70611703, 83330027, 433347}
Returns: 9824435
500
948307154
150
147
987856
84
45
{98925912, 3329069, 33977407, 70016833, 51864825, 2421352, 82907748, 31602247, 29251911, 579970}
Returns: 1447589313
22
27365705
423
158
199646
30
58
{11384608, 52804437, 30472331, 93970172, 5359004, 71113911, 13283533, 29013650, 76351583, 844248}
Returns: 7080176
648
830572861
65
143
66648
97
95
{66795269, 19295513, 64564105, 31026568, 80444890, 60353356, 7960697, 14413519, 69144284, 401294}
Returns: 3162061130
271
904957259
180
456
340057
94
50
{94417419, 22009212, 84271182, 30968395, 44065244, 89712604, 24847418, 65336203, 51039280, 265228}
Returns: 2260544380
298
151443935
945
138
933186
3
35
{92328840, 17854810, 77033260, 98279316, 1835674, 92217227, 68639434, 83163099, 15412344, 750475}
Returns: 16012196
414
678877211
683
852
663371
36
74
{29619802, 86906749, 83287904, 51370020, 64149483, 41917873, 76837482, 66987300, 5400341, 107411}
Returns: 990875634
520
450144247
986
214
606261
31
70
{78111784, 54172462, 14892593, 27337754, 17258377, 6621787, 3743224, 61039358, 26005237, 236203}
Returns: 369736772
892
555767094
404
278
237079
5
36
{19921693, 27095941, 46552230, 1365593, 87316889, 97313527, 24072138, 61543169, 50645652, 885107}
Returns: 13913280
396
309000791
134
987
311902
89
95
{80166610, 78484397, 55313837, 29833204, 43252621, 39797469, 37534364, 38613363, 94776735, 989830}
Returns: 108202815
138
220122583
761
293
638099
4
97
{19115092, 70468957, 69510628, 60248010, 55781464, 67691679, 18684510, 40267715, 20983398, 346023}
Returns: 121038680
781
515084657
539
232
435805
5
60
{98809332, 20371591, 14641097, 60688034, 36624414, 12505084, 16159855, 85966290, 4622709, 591155}
Returns: 9475980
17
618415859
547
323
497948
68
30
{43196363, 34387857, 44829946, 82812801, 49021145, 76417926, 59041654, 11086732, 92052898, 218905}
Returns: 100705976
17
618415859
547
323
497949
68
30
{43196363, 34387857, 44829946, 82812801, 49021145, 76417926, 59041654, 11086732, 92052898, 218905}
Returns: 100706112
665
353235963
365
696
766617
28
47
{59102411, 23804961, 19616825, 48748654, 49174170, 12371555, 60863369, 21681619, 17923489, 85992}
Returns: 1482745687
665
353235963
365
696
766618
28
47
{59102411, 23804961, 19616825, 48748654, 49174170, 12371555, 60863369, 21681619, 17923489, 85992}
Returns: 1565045836
706
725487449
967
993
361303
91
89
{59584991, 21459406, 65961368, 75728750, 27361003, 36854451, 80613637, 28697378, 52111977, 891704}
Returns: 78202609
706
725487449
967
993
361304
91
89
{59584991, 21459406, 65961368, 75728750, 27361003, 36854451, 80613637, 28697378, 52111977, 891704}
Returns: 79653042
557
918338924
486
523
430569
57
37
{73782350, 49337308, 94190065, 43451940, 73470575, 1746974, 79937350, 48032742, 25612979, 619540}
Returns: 25646106
557
918338924
486
523
430570
57
37
{73782350, 49337308, 94190065, 43451940, 73470575, 1746974, 79937350, 48032742, 25612979, 619540}
Returns: 100265116
106
150794336
172
830
803095
6
50
{65810612, 16454928, 88741899, 70834116, 89231641, 13171010, 37087947, 46586675, 32340823, 237585}
Returns: 167247324
106
150794336
172
830
803096
6
50
{65810612, 16454928, 88741899, 70834116, 89231641, 13171010, 37087947, 46586675, 32340823, 237585}
Returns: 167247504
657
617926481
942
549
975001
48
46
{29488570, 83410090, 4374991, 20571986, 28161791, 48007499, 70450079, 93500689, 46023661, 85404}
Returns: 1219444534
657
617926481
942
549
975002
48
46
{29488570, 83410090, 4374991, 20571986, 28161791, 48007499, 70450079, 93500689, 46023661, 85404}
Returns: 1219446070
922
725400724
684
803
692030
75
89
{58056393, 57962695, 2259465, 34107168, 86707247, 78919379, 58170899, 50983554, 10957545, 95270}
Returns: 3015204478
922
725400724
684
803
692031
75
89
{58056393, 57962695, 2259465, 34107168, 86707247, 78919379, 58170899, 50983554, 10957545, 95270}
Returns: 3023071286
715
674005192
573
668
636651
47
43
{63337834, 71316718, 94182891, 61885597, 53469280, 62477711, 61612570, 9008465, 39478579, 26315}
Returns: 4299962517
715
674005192
573
668
636652
47
43
{63337834, 71316718, 94182891, 61885597, 53469280, 62477711, 61612570, 9008465, 39478579, 26315}
Returns: 4299964585
98
959162327
548
508
628086
60
88
{83049279, 53841695, 4602590, 48060510, 34638607, 63107619, 6846828, 5571116, 90405075, 154299}
Returns: 2380821912
98
959162327
548
508
628087
60
88
{83049279, 53841695, 4602590, 48060510, 34638607, 63107619, 6846828, 5571116, 90405075, 154299}
Returns: 2380822152
714
697191643
501
398
423925
37
28
{61698337, 25671478, 83286003, 58613539, 98919657, 68713336, 59971999, 78874851, 6302812, 480124}
Returns: 121907044
714
697191643
501
398
423926
37
28
{61698337, 25671478, 83286003, 58613539, 98919657, 68713336, 59971999, 78874851, 6302812, 480124}
Returns: 128294740
580
246266649
30
440
433821
68
26
{62939748, 93929213, 91772543, 80606957, 9426543, 50075323, 5533232, 72153770, 99762203, 71806}
Returns: 6175102716
580
246266649
30
440
433822
68
26
{62939748, 93929213, 91772543, 80606957, 9426543, 50075323, 5533232, 72153770, 99762203, 71806}
Returns: -1
651
101073190
385
59
495955
58
6
{60809786, 86427734, 18398434, 67198250, 58890867, 11185562, 40111496, 58505108, 55212643, 50551}
Returns: 510601806
651
101073190
385
59
495956
58
6
{60809786, 86427734, 18398434, 67198250, 58890867, 11185562, 40111496, 58505108, 55212643, 50551}
Returns: -1
743
28804273
763
865
301270
65
45
{11266522, 66662012, 20614028, 87862741, 51129751, 27418135, 29958021, 58883666, 40032781, 7019}
Returns: 1242287210
743
28804273
763
865
301271
65
45
{11266522, 66662012, 20614028, 87862741, 51129751, 27418135, 29958021, 58883666, 40032781, 7019}
Returns: -1
682
140587333
13
230
237815
90
56
{55566134, 15965267, 84007413, 22105160, 54280341, 69197472, 11025233, 19622249, 913221, 69086}
Returns: 5403259826
682
140587333
13
230
237816
90
56
{55566134, 15965267, 84007413, 22105160, 54280341, 69197472, 11025233, 19622249, 913221, 69086}
Returns: -1
516
157320974
616
282
513222
62
59
{66740534, 27777401, 67536052, 94999065, 37687836, 37371446, 12375255, 78772679, 33710206, 16231}
Returns: 9164939878
516
157320974
616
282
513223
62
59
{66740534, 27777401, 67536052, 94999065, 37687836, 37371446, 12375255, 78772679, 33710206, 16231}
Returns: -1
582
967808847
212
21
212730
27
51
{79451557, 23131423, 10611767, 98559426, 80318857, 2541273, 18799200, 17783364, 54789917, 25648}
Returns: 47172292695
582
967808847
212
21
212731
27
51
{79451557, 23131423, 10611767, 98559426, 80318857, 2541273, 18799200, 17783364, 54789917, 25648}
Returns: -1
977
338430060
24
247
354464
94
91
{19443990, 99375269, 25365901, 80682041, 59934850, 7233184, 37472688, 99549451, 94065924, 123572}
Returns: 27480705150
977
338430060
24
247
354465
94
91
{19443990, 99375269, 25365901, 80682041, 59934850, 7233184, 37472688, 99549451, 94065924, 123572}
Returns: -1
313
206803334
792
55
557430
54
25
{84374601, 61917615, 11441474, 31477274, 90593557, 82502913, 18905566, 67041945, 32889428, 28799}
Returns: 4683378495
313
206803334
792
55
557431
54
25
{84374601, 61917615, 11441474, 31477274, 90593557, 82502913, 18905566, 67041945, 32889428, 28799}
Returns: -1
358
688820480
476
896
2568
32
4
{7554818, 29690239, 96462423, 29611956, 3691342, 63926876, 78374480, 12535258, 23283282, 50}
Returns: 2739050704
358
688820480
476
896
2569
32
4
{7554818, 29690239, 96462423, 29611956, 3691342, 63926876, 78374480, 12535258, 23283282, 50}
Returns: -1
398
548535174
237
728
67989
68
93
{37826955, 87126918, 51274247, 39935692, 47366491, 25727755, 5459354, 46005459, 44252669, 1915}
Returns: 50863648156
398
548535174
237
728
67990
68
93
{37826955, 87126918, 51274247, 39935692, 47366491, 25727755, 5459354, 46005459, 44252669, 1915}
Returns: -1
1
1
1
0
1
1
2
{1,2,1,0,1,1,0,0,1,2}
Returns: 0
1
1
1
0
1
1
2
{1,2,1,0,1,1,0,1,0,5}
Returns: -1
1
2
1
0
1
10
1
{1,0,1,1,1,0,0,1,1,2}
Returns: 1
2
1
1
0
1
1
1
{0,1,1,1,1,1,1,1,0,2}
Returns: 0
2
1
2
1
2
9
1
{0,1,1,1,1,1,1,1,0,2}
Returns: 9
2
1
2
0
2
9
1
{0,1,1,1,1,1,1,1,0,2}
Returns: -1
2
2
2
1
2
10
3
{0,1,1,1,1,1,1,1,0,2}
Returns: 13
2
2
3
0
1
10
3
{0,1,1,0,1,1,1,1,0,2}
Returns: 0
2
3
3
1
3
10
3
{0,1,1,2,1,1,1,1,0,2}
Returns: -1
2
3
3
2
3
10
3
{0,1,1,2,1,1,1,1,0,2}
Returns: 26
1000
17
1000
1000
10000029
9
59
{46228012, 916746958, 254402613, 426428238, 439023662, 848184805, 53628483, 485494847, 961515350, 743896}
Returns: 996
1000
36
1000
1000
10000067
51
4
{721218182, 638793196, 131791508, 154579447, 585222637, 940111140, 34350139, 237197951, 976576294, 722221}
Returns: 1756
1000
77
1000
1000
10000012
57
57
{394190077, 943451949, 973470584, 801746982, 879937367, 48032751, 825612987, 566618972, 283911295, 794487}
Returns: 171
1000
10
1000
1000
10000011
48
46
{229488572, 383410102, 504374996, 920572004, 628161797, 148007509, 270450090, 793500705, 946023670, 85404}
Returns: 34928
1000
91
1000
1000
10000072
28
34
{835802254, 674005191, 218293572, 911260018, 869655125, 474450546, 143487042, 863337842, 571316723, 184401}
Returns: 30768
1000
98
1000
1000
10000002
19
67
{777693498, 551449294, 117527822, 376779895, 286090376, 241411504, 203536487, 639335325, 994948292, 506909}
Returns: 8462
1000
95
1000
1000
10000074
94
42
{459459592, 551577639, 441323612, 750628063, 393832553, 198906759, 19476054, 771048351, 645820101, 848810}
Returns: 3276
1000
87
1000
1000
10000067
18
16
{883698356, 680777158, 562206047, 652285494, 829969922, 487688809, 333123871, 496040315, 264349700, 364615}
Returns: 5920
1000
92
1000
1000
10000011
92
7
{849003255, 318709527, 400892998, 751377156, 952839943, 70506418, 742945059, 899599046, 661185866, 234142}
Returns: 68314
1000
17
1000
1000
10000045
36
92
{545918070, 8291790, 594101739, 652299299, 407803574, 580231033, 104819118, 271305524, 412375803, 101858}
Returns: 368
1000
59
1000
1000
10000078
86
33
{574221224, 141412656, 188226225, 375355840, 222790179, 705592856, 892138451, 338770377, 5225530, 407781}
Returns: 5288
1000
28
1000
1000
10000074
27
91
{951092155, 60802961, 543254587, 261776766, 32868379, 425747539, 339632945, 530847224, 556326166, 175803}
Returns: 12223
1000
45
1000
1000
10000030
76
22
{570016847, 851864833, 802421360, 382907760, 531602252, 229251913, 819221041, 27365704, 716179272, 290715}
Returns: 9128
1000
51
1000
1000
10000028
58
28
{252804448, 130472341, 693970187, 205359006, 971113929, 313283536, 429013654, 376351595, 181844065, 159832}
Returns: 24868
1000
18
1000
1000
10000077
100
17
{940267724, 420983411, 393344627, 229181800, 515084656, 456097489, 857094691, 336442483, 630436004, 230829}
Returns: 31189
1000
65
1000
1000
10000056
57
63
{45298858, 15432366, 42400967, 849374155, 675030412, 39121408, 216637296, 327870818, 858597454, 490997}
Returns: 12633
1000
67
1000
1000
10000030
64
53
{567417026, 765493548, 372070537, 206637202, 489047379, 269379941, 89465430, 532423336, 324106875, 227377}
Returns: 50090
1000
47
1000
1000
10000030
35
35
{110554686, 222326165, 762935517, 254160211, 561434715, 352182137, 685367555, 465072384, 742408145, 567690}
Returns: 315
1000
47
1000
1000
10000089
7
93
{799104341, 973886745, 284600609, 928873087, 554115112, 957921743, 870368057, 177735451, 450245148, 854632}
Returns: 558
1000
82
1000
1000
10000098
93
7
{185380735, 697874629, 122312196, 741212782, 71342324, 863369059, 130992868, 492802028, 99751742, 921551}
Returns: 287
1000
136774004
1000
1000
11470335
22
43
{347685849,637616192,410176409,360423085,161700068,745903136,663336940,45497520,448071037,464261}
Returns: 1423582564
1000
907452439
1000
1000
11169432
56
73
{2696045,679879657,927595811,228711093,400262630,720486024,322658671,960267813,407138193,72835}
Returns: -1
1000
43639122
1000
1000
10846622
67
62
{46770084,492516710,260118329,378012522,187593756,979766492,610184498,736743425,664308447,442859}
Returns: 136282696
1000
12611138
1000
1000
13592349
47
46
{336014846,316872225,88196743,646679846,819175371,434510692,780034883,17412204,101023541,908216}
Returns: 36116888
1000
71414588
1000
1000
15543295
29
32
{229090279,107445428,668634392,495474226,338098950,429559327,912791213,389031854,192090681,160850}
Returns: 1335183720
1000
703700186
1000
1000
12282028
27
68
{307928045,633243116,676495941,120621939,654986835,847187162,768618383,572170169,150458303,16466}
Returns: -1
1000
730161870
1000
1000
11075020
38
82
{875059725,535110547,998888907,85788549,246954258,272401770,461761756,288902814,114904636,666776}
Returns: 6305999500
1000
54902200
1000
1000
18319636
60
50
{192007948,284734203,622009606,58447282,983451898,504008792,83820571,56801794,280873730,813921}
Returns: 669740000
1000
820367008
1000
1000
19049209
84
83
{579029199,796569704,480147949,510565681,468227767,833525252,473267014,83203793,705566791,688901}
Returns: 19153761683
1000
202396377
1000
1000
17580102
28
62
{919786265,66929743,67976805,639052485,569271949,880572479,904878852,104915101,300414836,914051}
Returns: 691697904
1000
666184708
1000
1000
13779780
39
77
{86130488,654095332,348812311,87332704,932190235,560165979,327318384,703242968,435174940,306071}
Returns: 26514990763
1000
19245227
1000
1000
16442488
10
45
{295324350,469633327,932677274,541657314,199014397,592709269,737094810,765055705,667502048,323005}
Returns: -1
1000
104423129
1000
1000
16447309
94
91
{387111907,827452137,277163053,664721554,959874431,754644132,181205816,857830536,910457044,127006}
Returns: -1
1000
733046654
1000
1000
18999525
19
6
{675622837,298553926,971402847,533376990,94630294,202597365,249255009,948194804,950728270,676485}
Returns: 1255362022
1000
816004946
1000
1000
15211545
18
60
{559100839,440283939,423367775,742125683,195400967,151418799,563262805,502748351,757863734,705346}
Returns: 7345863846
1000
304944402
1000
1000
19040072
90
84
{483161357,871913748,883607553,283779938,734587702,678134805,950968762,211704375,500508885,547735}
Returns: 13287507108
1000
463550889
1000
1000
13559408
71
60
{338241321,325738502,651458943,703714631,17807394,89982356,280586941,103701436,265936333,123448}
Returns: -1
1000
166254850
1000
1000
10483628
45
30
{319516272,996246959,195836994,747835096,527191826,333026825,202032282,166092882,811985619,735511}
Returns: 336440130
1000
503543063
1000
1000
10236069
15
5
{896687401,49601864,477807432,24852557,199946429,252565957,993928343,143900457,836031349,659911}
Returns: 156436915
1000
218575170
1000
1000
14541085
48
58
{155465514,836805639,389834200,947976632,306109607,981995121,257364326,698573357,216149550,390898}
Returns: 6645303370
1000
865
1000
1000
14925948
14
1
{941022384,665164998,832232837,700787814,360474953,188668272,561990771,675135672,314462249,247904}
Returns: 14864
1000
2
1000
1000
461438454
17
61
{117794505,985480001,676110883,294627297,329053478,709574787,442917710,630838929,344447970,926694}
Returns: 17044
1000
39
1000
1000
54113586
33
28
{514387901,304310547,504111428,282142840,417088805,83975497,243191463,101297519,582528043,465455}
Returns: 33678
1000
2
1000
1000
448016385
28
17
{512601231,180340520,866564279,463017471,455358471,686734763,387238344,488430086,327691672,887915}
Returns: 21297
1000
141
1000
1000
30457058
27
75
{579171739,145061209,330871464,444657697,49957486,434627035,484253934,754560853,916969711,599242}
Returns: 37500
1000
128
1000
1000
90408540
28
60
{71551841,250374590,285413675,806560488,551551411,705685470,717274263,512674914,839757930,179596}
Returns: 32200
1000
7
1000
1000
194862214
79
73
{532464998,298745412,517435091,65998111,732701605,106618242,292638132,110274854,459045949,718989}
Returns: 79438
1000
139
1000
1000
10560740
59
27
{243089014,307915386,992979055,960408760,589891090,999863400,937299920,363793036,505719573,185518}
Returns: 62726
1000
77
1000
1000
392672384
56
32
{647931993,507141310,757739458,919451198,888555334,688924664,180803787,514390427,573925576,788916}
Returns: 35936
1000
481
1000
1000
90813144
91
29
{683980886,268248387,28758023,25495471,980293318,857886392,796545319,274308714,938939113,795714}
Returns: 104084
1000
7
1000
1000
14406276
62
35
{26347122,625090730,198658596,12243760,723789056,633171270,649131925,938236975,75523193,28402}
Returns: 60970
1000
7
1000
1000
233548851
28
90
{644802407,301305987,348329280,462520568,476529413,865170266,488946470,841537056,527900710,452993}
Returns: 28036
1000
7
1000
1000
57875101
28
33
{952433550,388625706,159770397,527148802,35845336,128953089,804702679,177644030,465216105,306619}
Returns: 28165
1000
3
1000
1000
206341204
46
7
{647202725,500103740,407109343,522725057,790330296,758198892,670932557,447307043,72149268,417772}
Returns: 36800
1000
630
1000
1000
52010268
80
17
{359282863,137216006,229775023,543571817,876486937,50010651,724174785,279104478,728738459,713681}
Returns: 89826
1000
2
1000
1000
496525850
26
89
{529036668,688875873,782579843,534112692,405487721,19682446,675981965,192843315,838500065,984645}
Returns: 25714
1000
2
1000
1000
193296100
2
99
{736614558,490106810,766625585,619562122,810175590,701817034,954467860,161812771,144568755,379540}
Returns: 1400
1000
1
1000
1000
264791731
67
21
{175143072,627352318,718914081,257604322,781809365,73396291,749783719,376456416,197273106,533291}
Returns: 50920
1000
135
1000
1000
45377431
53
48
{277077595,590078768,287818357,507665446,841945343,182976406,955259615,850038191,891577752,608593}
Returns: 58112
1000
951
1000
1000
14042822
30
64
{33160689,685498059,861198948,864598524,427098239,143891784,617816078,779481193,402607656,167655}
Returns: 90096
1000
20575666
1000
1000
138292240
81
3
{986325658,595558435,284926521,124499407,872584030,673030653,803266027,263155471,465824368,818454}
Returns: 61400751
1000
75195134
1000
1000
62962218
41
59
{681610142,204314823,944398656,59883081,501119699,584865111,55086599,886678791,254337123,863946}
Returns: 4379021177
1000
164861798
1000
1000
47726882
71
17
{984121307,518846231,296652371,822341021,537460232,354314825,44648761,193727372,767456743,997115}
Returns: 2796825526
1000
66237580
1000
1000
19289728
1
57
{945220994,250210627,701248263,359342787,530677598,877654840,499369204,864024202,160146553,348363}
Returns: 3747262623
1000
484165513
1000
1000
43324596
70
32
{669400999,471983005,983123831,750226246,496655690,600830117,537469998,184279601,782585833,458090}
Returns: 15128500944
1000
62024295
1000
1000
32793383
89
73
{559963619,257865836,873466613,466662750,234181506,974207025,390136949,50248582,808752312,674337}
Returns: 4526441225
1000
542891668
1000
1000
20699521
77
44
{500409469,523986008,510463146,10208458,481771011,335532568,449363416,857060596,247244545,431387}
Returns: 23832017176
1000
808565249
1000
1000
98547061
32
49
{94544560,574124465,17123606,601435144,307034005,463888465,824266847,736379356,745880979,613066}
Returns: 39572465467
1000
64211332
1000
1000
8324398
26
45
{823847602,592611365,950807435,27952721,713833084,175865266,523185055,529519037,838780460,90052}
Returns: 2876508350
1000
603918455
1000
1000
37426273
5
60
{652691065,497822425,702667293,188389352,623712421,534797236,748756725,527644811,128564627,366217}
Returns: 36029729780
1000
47757282
1000
1000
193182580
81
10
{99709926,322570090,584395653,476836997,206271575,649297376,356032160,878712318,736591524,397352}
Returns: 476917790
1000
135324600
1000
1000
7521632
42
11
{433400646,12167512,611578355,576472748,294501069,855709371,367570173,867345830,724467782,147950}
Returns: 1438139463
1000
893396428
1000
1000
47933993
63
80
{832892844,97219078,161881921,21070413,938599095,673018958,121571678,493788251,438406763,977472}
Returns: 71019748656
1000
337951823
1000
1000
126627628
88
66
{341374426,378972030,738618004,879219213,323527560,314647294,682152888,818735716,275932019,248386}
Returns: 22293893182
1000
566872186
1000
1000
47459500
87
49
{710077988,999152079,841293007,956211261,328423218,324457628,859266952,837971020,867579250,925750}
Returns: 27462446408
1000
300882306
1000
1000
369465138
10
86
{625747674,834265410,324014386,871494355,723670045,344926222,93635279,755588136,13953078,739820}
Returns: 25845650306
1000
166877149
1000
1000
71756192
39
48
{199355301,946120424,389737451,904432532,29919671,40512334,844219919,708060946,406669660,746437}
Returns: 7960939152
1000
967112567
1000
1000
10105337
45
18
{366926288,969541109,30869754,675482573,557860512,155841238,265950710,660608196,284663365,195991}
Returns: 17273117610
1000
676296696
1000
1000
14225856
35
89
{284203475,230344524,994542048,996192230,572177375,582159209,998649413,538829873,787229831,150780}
Returns: 59469393966
1000
231234320
1000
1000
5240650
40
69
{136589789,731044858,146859042,797645787,207001077,466434786,884245869,790434511,960171184,85934}
Returns: 15808148863
1000
17
1000
1000
289714768
32
69
{578029832,239241160,854437981,307493578,16055173,141108156,446275880,761027703,798454647,590012}
Returns: 14701
1000
6
1000
1000
187136088
72
31
{380937950,384755996,446751678,171224380,12736655,308266967,280753587,25710044,897760712,719326}
Returns: 71548
1000
86
1000
1000
44741511
3
89
{960613034,413978792,157638471,959510333,853976057,425446935,573969496,232582730,958589857,624243}
Returns: 10445
1000
7
1000
1000
384685938
10
23
{242207400,728034027,324906379,266975566,168786553,177710496,547956435,219416663,978898311,779549}
Returns: 9802
1000
72
1000
1000
161510144
30
2
{852640874,976515539,157871197,316874764,124755105,926253772,344224739,294944611,12189075,627451}
Returns: 29198
1000
9
1000
1000
18319880
30
82
{207177160,729940450,782970965,253038918,571525988,908113105,587946055,777765039,492442381,35065}
Returns: 8074
1000
212
1000
1000
281800383
5
78
{492567145,686129735,765543524,728180502,678728559,915915527,109079197,528726763,597647292,865239}
Returns: 20678
1000
9
1000
1000
33655980
94
99
{195528049,905763487,598936845,385137756,4633174,486950866,176087790,411976790,777079000,415065}
Returns: 94510
1000
3
1000
1000
176527146
78
12
{111266292,129729614,650987167,605366903,771233437,767291246,147572047,312200302,415689565,960275}
Returns: 76152
1000
3
1000
1000
183234305
24
84
{819771289,272026930,684201862,613264106,268228387,830884245,944558741,646967869,664579616,361690}
Returns: 7368
1000
206527933
1000
1000
36850380
47
11
{752398026,503446986,71588902,642324725,98088068,946193675,473641235,512967302,798142627,806715}
Returns: 2263335109
1000
898057234
1000
1000
33810418
53
6
{85841095,775156984,389571636,342594187,501178615,602625562,644605523,368868034,195718535,626033}
Returns: 5385399318
1000
977431722
1000
1000
60329679
26
60
{860069379,793062057,516485141,978808044,341137669,219987451,38200757,845723110,578269035,618429}
Returns: 58120401320
1000
925924724
1000
1000
37975514
25
98
{522442953,116686841,337458451,933600217,795538368,747979693,600022892,959609399,181107794,753423}
Returns: 88921730785
1000
922677964
1000
1000
69294084
59
54
{448138813,926518595,430513169,214547469,704433912,577775294,243761258,123658688,524713495,445360}
Returns: 48697336652
1000
198352967
1000
1000
102437479
57
24
{805134004,435326650,104464506,631809155,286058134,445876203,624238389,462805862,481505276,209321}
Returns: 4754605944
1000
402996828
1000
1000
301381890
72
87
{420315851,783707750,987643257,255975589,261739540,605181253,447809883,147103525,161829814,606807}
Returns: 35015761479
1000
763032997
1000
1000
142094583
3
3
{827569399,285729932,951173613,522972471,589181833,823381259,359937969,69536473,37167717,902544}
Returns: 2275707972
1000
290563849
1000
1000
39515496
97
14
{127346546,998638687,828928328,257171226,704446477,122967524,786473607,799556990,472057397,761889}
Returns: 4010936252
1000
478369367
1000
1000
183164899
67
84
{84718841,797185190,228929568,201782931,984576178,812795586,276455889,419942808,992190730,359497}
Returns: 40179100716
50
50
1000
400
10000
99
37
{23, 19, 29, 31, 37, 39, 41, 47, 43, 50 }
Returns: 3906