F. Balloons
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tomorrow is Manuel's birthday, and you are preparing a surprise party for him. You are in charge of the decorations, but you are too lazy to go to the store. Fortunately, you already have a row of balloons left over from another birthday. To make it less obvious that they are the same, you plan to remove the balloons of a certain color and keep the rest. You have $$$n$$$ balloons arranged in a row, each of one of $$$2 \le k \le n$$$ colors. The color of the $$$i$$$-th balloon will be $$$1 \le a_i \le k$$$.

We will choose a color $$$c$$$ and pop all the balloons of that color. After popping them, there will be a new row of balloons that contains all the balloons that were not of color $$$c$$$, in the same order they were before the popping.

Manuel really likes consecutive segments of balloons of the same color. Therefore, you are interested in knowing for each color $$$c$$$ to pop what the maximum number of consecutive balloons of any color will remain after popping those of color $$$c$$$.

Input

The first line contains an integer $$$T$$$, the number of cases. There are $$$T$$$ cases, each with $$$2$$$ lines:

  • The first line contains $$$n$$$ and $$$k$$$, the number of balloons and the number of colors.
  • The second line contains the $$$n$$$ colors $$$a_1,\ldots,a_n$$$ of the balloons, in the order they are in the row.
Output

For each case, you must print $$$k$$$ numbers in one line: The $$$i$$$-th is the answer when you remove color $$$i$$$.

Scoring
  1. (6 points) $$$k=2$$$.
  2. (10 points) The sum of $$$n$$$ over all cases is at most $$$2000$$$.
  3. (17 points) The balloons of each color form at most $$$2$$$ segments.
  4. (36 points) There are no two consecutive balloons of the same color.
  5. (31 points) No additional restrictions.
Example
Input
1
7 3
1 1 2 1 2 3 1
Output
2 3 2
Note
  • $$$1 \le T \le 10^5$$$
  • $$$2 \le k \le n \le 2 \cdot 10^5$$$
  • The sum of $$$n$$$ over all cases is at most $$$2 \cdot 10^5$$$
  • There is at least one balloon of each color