Фермер Джон не любит возить навоз. Он придумал перемещать лотки с навозом
пор воздуху с помощью гигантской рогатки.
Ферма Джона построена вдоль прямой дороги, поэтому любое место фермы может
быть описано позицией на этой дороге (точка на числовой прямой). ФД построил
\(N\) рогаток (\(1 \leq N \leq 10^5\)), \(i\)-ая из которых описывается тремя целыми
числами \(x_i\), \(y_i\), \(t_i\), указывающими, что рогатка может переместить навоз
из позиции \(x_i\) в позицию \(y_i\) за \(t_i\) единиц времени.
У ФД есть \(M\) лотков с навозом для транспортировки (\(1 \leq M \leq 10^5\)).
\(j\)-ый лоток нужно переместить из позиции \(a_j\) в позицию \(b_j\). Перемещение
лотка с навозом на тракторе на расстояние \(d\) занимает \(d\) единиц времени.
ФД надеется сократить время использованием рогаток. Время перемещения трактора
без навоза не учитывается.
Для каждого из \(M\) лотков определите минимально возможное время транспортировки.
при условии использования не более одной рогатки.
ФОРМАТ ВВОДА (файл 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\) строк, по одной для каждого лотка с навозом, содержащих
минимальное время для транспортировки соответствующего лотка с навозом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
0 10 1
13 8 2
1 12
5 2
20 7
|
4
3
10
|