CF883L.Berland.Taxi

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:

• All cars are available for picking up passengers. Initially the j-th car is located next to the house with the number x__j at time 0.
• All cars have the same speed. It takes exactly 1 minute for any car to travel between neighboring houses i and i + 1.
• The i-th request for taxi ride comes at the time t__i, asking for a passenger to be picked up at the house a__i and dropped off at the house b__i. All requests for taxi rides are given in the increasing order of t__i. All t__i are distinct.

When a request for taxi ride is received at time t__i, Berland.Taxi operator assigns a car to it as follows:

• Out of cars which are currently available, operator assigns the car which is the closest to the pick up spot a__i. Needless to say, if a car is already on a ride with a passenger, it won't be available for any rides until that passenger is dropped off at the corresponding destination.
• If there are several such cars, operator will pick one of them which has been waiting the most since it became available.
• If there are several such cars, operator will pick one of them which has the lowest number.

After a car gets assigned to the taxi ride request:

• The driver immediately starts driving from current position to the house a__i.
• Once the car reaches house a__i, the passenger is immediately picked up and the driver starts driving to house b__i.
• Once house b__i is reached, the passenger gets dropped off and the car becomes available for new rides staying next to the house b__i.
• It is allowed for multiple cars to be located next to the same house at the same point in time, while waiting for ride requests or just passing by.

If there are no available cars at time t__i when a request for taxi ride comes, then:

• The i-th passenger will have to wait for a car to become available.
• When a car becomes available, operator will immediately assign it to this taxi ride request.
• If multiple cars become available at once while the passenger is waiting, operator will pick a car out of them according to the rules described above.

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 a__i, then the corresponding wait time will be 0.

Berland.Taxi 是一家新成立的出租车公司，拥有 $k$ 辆出租车，近日刚刚在 Berland 首都投入运营。首都共有 $n$ 座房屋，沿一条直线排列，编号从 1（最左侧）到 $n$（最右侧），任意两座相邻房屋之间的距离均相等。

你需要帮助该公司按如下规则调度全天收到的所有出租车订单：

• 所有出租车均可随时用于接载乘客。初始时刻（时间 $0$）第 $j$ 辆车位于编号为 $x_j$ 的房屋旁。
• 所有出租车速度相同：从任意相邻房屋 $i$ 行驶至 $i+1$ 恰好耗时 1 分钟。
• 第 $i$ 个出租车订单于时刻 $t_i$ 到达，要求乘客在编号为 $a_i$ 的房屋上车，并在编号为 $b_i$ 的房屋下车。所有出租车订单按 $t_i$ 严格递增顺序给出，且所有 $t_i$ 均互不相同。

当在时刻 $t_i$ 收到一个出租车订单时，Berland.Taxi 的调度员按如下规则为其分配一辆出租车：

• 在当前可用的车辆中，调度员选择距离上车点 $a_i$ 最近的一辆。显然，若某辆车正在载客途中，则在将该乘客送达目的地前，它不可用于任何其他订单。
• 若存在多辆满足上述条件的车辆，则从中选择自变为可用状态后等待时间最长的一辆。
• 若仍有多个候选，则选择编号最小的一辆。

一旦某辆车被分配给该订单：

• 司机立即从当前位置出发，驶向房屋 $a_i$；
• 到达房屋 $a_i$ 后，乘客立即上车，司机随即启程驶向房屋 $b_i$；
• 到达房屋 $b_i$ 后，乘客立即下车，该车即变为可用状态，并停留在房屋 $b_i$ 旁，等待下一个订单；
• 允许多辆出租车在同一时刻位于同一房屋旁（无论是在等待订单，还是仅途经该处）。

若在订单到达时刻 $t_i$ 没有可用出租车，则：

• 第 $i$ 位乘客需等待某辆车变为可用；
• 一旦有车变为可用，调度员将立即将其分配给该订单；
• 若在乘客等待期间多辆车同时变为可用，则调度员仍按前述规则从中选出一辆。

调度员按顺序逐个处理订单。因此，若有多位乘客正在等待车辆变为可用，则调度员不会提前处理第 $(i+1)$ 个订单，而必须先为第 $i$ 个订单成功分配车辆后，才继续处理后续订单。

你的任务是编写程序，处理给定的 $m$ 个出租车订单。对每个订单，你需要确定最终分配给它的出租车编号，以及乘客需等待出租车到达的时长（单位：分钟）。注意：若已有出租车恰好位于房屋 $a_i$，则对应等待时间为 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 _x_1, _x_2, ..., x__k (1 ≤ x__i ≤ n) — initial positions of cars. x__i 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 t__j, a__j and b__j (1 ≤ t__j ≤ 1012, 1 ≤ a__j, b__j ≤ n, a__j ≠ b__j), where t__j is time in minutes when a request is made, a__j is a house where passenger needs to be picked up, and b__j is a house where passenger needs to be dropped off. All taxi ride requests are given in the increasing order of t__j. All t__j are distinct.

输入的第一行包含整数 $n$、$k$ 和 $m$（$2 \leq n \leq 2\cdot10^5$，$1 \leq k,\,m \leq 2\cdot10^5$）——分别表示房屋数量、汽车数量和出租车乘车请求的数量。
第二行包含整数 $x_1,\,x_2,\,\dots,\,x_k$（$1 \leq x_i \leq n$）——表示各辆汽车的初始位置。其中 $x_i$ 表示第 $i$ 辆汽车最初所在房屋的编号。允许多辆汽车位于同一栋房屋旁。

接下来的 $m$ 行描述乘车请求信息。每条乘车请求由整数 $t_j$、$a_j$ 和 $b_j$（$1 \leq t_j \leq 10^{12}$，$1 \leq a_j,\,b_j \leq n$，且 $a_j \neq b_j$）表示：$t_j$ 是该请求提出的时间（单位：分钟），$a_j$ 是乘客需被接载的房屋编号，$b_j$ 是乘客需被送达的房屋编号。所有出租车乘车请求按 $t_j$ 递增顺序给出，且所有 $t_j$ 互不相同。

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.

输出 m 行：第 j 行应包含两个整数，即第 j 个乘车请求的答案——调度员分配的车辆编号和乘客等待时间。

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.

在第一个样例测试中，一个请求在时刻 5 到达，汽车需要从第 3 号房屋出发前往第 2 号房屋接乘客。因此等待时间为 1，行程将在时刻 $5 + 1 + 6 = 12$ 完成。第二个请求在时刻 9 到达，因此乘客需等待汽车在时刻 12 变得可用，之后汽车还需花费 2 分钟从第 8 号房屋前往第 10 号房屋。故总等待时间为 $3 + 2 = 5$。

在第二个样例测试中，汽车 1 和汽车 2 到第一位乘客的距离相同，且“自变为可用状态以来的等待时间”也相同。根据规则，编号更小的汽车在平局时获胜，因此汽车 1 获胜。它将于时刻 3 到达第 3 号房屋，因此等待时间为 2。