You are given data of customers that visit a bank in a day. The data contains the following details: (Customer ID, Entry time, Maximum wait time, Happiness Factor, time required for work completion). There $N$ are  such customers. There are only $K$ members in the staff that can assist these customers. Given the data, you need to assign these $K$ staff members to the customers in such a way that the total happiness at the end of the day is as maximum possible. There are following constraints of assigning the staff members - 

1. You can assign a staff member to at most one person at a time.
2. The closing time of the bank is 5:30 PM i.e. (1050th minute of the day). The time allocation should not be greater than that. Also, you need to allocate time in such a way that its completion time from the start does not exceed 1050.
3. The wait time of a particular customer includes its work completion time. Also, the customer remains in the bank even if his wait time gets over till 1050th minute of the day.

Note: It is very important to read the scoring mechanism of the statement as it is a relative scoring problem.

Input
The first line of the data contains two space-separated integers $N$ and $K$ as input which denotes how many customers are there and how many staff members. You can assume that staff member id is a sequence from integer $1$ to $K$.
Each of the next $N$ lines contains the following format - 
(Integer, Integer, Integer, Decimal, Integer) which refers to the following variables - (CustomerID, Entry time in minutes calculated after 00:00 AM, Maximum wait time in minutes, Happiness factor, time required for work completion in minutes)
All the values are separated by space in each line. Read the sample explanation.

Output
In the order of customer data given, you need to print 2 integers corresponding to each customer in a new line - The time of allocation of the staff member to him/her in minutes calculated from 00:00 AM and staff member id which is allocated to that customer. 
If it is impossible to allocate any staff member to a person, then you need to print -1 for both the integers.

Scoring and Verdict
There are two scenarios of scoring -

1. For the customer to which a staff member is allocated then the score is increased by (entry time + maximum_wait_time - staff_allocation_time - work_completion_time) * (happiness_index) * 100
2. If the customer is not allocated any staff member then the score is increased by (entry time - 1050) * (happiness_index) * 100

Constraints
$0 \le customer \_id \le 10^9 (unique)$
$1 \le N \le 100000$
$540 \le start \_ time \le 960$
$1 \le K \le 300$
$5 \le work \_completion \_time \le90$
$0.0 \le happiness \_factor \le 1.0$
$work\_completion\_time \le maximum \_wait \_time \le 180$