There are $N$ people entering a restaurant at different times (let us say they are numbered from 1 to $N$). There are $K$ chefs working in the restaurant (let us say they are numbered from 1 to $K$). A person orders immediately after he enters the restaurant. The arrival time of a person is given in an array $A$ and the time it takes to prepare his orders are given in an array $B$. You are also given an array $C$ where $C_i$ denotes that if the $i^{th}$ person waits for 1 unit of time after ordering the food (which is the same as entering the restaurant), his anger will increase by this amount. It is known that the restaurant will only be open till time $10^9$ units and all peoples' orders must be prepared by then (read verdict and scoring section for more information). You need to minimize the sum of total anger of all the people.

Due to a new policy, each chef has a contract from the restaurant on a timely basis. This means that each chef will stop accepting orders after a certain amount of time. For instance, if the chef 1 has his contract with 10 units of time, he will not accept orders after he has worked for at least 10 units of time. Note that the chef will still complete any ongoing orders that he has. Note that the chef's contract is the time that he should be preparing orders. If a chef is idle (not preparing any order for a customer), that does not count as his working time.

Note: Only one chef will work on preparing the order for 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 an order at time $t$, he will only be able to pick up and start preparing a new one 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 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 order for a person $i$.
• The fourth line contains an array $C$ of $N$ integers where $C_i$ denotes the anger of the $i^{th}$ person for each unit of time he has to wait. 
• The fifth line contains an array $D$ of $K$ integers where $D_i$ denotes the time unit mentioned in the $i^{th}$ chef's contract.

Output format

Print $N$ lines. Each line contains two space-separated integers (say $time_i$ and $chef_i$) denoting that $i^{th}$ person's order will be started to prepare at time $time_i$ by the chef $chef_i$. Note that 1-based indexing must be used for printing the chef. Please 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\\ 1 \le D_i \le 10^9$

It is given that $\sum_{i=1}^{k} D_i = \sum_{i=1}^{n} B_i$. And under this contraint, it can be proved that an answer always exists.

Verdict and scoring

Do note that if your output states that a person's order will be started processing at time $t$and all the $K$ chefs are busy at time $t$, it will result 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 in preparation or not yet given for preparation, it will result in a Wrong Answer verdict. If a chef is asked to prepare food, but his contract time is expired, it will still result in a Wrong Answer verdict.

The scoring for this problem is relative. The contestant with the best answer(in this case minimum anger) will receive the highest score and your score will be relative to that.