Chef and Mover

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef's dog Snuffles has so many things to play with! This time around, Snuffles has an array A containing N integers: A_{1}, A_{2}, ..., A_{N}.
Bad news: Snuffles only loves to play with an array in which all the elements are equal.
Good news: We have a mover of size D. !
A mover of size D is a tool which helps to change arrays. Chef can pick two existing elements A_{i} and A_{j} from the array, such that i + D = j and subtract 1 from one of these elements (the element should have its value at least 1), and add 1 to the other element. In effect, a single operation of the mover, moves a value of 1 from one of the elements to the other.
Chef wants to find the minimum number of times she needs to use the mover of size D to make all the elements of the array A equal. Help her find this out.
Input
 The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two integers N and D, denoting the number of elements in the array and the size of the mover.
 The second line of each testcase contains N spaceseparated integers: A_{1}, A_{2}, ..., A_{N}, denoting the initial elements of the array.
Output
 For each test case, output a single line containing the minimum number of uses or 1 if it is impossible to do what Snuffles wants.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 10^{5}
 1 ≤ D < N
 1 ≤ A_{i} ≤ 10^{9}
Subtasks
 Subtask 1 (30 points) : N ≤ 10^{3}
 Subtask 2 (70 points) : Original constraints
Example
Input: 3 5 2 1 4 5 2 3 3 1 1 4 1 4 2 3 4 3 5 Output: 3 2 1
Explanation
Testcase 1:
Here is a possible sequence of usages of the mover:
 Move 1 from A_{3} to A_{1}
 Move 1 from A_{3} to A_{1}
 Move 1 from A_{2} to A_{4}
At the end, the array becomes (3, 3, 3, 3, 3), which Snuffles likes. And you cannot achieve this in fewer moves. Hence the answer is 3.
Testcase 2:
Here is a possible sequence of usages of the mover:
 Move 1 from A_{2} to A_{1}
 Move 1 from A_{2} to A_{3}
At the end, the array becomes (2, 2, 2), which Snuffles likes. And you cannot achieve this in fewer moves. Hence the answer is 2.
Testcase 3:
It is impossible to make all the elements equal. Hence the answer is 1.
Author:  berezin 
Editorial  https://discuss.codechef.com/problems/CHEFMOVR 
Tags  adhoc, aug17, berezin, implementation 
Date Added:  14062016 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions