You helped Dima to have a great weekend, but it's time to work. Naturally, Dima, as all other men who have girlfriends, does everything wrong.

Inna and Dima are now in one room. Inna tells Dima off for everything he does in her presence. After Inna tells him off for something, she goes to another room, walks there in circles muttering about how useless her sweetheart is. During that time Dima has time to peacefully complete k - 1 tasks. Then Inna returns and tells Dima off for the next task he does in her presence and goes to another room again. It continues until Dima is through with his tasks.

Overall, Dima has n tasks to do, each task has a unique number from 1 to n. Dima loves order, so he does tasks consecutively, starting from some task. For example, if Dima has 6 tasks to do in total, then, if he starts from the 5-th task, the order is like that: first Dima does the 5-th task, then the 6-th one, then the 1-st one, then the 2-nd one, then the 3-rd one, then the 4-th one.

Inna tells Dima off (only lovingly and appropriately!) so often and systematically that he's very well learned the power with which she tells him off for each task. Help Dima choose the first task so that in total he gets told off with as little power as possible.


-----Input-----

The first line of the input contains two integers n, k (1 ≤ k ≤ n ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^3), where a_{i} is the power Inna tells Dima off with if she is present in the room while he is doing the i-th task.

It is guaranteed that n is divisible by k.


-----Output-----

In a single line print the number of the task Dima should start with to get told off with as little power as possible. If there are multiple solutions, print the one with the minimum number of the first task to do.


-----Examples-----
Input
6 2
3 2 1 6 5 4

Output
1

Input
10 5
1 3 5 7 9 9 4 1 8 5

Output
3



-----Note-----

Explanation of the first example.

If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as k = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12. 

Explanation of the second example.

In the second example k = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.

Difficulty: interview

Starter code:

Solutions:
n,k=list(map(int,input().split()))

A=list(map(int,input().split()))
L=[]
for i in range(k):
    s=0
    for j in range(i,n,k):
        s+=A[j]
    L.append(s)

x=min(L)

print(L.index(x)+1)
        


def read():
    n, k = list(map(int, input().split()))
    powers = list(map(int, input().split()))
    return n, k, powers


def get_min_power(n, k, powers):
    start_task = 0
    mins = []
    for i in range(k):
        s = 0
        for j in range(i, n, k):
            s += powers[j]
        mins.append(s)
    task = min(mins)
    return mins.index(task) + 1

def main():
    n, k, powers = read()
    print(get_min_power(n, k, powers))


def __starting_point():
    main()
__starting_point()

n, k = map(int, input().split())

a = list(map(int, input().split()))

s = [0 for i in range(k)]

for i in range(len(a)):	s[i % k] += a[i]

j = 0
for i in range(k):
	if s[i] < s[j]: j = i

print(j + 1)

__author__ = 'Lipen'

def actions(n, k, a):
	smin = -1
	answer = 1

	for i in range(k):
		s = sum(a[i::k])
		if s<smin or smin==-1:
			smin=s
			answer=i+1

	return answer

def main():
	n,k = list(map(int, input().split()))
	a = list(map(int, input().split()))

	print(actions(n, k ,a))

def __starting_point(): main()
__starting_point()

data = input().split(" ")
tasks = int(data[0])
k = int(data[1])
cost = input().split(" ")
cost = [int(x) for x in cost]
minCost = sum(cost)
ans = 1
for i in range(k):
	start = i
	c = 0
	for j in range(start, tasks, k):
		c += cost[j]
	if c < minCost:
		minCost = c
		ans = i+1
print(ans)




n,k = list(map(int, input().split()))
arr = [int(x) for x in input().split(' ')]
num = 10000000000
for i in range(0,k):
    sum = 0
    for j in range(0,int(n/k)):
        sum += arr[j*k+i]
    if sum < num:
        num = sum
        ans = i + 1
print(str(ans))


n, k = map(int, input().split())
t = list(map(int, input().split()))
print(min((sum(t[i :: k]), i) for i in range(k))[1] + 1)

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=1000000000
ans=1
for i in range(k):
    mt=0
    for j in range(i,n,k):
        mt+=a[j]
    if mt<m:
        m=mt
        ans=i+1
print(ans)

n, k = (int(x) for x in input().split())

s = input()
deals = [int(x) for x in s.split()]

punish = [0 for x in range(k)]

for i in range(n):
    punish[i%k] += deals[i]

print(punish.index(min(punish))+1)

