Flower Pots FLOWERPO

All submissions for this problem are available.<h3>Read problems statements in mandarin chinese and russian.</h3>

The Chef wants to celebrate Independence Day with fireworks. He's particularly fond of Flower Pot crackers (or Fountain fireworks) which spew out fire around them:

He's decided that he wants a row of N of these crackers. He has decided where exactly each of them will be placed. In particular, we can say that the crackers will be on a line with coordinates A₁, A₂, ..., A_N.

These crackers come in many strengths. For any integer S ≥ 0, unlimited number of crackers of strength S are available for sale at the shop. The larger the strength of a cracker, the higher and wider it will spew fire. In particular, a cracker whose strength is s, and which is placed at coordinate X will spew fire everywhere in the interval [X - S, X + S], both end points inclusive. The cost of a cracker of strength S is S².

Chef wants to decide what the strengths of each of the N crackers should be. He wants to light up only one of the N crackers, the C-th one, which is as coordinate A_C. The other N - 1 crackers should light up automatically. That is, suppose the cracker at A_C has a strength of S_C, then it will light up any unlit cracker in the interval [A_C - S_C, A_C + S_C]. And these should then explode and light up more crackers, etc. This should continue until all the crackers are lit. Also, each cracker, once lit, takes 1 second to explode. Once it explodes, it instantaneously lights up all the unlit crackers in its interval. And Chef wants all the crackers to be lit up (not necessarily explode) within B seconds after he has lit A_C. That is, if a cracker is lit up B seconds after he has lit A_C, even though it has not exploded, Chef is happy with it, and it is valid.

Find out the minimum amount Chef has to spend in buying the crackers so as to achieve his goals.

Input

• The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each testcase contains three integers, N, B and C, which denote the number of crackers, the time within which all the crackers should be lit up, and the index of the cracker which he will light up, respectively.
• The next line contains N integers: A₁, A₂, ..., A_N.

Output

• For each test case, output a single line containing a single integer which should be the minimum total cost.

Constraints

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 3000
• 1 ≤ B ≤ 3000
• 1 ≤ C ≤ N
• 1 ≤ N * B ≤ 30000
• 1 ≤ A₁ < A₂ < ... < A_N ≤ 10⁸

Subtasks

• Subtask 1 (20 points) : C = 1
• Subtask 2 (80 points) : Original constraints

Example

Input:
1
5 2 4
2 4 10 15 18

Output:
89

Explanation

One optimal way is to choose the strengths of the crackers as (0, 0, 8, 5, 0). That is, the leftmost cracker has strength 0, the next has 0, the next has 8, etc. Now, Chef lights up the 4-th cracker.

After 1 second, it explodes and it lights up all the unlit crackers in its interval. Because its strength is 5, its interval would be [15 - 5, 15 + 5] = [10, 20]. So after 1 second, the third and fifth cracker are also lit.

After one more second (ie. 2 seconds from when Chef lit up the 4- cracker), those two explode. Because the fifth's strength is 0, it doesn't affect anything else. But the third cracker's strength is 8, and hence it lights up all unlit crackers in the interval [10 - 8, 10 + 8] = [2, 18]. Note that this includes all the crackers. Hence all the unlit crackers are lit up instantaneously, and so all the five crackers have been lit within 2 seconds of Chef lighting up the one cracker. Thus this is a valid configuration. Also note that the first and second crackers have only been lit, and they are yet to explode. But that is fine.

The total cost of this is 0² + 0² + 8² + 5² + 0² = 89. You cannot get a lower cost, and hence this is the answer.