题目描述

One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with an intriguing idea: instead of hauling manure between two points in a cart behind his tractor, why not shoot it through the air with a giant manure slingshot? (indeed, what could possibly go wrong...) Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). FJ builds $N$ slingshots ($1 \leq N \leq 10^5$), where the $i$th slingshot is described by three integers $x_i$, $y_i$, and $t_i$, specifying that this slingshot can shoot manure from position $x_i$ to position $y_i$ in only $t_i$ total units of time.

FJ has $M$ piles of manure to transport ($1 \leq M \leq 10^5$). The $j$th such pile needs to be moved from position $a_j$ to position $b_j$. Hauling manure with the tractor for a distance of $d$ takes $d$ units of time. FJ is hoping to reduce this by allowing up to one use of any slingshot for transporting each pile of manure. Time FJ spends moving his tractor without manure in it does not count.

For each of the $M$ manure piles, please help FJ determine the minimum possible transportation time, given that FJ can use up to one slingshot during the process.

输入格式

The first line of input contains $N$ and $M$. The next $N$ lines each describe a single slingshot in terms of integers $x_i$, $y_i$, and $t_i$ ($0 \leq x_i, y_i, t_i \leq 10^9$). The final $M$ lines describe piles of manure that need to be moved, in terms of integers $a_j$ and $b_j$.

输出格式

Print $M$ lines of output, one for each manure pile, indicating the minimum time needed to transport it.

题目大意

Farmer John最讨厌的农活是运输牛粪。为了精简这个过程，他产生了一个新奇的想法：与其使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点，为什么不用一个巨大的便便弹弓把牛粪直接发射过去呢？（事实上，好像哪里不太对……） Farmer John的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。FJ建造了$N$个弹弓（$1 \leq N \leq 10^5$），其中第$i$个弹弓可以用三个整数$x_i$，$y_i$以及$t_i$描述，表示这个弹弓可以在$t_i$单位时间内将牛粪从位置$x_i$发射到位置$y_i$。

FJ有$M$堆牛粪需要运输（$1 \leq M \leq 10^5$）。第$j$堆牛粪需要从位置$a_j$移动到位置$b_j$。使用拖拉机运输牛粪，经过路程$d$需要消耗$d$单位时间。FJ希望通过对每一堆牛粪使用至多一次弹弓来减少运输时间。FJ驾驶没有装载牛粪的拖拉机的时间不计。

对这$M$堆牛粪的每一堆，在FJ可以在运输过程中使用至多一次弹弓的条件下，帮助FJ求出其最小运输时间。

输入格式（文件名：slingshot.in）： 输入的第一行包含$N$和$M$。下面$N$行，每行用$x_i$，$y_i$，$t_i$（$0 \leq x_i, y_i, t_i \leq 10^9$）描述了一个弹弓。最后$M$行用$a_j$和$b_j$描述了需要移动的牛粪。

输出格式（文件名：slingshot.out）： 输出$M$行，每堆牛粪一行，表示运输这堆牛粪需要的最短时间。

2 3
0 10 1
13 8 2
1 12
5 2
20 7

4
3
10

提示

Here, the first pile of manure needs to move from position 1 to position 12. Without using an slingshot, this would take 11 units of time. However, using the first slingshot, it takes 1 unit of time to move to position 0 (the slingshot source), 1 unit of time to fling the manure through the air to land at position 10 (the slingshot destination), and then 2 units of time to move the manure to position 12. The second pile of manure is best moved without any slingshot, and the third pile of manure should be moved using the second slingshot.

Problem credits: Brian Dean