H. 小小的英特纳雄耐尔一定要实现!

内存限制:369 MiB 时间限制:3232 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

本题与 英特纳雄耐尔一定要实现! 仅数据范围不同

说白了是签到题

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

个革命集体当前的建设水平为 ,每当它获得一次国际主义支援后,其建设水平就会增加

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

每次操作时,必须选择当前最落后建设水平最小的革命集体进行支援(即 最小);

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

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

输入格式

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

接下来 行,每行包含 个整数 。

第一行 ,表示第 个革命集体的初始建设水平。

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

输出格式

输出一行,共 个整数。

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

样例

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

数据范围与提示