Getting the same color

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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.

Sample Input

1
7 2 3
0 0 1 0 1 0 0

Sample Output

3 1

Hint

Output details You need three operations to let all the students wear the same color (the color 1):
 
   0  1  1   1
   0  1  1   1
   1  0  1   1
   0  0  1   1
   1  1  0   1
   0  0  0   1
   0  0  0   1


Source

2008湖南大学校赛