Slingshot

Of all the chores on the farm, Farmer John dislikes hauling manure the most. To cut the work down he comes up with an odd plan: instead of moving manure between two points in a cart behind his tractor, he shoots it through the air with a giant manure slingshot. (what could possibly go wrong)

John's farm runs along one long straight road, so every location on the farm is a single coordinate along that road, a point on the number line. John builds $N$ slingshots ($1 \leq N \leq 10^5$). Slingshot $i$ is given by three integers $x_i$, $y_i$, and $t_i$: it shoots manure from position $x_i$ to position $y_i$ in only $t_i$ units of time.

John has $M$ piles of manure to move ($1 \leq M \leq 10^5$). Pile $j$ has to go from position $a_j$ to position $b_j$. Hauling manure a distance of $d$ with the tractor takes $d$ units of time. John hopes to cut that down by allowing up to one slingshot use for each pile. Time the tractor spends moving with no manure in it does not count.

For each of the $M$ piles of manure, find the smallest possible transport time, given that John may use at most one slingshot along the way.

The first line contains $N$ and $M$. Each of the next $N$ lines describes one slingshot with the integers $x_i$, $y_i$, and $t_i$ ($0 \leq x_i, y_i, t_i \leq 10^9$). Each of the final $M$ lines describes one pile of manure that has to be moved, with the integers $a_j$ and $b_j$.

Print $M$ lines, one for each pile of manure, each holding the smallest time needed to move that pile.

In the example, the first pile of manure has to move from position 1 to position 12. Without a slingshot that takes 11 units of time. With the first slingshot it takes 1 unit of time to move the manure to position 0, the launch point, 1 unit of time to fling it through the air to position 10, the landing point, and then 2 units of time to move it to position 12, for a total of 4. The second pile is fastest with no slingshot at all, and the third pile is fastest with the second slingshot.