На 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\)) найдите минимальный момент времени, когда он будет удален из поля «Прямой эфир», или скажите, что он не будет удален.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(t_1, t_2, \ldots, t_n\), где \(t_i=-1\), если пост \(i\) не будет удален, иначе \(t_i\) равняется первому моменту времени, когда пост \(i\) будет удален (\(1 \leq t_i \leq m\)).
Примечание
В первом наборе входных данных единственный пост \(1\) будет удален в момент времени \(1\) и будет заменен на пост \(2\).
Во втором наборе входных данных поле «Прямой эфир» будет (в порядке сверху вниз):
- Перед моментом времени \(1\): \([1, 2, 3]\), после момента времени \(1\): \([5, 1, 2]\). Пост \(3\) был удален.
- Перед моментом времени \(2\): \([5, 1, 2]\), после момента времени \(2\): \([4, 5, 1]\). Пост \(2\) был удален.
Пост \(1\) не будет удален.
Во третьем наборе входных данных поле «Прямой эфир» будет (в порядке сверху вниз):
- Перед моментом времени \(1\): \([1, 2, 3, 4]\), после момента времени \(1\): \([5, 1, 2, 3]\). Пост \(4\) был удален.
- Перед моментом времени \(2\): \([5, 1, 2, 3]\), после момента времени \(2\): \([9, 5, 1, 2]\). Пост \(3\) был удален.
- Перед моментом времени \(3\): \([9, 5, 1, 2]\), после момента времени \(3\): \([9, 5, 1, 2]\). Ничего не изменилось.
- Перед моментом времени \(4\): \([9, 5, 1, 2]\), после момента времени \(4\): \([5, 9, 1, 2]\). Поменялся только порядок постов.
- Перед моментом времени \(5\): \([5, 9, 1, 2]\), после момента времени \(5\): \([7, 5, 9, 1]\). Пост \(2\) был удален.
Пост \(1\) не будет удален.
Примеры
| № | Входные данные | Выходные данные |
|
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 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
|