给你两个整数 $$$n$$$ 和 $$$k$$$。您还会获得一个大小为 $$$n$$$ 的整数数组 $$$a_1, a_2, \ldots, a_n$$$。已知对于所有$$$1 \leq i \leq n$$$,$$$1 \leq a_i \leq k$$$。
定义一个大小为 $$$n \times n$$$ 的二维数组 $$$b$$$,如下所示:$$$b_{i, j} = \min(a_i, a_j)$$$。将数组 $$$b$$$ 表示为正方形,其中左上角单元格为 $$$b_{1, 1}$$$,行从上到下从 $$$1$$$ 到 $$$n$$$ 编号,列从左到右从 $$$1$$$ 到 $$$n$$$ 编号。令单元格的颜色为其中写入的数字(对于坐标为 $$$(i, j)$$$ 的单元格,这是 $$$b_{i, j}$$$)。
对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色,在数组 $$$b$$$ 中找到包含该颜色所有单元格的最小矩形。输出该矩形的宽度和高度之和。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) — 数组 $$$a$$$ 的大小和颜色数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$) — 数组 $$$a$$$。
保证所有测试用例的$$$n$$$和$$$k$$$的值之和不超过$$$10^5$$$。
输出
对于每个测试用例,输出 $$$k$$$ 数字:包含颜色所有单元格的最小矩形的宽度和高度之和,对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色。
示例
输入 #1
5 2 1 1 1 2 2 1 2 3 5 3 2 4 4 2 1 2 1 2 5 3 1 2 3 2 1
输出 #1
4 4 2 0 6 6 2 0 8 6 10 6 2
注意
在第一个测试用例中,整个数组 $$$b$$$ 由颜色 $$$1$$$ 组成,因此颜色 $$$1$$$ 的最小矩形的大小为 $$$2 \times 2$$$,其边长之和为 $$$4$$$。
在第二个测试用例中,数组 $$$b$$$ 如下所示:
1112
角单元格之一的颜色为 $$$2$$$,其他三个单元格的颜色为 $$$1$$$。因此,颜色 $$$1$$$ 的最小矩形的大小为 $$$2 \times 2$$$,颜色 $$$2$$$ 的最小矩形大小为 $$$1 \times 1$$$。
在最后一个测试用例中,数组 $$$b$$$ 如下所示:
1111112221123211222111111