n, k = map(int, input().split())
a = list(map(int, input().split()))
start_job = 1
min_hate = 1000 * n + 1
for i in range(k):
  hate = sum(a[i::k])
  if hate < min_hate:
    start_job = i + 1
    min_hate = hate
print(start_job)

import sys
import math

n, k = [int(x) for x in (sys.stdin.readline()).split()]
an = [int(x) for x in (sys.stdin.readline()).split()]

vmin = 1000000000
rez = 0
for i in range(k):
    vsum = 0
    vvmin = 1001
    for j in range(i, n, k):
        vsum += an[j]
    
    if(vsum < vmin):
        vmin = vsum
        rez = i + 1
    
print(rez)
    


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
from collections import *
setrecursionlimit(10**7)
dX= [-1, 1, 0, 0,-1, 1,-1, 1]
dY= [ 0, 0,-1, 1, 1,-1,-1, 1]
RI=lambda: list(map(int,input().split()))
RS=lambda: input().rstrip().split()
#################################################
n,k=RI()
v=[0]*k
a=RI()
for i in range(n):
    v[i%k]+=a[i]
minInd=0
for i in range(k):
    if v[i]<v[minInd]:
        minInd=i
print(minInd+1)






def main():
    n, k = list(map(int, input().split()))
    aa = list(map(int, input().split()))
    res = [sum(aa[i::k]) for i in range(k)]
    print(min(list(range(k)), key=res.__getitem__) + 1)


def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
num = list(map(int, input().split()))
dp = [0] * (2 * n)
for i in range(n - 1, -1, -1):
    dp[i] = dp[i + k] + num[i]
ans = 2**100
for i in range(0, k):
    ans = min(ans, dp[i])
print(dp.index(ans) + 1)

n, k = map(int, input().split())
a = list(map(int, input().split()))
ind = [x for x in range(0,n,k)]
m=1e8
mi=0
for i in range(0,k):
    x=sum(a[i+j] for j in ind)
    if x<m:
        m=x
        mi=i 
print(mi+1)

n, k = map(int, input().split())
xs = list(map(int, input().split()))

res = (10**9, -1)

for i in range(k):
	s = 0
	for j in range(i, n, k):
		s+=xs[j]
	res = min(res, (s, i+1))

print(res[1])

[n,k] = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]

m = -1
valm = 10**10

for i in range(k):
    temp = sum([A[(k*j + i)%n] for j in range(n//k)])
    if temp < valm:
        valm = temp
        m = i

print(m+1)




n, k = map(int, input().split())
t = list(map(int, input().split()))
print(min((sum(t[i :: k]), i) for i in range(k))[1] + 1)

n,k=map(int,input().split())
a=list(map(int,input().split()))*2
for i in range(n+n-k-1, -1,-1):a[i]+=a[i+k]
mi,mm=0,float("inf")
for i in range(n):
    x=a[i]-a[i+n]
    if mm>x:mi=i;mm=x
print(mi+1)


"""
6 2
3 2 1 6 5 4
"""

n, k = map(int, input().split())
l = [int(x) for x in input().split()]
ans = []
minn = 123456567
key = 0
for i in range(k):
    j = i
    summ = 0
    while j < n:
        summ += l[j]
        j += k
    if(summ < minn):
        minn = summ
        key = i
print(key + 1)



n, k = list(map(int, input().split()))

t = list(map(int, input().split()))

print(min((sum(t[i :: k]), i) for i in range(k))[1] + 1)



# Made By Mostafa_Khaled


n, k = list(map(int, input().split()))

t = list(map(int, input().split()))

print(min((sum(t[i :: k]), i) for i in range(k))[1] + 1)



# python3
import sys, threading, os.path
import collections, heapq, math, bisect
import string

sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)


def main():
    if os.path.exists('in.txt'):
        input = open('in.txt', 'r')
    else:
        input = sys.stdin
    # --------------------------------INPUT---------------------------------
    n, k = list(map(int, input.readline().split()))
    lis = list(map(int, input.readline().split()))

    lis1 = [0 for i in range(k)]



    case1 = n/k
    ans1, ans2 = 10000000, 0
    for i, x in enumerate(lis):
        lis1[i%k]+= lis[i]

    ans1 = min(lis1)
    for i,x in enumerate(lis1):
        if x == ans1:
            ans2 = i+1
            break

    output = ans2
    # -------------------------------OUTPUT----------------------------------
    if os.path.exists('out.txt'):
        open('out.txt', 'w').writelines(str(output))
    else:
        sys.stdout.write(str(output))


def __starting_point():
    main()
# threading.Thread(target=main).start()

__starting_point()