Cossack Vus and the Railway#11074
Cossack Vus came to the railway station to travel to the magic boots trials and discovered that there are lighting problems along the entire railway track. The railway has the shape of a large figure-eight, along which a train travels. We will call the place where the tracks intersect the intersection.
Cossack Vus wants to fix the lighting problems. For this purpose, he purchased lanterns, each of which has a color from to . It is guaranteed that at least one lantern of each color was purchased. The lighting problems will be fixed if:
lanterns are placed along the railway.
One of the lanterns stands at the intersection.
If two lanterns stand next to each other (i.e., they both stand on the same branch and there is no other lantern between them), then they have different colors.
At least 2 lanterns stand on the upper and lower branches of the road (not including the intersection).
Help Cossack Vus find any way to fix the lighting problems or indicate that it does not exist.
The first line contains three integers , , and (5 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5, 0 \leq g \leq 8) — the number of lanterns and colors respectively, as well as the block number.
The next line contains integers a_1, a_2, \dots, a_n (1 \leq a_i \leq k) — the colors of the lanterns.
It is guaranteed that each number from to is present in this array.
If there is no answer, print .
Otherwise, in the first line print two numbers and (2 \leq x, y < n, 1 + x + y = n) — the number of lanterns on the upper and lower branches not counting the intersection, respectively.
In the second line print numbers b_1, b_2, \dots, b_x (1 \leq b_i \leq k) — the colors of the lanterns standing on the upper branch in clockwise order, starting from the first lantern after the intersection.
In the third line print one number (1 \leq c \leq k) — the color of the lantern standing at the intersection.
In the fourth line print numbers d_1, d_2, \dots, d_y (1 \leq d_i \leq k) — the colors of the lanterns standing on the lower branch in clockwise order, starting from the first lantern after the intersection.
If there are multiple answers, you may print any of them.
Example 1
Example 2
Example 3
Example 4
Example 5
Consider that the lantern at the intersection stands on both branches simultaneously.
In the first example, we can place two lanterns with colors and on the upper branch, two lanterns with colors and on the lower branch, and a lantern with color at the intersection. Thus, every two adjacent lanterns will have different colors.
The second example is shown in the picture above.
In the third example, Cossack Vus will not be able to fix the lighting problems, because with any arrangement there will be two adjacent lanterns of color .
( points): n \leq 8.
( points): is even, one of the colors appears exactly \frac{n}{2} times, n \leq 1000.
( points): n = k, n \leq 1000.
( points): n \leq 18; k = 2.
( points): k = 2, n \leq 1000.
( points): k \neq 2, n \leq 1000.
( points): n \leq 1000.
( points): without additional constraints.