← 返回题目列表

Codeforces · 1799/A

A. 近期行动

中文机器翻译题面 查看原题

在 Codeforces 上,“最近操作”字段显示最后 $$$n$$$ 帖子以及最近操作。

最初,该字段中有帖子$$$1, 2, \ldots, n$$$(按从上到下的顺序)。此外,还有无数不在该领域的帖子,用整数 $$$n + 1、n + 2、\ldots$$$ 编号。

当最近的操作发生在帖子 $$$p$$$ 中时:

- 如果它位于“最近操作”字段中,则它会从其位置移动到顶部位置。
- 否则,它会被添加到顶部位置,而底部位置的帖子将从“最近操作”字段中删除。

你知道,下一个 $$$m$$$ 最近的操作将发生在 $$$p_1, p_2, \ldots, p_m$$$ ($$$n + 1 \leq p_i \leq n + m$$$) 时刻 $$$1, 2, \ldots, m$$$ 的帖子中。请注意,最近的操作仅适用于编号为 $$$\geq n + 1$$$ 的帖子。

对于每个帖子 $$$i$$$ ($$$1 \leq i \leq n$$$),找到它第一次从“最近操作”字段中删除的时间,或者说它不会被删除。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^4$$$) — “最近操作”字段的大小和操作数量。

下一行包含 $$$m$$$ 整数 $$$p_1, p_2, \ldots, p_m$$$ ($$$n + 1 \leq p_i \leq n + m$$$)。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$5 \cdot 10^4$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数 $$$t_1, t_2, \ldots, t_n$$$,其中 $$$t_i=-1$$$ 如果帖子 $$$i$$$ 不会被删除,或者 $$$t_i$$$ 等于帖子 $$$i$$$ 将被删除的第一个时刻 ($$$1 \leq t_i \leq m$$$)。

示例

输入 #1

10
1 1
2
3 2
5 4
4 5
5 9 9 5 7
5 5
6 7 8 9 10
3 4
4 4 4 4
4 4
5 5 6 6
3 5
4 5 5 5 4
4 20
5 5 24 24 24 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20
5 7
7 8 7 11 7 12 10
6 7
8 11 7 8 8 8 12

输出 #1

1 
-1 2 1 
-1 5 2 1 
5 4 3 2 1 
-1 -1 1 
-1 -1 3 1 
-1 2 1 
8 7 3 1 
7 6 4 2 1 
-1 -1 7 3 2 1

注意

在第一个测试用例中,唯一的帖子 $$$1$$$ 将在 $$$1$$$ 时刻被删除,并替换为帖子 $$$2$$$。

在第二个测试用例中,“最近操作”字段将为(从上到下排列):

1. $$$1$$$ 时刻之前:$$$[1, 2, 3]$$$,$$$1$$$ 时刻之后:$$$[5, 1, 2]$$$。帖子编号 $$$3$$$ 已删除。
2. $$$2$$$ 时刻之前:$$$[5, 1, 2]$$$,$$$2$$$ 时刻之后:$$$[4, 5, 1]$$$。帖子编号 $$$2$$$ 已删除。

帖子编号 $$$1$$$ 不会被删除。

在第三个测试用例中,“最近操作”字段将为(从上到下排列):

1. $$$1$$$ 时刻之前:$$$[1, 2, 3, 4]$$$,$$$1$$$ 时刻之后:$$$[5, 1, 2, 3]$$$。帖子编号 $$$4$$$ 已删除。
2. $$$2$$$ 时刻之前:$$$[5, 1, 2, 3]$$$,$$$2$$$ 时刻之后:$$$[9, 5, 1, 2]$$$。帖子编号 $$$3$$$ 已删除。
3. $$$3$$$ 时刻之前:$$$[9, 5, 1, 2]$$$,$$$3$$$ 时刻之后:$$$[9, 5, 1, 2]$$$。一切都没有改变。
4. $$$4$$$ 时刻之前:$$$[9, 5, 1, 2]$$$,$$$4$$$ 时刻之后:$$$[5, 9, 1, 2]$$$。顺序已更改。
5. $$$5$$$ 时刻之前:$$$[5, 9, 1, 2]$$$,$$$5$$$ 时刻之后:$$$[7, 5, 9, 1]$$$。帖子编号 $$$2$$$ 已删除。

帖子编号 $$$1$$$ 不会被删除。