Start: Jan, 29, 2016 12:00:00
2016年1月寒假集训训练赛Round#5
End: Jan, 29, 2016 17:00:00
Time elapsed:
Time remaining:

Getting the same color 1458

Time Limit:  1 s      Memory Limit:   32 MB
Submission:0     AC:0     Score:1

Description

There are n students standing in a line, each of them is wearing clothes of one certain color. There is total m different colors, so each color can be represented by a single number from 0 to m-1.Teacher Wu wants to let his students wear clothes of the same color, so he need some operations. As we all know teacher Wu is an erratic person, if one student is wearing clothes of i-th color and teacher Wu wants to change this student’s color, he only asks this student to wear ((i+1)%m)-th color in one operation. What’s more, in one operation, teacher Wu always let the t consecutive students change their colors. Now here comes the problem, give you the number n,m,t,(n<2000, m<150, t<n)and all students’ clothes color, you are required to calculate the least operations through which all the students can wear clothes of the same color.

Input

In the first of the input, there is a number k<=30, indicating the number of test cases.

For every test case, there is one line containing three positive integers n, m, t, followed by some lines containing n numbers ai (0<=ai<=m-1) indicating the color of the i-th student’s clothes.

Output

For each test case, you are to output two integers in one line, the minimal operations and the color these students wear at last. If there are two colors which can be achieved by the same number of operations, you need to output the small one. It’s guaranteed that you can find some operations getting the same color for all of the input.

Samples

input
1 7 2 3 0 0 1 0 1 0 0
output
3 1