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$