Chef's dog Snuffles has so many things to play with! This time around, Snuffles has an array A containing N integers: A1, A2, ..., AN.
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 Ai and Aj 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 space-separated integers: A1, A2, ..., AN, 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 ≤ 105
- 1 ≤ D < N
- 1 ≤ Ai ≤ 109

-----Subtasks-----
- Subtask 1 (30 points) : N ≤  103
- 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 A3 to A1
- Move 1 from A3 to A1
- Move 1 from A2 to A4
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 A2 to A1
- Move 1 from A2 to A3
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.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
tc = int(input())
for case in range(tc):
	(n, d) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	sm = sum(a)
	f = True
	if sm % n == 0:
		avg = sm / n
		for i in range(d):
			tmp_sm = 0
			tmp_n = 0
			for j in range(i, n, d):
				tmp_sm = tmp_sm + a[j]
				tmp_n += 1
			if tmp_sm % tmp_n == 0:
				if avg != tmp_sm / tmp_n:
					f = False
					break
			else:
				f = False
				break
	else:
		f = False
	if f:
		ans = 0
		cur = 0
		for i in range(d):
			for j in range(i, n, d):
				cur = cur + avg - a[j]
				ans = ans + abs(cur)
		print(ans)
	else:
		print(-1)


for _ in range(eval(input())):
	(n, d) = list(map(int, input().strip().split()))
	l = list(map(int, input().strip().split()))
	main_flag = 0
	final_count = 0
	total = sum(l)
	if total % n != 0:
		print(-1)
		continue
	else:
		expected_value = total / n
		for i in range(d):
			delta = []
			j = i
			while j < n:
				delta.append(expected_value - l[j])
				j += d
			diff = 0
			curr_diff = 0
			flag = 0
			count = 0
			for k in range(len(delta)):
				if diff != 0 and flag:
					count += abs(diff)
				if delta[k] != 0:
					diff += delta[k]
					if diff == 0:
						flag = 0
					else:
						flag = 1
			if flag == 0:
				final_count += count
			else:
				main_flag = 1
				break
	print(final_count if not main_flag else -1)


import sys
import string
import cmath
import math
T = int(input())
for i in range(T):
	(N, D) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	s = sum(A)
	ans = 0
	if s % N == 0:
		x = s / N
		for j in range(N - D):
			if A[j] < x:
				A[j + D] -= x - A[j]
				ans += x - A[j]
				A[j] = x
			elif A[j] > x:
				A[j + D] += A[j] - x
				ans += A[j] - x
				A[j] = x
		for j in range(N):
			if A[j] != x:
				ans = -1
	else:
		ans = -1
	print(ans)


T = int(input())
for i in range(0, T):
	(N, D) = input().split()
	N = int(N)
	D = int(D)
	L = [int(i) for i in input().split()]
	A = 0
	flag = ''
	MOVE = 0
	s = 0
	s = sum(L)
	if s % len(L) != 0:
		print(-1)
		flag = False
	else:
		A = s / len(L)
		for i in range(N):
			if L[i] > A and i + D < N:
				diff = L[i] - A
				L[i] = L[i] - diff
				L[i + D] = L[i + D] + diff
				MOVE = MOVE + diff
			elif L[i] < A and i + D < N:
				diff = A - L[i]
				L[i] = L[i] + diff
				L[i + D] = L[i + D] - diff
				MOVE = MOVE + diff
		for i in L:
			if i != A and flag != False:
				print(-1)
				flag = False
				break
		if flag != False:
			print(int(MOVE))


