Dhoni is in a Dilemma
All submissions for this problem are available.
Dhoni is fondly known as Mr. Cool but he is in a lot of trouble these days. The opposing batsmen are constantly scoring runs. Thus Dhoni is worried about when to take a powerplay such that runs scored by the opposite teams can be minimized.
More precisely, he wants to take a powerplay in those stretch of the overs in which XOR of the runs (in those overs) scored by the opposing team is minimum. Now Dhoni is able to guess the strategy of opposition teams and the amount of runs they intend to score in each over. He has found out that runs scored by the opposing team from over 'i' (Oi) to over 'j' (Oj) is the XOR (not sum) of all runs between Oi and Oj (i, j inclusive). The match consists of N overs for each team and there is one single powerplay of Z overs.
Note : The runs scored in a powerplay from over 'i' to over 'j' is NOT sum but XOR of the runs scored in the individual overs. And if there is more than one possibility of choosing a powerplay then prefer the later overs.
Can you help the Mr. Cool in deciding when to take the powerplay?
- First line of the input will have T (number of test cases).
- Then for each test case first line will have two integers N and Z.
- The second line (of each test case) will have a list of N integers [O1, O2, ..., ON] which are the runs the opposing team intends to score in that respective over of the match.
- For each test case, output a single integer denoting from which over Dhoni should start the powerplay.
- 1 ≤ T ≤ 100
- 1 ≤ Z ≤ N ≤ 104
- 0 ≤ Oi ≤ 1012
Input 1 3 2 1 2 3 Output 2
Runs in over 1 and 2 : 1 XOR 2 = 3 Runs in over 2 and 3 : 2 XOR 3 = 1 Since runs scored from over 1 to 2 is more than those in over 2 to 3, Dhoni should take powerplay from 2nd over itself.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions