Điều khiển tâm trí

Bạn và $n-1$ người bạn cùng chia nhau một dãy số nguyên $a_1,a_2,\dots ,a_n$ theo quy tắc sau: tất cả xếp thành một hàng theo thứ tự đã định. Tại mỗi lượt, người đứng đầu hàng chọn phần tử đầu hoặc cuối của dãy còn lại, lấy nó cho mình và rời khỏi hàng. Người tiếp theo lặp lại tương tự với phần dãy còn lại.

Bạn đứng ở vị trí thứ $m$ trong hàng. Trước khi quá trình bắt đầu, bạn được phép chọn tối đa $k$ người khác trong hàng và bắt mỗi người đó cam kết: khi đến lượt họ sẽ luôn lấy phần tử đầu, hoặc luôn lấy phần tử cuối (mỗi người một lựa chọn riêng do bạn quyết định). Khi quá trình bắt đầu, bạn không được điều khiển thêm ai, cũng không được đổi ý cho những người đã bị điều khiển.

Những người không bị bạn điều khiển có thể chọn đầu hoặc cuối một cách hoàn toàn tùy ý — họ không nhất thiết lấy phần tử lớn nhất, mà có thể chọn theo cách bất lợi nhất cho bạn.

Giả sử bạn lựa chọn tối ưu, hãy tìm số nguyên $x$ lớn nhất sao cho dù những người không bị điều khiển chọn thế nào, phần tử bạn lấy được khi đến lượt mình vẫn $\ge x$.

Dữ liệu vào

Dòng đầu chứa một số nguyên $t$ ($1\le t\le 1000$) — số test.

Mỗi test gồm hai dòng:

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$ ($1\le m\le n\le 3500$, $0\le k\le n-1$).
• Dòng sau chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Tổng $n$ trên toàn bộ các test không vượt quá $3500$.

Dữ liệu ra

Với mỗi test, in ra một dòng chứa giá trị $x$ lớn nhất.

Ví dụ