#P1052. 序列统计

序列统计

Description

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

Format

Input

第一行读入一个正整数 TT,表示数据组数。

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

接下来一行 nn 个数字 aia_i,表示序列 aa

Output

输出共 TT 行。

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

Samples

1
5 3
1 3 2 3 1
1 3 3


见附加文件。

Limitation

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

对于另外 20%20\% 的数据,保证 1n5×104,1m5001 \le \sum n\leq 5\times 10^4,1\leq m\leq 500

对于 100%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。