There are \(N\) people entering a restaurant at different times. These people are numbered from 1 to \(N\) by the staffs of the restaurant. There are \(K\) chefs working in the restaurant. These chefs are also numbered from 1 to \(N\) by the management of the restaurant. A person has to order immediately after he or she enters the restaurant. The arrival time of a person is given in an array \(A\) so that the restaurant can track the timings of the customers. Also, the time that a chef takes to prepare the customer's orders is given in an array \(B\).

The management of the restaurant also stores some data in array \(C\). The element of this array, \(C_i\), denotes the increased amount of the satisfaction level of the \(i^{th}\) customer if he or she has to wait for 1 unit of time after giving the order.

The restaurant is open until \(10^9\) units of time and all the orders must be prepared by this time.

Your task is to minimize the sum of the total satisfaction level of all the customers who come to the restaurant.

Note: Only one chef works to prepare an order of one person. A chef can only prepare one order at a time and a person's order can only be prepared by one chef. Also, if a chef completes preparation of order at time \(t\), then he or she can pick up another order and start preparing it at time \(t + 1\).

Input format

The first line contains two space-separated integers \(N\) and \(K\).
The second line contains an array \(A\) of \(N\) integers where \(A_i\) denotes the arrival time of the \(i^{th}\) person.
The third line contains an array \(B\) of \(N\) integers where \(B_i\) denotes the time it takes for preparing an order of a person \(i\).
The fourth line contains an array \(C\) of \(N\) integers where \(C_i\) denotes the satisfaction level of the \(i^{th}\) person for each unit of time that he or she has to wait.

Output Format

Print \(N\) space-separated integers(say \(q_i\)) denoting that the \(i^{th}\) person's order is picked up for preparation at time \(q_i\) by one of the free chefs. If no chef is available at that time, then your program must result in Wrong Answer verdict for that test.

Refer to the verdict and scoring section for caveats and the sample explanation for better understanding.

Constraints

\(1 \le K \le N \le 10^4\\ 1 \le A_i \le 10^5\\ 1 \le B_i, C_i \le 10^4\)

Verdict and Scoring

Note that if your output states that a person's order starts getting processing at time \(t\) and all the \(K\) chefs are busy at time \(t\), then it results in a Wrong Answer verdict. Since the restaurant closes at time \(t = 10^9\), all the orders must be ready by then. If there is any person whose order is still getting preparation or not yet given for preparation, then it results in a Wrong Answer verdict.

The scoring for this problem is relative. The participant with the best answer (in this case minimum satisfaction) receives the highest score and your score is relative to that.