Рогатка
Фермер Джон не любит возить навоз. Он придумал перемещать лотки с навозом пор воздуху с помощью гигантской рогатки.
Ферма Джона построена вдоль прямой дороги, поэтому любое место фермы может быть описано позицией на этой дороге (точка на числовой прямой). ФД построил n рогаток, i-ая из которых описывается тремя целыми числами x[i], y[i], t[i], указывающими, что рогатка может переместить навоз из позиции x[i] в позицию y[i] за t[i] единиц времени.
У ФД есть m лотков с навозом для транспортировки. j-ый лоток нужно переместить из позиции a[j] в позицию b[j]. Перемещение лотка с навозом на тракторе на расстояние d занимает d единиц времени. ФД надеется сократить время использованием рогаток. Время перемещения трактора без навоза не учитывается.
Для каждого из m лотков определите минимально возможное время транспортировки. при условии использования не более одной рогатки.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 10^5) и m (1 ≤ m ≤ 10^5). Каждая из следующих n строк описывает одну рогатку тремя числами x[i], y[i], t[i] (0 ≤ x[i], y[i], t[i] ≤ 10^9). Последние m строк описывают лотки навоза, которые необходимо перемещать, двумя целыми числами a[j] и b[j].
Выходные данные
Выведите m строк, по одной для каждого лотка с навозом, содержащих минимальное время для транспортировки соответствующего лотка с навозом.
Пример
Здесь первый лоток необходимо переместить из позиции 1 в позицию 12. Без использования рогаток это займёт 11 единиц времени. Однако, если использовать первую рогатку, это займёт 1 единицу времени, чтобы переместить лоток из позиции 1 в позицию 0 (исходная точка первой рогатки), 1 единицу времени перебросить по воздуху в позицию 10 (финишная точка первой рогатки) и затем 2 единицы времени переместить на тракторе в позицию 12. Второй лоток навоза выгоднее перемещать без рогатки. Третий лоток навоза выгоднее всего перемещать с помощью второй рогатки.