Description

约瑟夫问题是一个经典的问题，现在被某些大学生们演变为一种无聊的“杀人游戏”。游戏规则是这样的：假设 n 个人围成一圈，从第一个人开始，向一个方向数 k 个人，那么数到的那个人就是第一个被“杀”的人，于是他就出局了；同样，再数 k 个人，那么数到的那个人就是第二个人，于是又一个人出局了……直到剩下最后一个人，那么这个人胜出。比如说 n = 4, k = 3 ，那么出局的人的编号依次是 3 2 4 ，最后剩下 1 号胜出。对于出局的人来说，他们不仅要接受“拖出去枪毙五分钟”的惩罚，还要送给最后胜出的人他们对应的值乘以出局轮次的分数。而最后胜出的人的得分便是前面出局人送出的分数之和加上他自身对应值乘以n的和。你的任务就是确定胜出者的编号以及他的得分。

Input

第一行是一个整数 T ，表示有 T 组数据。每组数据两行，第一行是 n 和 k ，其中 1 <= n, k <= 100000 。第二行是 n 个非负整数，分别表示每个人对应的值，每个数小于 10000 。

Output

对于每组数据，在一行内输出最后的获胜者编号及其得分，中间用一个空格隔开。

Sample

Input

2
4 3
1 2 3 4
1 1
1

Output

1 23
1 1

Source: ycc