The Kingdom ALPHA has n warehouses of golds located on a straight line and are numbered 1, 2, ..., n. The warehouse i has amount of ai (ai is non-negative integer) and is located at coordinate i (all i = 1;.....n). The King of ALPHA opens a competition for hunters who are responsible to Fi?nd a subset of gold warehouses having largest total amount of golds with respect to the condition that the distance between two selected warehouses must be less than or equal to L1 and greater or equal to L2.

Input

The input consists of following lines:

*Line 1 contains the number T of tests. The test t (t = 1; 2; : : : ; T) is given in the following 2 lines: { Line 2t contains n, L1, and L2 (1 = < n = < 100000; 1 = < L1 = < L2 = < n) { Line 2t+1 contains n integers a1; a2;....an

Output

The output consists of T lines, line t contains only one single integer denoting the total amount of golds of selected warehouses of the test t (t = 1; 2;......, T).

Example

Input 2

6 2 3

3 5 9 6 7 4

10 2 8

1 1 1 2 0 0 0 2 2 1

Output

19 6

Explanation

The selected warehouses of test 1 are 1, 3, 5 and the total amount of golds is 19. The selected warehouses of test 2 are 2, 4, 8, 10, and the total amount of golds is 6.