你帮助 Dima 度过了一个愉快的周末,但现在是工作时间了。当然,迪马和所有其他有女朋友的男人一样,做的每件事都是错的。
Inna 和 Dima 现在在一间房间里。伊娜责备迪玛在她面前所做的一切。伊娜因某件事斥责了他之后,她去了另一个房间,绕着圈子走到那里,嘀咕着她的爱人是多么无用。在那段时间里迪玛有时间平静地完成k-1个任务。然后伊娜回来并告诉迪玛他在她面前要做的下一个任务,然后又去了另一个房间。它会一直持续到迪马完成他的任务为止。
总的来说,迪玛有 n 个任务要做,每个任务都有一个从 1 到 n 的唯一编号。迪马喜欢秩序,所以他从某项任务开始连续执行任务。例如,如果迪马总共有6个任务要做,那么,如果他从第5个任务开始,顺序是这样的:迪马先做第5个任务,然后是第6个任务,然后是第1个任务,然后是第2个任务,然后是第3个任务,然后是第4个任务。
伊娜(Inna)如此频繁且系统地责备迪玛(只是充满爱意且恰当!),以至于他非常了解她在每项任务中责备他的力量。帮助迪马选择第一个任务,这样他就可以用尽可能小的力量被训斥。
输入
输入的第一行包含两个整数 n, k (1 ≤ k ≤ n ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 103),其中 ai 是 Inna 告诉 Dima 的权力,如果 Dima 正在执行第 i 个任务时她在房间里。
保证n能被k整除。
输出
在一行中打印 Dima 应该开始的任务编号,以便以尽可能少的功率被告知。如果有多个解决方案,则打印第一个要做的任务数量最少的解决方案。
示例
输入 #1
6 2 3 2 1 6 5 4
输出 #1
1
输入 #2
10 5 1 3 5 7 9 9 4 1 8 5
输出 #2
3
注意
第一个示例的说明。
如果 Dima 从第一个任务开始,Inna 用权力 3 告诉他,然后 Dima 可以再做一项任务(当 k = 2),然后 Inna 用权力 1 告诉他第三个任务,然后她用权力 5 告诉他第五个任务。因此,Dima 被告知总权力 3 + 1 + 5 = 9。例如,如果 Dima 从第二个任务开始,那么 Inna 会告诉他任务 2、4 和 6,功率为 2 + 6 + 4 = 12。
第二个示例的说明。
在第二个示例中,k = 5,因此,Dima 设法在训斥会话之间完成 4 项任务。因此,Inna 会告诉 Dima 任务 1 和 6(如果他从 1 或 6 开始)、2 和 7(如果他从 2 或 7 开始)等等。最佳答案是从任务3或8开始,3的数字较小,所以答案是3。