UOJ Logo Universal Online Judge

UOJ

#771. 【UER #11】科考工作

附件下载 统计

为了完成南极的科考工作,跳蚤国王在南极设立了 $N$ 个科考站!由于跳蚤国王喜欢素数,因此其建造的科考站的数量 $N$ 也为一个素数。

现在,有 $2N-1$ 个科考项目等待着科考人员们完成。对于第 $i$ 个科考项目($1 \le i \le 2N-1$),需要前往 $A_i$ 个地点进行考察($A_i$ 可能为 $0$,表示该科考项目不需要考察即可完成)。由于每个项目所研究的方向不同,因此每个项目所前往的地点都是不同的。

为了保证每个科考站的考察工作能够高质量地完成,每个科考站一天只能前往一个地点进行考察。好在,由于科考站之间的通信顺畅,因此一个科考项目所需要考察的地点可以由多个不同的科考站内的团队来完成。

作为跳蚤国王的助手,伏特需要恰当固定分配科考任务,以保证科考站之间的合作能够顺利进行。伏特认为,如果有一个科考站所考察的地点比另一个科考站多,那么该科考站的工作人员便可能感到分配工作的不合理。因此,伏特希望恰当的分配科考任务,使得所有科考站所考察的地点数量相同。

但是,伏特很快发现,只要 $\displaystyle \sum_{i=1}^{2N-1} A_i$ 不是 $N$ 的倍数,便不可能存在一种公平的分配方案!因此,伏特决定退而求其次,仅保留恰好 $N$ 个科考项目,从而使得在任务能够公平地进行分配的同时,能够让每个科考站都有恰好一个项目进行汇报。

由于伏特还要前去监督激光雷达的建造,因此寻找需要分配哪些科考项目的任务就交给了你!

输入格式

输入的第一行包含一个正整数 $N$。保证 $N$ 是素数。

接下来一行,包含 $2N-1$ 个整数 $A_1, A_2, \cdots, A_{2N-1}$,表示每个科考项目所需考察的地点的数量。

输出格式

如果无论如何,都无法寻找到 $N$ 个科考项目,使得 $N$ 个科考站可以公平地分配科考地点的数量,则输出一行一个整数 $-1$。

否则输出一行,包含 $N$ 个整数,表示保留下来的科考项目 $B_1, B_2, \cdots, B_N$。

即,你需要保证 $B_1, B_2, \cdots, B_N$ 均为 $[1, 2N-1]$ 内两两不同的整数,且 $\sum_{i=1}^N A_{B_i} \equiv 0 \pmod N$。

如果存在多组合法的方案,你可以输出任意一种。

样例一

input

3
0 1 1 2 2

output

1 3 4

explanation

共有 $N=3$ 个科考站,以及 $5$ 个可用的科考项目。

  • 对于科考项目 $1$,我们不需要进行任何考察工作,因此不需要进行任何安排。
  • 对于科考项目 $3$,我们需要前往 $1$ 个地点进行考察,伏特可以安排科考站 $1$ 前往考察。
  • 对于科考项目 $4$,我们需要前往 $2$ 个地点进行考察,伏特可以安排科考站 $2$ 前往考察第一个地点,安排科考站 $3$ 前往考察第二个地点。

因此,每个科考站都需要去恰好一个地点进行考察,这样的分配是公平的。

1 2 41 2 51 3 5 也是合法的答案。

样例二

input

7
0 0 1 1 1 1 2 3 4 4 5 5 6

output

2 3 5 8 11 12 13

样例三

见附件下载。该样例满足子任务 3 的限制。

样例四

见附件下载。该样例满足子任务 4 的限制。

数据范围

对于所有数据,$2\leq N\leq 3\times 10^5$,对于任意 $1 \le i \le 2N-1$,都有 $0 \le A_i < N$,且保证 $N$ 是素数。

子任务编号 $N\leq$ 分值 子任务依赖
$1$ $10$ $5$
$2$ $20$ $15$ $1$
$3$ $200$ $15$ $2$
$4$ $2000$ $20$ $3$
$5$ $10^5$ $35$ $4$
$6$ $3\times 10^5$ $10$ $5$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$