农夫约翰最讨厌的农活之一就是搬运大量的牛粪。为了简化这个过程，他想出了一个有趣的主意：与其用拖拉机后面的车斗在两点之间搬运，为什么不用一个巨大的弹弓把牛粪射向空中呢？（确实，这能出什么差错呢……）

农夫约翰的农场沿着一条笔直的长路建造，因此农场上的任何位置都可以简单地用它在这条路上的坐标（实际上就是数轴上的一个点）来描述。约翰建造了 $N$ 个弹弓（$1 \leq N \leq 10^5$），其中第 $i$ 个弹弓由三个整数 $x_i$、$y_i$ 和 $t_i$ 描述，表示该弹弓可以将牛粪从位置 $x_i$ 射向位置 $y_i$，且仅需 $t_i$ 单位时间。

约翰有 $M$ 堆牛粪需要运输（$1 \leq M \leq 10^5$）。第 $j$ 堆牛粪需要从位置 $a_j$ 移动到位置 $b_j$。用拖拉机搬运距离为 $d$ 的牛粪需要 $d$ 单位时间。约翰希望通过允许每堆牛粪最多使用一次弹弓来减少运输时间。约翰在没有牛粪的情况下驾驶拖拉机所花费的时间不计入总时间。

对于每一堆牛粪，请帮助约翰确定在整个过程中最多使用一次弹弓的情况下，运输所需的最短时间。

输入格式

第一行包含 $N$ 和 $M$。接下来的 $N$ 行，每行描述一个弹弓，包含三个整数 $x_i$、$y_i$ 和 $t_i$（$0 \leq x_i, y_i, t_i \leq 10^9$）。最后 $M$ 行描述需要移动的牛粪堆，包含两个整数 $a_j$ 和 $b_j$。

输出格式

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

样例

样例输入 1

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

样例输出 1

4
3
10

说明

这里，第一堆牛粪需要从位置 1 移动到位置 12。如果不使用弹弓，需要 11 单位时间。然而，使用第一个弹弓，花费 1 单位时间移动到位置 0（弹弓起点），花费 1 单位时间将牛粪射向空中到达位置 10（弹弓终点），然后花费 2 单位时间将牛粪移动到位置 12。第二堆牛粪最好不使用任何弹弓移动，第三堆牛粪应该使用第二个弹弓移动。

题目来源：Brian Dean