Count Distinct Numbers

 

Chef has a sequence 

A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and an integer K$K$. Now there is a sliding window of size K$K$ which is moving from the very left of the array to the very right and at a particular time Chef has access to only those K$K$ elements that are present in that window and Chef wants to find the number of the distinct elements of each window of size K$K$. Help Chef to find the answer.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two integers N$N$ and K$K$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output

For each test case, print a single line containing N−K+1$N-K+1$ space-separated integers — the number of the distinct elements of each window of size K$K$ from the very left of the array to the very right of the sequence.

Constraints

• 1≤T≤10$1\le T\le 10$
• 1≤K≤N≤105$1\le K\le N\le {10}^5$
• 1≤Ai≤105$1\le A_i\le {10}^5$ for each valid i$i$

Example Input

2
6 3
5 8 5 4 4 1
4 2
4 5 2 2

Example Output

2 3 2 2
2 2 1

Explanation

Example case 1: Number of the distinct elements of [5,8,5]$[5,8,5]$, [8,5,4]$[8,5,4]$, [5,4,4]$[5,4,4]$, [4,4,1]$[4,4,1]$ are respectively 2$2$, 3$3$, 2$2$, 2$2$.

• Tweet
• Share
• Share
• Share
• Share

Related Post