A. Прямой эфир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На 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$$$).

Пример
Входные данные
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 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$$$ не будет удален.