You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

当朴素暴力无法通过题目，算法的大门才真正打开

国际共产主义一定要实现。为了推动 全世界共产事业 均衡发展，现有 $n$ 个革命集体，编号为 $1$ 到 $n$ 。

第 $i$ 个革命集体当前的建设水平为 $a_i$，每当它获得一次国际主义支援后，其建设水平就会增加 $b_i$ 。

为了贯彻落实党中央 “着力补齐短板，促进均衡发展” 的共同富裕总原则，计划总共将进行 $X$ 次支援操作。

每次操作时，必须选择当前最落后建设水平最小的革命集体进行支援（即 $a_i$ 最小）；

若有多个集体的建设水平同为最小，则选择其中编号最小的那个（即第二关键字为 $i$ ）。被选中的集体在这次支援后，其建设水平增加 $b_i$ 。

pgh 很想知道答案。现在请你计算，在完成全部 $X$ 次支援之后，所有革命集体的最终建设水平。

Input Format

第一行包含两个整数 $n, X$ ，表示革命集体的数量和支援的总次数。

接下来 $2$ 行，每行包含 $n$个整数 。

第一行 $a_i$，表示第 $i$ 个革命集体的初始建设水平。

第二行 $b_i$，表示第 $i$ 个革命集体每次获得支援后建设水平的增加量。

Output Format

输出一行，共 $n$ 个整数。

第 $i$ 个整数表示第 $i$ 个革命集体在完成 $X$ 次支援后的最终建设水平。

Sample

样例输入1

2 32
911 1121
626 2021

样例输出1

15935 17289

样例输入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

Hint

• $1 \le n \le 5 \times 10^5$
• $1 \le X \le 10^{12}$
• $0 \le a_i \le 10^6$
• $1 \le b_i \le 10^6$