JOI 2017 Final T5: Rope Folding

This problem is translated from JOI 2017 Final T5 "Rope".

JOI Baby is playing with a rope. The rope can be viewed as a line segment extending to both left and right and is composed of N pieces. Each piece has length 1 and thickness 1. There are M colors on the rope. The i-th piece from the left (1 ≤ i ≤ N) is painted in color C_i (1 ≤ C_i ≤ M). The left endpoint of the rope is defined as the left endpoint of the first piece and the right endpoint as the right endpoint of the last piece. In particular, the distance from the right endpoint of the i-th piece (from the left) to the left endpoint is exactly i.

JOI shortens the rope by repeatedly performing the following folding process until the rope length becomes 2:

• Suppose the rope currently consists of L pieces. Choose an integer j (1 ≤ j < L) and designate the j-th piece from the left as the new left endpoint. Then, fold the rope as follows:
• If j ≤ L/2, then for each i (1 ≤ i ≤ j) the i-th piece from the left is twisted together with the (2j-i+1)-th piece. In this case, the original right endpoint remains the right endpoint and the rope length becomes L − j.
• If j > L/2, then for each i (2j − L + 1 ≤ i ≤ j) the i-th piece from the left is twisted together with the (2j-i+1)-th piece. In this case, the original left endpoint becomes the right endpoint and the rope length becomes j.

Twisting can be performed only if the two pieces have the same color. Before twisting, you are allowed to change the color of any piece arbitrarily, and the cost to change the color of a piece is equal to its thickness. After twisting, the two pieces become one twisted group whose thickness is the sum of their thicknesses.

The final rope is the one with length 2. JOI wants to know, for each color from 1 to M, the minimum total cost required to shorten the rope to length 2 so that the final rope contains that color (i.e. at least one of its two groups is painted in that color).

Note on Folding: A fold operation can be performed from the left or from the right. In the case of a right fold (j > L/2), it is equivalent to reversing the rope, performing a left fold with parameter j' = L − j, and then reversing the result. Thus, you may simulate both operations using the left fold logic.

---

Input Format

The first line contains two integers N and M.

The second line contains N integers: C₁, C₂, …, C_N where 1 ≤ C_i ≤ M.

Output Format

Output M integers separated by spaces. The i-th integer represents the minimum total cost required so that in the final rope (of length 2) at least one twisted group has color i. If it is impossible for the final rope to contain color i, output -1 for that color.

---

Problem Constraints and Notes

• You are allowed to change colors before twisting, and the cost of changing a piece's color is equal to its thickness.
• When twisting two groups with thicknesses T₁ and T₂ and colors a and b respectively, you may change one or both colors so that they match. Changing the color of a group to a chosen color c costs T₁ if a ≠ c and T₂ if b ≠ c.
• For small input sizes, a brute-force DFS with memoization is feasible.

---

Example Test Cases

Test Case 1:

Input:
2 3
1 2
Output:
0 0 -1

</p>

Explanation: The rope already has length 2 and the final colors are 1 and 2. Color 3 is not present, so the answer for color 3 is -1.

Test Case 2:

Input:
4 2
1 2 1 2
Output:
1 1

</p>

Test Case 3:

Input:
3 3
3 1 2
Output:
1 1 1

</p>

---

Implementation Note: Since the folding process is very flexible and the rope length is reduced via a sequence of operations (each of which pairs symmetric pieces), one way to solve the problem is to use DFS to enumerate all valid folding sequences. In each fold operation, you consider every possible valid folding position and every way to match the colors (by optionally paying the cost to change a group’s color). The state in the DFS is the current ordered list of twisted groups, where each group is represented by its color and thickness. Once the state length reaches 2, update the answer for each color present.

inputFormat

The first line contains two integers N and M. The second line contains N integers: C₁, C₂, …, C_N (1 ≤ C_i ≤ M).

outputFormat

Output M integers separated by spaces. The i-th integer is the minimum cost required to achieve a final rope (of length 2) that contains color i. If it is impossible, output -1 for that color.

sample

2 3
1 2

0 0 -1

</p>