#215185. [UOI 2022 II Stage] 铁路

哥萨克胡子来到铁路上，准备去测试魔法鞋，却发现整条铁路线上都有照明问题。铁路呈一个大“8”字形，火车在其上行驶。两条线路相交的地方称为交叉点。

:::align{center} :::

哥萨克胡子想解决照明问题。为此，他购买了 盏路灯，每盏灯的颜色为 到 中的一种。保证至少购买了每种颜色的一盏灯。当满足以下条件时，照明问题将被解决：

• 沿铁路线放置 盏路灯。
• 其中一盏路灯位于交叉点上。
• 如果两盏路灯相邻（即它们位于同一条支线上，且它们之间没有其他路灯），则它们的颜色必须不同。
• 在铁路的上支路和下支路上（不包括交叉点）均至少有 盏路灯。

请帮助哥萨克胡子找到任意一种解决照明问题的方法，或者指出该方法不存在。

第一行包含三个整数 、 和 (, , ) —— 分别表示路灯的数量、颜色的数量以及子任务编号。

下一行包含 个整数 () —— 路灯的颜色。

保证从 到 的每个数字都在该数组中至少出现一次。

如果无解，则输出 。

否则，在第一行输出两个数字 和 (, ) —— 分别表示上支路和下支路上（不包括交叉点）的路灯数量。

在第二行输出 个数字 () —— 上支路上路灯的颜色，按顺时针方向从交叉点后的第一个路灯开始排序。

在第三行输出一个数字 () —— 位于交叉点的路灯颜色。

在第四行输出 个数字 () —— 下支路上路灯的颜色，按顺时针方向从交叉点后的第一个路灯开始排序。

如果存在多个答案，可以输出任意一个。

样例输入 1

5 3 0
1 2 3 2 1

样例输出 1

2 2
2 1 
3
1 2

样例输入 2

8 3 0
1 1 1 1 2 2 2 3

样例输出 2

5 2
1 2 1 2 1
3
2 1

样例输入 3

7 3 0
1 1 1 1 1 2 3

样例输出 3

-1

样例输入 4

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

样例输出 4

5 3
1 2 1 2 1 
2
1 2 1

样例输入 5

6 6 0
1 2 3 4 5 6

样例输出 5

3 2
6 2 5 
1
4 3

样例说明

请注意，位于交叉点的路灯同时属于两条支路。

在第一个样例中，我们可以将颜色为 和 的两盏路灯放在上支路，将颜色为 和 的两盏路灯放在下支路，并将一盏颜色为 的路灯放在交叉点。这样，每两盏相邻的路灯颜色都不同。

第二个样例对应于上图。

在第三个样例中，哥萨克胡子将无法解决照明问题，因为无论怎样放置，总会找到两盏相邻的颜色为 的路灯。

评分细则

• （8 分）： 。
• （20 分）： 为偶数，有一种颜色恰好出现 次，且 。
• （5 分）： , 。
• （8 分）： ; 。
• （10 分）： , 。
• （14 分）： , 。
• （20 分）： 。
• （15 分）： 无额外限制。

翻译由 DeepSeek V3 完成