题目描述

$2N$ 名选手编号为 $1$ 至 $2N$，每人有初始得分和互不相同的实力值。排名按得分从高到低，得分相同时编号小的在前。每轮按当前排名把第 $1,2$ 名、第 $3,4$ 名等两两配对，实力值大者得 $1$ 分，另一人得分不变，之后重新排名。求 $R$ 轮后排名第 $Q$ 的选手编号。

输入格式

第一行三个整数 $N,R,Q$。第二行 $2N$ 个初始得分。第三行 $2N$ 个实力值。

输出格式

输出所求选手的编号。

样例

2 4 2
7 6 6 7
10 5 20 15

1

数据范围

对于 $30\%$ 的数据，$N\le100$；对于 $50\%$ 的数据，$N\le10000$；对于 $100\%$ 的数据，$1\le N\le100000$，$1\le R\le50$，$1\le Q\le2N$，$0\le s_i\le10^8$，$1\le w_i\le10^8$，实力值互不相同。