Submission

Problem Description

有一道题有 $n$ 条提交记录，分别由 $m$ 个人提交，且每个人至少提交了一次。不妨把这 $m$ 个人按 $1\sim m$ 编号，那么这 $n$ 条提交记录可以由一个长为 $n$，值域为 $[1,m]$ 的正整数序列 $a$ 表示。 你打算按顺序浏览一遍这些人的提交记录，但是对于同一个人的，你不想反复「仔细阅读」。同时，你的大脑容量也有限制，只能记录 $k$ 个人的名字。于是，你决定这样做：

• 先给每个人分配一个「优先级」，其中「优先级」是一个 $1\sim m$ 的排列；
• 然后清空大脑，并按顺序浏览提交记录：
• 如果当前提交的人在大脑里，直接跳过这份提交记录；否则「仔细阅读」这份提交记录，并把他的名字加入大脑；
• 任何时刻，只要大脑中超过 $k$ 个名字，就把「优先级」最小的删掉，直到剩下 $\le k$ 个名字为止。 显然，根据「优先级」的不同，你「仔细阅读」的次数也可能不同。为了省时间，你需要合理安排一个「优先级」，使得你「仔细阅读」的次数最少。 对于 $[1,m]$ 中的每个整数 $k$，回答最少的「仔细阅读」次数。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le1.5\cdot10^5$）表示数据组数。对于每组测试数据： 第一行输入两个正整数 $n,m$（$1\le m\le n\le5000$）。 第二行一个长为 $n$ 的正整数序列 $a$（$1\le a_i\le m$）。保证 $a$ 中 $1\sim m$ 各出现至少一次。 保证 $\sum n\le1.5\cdot10^6,\sum n^2\le1.5\cdot10^8$。

Output

对于每组数据，输出一行 $m$ 个正整数，其中第 $i$ 个正整数表示当 $k=i$ 时的最小「仔细阅读」次数。

Sample Input

3
5 2
1 2 1 1 2
5 3
2 3 1 3 2
9 3
3 1 2 3 3 1 2 1 3

Sample Output

3 2
4 3 3
6 4 3

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）