Day of the Programmer- HackerRank problem

                                                                B. Tournament

time limit per test

2 seconds

memory limit per test

256 megabytes

You are given an array of integers a1,a2,…,an$a_1,a_2,\dots ,a_n$. A tournament is held with n$n$ players. Player i$i$ has strength ai$a_i$.

While more than k$k$ players remain,

• Two remaining players are chosen at random;
• Then the chosen player with the lower strength is eliminated. If the chosen players have the same strength, one is eliminated at random.

Given integers j$j$ and k$k$ (1≤j,k≤n$1\le j,k\le n$), determine if there is any way for player j$j$ to be one of the last k$k$ remaining players.

Input

The first line contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$)  — the number of test cases.

The first line of each test case contains three integers n$n$, j$j$, and k$k$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$, 1≤j,k≤n$1\le j,k\le n$).

The second line of each test case contains n$n$ integers, a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$).

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output on a single line "YES" if player j$j$ can be one of the last k$k$ remaining players, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example

Input

Copy

3
5 2 3
3 2 4 4 1
5 4 1
5 3 4 5 2
6 1 1
1 2 3 4 5 6

Output

Copy

YES
YES
NO

Note

In the first sample, suppose that players 2$2$ and 5$5$ are chosen. Then player 2$2$ defeats player 5$5$. Now, the remaining player strengths are

3

2

4

4

Next, suppose that players 3$3$ and 4$4$ are chosen. Then player 3$3$ might defeat player 4$4$. Now, the remaining player strengths are

3

2

4

Player 2$2$ is one of the last three players remaining.

In the third sample, it can be shown that there is no way for player 1$1$ to be the last player remaining.

Tournament problem solution by Java,

Tournament problem solution by Python