t = int(input())
while t > 0:
	(n, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	sum1 = sum(arr)
	if sum1 % n != 0:
		print('-1')
	else:
		ans = 0
		average = sum1 / n
		for i in range(0, n):
			if arr[i] != average and i + d >= n:
				ans = -1
				break
			else:
				y = arr[i] - average
				ans += abs(y)
				if i + d < n:
					arr[i + d] += y
		print(ans)
	t = t - 1


import sys

def solve():
	(N, D) = list(map(int, sys.stdin.readline().split()))
	A = list(map(int, sys.stdin.readline().split()))
	V = None
	M = 0
	for i in range(D):
		X = A[i::D]
		if sum(X) % len(X) != 0:
			return -1
		v = sum(X) / len(X)
		if V and V != v:
			return -1
		for i in range(len(X)):
			c = X[i] - v
			M += abs(v - X[i])
			if i < len(X) - 1:
				X[i + 1] += c
	return M
T = int(sys.stdin.readline())
for _ in range(T):
	print(solve())


n = int(input())
while n != 0:
	(no, b) = list(map(int, input().split()))
	v = list(map(int, input().split()))
	number = sum(v) / no
	count = 0
	flag = True
	values = []
	if sum(v) % no != 0 or b > no:
		flag = False
	for i in range(b):
		vals = []
		for j in range(i, len(v), b):
			vals.append(v[j])
		values.append(vals)
	for i in range(len(values)):
		if sum(values[i]) / len(values[i]) != number:
			flag = False
	if flag:
		for i in range(no - b):
			y = v[i] - number
			v[i] -= y
			v[i + b] += y
			count += abs(y)
		print(count)
	else:
		print('-1')
	n = n - 1


t = int(input())
for i0 in range(t):
	(n, d) = list(map(int, input().strip().split(' ')))
	a = list(map(int, input().strip().split(' ')))
	flag = 0
	count = 0
	if sum(a) % len(a) != 0:
		flag = 1
	else:
		x = sum(a) / len(a)
		for i in range(len(a) - d):
			if flag != 1:
				if a[i] == x:
					pass
				elif a[i] < x:
					j = 1
					y = x - a[i]
					while a[i] != x:
						if a[i + j * d] - y >= 0:
							a[i] = x
							a[i + j * d] -= y
							count += j * y
							break
						if i + j * d < len(a):
							j += 1
						else:
							flag = 1
							break
				elif i + d < len(a):
					count += a[i] - x
					a[i + d] += a[i] - x
					a[i] = x
				else:
					flag = 1
			else:
				break
	if a.count(x) != len(a):
		flag = 1
	if flag:
		print(-1)
	else:
		print(count)


w = int(input())

def checkEqual(lst):
	return lst[1:] == lst[:-1]
v = 0
while v < w:
	sign = 0
	v += 1
	[n, d] = [int(i) for i in input().split()]
	arr = list(map(int, input().split()))
	my_dict = {}
	i = 0
	while i < d:
		my_dict[i] = list()
		j = 0
		while i + j < n:
			my_dict[i].append(arr[i + j])
			j += d
		i += 1
	mean = float(sum(arr)) / len(arr)
	if mean % 1 != 0.0:
		print(-1)
		continue
	else:
		means = []
		for i in range(d):
			means.append(sum(my_dict[i]) / len(my_dict[i]))
		if not checkEqual(means):
			print(-1)
			continue
		steps = 0
		for x in range(d):
			for y in range(len(my_dict[x])):
				if my_dict[x][y] < mean:
					steps += mean - my_dict[x][y]
					my_dict[x][y + 1] -= mean - my_dict[x][y]
					my_dict[x][y] = mean
				elif my_dict[x][y] > mean:
					steps += my_dict[x][y] - mean
					my_dict[x][y + 1] += my_dict[x][y] - mean
					my_dict[x][y] = mean
				elif my_dict[x][y] == mean:
					continue
				else:
					print('impossible')
		print(int(steps))


t = eval(input())
for _ in range(t):
	(n, d) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	avg = sum(a) / n
	res = 0
	for i in range(n - d):
		if a[i] < avg:
			diff = avg - a[i]
			a[i] += diff
			a[i + d] -= diff
			res += diff
		elif a[i] > avg:
			diff = a[i] - avg
			a[i] -= diff
			a[i + d] += diff
			res += diff
	flag = True
	for i in range(n):
		if a[i] != avg:
			flag = False
			break
	if flag:
		print(res)
	else:
		print(-1)


T = eval(input())

def is_equal(ar, D):
	N = len(ar)
	last = -1
	for i in range(D):
		count = 0
		ans = 0
		for j in range(i, N, D):
			ans += ar[j]
			count += 1
		if ans % count != 0:
			return -1
		if last == -1:
			last = ans / count
		elif last != ans / count:
			return -1
	return last

def solve(ar, D, equal):
	ans = 0
	N = len(ar)
	for i in range(D):
		for j in range(i, N - D, D):
			diff = ar[j] - equal
			ar[j] -= diff
			ar[j + D] += diff
			ans += abs(diff)
	return ans
for _ in range(T):
	(N, D) = list(map(int, input().split(' ')))
	ar = list(map(int, input().split(' ')))
	ans = is_equal(ar, D)
	if ans == -1:
		print(-1)
	else:
		print(solve(ar, D, ans))


t = int(input())
while t != 0:
	(n, d) = list(map(int, input().strip().split()))
	a = input().strip()
	a = a.split()
	c = 0
	b = []
	c = sum((int(i) for i in a))
	if c % n != 0:
		print('-1')
	else:
		m = 0
		b += n * [c / n]
		f = 1
		for i in range(0, len(a) - d):
			if a.count(a[0]) == len(a):
				f = 0
				break
			elif int(a[i]) > int(b[i]):
				temp = int(a[i]) - int(b[i])
				a[i] = int(b[i])
				a[i + d] = int(a[i + d]) + temp
				m = m + temp
			elif int(a[i]) < int(b[i]):
				temp = int(b[i]) - int(a[i])
				a[i] = int(b[i])
				a[i + d] = int(a[i + d]) - temp
				m = m + temp
			if i == len(a) - d - 1 and all((int(x) == int(a[0]) for x in a)):
				f = 0
		if f == 0:
			print(m)
		else:
			print('-1')
	t = t - 1


t = int(input())
for i in range(t):
	(n, d) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	sum = 0
	for j in arr:
		sum += j
	if sum % n != 0:
		print('-1')
	else:
		tmp = 0
		avg = sum / n
		num = [0] * d
		cnt = [0] * d
		for j in range(n):
			num[j % d] += arr[j]
			cnt[j % d] += 1
		for j in range(d):
			if num[j] % cnt[j] != 0 or num[j] / cnt[j] != avg:
				tmp = 1
				break
		if tmp:
			print('-1')
		else:
			ans = 0
			for j in range(n):
				if arr[j] < avg:
					tmp = avg - arr[j]
					ind = j + d
					if ind < n and arr[ind] > 0:
						ans += tmp
						arr[j] = avg
						arr[ind] -= tmp
				elif arr[j] > avg:
					tmp = arr[j] - avg
					ind = j + d
					if ind < n:
						ans += tmp
						arr[j] = avg
						arr[ind] += tmp
			print(ans)


t = int(input())
for _ in range(t):
	(N, D) = list(map(int, input().split()))
	L = list(map(int, input().split()))
	flag = True
	avg = None
	for x in range(D):
		temp = x
		sumA = L[x]
		numElem = 1
		while temp + D < N:
			numElem += 1
			sumA += L[temp + D]
			temp += D
		if sumA % numElem:
			flag = False
			break
		if avg == None:
			avg = sumA / numElem
		elif avg != sumA / numElem:
			flag = False
			break
	if flag:
		res = 0
		tempDiff = 0
		for x in range(D):
			temp = x
			tempDiff = L[x] - avg
			while temp + D < N:
				L[temp + D] += tempDiff
				if tempDiff < 0:
					res -= tempDiff
				else:
					res += tempDiff
				temp += D
				tempDiff = L[temp] - avg
		print(res)
	else:
		print(-1)


def main():
	t = eval(input())
	while t > 0:
		(n, d) = list(map(int, input().split()))
		l = list(map(int, input().split()))
		count = 0
		k = sum(l)
		if k % n != 0:
			print('-1')
		else:
			r = sum(l) / n
			for i in range(n - d):
				if l[i] < r:
					count += r - l[i]
					l[i + d] -= r - l[i]
					l[i] = r
				else:
					count += l[i] - r
					l[i + d] += l[i] - r
					l[i] = r
			if l.count(r) == n:
				print(count)
			else:
				print('-1')
		t -= 1
main()


t = eval(input())
for _ in range(t):
	(n, d) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = sum(a)
	if s % n != 0:
		print(-1)
		continue
	each = s / n
	(ans, ok) = (0, True)
	for i in range(d):
		(cur, rem) = (i, 0)
		while cur < n:
			rem = a[cur] + rem - each
			ans += abs(rem)
			cur += d
		if rem != 0:
			ok = False
			break
	print(ans if ok else -1)


import sys
t = int(sys.stdin.readline().strip())
while t:
	(n, d) = list(map(int, sys.stdin.readline().strip().split(' ')))
	nums = list(map(int, sys.stdin.readline().strip().split(' ')))
	a = False
	s = 0
	for i in nums:
		s = s + i
	avg = s // n
	ans = 0
	count = 0
	if s % n != 0:
		ans = -1
	else:
		arr = [avg] * n
		for i in range(len(arr) - d):
			k = arr[i] - nums[i]
			if k != 0:
				arr[i] = arr[i] - k
				arr[i + d] = arr[i + d] + k
				count += abs(k)
		for i in range(len(arr)):
			if arr[i] != nums[i]:
				ans = -1
				a = True
				break
		if a != True:
			ans = count
	print(ans)
	t -= 1