Description

There are 2*N players numbered from 1 to 2*N who participate in R rounds of matches. Before each round begins and after all matches conclude, the players are ranked based on their total scores in descending order. A player's total score is the sum of their initial score before the first round and all points earned in completed matches. If two players have the same total score, the one with the smaller ID is ranked higher.

The match pairings for each round are determined by the rankings before that round: the 1st-ranked player faces the 2nd-ranked, the 3rd-ranked faces the 4th-ranked, ..., the (2K-1)-th-ranked faces the (2K)-th-ranked, ..., and the (2N-1)-th-ranked faces the (2N)-th-ranked. Each match awards the winner 1 point and the loser 0 points. This means that except for the first round, the match arrangements for subsequent rounds cannot be predetermined and depend on the players' performances in prior matches.

Given the initial scores and strength values of all players, calculate the ID of the player ranked Q-th after R rounds of matches. Assume all players have distinct strength values, and the stronger player always wins in any match.

Input Format

The first line of input contains three positive integers N, R, and Q, separated by spaces, representing the number of player pairs (2*N players), the number of rounds (R), and the rank of interest (Q).

The second line contains 2*N non-negative integers s1, s2, ..., s2N, separated by spaces, where si denotes the initial score of the player with ID i.

The third line contains 2*N positive integers w1, w2, ..., w2N, separated by spaces, where wi denotes the strength value of the player with ID i.

Output Format

The output consists of a single line containing an integer, which is the ID of the player ranked Q-th after R rounds of matches.

```input1 2 4 2 7 6 6 7 10 5 20 15 ``` ```output1 1 ``` ## Source

NOIP2003-J3

(Note: NOIP stands for National Olympiad in Informatics in Provinces, which is a Chinese programming competition for secondary school students. The "J3" likely indicates this is the third problem of the junior division in the 2003 competition.)