CF1181D Irrigation

Misha 从小就对送水很感兴趣。因此，他的妈妈把他送去参加一年一度的创新灌溉奥林匹克（IOI）。来自 Berland 的学生们在这里比拼他们的浇水技能。举办这样一场奥林匹克的花费极高，所以在举办了前 $n$ 届奥林匹克后，主办方引入了新的主办城市选择规则。 奥林匹克的主办城市选择规则如下：Berland 有 $m$ 个城市希望承办奥林匹克，它们编号为 $1$ 到 $m$。每一届新的奥林匹克的主办城市，都会选择此前承办次数最少的城市。如果有多个城市承办次数相同，则选择编号最小的城市。 Misha 的妈妈想知道某些特定年份奥林匹克的主办城市。她只知道上述的选择规则，以及前 $n$ 届奥林匹克的主办城市。请你帮她解答，如果你能做到，她会让 Misha 不去淹你家。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m, q \leq 500\,000$），分别表示引入新规则前的奥林匹克届数、希望承办奥林匹克的城市数量，以及 Misha 的妈妈感兴趣的年份数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq m$），其中 $a_i$ 表示第 $i$ 届奥林匹克的主办城市。注意，在引入规则前，主办城市是任意选择的。 接下来 $q$ 行，每行包含一个整数 $k_i$（$n + 1 \leq k_i \leq 10^{18}$），表示 Misha 的妈妈想知道第 $k_i$ 届奥林匹克的主办城市。

输出 $q$ 个整数，第 $i$ 个表示第 $k_i$ 届奥林匹克的主办城市编号。

在第一个样例中，Misha 的妈妈想知道新规则引入后前 $10$ 届奥林匹克的主办城市。对应的主办城市依次为 4、3、4、2、3、4、1、2、3、4。 在第二个样例中，新城市加入后，后续的主办城市依次为 2、3、1、2、3、5、1、2、3、4、5、1。 由 ChatGPT 4.1 翻译