The AI expert The NIT is training a robot, The BOT.

The BOT moves on a $1 \times n$ grid, where the cell $(1, i)$ contains the number $a_i$. The BOT starts at position $(1, x)$. The BOT wants to reach a cell with the largest possible number. In each step, The BOT can choose to move to an adjacent cell or stay put. After moving, it can choose whether to select the number on the current cell and end the game. To train The BOT's capabilities, The NIT introduces obstacles: after The BOT decides whether to end the game, The NIT can swap the values of two numbers.

Specifically, the game consists of several rounds. Initially, The BOT is at position $(1, x)$. In each round, the following events occur in order:

1. The NIT chooses two positions $1 \leq i, j \leq n$ and swaps the values of $a_i$ and $a_j$. Note that $i$ can be equal to $j$, in which case the swap has no effect.
2. The BOT chooses to move to an adjacent position or stay put. Let the current position of The BOT be $y$. It chooses $1 \leq z \leq n$ such that $|z - y| \leq 1$ and moves to $(1, z)$.
3. The BOT chooses whether to end the game. Let the current position of The BOT be $y$. If it chooses to end, it receives a score of $a_y$ and the game ends immediately. Otherwise, nothing happens.

It can be observed that if The BOT never chooses to end the game, the game will never end. To prevent this, in the $10^{114514}$-th round, The BOT must choose to end the game immediately.

The NIT wants to minimize the score when The BOT ends the game, while The BOT wants to maximize this score. Both The NIT and The BOT are perfectly rational. Since they do not have time to play $10^{114514}$ rounds, please calculate the final score of the game.

Input

The input is read from standard input.

This problem contains multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 10^5$), representing the number of test cases.

For each test case:

The first line contains two positive integers $n$ and $x$ ($1 \leq n \leq 10^5, 1 \leq x \leq n$), representing the length of the grid and the initial position $(1, x)$, respectively.

The next line contains $n$ non-negative integers $a_i$ ($0 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

Output to standard output.

For each test case, output a single line containing the answer.

Examples

Input 1

4
3 2
1 2 3
13 4
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
1 10 100 1000
1 1
114514

Output 1

3
4
100
114514