该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的序列 $a$，里面每一个元素的都是 $[1,m]$ 的正整数，且保证每个数字都至少出现了一次。 对于 $i=1...m$ 分别求出最短长度的区间，使得区间包含 ${1,2,3,...i}$。

Format

Input

第一行读入一个正整数 $T$，表示数据组数。

对于每组数据，首先读入两个正整数 $n,m$。

接下来一行 $n$ 个数字 $a_i$，表示序列 $a$。

Output

输出共 $T$ 行。

每行 $m$ 个数，第 $i$ 个数表示包含 ${1,2,3,...i}$ 的最短区间的长度。

Samples

1
5 3
1 3 2 3 1

1 3 3

见附加文件。

Limitation

对于 $20\%$ 的数据，保证 $1 \le \sum n\leq 2\times 10^3,1\leq m \le 2 \times 10^3$。

对于另外 $20\%$ 的数据，保证 $1 \le \sum n\leq 5\times 10^4,1\leq m\leq 500$。

对于 $100\%$ 的数据，保证 $1\leq T\leq 100,1 \le n,m \le 5\times 10^5,1\le a_i \le m,\sum n\leq 5\times 10^5$。

时空限制：1000ms/256MB。