在 3025 年，ICPC（星际奇异生物宪法组织）在小行星 KP-124 上发现了一种奇异动物。经过进一步检查，ICPC 成功弄清了它们的生活方式以及整个生态系统的运作机制：

• 它们的腹部有一个按钮，形状就像我们地球人的肚脐一样。
• 它们的头上有一系列奇怪的符号，其运作方式就像我们地球人的十进制系统。ICPC 已经掌握了每个符号的含义，因此对于作为地球人的你，我们将直接使用“它们的数字”这一术语，并用标准的十进制记数法来表示这些数值。
• 当它们的按钮被按下时，它们头上的数字会增加一个固定的值，这个值对于每个个体可能不同。它们会尽可能多地按下自己的按钮，因为每次按下按钮都会增加它们生存的机会。

KP-124 上的研究人员很快被这些生物所吸引，并将其中 $n$ 只作为宠物养在研究站里，不时以此自娱。让我们给它们分配从 1 到 $n$ 的唯一编号。在宠物的精神支持下，KP-124 上的任务取得了成功，研究人员是时候离开这颗小行星了。作为给宠物的告别礼物，身为研究人员之一的你决定总共按下按钮 $X$ 次。为了确保生物之间有均等的生存机会，你制定了一条规则：每次都按下头上数字最小的那只生物的按钮。如果存在平局，则在平局的生物中选择编号最小的那一个。

例如，设 $n = 3$，$X = 3$，3 只宠物的信息如下表所示。初始时它们的数字为 $[5, 1, 3]$。第一次按下时，你会按下 2 号生物的按钮，因为它拥有最小的数字。现在数字变为 $[5, 5, 3]$，此时最小的是 3 号生物，你会按下它的按钮。接着数字变为 $[5, 5, 9]$，此时 1 号和 2 号生物的数字并列最小。由于 1 号生物的编号最小，你会按下 1 号生物的按钮，使得它们的数字变为 $[8, 5, 9]$。

给定按下按钮前有关这些生物的信息，编写一个程序来计算按下按钮后它们头上的最终数字。

输入格式

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $X$ ($1 \le n \le 500,000$; $1 \le X \le 10^{12}$)，其中 $n$ 和 $X$ 的含义如上所述。第二行包含 $n$ 个非负整数，其中第 $i$ 个数是初始时写在第 $i$ 只生物头上的数字。第三行包含 $n$ 个正整数，其中第 $i$ 个数是按下第 $i$ 只生物的按钮时，其头上数值增加的量。第二行和第三行中的所有整数均不超过 $10^6$。

输出格式

你的程序需要写入标准输出。打印一行，包含 $n$ 个整数，其中第 $i$ 个数是总共按下 $X$ 次按钮后，写在第 $i$ 只生物头上的数字。

样例

输入 1

3 3
11 1 22
14 5 1

输出 1

25 11 22

输入 2

9 5
9 8 6 2 1 6 5 10 9
9 3 9 1 1 4 10 5 3

输出 2

9 8 6 4 4 6 5 10 9