嘤嘤的猫娘
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

        世界名画——《番茄炒蛋拳》(嘉然)(图片加载失败)

        你每天都要吃一颗嘉心糖。在一天中:

             \bullet 你可以买若干颗(可以为 0 )嘉心糖放在家里,然后吃 1 颗家里的剩余的嘉心糖;

             \bullet 如果家里没有剩余的嘉心糖,并且你今天还没吃嘉心糖,你必须去买至少 1 颗嘉心糖。

        嘤嘤养了一只名叫怕door菲莉丝的猫猫(简称帕朵)。帕朵开了一家卖嘉心糖的商店,每天出售嘉心糖的数量、定价都可能不同。如果你知道接下来每天嘉心糖的定价和数量,你必然会花最少的钱购买嘉心糖,但作为奸商的帕朵显然想让你花最多的钱。

        嘤嘤告诉了你接下来 n嘉心糖的定价和出售的嘉心糖总数。帕朵会安排每一天的定价,并制定每天的销售数量(每天的销售数量至少为 1 )使得你接下来 n 天购买嘉心糖的花费最高。你想知道帕朵可能会安排的每天的定价和数量。

输入描述:

输入数据共两行。

第一行,两个整数 n (1 \le n \le 5 \times 10^5) ,表示接下来的天数, m(n \le m \le 10^9) 表示嘉心糖的总数。

第二行,n 个整数 a_1,a_2,…,a_n (1≤a_i≤10^9) 表示原本嘉心糖每天的定价(单位:¥ / 颗)。

输出描述:

输出两行。

第一行,输出 n 个整数 v_1,v_2,…,v_n (1≤v_i≤10^9) 表示接下来 n 天出售的嘉心糖的价格(单位:¥ / 颗) , v_i 必须取自 a ,并且 a 中每一个位置的元素必须使用一次,简而言之,v 必须是 a 的一个排列

第二行,输出 n 个整数 num_1,num_2,…,num_n (1 ≤ num_i ≤ m) 表示接下来 n 天出售的嘉心糖的数量(单位:颗),并且 \sum _1^n num_i=m

如果有多种解决方案,输出任意一种皆可。
示例1

输入

复制
6 38
1 1 4 5 1 4

输出

复制
1 5 1 4 4 1
1 9 1 9 8 10

说明

以这种定价方式时,你的最优方案之一是在第一、二、三、六天各买一颗嘉心糖,在第四天买两颗嘉心糖,总共需要花费¥16。
可以证明,不论如何安排定价方式,你最多只需要花费¥16就可以购买足够数量的嘉心糖。