题目描述

题目来自 USACO 2018 February Contest, Platinum Problem 1. Slingshot

Farmer John 最讨厌的农活是运输牛粪。为了精简这个过程，他产生了一个新奇的想法：与其使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点，为什么不用一个巨大的便便弹弓把牛粪直接发射过去呢？（事实上，好像哪里不太对……）

Farmer John 的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。FJ 建造了 $N$ 个弹弓（$1\le N\le 10^5$），其中第 $i$ 个弹弓可以用三个整数 $x_i$，$y_i$ 以及 $t_i$ 描述，表示这个弹弓可以在 $t_i$ 单位时间内将牛粪从位置 $x_i$ 发射到位置 $y_i$。

FJ 有 $M$ 堆牛粪需要运输（$1\le M\le 10^5$）。第 $j$ 堆牛粪需要从位置 $a_j$ 移动到位置 $b_j$。使用拖拉机运输牛粪，经过路程 $d$ 需要消耗 $d$ 单位时间。FJ 希望通过对每一堆牛粪使用至多一次弹弓来减少运输时间。FJ 驾驶没有装载牛粪的拖拉机的时间不计。

对这 $M$ 堆牛粪的每一堆，在 FJ 可以在运输过程中使用至多一次弹弓的条件下，帮助 FJ 求出其最小运输时间。

输入格式

输入的第一行包含 $N$ 和 $M$。

下面 $N$ 行，每行用 $x_i,y_i,t_i\ (0\le x_i,y_i,t_i\le 10^9)$ 描述了一个弹弓。

最后 $M$ 行用 $a_j$ 和 $b_j$ 描述了需要移动的牛粪。

输出格式

输出 $M$ 行，每堆牛粪一行，表示运输这堆牛粪需要的最短时间。

2 3
0 10 1
13 8 2
1 12
5 2
20 7

4
3
10