Qurbongoh

Input

Birinchi qator bitta butun son $t$ (1 \le t \le 10) – test hollari soni.

Har bir test holining birinchi qatori uchta butun son $n$, $m$, $k$ (1 \le m \le n \le 10^5) (1 \le k \le 10^9) ni o'z ichiga oladi.

Har bir test holining ikkinchi qatori $n$ ta bo'sh joy bilan ajratilgan butun sonlar a_1,a_2,..,a_n (1 \le a_1,a_2,..,a_n \le 10^9) – massiv $a$.

Barcha testlar uchun $n$ lar yig'indisi 2 \cdot 10^5 dan oshmasligi kafolatlanadi.

Output

Qiymatni maksimal darajada oshiradigan $a$ ning har qanday to'g'ri permutatsiyasini chiqarishingiz kerak.

Examples

Note

Birinchi test holida, yig'indi qalin maydonda [3,[\textbf{4,9,5}],\text{1}] amalga oshiriladi, bu esa \max(f)=18 beradi.

Ikkinchi test holida, yig'indi qizil maydonda amalga oshiriladi: [\color{red}{2_{(2)},1_{(3)},3_{(1)}} \color{black}], bu esa \max(f)=6 beradi.

Uchinchi test holida, yig'indi quyidagi tarzda amalga oshiriladi (tsiklik naqshiga muvofiq):

1. [6,3,2,\color{red}{10}], umumiy yig'indi $10$, va biz shu nuqtaga $1$ elementni qo'shdik.

2. [\color{red}{6,3,2,10}], umumiy yig'indi $31$, va biz shu nuqtaga $5$ elementni qo'shdik.

3. [\color{red}{6,3,2,10}], umumiy yig'indi $52$, va biz shu nuqtaga $9$ elementni qo'shdik.

4. [\color{red}{6,3,2,10}], umumiy yig'indi $73$, va biz shu nuqtaga $13$ elementni qo'shdik.

5. [\color{red}{6,3,2,10}], umumiy yig'indi $94$, va biz shu nuqtaga $17$ elementni qo'shdik.

Bu \max(f)=94 beradi.

Scoring

1. (5 ball) : (m+k-1 \le n)

2. (10 ball) : (1 \le k \le n \le 10)

3. (10 ball) : (1 \le k \le n \le 500)

4. (15 ball) : (m=1)

5. (20 ball) : (a_i \le 2)

6. (40 ball) : qo'shimcha cheklovlar yo'q.