Catapulta#10414
Uno de los trabajos de la granja que menos le gusta al Granjero John es transportar grandes cantidades de estiércol de vaca. Para simplificar este proceso, se le ha ocurrido una idea interesante: en lugar de transportar el estiércol de un punto a otro en un remolque tirado por un tractor, ¿por qué no lanzarlo por el aire usando una gigantesca catapulta de estiércol? (De hecho, ¿qué podría salir mal...?)
La granja del Granjero John está ubicada a lo largo de un único camino largo y recto, por lo que cualquier lugar de la granja puede describirse simplemente por su posición en ese camino (esencialmente, un punto en la recta numérica). El Granjero John ha construido n~(1 \le n \le 10^5) catapultas. La -ésima catapulta se describe mediante tres números enteros x_i, y_i y t_i, lo que significa que puede lanzar estiércol desde la posición x_i hasta la posición y_i en tan solo t_i unidades de tiempo.
El Granjero John tiene m~(1 \le m \le 10^5) montones de estiércol que necesita transportar. El -ésimo montón debe moverse desde la posición a_j hasta la posición b_j. Transportar estiércol en el tractor a una distancia toma unidades de tiempo. El Granjero John espera reducir este tiempo utilizando, como máximo, una catapulta para transportar cada montón. El tiempo que el Granjero John pasa conduciendo el tractor sin estiércol no se tiene en cuenta.
Para cada uno de los montones de estiércol, ayuda al Granjero John a determinar el tiempo mínimo posible de transporte, teniendo en cuenta que se puede usar como máximo una catapulta por montón.
La primera línea contiene dos números enteros y . Cada una de las siguientes líneas describe una catapulta mediante tres números enteros x_i, y_i y t_i~(0 \le x_i, y_i, t_i \le 10^9). Cada una de las últimas líneas describe un montón de estiércol que debe moverse, mediante dos números enteros a_j y b_j~(0 \le a_j, b_j \le 10^9).
Imprime líneas, una por cada montón de estiércol, con el tiempo mínimo necesario para transportarlo.
Ejemplo 1
El primer montón de estiércol debe moverse desde la posición hasta la posición . Sin usar ninguna catapulta, esto toma unidades de tiempo. Sin embargo, usando la primera catapulta, se necesita unidad de tiempo para transportar el estiércol hasta la posición (el punto de inicio de la catapulta), unidad de tiempo para lanzarlo por el aire hasta la posición (el punto final de la catapulta) y unidades de tiempo más para transportarlo hasta la posición , lo que da un total de unidades de tiempo. El segundo montón se transporta de manera más eficiente sin usar ninguna catapulta, y el tercero debe transportarse usando la segunda catapulta.