Фермер Джон не любит возить навоз. Он придумал перемещать лотки с навозом пор воздуху с помощью гигантской рогатки.

Ферма Джона построена вдоль прямой дороги, поэтому любое место фермы может быть описано позицией на этой дороге (точка на числовой прямой). ФД построил n рогаток, i-ая из которых описывается тремя целыми числами xi, yi, ti, указывающими, что рогатка может переместить навоз из позиции xi в позицию yi за ti единиц времени.

У ФД есть m лотков с навозом для транспортировки. j-ый лоток нужно переместить из позиции aj в позицию bj. Перемещение лотка с навозом на тракторе на расстояние d занимает d единиц времени. ФД надеется сократить время использованием рогаток. Время перемещения трактора без навоза не учитывается.

Для каждого из m лотков определите минимально возможное время транспортировки. при условии использования не более одной рогатки.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 105). Каждая из следующих n строк описывает одну рогатку тремя числами xi, yi, ti (0 ≤ xi, yi, ti ≤ 109). Последние m строк описывают лотки навоза, которые необходимо перемещать, двумя целыми числами aj и bj.

Выходные данные

Выведите m строк, по одной для каждого лотка с навозом, содержащих минимальное время для транспортировки соответствующего лотка с навозом.

Пример

Здесь первый лоток необходимо переместить из позиции 1 в позицию 12. Без использования рогаток это займёт 11 единиц времени. Однако, если использовать первую рогатку, это займёт 1 единицу времени, чтобы переместить лоток из позиции 1 в позицию 0 (исходная точка первой рогатки), 1 единицу времени перебросить по воздуху в позицию 10 (финишная точка первой рогатки) и затем 2 единицы времени переместить на тракторе в позицию 12. Второй лоток навоза выгоднее перемещать без рогатки. Третий лоток навоза выгоднее всего перемещать с помощью второй рогатки.