Description

A Swiss-system tournament is a tournament which uses a non-elimination format. The first tournament of this type was a chess tournament in Zurich in 1895, hence the name "Swiss system". The tournament will be held based on following rules.

$2*N$ contestants (indexed $1, 2, ..., 2*N$) will have $R$ rounds matches. Before the first round, every contestant has an origin score. After every match, winner will get 1 score and loser will get 0 score. Before and after every round, contestants will be sorted by their scores in descending order. Two contestants with the same score will be sorted by their index with ascending order.

In every round, contestants will have match based on the sorted list. The first place versus the second place, the third place versus the forth place, ..., the $Kth$ place versus the $(K + 1)th$ place, ..., the $(2*N - 1)th$ place versus $(2*N)th$ place.

Now given the origin score and the ability of every contestant, we want to know the index of the $Qth$ place contestant. We ensured that there won’t be two contestants with the same ability and the contestant with higher ability will always win the match.

Format

Input

Multiple test cases. The first line contains a positive integer $T (T\leq10)$ indicating the number of test cases.

For each test case, the first line contains three positive integers $N (N \leq 100,000), R (R \leq 50), Q (Q \leq 2*N)$, separated by space.

The second line contains $2*N$ non-negative integers, $s1, s2, ..., s2*N, si (si\leq 100000000)$ indicates the origin score of constant indexed $i$.

The third line contains $2*N$ positive integers, $a1, a2, ..., a2*N, ai (ai\leq 100000000)$ indicates the ability of constant indexed $i$.

Output

One line per case, an integer indicates the index of the $Qth$ place contestant after $R$ round matches.

Samples

1
2 4 2
7 6 6 7
10 5 20 15

1

Hints