English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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_.
[samples]
## Note
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.
Berland.Taxi 是一家新成立的出租车公司，刚刚在 Berland 首都投入运营，拥有 #cf_span[k] 辆出租车。首都的街道上共有 #cf_span[n] 栋房屋，沿直线排列，编号从 #cf_span[1]（最左端）到 #cf_span[n]（最右端），任意相邻两栋房屋之间的距离相同。
你需要帮助该公司按照以下规则调度全天的出租车订单：
当在时间 #cf_span[ti] 收到出租车订单时，Berland.Taxi 操作员按如下方式分配车辆：
在车辆被分配给出租车订单后：
如果在时间 #cf_span[ti] 收到订单时没有可用的车辆，则：
操作员按顺序处理出租车订单。因此，如果有多个乘客在等待车辆可用，操作员在为第 #cf_span[i] 个订单分配车辆之前，不会处理第 #cf_span[(i + 1)] 个订单。
你的任务是编写一个程序，处理给定的 #cf_span[m] 个出租车订单。对于每个订单，你需要确定哪一辆车会被分配给它，以及乘客需要等待多久车辆才会到达。注意，如果已有车辆位于房屋 #cf_span[ai]，则对应的等待时间为 #cf_span[0]。
输入的第一行包含整数 #cf_span[n], #cf_span[k] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·10^5], #cf_span[1 ≤ k, m ≤ 2·10^5]）——房屋数量、车辆数量和出租车订单数量。第二行包含整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]）——车辆的初始位置。#cf_span[xi] 表示第 #cf_span[i] 辆车初始所在的房屋编号。允许多辆车辆位于同一房屋。
接下来的 #cf_span[m] 行包含订单信息。每个订单由整数 #cf_span[tj], #cf_span[aj] 和 #cf_span[bj] 表示（#cf_span[1 ≤ tj ≤ 10^{12}], #cf_span[1 ≤ aj, bj ≤ n], #cf_span[aj ≠ bj]），其中 #cf_span[tj] 是订单发起的时间（分钟），#cf_span[aj] 是乘客上车的房屋，#cf_span[bj] 是乘客下车的房屋。所有出租车订单按 #cf_span[tj] 递增顺序给出，且所有 #cf_span[tj] 互不相同。
请输出 #cf_span[m] 行：第 #cf_span[j] 行应包含两个整数，表示第 #cf_span[j] 个订单的答案——操作员分配的 _车辆编号_ 和 _乘客等待时间_。
在第一个样例中，订单在时间 #cf_span[5] 到达，车辆需要从房屋 #cf_span[3] 移动到房屋 #cf_span[2] 接乘客。因此等待时间为 #cf_span[1]，行程将在时间 #cf_span[5 + 1 + 6 = 12] 完成。第二个订单在时间 #cf_span[9] 到达，乘客必须等到车辆在时间 #cf_span[12] 可用，然后车辆还需 #cf_span[2] 分钟从房屋 #cf_span[8] 移动到房屋 #cf_span[10]。因此总等待时间为 #cf_span[3 + 2 = 5]。
在第二个样例中，车辆 #cf_span[1] 和 #cf_span[2] 距离第一位乘客的房屋距离相同，且“自可用以来的等待时间”也相同。根据规则，车辆 #cf_span[1] 因编号较小而胜出。它将在时间 #cf_span[3] 到达房屋 #cf_span[3]，因此等待时间为 #cf_span[2]。
## Input
输入的第一行包含整数 #cf_span[n], #cf_span[k] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·10^5], #cf_span[1 ≤ k, m ≤ 2·10^5]）——房屋数量、车辆数量和出租车订单数量。第二行包含整数 #cf_span[x1, x2, ..., xk]（#cf_span[1 ≤ xi ≤ n]）——车辆的初始位置。#cf_span[xi] 表示第 #cf_span[i] 辆车初始所在的房屋编号。允许多辆车辆位于同一房屋。接下来的 #cf_span[m] 行包含订单信息。每个订单由整数 #cf_span[tj], #cf_span[aj] 和 #cf_span[bj] 表示（#cf_span[1 ≤ tj ≤ 10^{12}], #cf_span[1 ≤ aj, bj ≤ n], #cf_span[aj ≠ bj]），其中 #cf_span[tj] 是订单发起的时间（分钟），#cf_span[aj] 是乘客上车的房屋，#cf_span[bj] 是乘客下车的房屋。所有出租车订单按 #cf_span[tj] 递增顺序给出，且所有 #cf_span[tj] 互不相同。
## Output
请输出 #cf_span[m] 行：第 #cf_span[j] 行应包含两个整数，表示第 #cf_span[j] 个订单的答案——操作员分配的 _车辆编号_ 和 _乘客等待时间_。
[samples]
## Note
在第一个样例中，订单在时间 #cf_span[5] 到达，车辆需要从房屋 #cf_span[3] 移动到房屋 #cf_span[2] 接乘客。因此等待时间为 #cf_span[1]，行程将在时间 #cf_span[5 + 1 + 6 = 12] 完成。第二个订单在时间 #cf_span[9] 到达，乘客必须等到车辆在时间 #cf_span[12] 可用，然后车辆还需 #cf_span[2] 分钟从房屋 #cf_span[8] 移动到房屋 #cf_span[10]。因此总等待时间为 #cf_span[3 + 2 = 5]。在第二个样例中，车辆 #cf_span[1] 和 #cf_span[2] 距离第一位乘客的房屋距离相同，且“自可用以来的等待时间”也相同。根据规则，车辆 #cf_span[1] 因编号较小而胜出。它将在时间 #cf_span[3] 到达房屋 #cf_span[3]，因此等待时间为 #cf_span[2]。
**Definitions**
Let $ n, k, m \in \mathbb{Z}^+ $: number of houses, cars, and ride requests.
Let $ X = (x_1, x_2, \dots, x_k) \in \{1, \dots, n\}^k $: initial positions of cars.
Let $ R = \{(t_j, a_j, b_j) \mid j \in \{1, \dots, m\}\} $: sequence of ride requests, with $ t_j < t_{j+1} $, $ a_j \ne b_j $, and $ t_j \in \mathbb{Z}^+ $, $ a_j, b_j \in \{1, \dots, n\} $.
Each car $ i \in \{1, \dots, k\} $ has a state:
- $ p_i \in \{1, \dots, n\} $: current position.
- $ f_i \in \mathbb{R}_{\ge 0} $: time when car becomes free (initially 0).
**Constraints**
1. $ 2 \le n \le 2 \cdot 10^5 $
2. $ 1 \le k, m \le 2 \cdot 10^5 $
3. $ 1 \le x_i \le n $ for all $ i \in \{1, \dots, k\} $
4. $ 1 \le t_j \le 10^{12} $, $ 1 \le a_j, b_j \le n $, $ a_j \ne b_j $ for all $ j \in \{1, \dots, m\} $
5. Requests are processed in increasing $ t_j $ order; no concurrent processing.
**Objective**
For each request $ j \in \{1, \dots, m\} $:
- Find car $ i^* \in \{1, \dots, k\} $ minimizing:
$$
\text{wait}_i = \max(0, t_j - f_i) + |p_i - a_j|
$$
with tie-breaker: smallest $ i $ if equal.
- Assign car $ i^* $ to request $ j $.
- Compute:
- **Wait time**: $ \text{wait}_{i^*} $
- **New free time**: $ f_{i^*} \leftarrow t_j + \text{wait}_{i^*} + |a_j - b_j| $
- **New position**: $ p_{i^*} \leftarrow b_j $
- Output: $ (i^*, \text{wait}_{i^*}) $
API Response (JSON)
{
"problem": {
"name": "L. Berland.Taxi",
"description": {
"content": "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_ (right",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF883L"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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_ (right...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Berland.Taxi 是一家新成立的出租车公司，刚刚在 Berland 首都投入运营，拥有 #cf_span[k] 辆出租车。首都的街道上共有 #cf_span[n] 栋房屋，沿直线排列，编号从 #cf_span[1]（最左端）到 #cf_span[n]（最右端），任意相邻两栋房屋之间的距离相同。\n\n你需要帮助该公司按照以下规则调度全天的出租车订单：\n\n当在时间 #cf_span[ti] 收到...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k, m \\in \\mathbb{Z}^+ $: number of houses, cars, and ride requests. \nLet $ X = (x_1, x_2, \\dots, x_k) \\in \\{1, \\dots, n\\}^k $: initial positions of cars. \nLet $ R = \\{(t_j...",
"is_translate": false,
"language": "Formal"
}
]
}