Рогатка
Фермер Джон не любить возити гній. Він придумав переміщати лотки з гноєм повітрям за допомогою гігантської рогатки.
Ферма Джона розташована вздовж прямої дороги, тому будь-яке місце на фермі можна описати позицією на цій дорозі (точка на числовій прямій). Фермер Джон побудував n рогаток, кожна з яких описується трьома цілими числами 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. Другий лоток гною вигідніше переміщати без рогатки. Третій лоток гною найкраще переміщати за допомогою другої рогатки.