Movie Collection

Interview

Time limit1sMemory limit256 MB

Summary

Given a stack of DVDs and a sequence of watched movie numbers, output for each watch how many DVDs sat above it before moving it to the top.

Level: Medium4 of 10
Topics: Array, Simulation, Implementation
Solved: No attempts yet

Problem

Sanggeun is a movie DVD collector. He keeps his DVDs stacked in a single pile.

Whenever he wants to watch a movie, he locates its DVD and carefully pulls it out without toppling the pile. After finishing the movie, he places that DVD back on top of the pile.

Because Sanggeun owns so many DVDs, locating a movie takes a long time. The position of a DVD is easy to determine once you know how many DVDs are stacked on top of it. Each movie is identified by the number printed on its cover.

Write a program that, every time Sanggeun watches a movie, reports how many DVDs were on top of that DVD.

Input

The first line contains the number of test cases, which is at most $100$ .

The first line of each test case contains $n$ , the number of movies Sanggeun owns, and $m$ , the number of movies he will watch. ( $1 \le n, m \le 100{,}000$ )

The second line contains the $m$ movie numbers, in the order he watches them.

Movies are numbered from $1$ to $n$ . Initially the DVDs are stacked in increasing order of their numbers, and the DVD on the very top has number $1$ .

Output

For each test case, print $m$ integers on a single line, separated by spaces.

The $i$ -th number is the number of DVDs that were on top of the DVD when the $i$ -th movie is watched. Each time Sanggeun watches a movie, he puts that DVD back on top of the pile.

Examples7

Example 1
Input
```
2
3 3
3 1 1
5 3
4 4 5
```
Expected output
```
2 1 0
3 0 4
```
Example 2
Input
```
1
1 1
1
```
Expected output
```
0
```
Example 3
Input
```
1
5 4
5 5 5 5
```
Expected output
```
4 0 0 0
```
Example 4
Input
```
1
4 4
1 2 3 4
```
Expected output
```
0 1 2 3
```
Example 5
Input
```
1
4 4
4 3 2 1
```
Expected output
```
3 3 3 3
```
Example 6
Input
```
1
10 6
10 1 10 5 5 2
```
Expected output
```
9 1 1 5 0 3
```

Example 7

Input

Expected output

1 1
0
2 0 1 2