Description

$2 \times N$ players, numbered $1 \sim 2 \times N$, play $R$ rounds. Before each round starts, and after all matches are finished, players are ranked in descending order by total points. A player's total points equal the initial points before round $1$ plus the sum of points earned in all matches already played. If the total points are the same, the player with the smaller id ranks ahead.

The pairings of each round depend on the ranking at the start of that round: rank $1$ vs rank $2$, rank $3$ vs rank $4$, ..., rank $2 \times K - 1$ vs rank $2 \times K$, ..., rank $2 \times N - 1$ vs rank $2 \times N$. The winner of each match gets $1$ point and the loser gets $0$ points. That is, except for the first round, the arrangements of the other rounds cannot be determined in advance; they depend on the players' performances in previous matches.

Given each player's initial points and strength value, compute the id of the player ranked $Q$-th after $R$ rounds. We assume all strength values are pairwise distinct, and in every match the player with the higher strength always wins.

Input Format

The first line contains three positive integers $N, R, Q$, separated by single spaces, indicating there are $2 \times N$ players, $R$ rounds, and we are interested in the $Q$-th place.

The second line contains $2 \times N$ non-negative integers $s_1, s_2, \dots, s_{2 \times N}$, separated by single spaces, where $s_i$ denotes the initial points of the player with id $i$.

The third line contains $2 \times N$ positive integers $w_1, w_2, \dots, w_{2 \times N}$, separated by single spaces, where $w_i$ denotes the strength value of the player with id $i$.

Output Format

Output a single integer: the id of the player ranked $Q$-th after $R$ rounds.

2 4 2 
7 6 6 7 
10 5 20 15 

1

Hint

Sample Explanation:

Constraints:

• For $30\%$ of the testdata, $1 \le N \le 100$.
• For $50\%$ of the testdata, $1 \le N \le 10000$.
• For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le R \le 50$, $1 \le Q \le 2 \times N$, $0 \le s_1, s_2, \dots, s_{2 \times N} \le 10^8$, $1 \le w_1, w_2, \dots, w_{2 \times N} \le 10^8$.

NOIP 2011 Junior Problem 3.

Translated by ChatGPT 5