#P18177. Penguins in Refrigerator
Penguins in Refrigerator
Penguins in Refrigerator
有 只企鹅,编号为 。编号为 的企鹅宽度为 。它们按照排列 依次进入冰箱:第 个进入的是编号 的企鹅。
冰箱宽度为 ,深度视为无限。所有企鹅进入后,如果相邻两只企鹅的宽度之和不超过 ,它们就可以交换位置。可以进行任意多次这样的交换,同一只企鹅也可以参与多次交换。
冰箱只有一扇门,采用后进先出的方式:如果不进行交换,企鹅的出门顺序为 。
请计算所有可能的不同出门顺序的数量,并求出其中字典序最小的顺序。每只企鹅按编号区分,宽度相同的企鹅仍是不同的企鹅;同一个最终顺序只计一次,不按交换操作序列计数。
两个排列的字典序按从左往右第一个不同位置的企鹅编号比较,编号较小的排列字典序较小。
输入格式
第一行两个整数 ,满足 、。
第二行 个整数 ,表示进入冰箱的顺序。保证它们是 的一个排列。
第三行 个整数 ,满足 。注意宽度按企鹅编号给出。
输出格式
第一行输出不同出门顺序的数量,对 取模。
第二行输出 个整数,表示字典序最小的出门顺序。
样例 1
输入:
5 10
1 2 3 4 5
6 5 3 9 2
输出:
3
5 4 2 1 3
样例 2
输入:
5 10
1 2 3 4 5
2 4 3 3 8
输出:
30
1 5 2 3 4