题目描述

:::align{center} :::

In the year 3025, ICPC (Interplanetary Constitution for Peculiar Creatures) found an exotic animal in asteroid KP-124. Upon further inspection, ICPC succeeded in figuring out how they live and how their ecosystem works altogether:

• They have a button on their belly, shaped just like a belly button of us earthers.
• On their head is a series of strange-looking symbols that works just like the decimal system of us earthers. ICPC already has a knowledge of what each of the symbols means, so for you as an earther we will just use the term “their number” and the standard decimal notation to represent the values.
• When their button is pressed, their number increases by a fixed value, possibly different for each entity. They try to hit their button as much as they can since each button press increases their chance of survival.

The researchers on KP-124 quickly became fascinated by these creatures and kept $n$ of those as pets in the research station to amuse themselves from time to time. Let us give them a unique id from 1 to $n$. The mission on KP-124 was a success with the pets’ emotional support and it was time for the researchers to leave the asteroid. As a farewell present to the pets, you, one of the researchers, decided to press buttons a total of $X$ times. To ensure an even chance of survival among the creatures, you made a rule to press the button on one that has the smallest number on its head each time. If there is a tie, you choose the one having the smallest id among those tied.

For example, let $n = 3$, $X = 3$, and the information of the 3 pets be as the table on the right. Initially they have the numbers $[5, 1, 3]$. On the first press, you will press the button on creature 2, since it has the smallest number. Now the numbers become $[5, 5, 3]$, so that the smallest will be creature 3 and you will press its button. Then the numbers become $[5, 5, 9]$ where the smallest one is tied between creature 1 and 2. Since creature 1 has the smallest id, you will press the button on creature 1, making the numbers on them $[8, 5, 9]$.

Given the information about the creatures before pressing their buttons, write a program to find the resulting numbers on the creatures’ heads.

输入格式

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $X$ ($1 \le n \le 500,000$; $1 \le X \le 10^{12}$), where $n$ and $X$ are as explained above. The second line contains $n$ nonnegative integers, $i$-th of which is the number initially written on the head of creature $i$. The third line contains $n$ positive integers, $i$-th of which is how much the value on creature $i$ is increased by when its button is pressed. All the integers on the second and the third lines are no more than $10^6$.

输出格式

Your program is to write to standard output. Print exactly one line. The line should contain $n$ integers, $i$-th of which is the number written on the head of creature $i$ after buttons are pressed $X$ times in total.

3 3
11 1 22
14 5 1

25 11 22

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

9 8 6 4 4 6 5 10 9