P13701 [NWERC 2023] Brickwork

Bob the Builder 厌倦了建造小房子和铺设狭窄的道路，他渴望做一些更宏大的事情。 一个非常古怪的客户给他的新工作正好满足了他的需求： 他被要求建造一堵具有特定宽度且无限高的墙！ 客户向他保证，无需担心建筑材料，因为已经为他订购了无限供应的各种砖块。 当然，建造一堵稳定的墙需要非常仔细的规划，尤其是当它要无限高时。 特别地，只有当连续两行砖块之间的所有缝隙都不在同一竖线上时，这堵墙才是稳定的，如下图 B.1 所示。 Bob 以他多年的经验知道，如果可以建造这样的墙，那么只需交替使用两种行的排布即可完成。  :::align{center} 图 B.1：左图为使用样例输入 1 的砖块类型搭建的不稳定墙。右图为使用相同砖块类型搭建的稳定墙。注意，虽然只展示了两行，但通过交替重复这两种行的排布，可以建造无限高的墙。 ::: Bob 对这项新工作感到非常兴奋，并迅速投入工作。 给定可用的砖块类型，是否可以建造一堵宽度恰好为 $w$、无限高且稳定的墙？ 如果可以，Bob 应该如何仅用两种交替的行排布来建造这堵墙？

输入包括： - 一行，包含两个整数 $n$ 和 $w$（$1\leq n,w\leq 3\times 10^5$），分别表示砖块类型的数量和墙的宽度。 - 一行，包含 $n$ 个整数 $b$（$1\leq b\leq w$），表示每种砖块的宽度。 注意，Bob 对所有砖块类型都有无限供应。

如果可以建造这样的墙，输出 “possible”。 否则，输出 “impossible”。 如果可以建造，接下来输出两行，分别表示可以交替使用的两种行排布。 对于每一行，先输出该行所用砖块的数量，然后依次输出这些砖块的宽度（按你希望的顺序）。 只要交替使用这两种行排布可以无限高地搭建出稳定的墙，你的方案就是有效的。 如果存在多种有效方案，你可以输出任意一种。

由 ChatGPT 4.1 翻译