SP13055 IZHONYT - New Year Train

在新年前夕，一个国家的政府决定向每个城镇发送一列满载礼物的火车。每个城镇都会收到装有礼物的一节车厢。安排的路线是这样的：火车到达一个站点后，会卸下最后一节车厢，继续前往下一个城镇，直到所有礼物都送完。但是，出发前发现装载工人没有按照车厢的编号顺序进行装载，而是随机装车。无法从火车中间卸下一节车厢，也没有时间重新排列这些车厢。幸运的是，车库有多条平行轨道。在车厢进入车库时，可以被引导到任意一条轨道上，而车厢可以按照正确的顺序（1, 2, 3, 4 等）从另一侧驶出，请注意，送达城镇的顺序是反向的（..., 4, 3, 2, 1）。 例如，假设火车上的车厢顺序是 2, 5, 1, 4, 6, 3。我们可以将车厢 2, 5, 6 引导到第一条轨道；车厢 1, 4 引导到第二条轨道；车厢 3 引导到第三条轨道。这样，车厢便能够按正确顺序驶出车库。幸运的是，车库中有足够多的轨道来进行重新排列。

第一行输入两个整数 $N$ 和 $M$，表示火车上车厢的数量和车库中轨道的数量（1 ≤ N ≤ 800,000，1 ≤ M ≤ 100,000，M ≤ N）。第二行是 $N$ 个整数，表示在进入车库前车厢的排列顺序。保证总能找到解决方案。

输出第一行需包含 $N$ 个整数，表示输入中每节车厢要选择的轨道编号（轨道编号从 1 到 $M$）。第二行则是表示轨道的出库顺序，使得车厢按 1, 2, 3 等依次驶出。如果有多个解决方案，请输出在第一行字典序最小的那个方案。 **本翻译由 AI 自动生成**