Ma thuật thực sự rất đơn giản, bạn chỉ cần muốn điều gì bạn sẽ có được nó.

Rex và người bạn pháp sư Zatara của mình đang khám phá khu rừng phù thủy vào đêm Halloween. Khi Rex vô tình phát hiện một mảng các số kỳ diệu ~a~ có độ dài ~n~, nó đưa anh ta vào một thế giới khác.

Rex nhớ rằng Zatara đã đưa cho anh ta hai số nguyên ~p~ và ~q~ để sử dụng trong tình huống như này. Khi sử dụng các số nguyên này, Rex có thể sửa đổi mảng ~a~ như sau:

• Tối đa ~p~ lần, thực hiện thao tác sau:
  1. Chọn hai phần tử ~x~ và ~y~ từ ~a~, xóa cả hai phần tử này khỏi ~a~, và chèn ~x + y~ vào ~a~.
  2. Thao tác này chỉ có thể thực hiện nếu ~a~ có ít nhất hai phần tử.
• Tối đa ~q~ lần, thực hiện thao tác sau:
  1. Chọn hai phần tử ~x~ và ~y~ từ ~a~, xóa cả hai phần tử này khỏi ~a~, và chèn ~x - y~ vào ~a~.
  2. Thao tác này chỉ có thể thực hiện nếu ~a~ có ít nhất hai phần tử.

Lưu ý rằng mỗi thao tác làm giảm kích thước của ~a~ đi một.

Hai loại thao tác (cộng và trừ) có thể thực hiện theo bất kỳ thứ tự nào, miễn là tối đa ~p~ thao tác cộng và ~q~ thao tác trừ được thực hiện.

Gọi ~b~ là mảng số kỳ diệu sau khi thực hiện một số lượng thao tác. Để trở lại thế giới ban đầu của mình, Rẽ phải tìm giá trị lớn nhất có thể của:

$$\max{(b)} - \min{(b)}$$

trên tất cả các trường hợp khả thi của ~b~. Bạn có thể giúp Rex tìm giá trị này không?

Input Specification

• Dòng thứ nhất chứa số nguyên ~t~ ~(t \le t \le 10^5)~ - Số lượng truy vấn.
• Mỗi truy vấn:
  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ - Kích thước mảng.
  • Dòng thứ hai chứa hai số nguyên ~p~, ~q~ ~(0 \le p, q \le n - 1)~ - Số lượng thao tác cộng và trừ tối đa Rex có thể thực hiện.
  • Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9 \ \forall \ 1 \le i \le n)~.

Tổng của ~n~ trong tất cả các trường hợp thử sẽ không vượt quá ~3 \times 10^5~, tức ~\displaystyle \sum_{k = 1}^{t} n_k \le 3 \times 10^5~.

Output Specification

• Gồm ~t~ dòng tương ứng với ~t~ truy vấn. Với mỗi truy vấn, in ra duy nhất một số nguyên là số có thể đưa Rex trở lại thế giới ban đầu.

Sample Cases

Input #1:

3 2
0 0
5 1
6
1 2
8 -1 -4 2 6 -3
7
6 6
-2 -4 2 -2 -3 -1 -1

Output #1:

4
23
15

Explanation #1:

• Mảng ~a = [8; -1; -4; 2; 6; -3]~. Dãy thao tác sau có thể được thực hiện:
  1. Chọn ~2~ và ~-3~, loại bỏ chúng và chèn ~2 - (-3) = 5~ vào mảng. Khi đó mảng là: ~[8; -1; -4; 6; 5]~.
  2. Chọn ~8~ và ~5~, loại bỏ chúng và chèn ~8 + 5 = 13~ vào mảng. Khi đó mảng là: ~[13; -1; -4; 6]~.
  3. Chọn ~-4~ và ~6~, loại bỏ chúng và chèn ~(-4) - 6 = -10~ vào mảng. Khi đó mảng là: ~[13; -1; -10]~.
• Hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất trong mảng này là ~13 - (-10) = 23~.