Danh sách công việc

Có $n$ công việc được đánh số từ $1$ đến $n$. Công việc thứ $i$ có độ nặng nhắc nhở là $a_i$.

Bạn phải làm hết cả $n$ công việc theo thứ tự vòng tròn: chọn một công việc bắt đầu $s$, rồi lần lượt làm $s,s+1,\dots ,n,1,2,\dots ,s-1$. Ví dụ với $n=6$ và $s=5$, thứ tự làm việc là $5,6,1,2,3,4$.

Trong lúc bạn làm việc, người giám sát chỉ có mặt ở phòng theo chu kỳ: họ nhắc nhở bạn ở công việc đầu tiên bạn làm, rồi rời đi đủ lâu để bạn làm yên ổn $k-1$ công việc tiếp theo, sau đó quay lại và nhắc nhở ở công việc kế tiếp, cứ thế cho đến hết. Nói cách khác, nếu tính theo thứ tự thực hiện thì các công việc bị nhắc nhở là công việc thứ $1,k+1,2k+1,\dots$

Tổng độ nặng bạn phải chịu là tổng các $a_i$ của những công việc bị nhắc nhở. Hãy chọn công việc bắt đầu $s$ sao cho tổng này nhỏ nhất.

Dữ liệu đảm bảo $n$ chia hết cho $k$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất: số hiệu công việc bắt đầu $s$ cho tổng độ nặng nhỏ nhất. Nếu có nhiều đáp án, in ra $s$ nhỏ nhất.

Ràng buộc

• $1\le k\le n\le {10}^5$
• $1\le a_i\le {10}^3$
• $n$ chia hết cho $k$

Ví dụ