SP23737 OGLEDALA - Ogledala

在一家大型购物中心的女洗手间里，从左到右排列着 $M$ 个现代化的洗手池，编号依次为 $1$ 到 $M$。 当前有 $N$ 位女士在洗手间内（她们的编号为 $1$ 到 $N$），分别占用了编号为 $A_1, A_2, \ldots, A_N$ 的洗手池。接下来，还会有 $M - N$ 位女士到来（到达顺序的编号为 $N + 1$ 到 $M$），她们将占用所有剩余的空闲洗手池。 这些新来的女士希望尽可能保持隐私，因此她们会按以下步骤选择一个空闲的洗手池： - 首先，她会找到最长的一段连续空闲的洗手池。如果有多段长度相同，她会选择最左边的那一段。 - 接着，她占用这一段中的中间的洗手池。如果该段有偶数个洗手池，她会选择两者中靠左的那个。 我们假设女士们占用洗手池后，不会在近期离开。 请编写一个程序，对每个给定的整数 $B_i$，确定编号为 $B_i$ 的女士将会使用哪个洗手池。

第一行输入三个整数 $M, N, Q$，分别表示洗手池总数、当前已在使用的女士数量以及需要查询的女士数量。 第二行有 $N$ 个用空格隔开的整数，这些数是 $A_1, A_2, \ldots, A_N$，分别表示每位女士所占用洗手池的编号。 第三行有 $Q$ 个用空格隔开的整数，这些数是我们想知道分配情况的女士编号 $B_1, B_2, \ldots, B_Q$。 注意，最初的 $N$ 位女士占用的洗手池不一定是按上述过程选择的。 数组 $A$ 和 $B$ 是严格递增的，即满足 $1 \leq A_1 < A_2 < \ldots < A_N \leq M$ 和 $1 \leq B_1 < B_2 < \ldots < B_Q \leq M$。

输出 $Q$ 行，每行的数字表示该编号的女士将要使用的洗手池编号。

1. $1 \leq N \leq M \leq 10^{14}$ 2. $1 \leq Q, N \leq 10^5$ **本翻译由 AI 自动生成**