CF883L Berland.Taxi

Berland.Taxi 是一家新成立的出租车公司，目前有 $k$ 辆车，刚刚在 Berland 首都开始运营。首都有 $n$ 栋房屋，沿一条直线从左到右编号为 $1$ 到 $n$，任意相邻两栋房屋之间距离相等。 你需要帮助公司按照以下规则为全天收到的所有叫车订单安排车辆： - 所有车辆均可用于接送乘客。最初，第 $j$ 辆车位于编号为 $x_j$ 的房屋旁，时间为 $0$。 - 所有车辆速度相同，从相邻的第 $i$ 号房屋到第 $i+1$ 号房屋恰好需要 $1$ 分钟。 - 第 $i$ 条叫车请求在时间 $t_i$ 提出，请求派车到 $a_i$ 号房屋接乘客，并送到 $b_i$ 号房屋。所有叫车请求按 $t_i$ 升序给出，且所有 $t_i$ 互不相同。 收到第 $i$ 条叫车请求时，Berland.Taxi 的调度员依照以下规则分配车辆： - 从当前可用车辆中，分配距离接客点 $a_i$ 最近的车辆。如果有多辆车距离相同，则分配自可用以来等待时长最长的那一辆。如果仍有多辆车，则分配编号最小的车辆。 - 如果有车被分配到该乘车请求： - 司机立即从当前位置前往 $a_i$ 号房屋。 - 到达 $a_i$ 后立即接上乘客，并开往 $b_i$ 号房屋。 - 到达 $b_i$ 后乘客下车，该车辆在 $b_i$ 号房屋等待，可以接收新订单。 - 允许多辆车在同一时间停在同一房屋，无论是在等待叫单还是经过时。 - 如果在时间 $t_i$ 没有可用车辆： - 第 $i$ 位乘客只能等待有车辆完成任务变为可用为止。 - 一旦有车变为可用，立即分配给本次叫车请求。如果同时有多辆车变为可用，依然按上述分配规则决定。 - 调度员逐一处理叫车请求。如果有多名乘客因无可用车辆而等待，在第一名乘客分配车辆前，不会考虑后续请求。 你的任务是，依次处理给定的 $m$ 条叫车请求。对于每条请求，你需要确定分配给它的车辆编号，以及乘客实际等待该车到达的时间。注意，如果已经有车在 $a_i$ 号房屋等待，本次等候时间应为 $0$。

输入第一行为 $n$、$k$、$m$，分别表示房屋数量、车辆数量和叫车请求数量（$2\leq n\leq 2\cdot 10^{5}$，$1\leq k,m\leq 2\cdot 10^{5}$）。 第二行包含 $k$ 个整数 $x_1,x_2,\dots,x_k$（$1\leq x_i\leq n$），表示每辆车的初始位置（房屋编号）。允许多辆车初始在同一房屋。 接下来 $m$ 行，每行包含 $t_j$、$a_j$、$b_j$（$1\leq t_j\leq 10^{12}$，$1\leq a_j,b_j\leq n$，$a_j\ne b_j$），依次描述每条叫车请求。每行含义分别为请求时间、接客房屋和送达房屋。所有请求按 $t_j$ 升序给出且所有 $t_j$ 均不相同。

输出 $m$ 行，每行包含两个整数，分别为调度员为第 $j$ 次叫车请求分配的车辆编号，以及乘客的实际等待时间。

在第一个样例中，第一个请求在时间 $5$ 到来，车辆需从房屋 $3$ 前往房屋 $2$，用时 $1$，乘客等待 $1$，送达在 $5+1+6=12$。第二个请求在 $9$ 时发生，只有车辆在 $12$ 时可用，然后需 $2$ 分钟从 $8$ 到 $10$，总共等待 $3+2=5$。 在第二个样例中，车辆 $1$ 和 $2$ 距离乘客距离相等，且空闲时间相同。按照编号最小的规则，分配给车辆 $1$。车辆在 $3$ 时抵达房屋 $3$，所以等待时间为 $2$。 由 ChatGPT 5 翻译