Manure Slingshot Optimization

Farmer John wants to transport manure along his straight farm road. He built N slingshots, where the i-th one can shoot manure from position \(x_i\) to \(y_i\) in \(t_i\) time units. He also has M manure piles, each needing to be moved from \(a_j\) to \(b_j\). Hauling manure with the tractor costs one time unit per unit distance. For each pile, Farmer John can use at most one slingshot, so the total time becomes the sum of the tractor travel to the slingshot start, the slingshot time, and then the tractor travel from the slingshot end to the destination.

The goal is to determine the minimum transportation time for each manure pile. If no slingshot is used, the time is \(|a_j - b_j|\). Otherwise, for a chosen slingshot \((x_i, y_i, t_i)\), the time is \(|a_j - x_i| + t_i + |b_j - y_i|\). Your task is to compute the minimum possible time for each manure pile.

Constraints:

• \(1 \le N \le 10^5\)
• \(1 \le M \le 10^5\)
• All positions and \(t_i\) are integers.

inputFormat

The first line contains two integers \(N\) and \(M\). The next \(N\) lines each contain three integers \(x_i\), \(y_i\), and \(t_i\) describing a slingshot. The following \(M\) lines each contain two integers \(a_j\) and \(b_j\) describing a manure pile that needs to be moved.

outputFormat

Output \(M\) lines. The \(j\)-th line should contain a single integer representing the minimum time required to transport the \(j\)-th manure pile.

sample

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

8
3
10