Slingshot#10414
One of the farm chores Farmer John dislikes most is hauling large amounts of cow manure. To streamline this process, he comes up with an intriguing idea: instead of hauling manure from one point to another 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 the farm can be described simply by its position along this road (effectively, a point on the number line). FJ builds n~(1 \le n \le 10^5) slingshots. The -th slingshot is described by three integers x_i, y_i and t_i, meaning that it can shoot manure from position x_i to position y_i in just t_i units of time.
FJ has m~(1 \le m \le 10^5) piles of manure to transport. The -th pile must be moved from position a_j to position b_j. Hauling manure with the tractor over a distance takes units of time. FJ hopes to reduce this time by using at most one slingshot to transport each pile. The time FJ spends driving the tractor without manure is not counted.
For each of the piles of manure, help FJ determine the minimum possible transportation time, given that at most one slingshot can be used for each pile.
The first line contains two integers and . Each of the next lines describes one slingshot with three integers x_i, y_i and t_i~(0 \le x_i, y_i, t_i \le 10^9). Each of the last lines describes one pile of manure to be moved with two integers a_j and b_j~(0 \le a_j, b_j \le 10^9).
Print lines, one for each pile of manure, containing the minimum time needed to transport it.
Example 1
The first pile of manure must be moved from position to position . Without a slingshot, this takes units of time. However, with the first slingshot, it takes unit of time to move the manure to position (the slingshot's source), unit of time to fling it through the air to position (the slingshot's destination), and more units of time to move it to position , for a total of units of time. The second pile is best moved without any slingshot, and the third pile should be moved using the second slingshot.