Berland.Taxi 是一家新的出租车公司,拥有 k 辆车,最近刚刚在 Berland 首都开始运营。首都在一条直线上有n栋房屋,编号从1(最左边)到n(最右边),并且任意两相邻房屋之间的距离相同。
您必须根据以下规则帮助公司安排全天的所有出租车行程:
- 所有车辆都可以接载乘客。最初,第 j 辆车在时间 0 位于编号为 xj 的房子旁边。
- 所有汽车的速度相同。任何一辆车在相邻房屋 i 和 i + 1 之间行驶都需要 1 分钟。
- 第 i 个出租车乘车请求在时间 ti 发出,要求在 ai 房子接乘客并在 bi 房子下车。所有乘坐出租车的请求均按 ti 的升序给出。所有的 ti 都是不同的。
当在时间 ti 收到出租车乘车请求时,Berland.Taxi 运营商将按如下方式为其分配车辆:
- 在当前可用的汽车中,操作员分配距离接载点 ai 最近的汽车。不用说,如果汽车已经载有乘客,则在该乘客在相应目的地下车之前,该汽车将无法用于任何乘车。
- 如果有几辆这样的汽车,操作员将选择其中一辆自可用以来等待时间最长的汽车。
- 如果有几辆这样的车,操作员将选择其中编号最小的一辆。
将汽车分配给出租车乘车请求后:
- 驾驶员立即开始从当前位置行驶到房屋ai。
- 一旦汽车到达 ai 房屋,乘客就会立即被接走,司机开始开车前往 bi 房屋。
- 一旦到达 bi 房屋,乘客就会下车,并且汽车可用于住在 bi 房屋旁边的新行程。
- 在等待乘车请求或只是路过时,允许多辆汽车在同一时间点位于同一栋房屋旁边。
如果当出租车请求到来时,在时间 ti 没有可用的汽车,则:
- 第 i 位乘客必须等待车辆可用。
- 当汽车可用时,运营商将立即将其分配给此出租车乘车请求。
- 如果乘客等待时同时有多辆汽车可用,运营商将根据上述规则从中挑选一辆汽车。
运营商一一处理出租车乘车请求。因此,如果多名乘客正在等待车辆可用,则操作员将不会继续处理第 (i + 1) 个乘车请求,直到车辆被分配给第 i 个乘车请求。
您的任务是编写一个程序来处理给定的 m 个出租车乘车请求列表。对于每个请求,您都必须找出将分配给哪辆车,以及乘客需要等待汽车到达的时间。注意,如果 ai 房子已经有车,那么相应的等待时间将为 0。
输入
输入的第一行包含整数 n、k 和 m (2 ≤ n ≤ 2·105, 1 ≤ k, m ≤ 2·105) — 房屋数量、汽车数量和出租车乘车请求数量。第二行包含整数 x1, x2, ..., xk (1 ≤ xi ≤ n) — 汽车的初始位置。 xi 是第 i 辆车最初所在的门牌号。同一栋房子旁边可以停放多于一辆车。
以下 m 行包含有关乘车请求的信息。每个乘车请求由整数 tj、aj 和 bj 表示(1 ≤ tj ≤ 1012, 1 ≤ aj, bj ≤ n, aj ≠ bj),其中 tj 是发出请求的时间(以分钟为单位),aj 是需要接送乘客的房屋,bj 是需要乘客下车的房屋。所有出租车乘车请求均按 tj 的升序给出。所有 tj 都是不同的。
输出
打印m行:第j行应包含两个整数,即第j个乘车请求的答案——运营商分配的车厢号和乘客等待时间。
示例
输入 #1
10 1 2 3 5 2 8 9 10 3
输出 #1
1 1 1 5
输入 #2
5 2 1 1 5 10 3 5
输出 #2
1 2
输入 #3
5 2 2 1 5 10 3 5 20 4 1
输出 #3
1 2 2 1
注意
在第一个示例测试中,在时间 5 收到请求,汽车需要从房屋 3 到达房屋 2 来接载乘客。因此,等待时间为 1,行程将在时间 5 + 1 + 6 = 12 完成。第二个请求在时间 9 到达,因此乘客必须等待汽车在时间 12 可用,然后汽车还需要 2 分钟才能从 8 号房屋到达 10 号房屋。因此总等待时间为 3 + 2 = 5。
在第二个样本测试中,1号车和2号车与第一位乘客的距离相同,并且具有相同的“自可用以来的等待时间”。根据规则,1 号车因编号最小而赢得决胜局。它将在时间 3 到达房屋 3,因此等待时间为 2。