Problem Description

Cossack Moustache came to the railway to test the magic shoes, but found that the entire railway line had lighting problems. The railway has the shape of a big “8”, and trains run on it. The place where the two tracks intersect is called the intersection.

:::align{center} :::

Cossack Moustache wants to solve the lighting problem. To do this, he bought $n$ street lights. Each light has a color from $1$ to $k$. It is guaranteed that at least one light of each color is bought. The lighting problem is considered solved when the following conditions are satisfied:

• Place the $n$ street lights along the railway.
• One of the street lights is placed at the intersection.
• If two street lights are adjacent (i.e., they are on the same branch, and there is no other street light between them), then their colors must be different.
• On both the upper branch and the lower branch of the railway (excluding the intersection), there are at least $2$ street lights.

Please help Cossack Moustache find any way to solve the lighting problem, or state that no such way exists.

Input Format

The first line contains three integers $n$, $k$, and $g$ ($5 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq 2 \cdot 10^5$, $0 \leq g \leq 8$), representing the number of street lights, the number of colors, and the subtask index, respectively.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq k$), the colors of the street lights.

It is guaranteed that every number from $1$ to $k$ appears at least once in this array.

Output Format

If there is no solution, output $-1$.

Otherwise, on the first line output two numbers $x$ and $y$ ($2 \leq x, y < n$, $1 + x + y = n$), representing the number of street lights on the upper branch and the lower branch (excluding the intersection), respectively.

On the second line output $x$ numbers $b_1, b_2, \dots, b_x$ ($1 \leq b_i \leq k$), the colors of the street lights on the upper branch, listed in clockwise order starting from the first street light after the intersection.

On the third line output one number $c$ ($1 \leq c \leq k$), the color of the street light at the intersection.

On the fourth line output $y$ numbers $d_1, d_2, \dots, d_y$ ($1 \leq d_i \leq k$), the colors of the street lights on the lower branch, listed in clockwise order starting from the first street light after the intersection.

If there are multiple answers, output any one of them.

5 3 0
1 2 3 2 1

2 2
2 1 
3
1 2

8 3 0
1 1 1 1 2 2 2 3

5 2
1 2 1 2 1
3
2 1

7 3 0
1 1 1 1 1 2 3

-1

9 2 0
1 1 1 1 1 2 2 2 2

5 3
1 2 1 2 1 
2
1 2 1

6 6 0
1 2 3 4 5 6

3 2
6 2 5 
1
4 3

Hint

Sample Explanation

Please note that the street light at the intersection belongs to both branches at the same time.

In the first sample, we can place two street lights of colors $1$ and $2$ on the upper branch, place two street lights of colors $1$ and $2$ on the lower branch, and place one street light of color $3$ at the intersection. In this way, every pair of adjacent street lights has different colors.

The second sample corresponds to the figure above.

In the third sample, Cossack Moustache will not be able to solve the lighting problem, because no matter how the lights are placed, there will always be two adjacent street lights of color $1$.

Scoring

• (8 points): $n \leq 8$.
• (20 points): $n$ is even, there is a color that appears exactly $\frac{n}{2}$ times, and $n \leq 1000$.
• (5 points): $n = k$, $n \leq 1000$.
• (8 points): $n \leq 18$; $k = 2$.
• (10 points): $k = 2$, $n \leq 1000$.
• (14 points): $k \neq 2$, $n \leq 1000$.
• (20 points): $n \leq 1000$.
• (15 points): No additional constraints.

Translated by DeepSeek V3.

Translated by ChatGPT 5