Recent Actions
Contest: Codeforces Round 854 by cybercats (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: data structures, greedy, implementation, math

On Codeforces the "Recent Actions" field shows the last $$$n$$$ posts with recent actions.

Initially, there are posts $$$1, 2, \ldots, n$$$ in the field (this is in order from top to down). Also there are infinitely many posts not in the field, numbered with integers $$$n + 1, n + 2, \ldots$$$.

When recent action happens in the post $$$p$$$:

- If it is in the "Recent Actions" field, it moves from its position to the top position.
- Otherwise, it is added to the top position, and the post on the down position is removed from the "Recent Actions" field.

You know, that the next $$$m$$$ recent actions will happen in the posts $$$p_1, p_2, \ldots, p_m$$$ ($$$n + 1 \leq p_i \leq n + m$$$) in the moments of time $$$1, 2, \ldots, m$$$. Note, that recent actions only happen with posts with numbers $$$\geq n + 1$$$.

For each post $$$i$$$ ($$$1 \leq i \leq n$$$), find the first time it will be removed from the "Recent Actions" field or say, that it won't be removed.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^4$$$) — the size of the "Recent Actions" field and the number of actions.

The next line contains $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$ ($$$n + 1 \leq p_i \leq n + m$$$).

It is guaranteed, that the sum of $$$n$$$ and the sum of $$$m$$$ for all test cases does not exceed $$$5 \cdot 10^4$$$.

Output format:
For each test case print $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$, where $$$t_i=-1$$$ if the post $$$i$$$ won't be removed or $$$t_i$$$ equals to the first moment of time the post $$$i$$$ will be removed ($$$1 \leq t_i \leq m$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only post $$$1$$$ will be removed at the moment $$$1$$$ and replaced by the post $$$2$$$.

In the second test case the "Recent Actions" field will be (given an order from top to down):

1. Before moment $$$1$$$: $$$[1, 2, 3]$$$, after moment $$$1$$$: $$$[5, 1, 2]$$$. Post number $$$3$$$ was removed.
2. Before moment $$$2$$$: $$$[5, 1, 2]$$$, after moment $$$2$$$: $$$[4, 5, 1]$$$. Post number $$$2$$$ was removed.

Post number $$$1$$$ won't be removed.

In the third test case the "Recent Actions" field will be (given an order from top to down):

1. Before moment $$$1$$$: $$$[1, 2, 3, 4]$$$, after moment $$$1$$$: $$$[5, 1, 2, 3]$$$. Post number $$$4$$$ was removed.
2. Before moment $$$2$$$: $$$[5, 1, 2, 3]$$$, after moment $$$2$$$: $$$[9, 5, 1, 2]$$$. Post number $$$3$$$ was removed.
3. Before moment $$$3$$$: $$$[9, 5, 1, 2]$$$, after moment $$$3$$$: $$$[9, 5, 1, 2]$$$. Nothing was changed.
4. Before moment $$$4$$$: $$$[9, 5, 1, 2]$$$, after moment $$$4$$$: $$$[5, 9, 1, 2]$$$. The order was changed.
5. Before moment $$$5$$$: $$$[5, 9, 1, 2]$$$, after moment $$$5$$$: $$$[7, 5, 9, 1]$$$. Post number $$$2$$$ was removed.

Post number $$$1$$$ won't be removed.

Example input:
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

Example output:
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

Editorial:
Note, that posts will be removed in the order $$$n, n - 1, \ldots, 1$$$.
The post $$$n - k + 1$$$ will be removed at the first time, when there are at least $$$k$$$ different numbers among $$$p_1, p_2, \ldots, p_i$$$.
So let's calculate the number of different numbers among $$$p_1, p_2, \ldots, p_i$$$ for each $$$i$$$ using boolean array of length $$$m$$$ iterating $$$i$$$ from $$$1$$$ to $$$m$$$. Using them we can calculate the answer.
Time complexity: $$$O(n + m)$$$.