|2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)|
Berland.Taxi is a new taxi company with k cars which started operating in the capital of Berland just recently. The capital has n houses on a straight line numbered from 1 (leftmost) to n (rightmost), and the distance between any two neighboring houses is the same.
You have to help the company schedule all the taxi rides which come throughout the day according to the following rules:
When a request for taxi ride is received at time ti, Berland.Taxi operator assigns a car to it as follows:
After a car gets assigned to the taxi ride request:
If there are no available cars at time ti when a request for taxi ride comes, then:
Operator processes taxi ride requests one by one. So if multiple passengers are waiting for the cars to become available, operator will not move on to processing the (i + 1)-th ride request until the car gets assigned to the i-th ride request.
Your task is to write a program that will process the given list of m taxi ride requests. For each request you have to find out which car will get assigned to it, and how long the passenger will have to wait for a car to arrive. Note, if there is already car located at the house ai, then the corresponding wait time will be 0.
The first line of input contains integers n, k and m (2 ≤ n ≤ 2·105, 1 ≤ k, m ≤ 2·105) — number of houses, number of cars, and number of taxi ride requests. The second line contains integers x1, x2, ..., xk (1 ≤ xi ≤ n) — initial positions of cars. xi is a house number at which the i-th car is located initially. It's allowed for more than one car to be located next to the same house.
The following m lines contain information about ride requests. Each ride request is represented by integers tj, aj and bj (1 ≤ tj ≤ 1012, 1 ≤ aj, bj ≤ n, aj ≠ bj), where tj is time in minutes when a request is made, aj is a house where passenger needs to be picked up, and bj is a house where passenger needs to be dropped off. All taxi ride requests are given in the increasing order of tj. All tj are distinct.
Print m lines: the j-th line should contain two integer numbers, the answer for the j-th ride request — car number assigned by the operator and passenger wait time.
10 1 2
5 2 8
9 10 3
5 2 1
10 3 5
5 2 2
10 3 5
20 4 1
In the first sample test, a request comes in at time 5 and the car needs to get from house 3 to house 2 to pick up the passenger. Therefore wait time will be 1 and the ride will be completed at time 5 + 1 + 6 = 12. The second request comes in at time 9, so the passenger will have to wait for the car to become available at time 12, and then the car needs another 2 minutes to get from house 8 to house 10. So the total wait time is 3 + 2 = 5.
In the second sample test, cars 1 and 2 are located at the same distance from the first passenger and have the same "wait time since it became available". Car 1 wins a tiebreaker according to the rules because it has the lowest number. It will come to house 3 at time 3, so the wait time will be 2.