Byteland 有 $n$ 个城镇，编号为 $1, 2, \dots, n$。第 $i$ 个城镇的位置为 $(x_i, y_i)$。小 Q 获得了一张出租车 VIP 卡，他可以使用这张卡来减少出租车费用。形式化地，假设小 Q 位于 $(x', y')$，如果他叫了一辆出租车前往第 $k$ 个城镇，VIP 卡将减少 $\min(|x' - x_k| + |y' - y_k|, w_k)$ 美元的费用。

小 Q 想要充分利用他的 VIP 卡。他会向你提出 $q$ 次询问，每次询问给出他的位置，你需要选择一个城镇，使得 VIP 卡减少的费用最多。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100\,000$)，分别表示城镇的数量和询问的数量。

接下来的 $n$ 行，每行包含三个整数 $x_i, y_i$ 和 $w_i$ ($1 \le x_i, y_i, w_i \le 10^9$)，描述一个城镇。

接下来的 $q$ 行，每行包含两个整数 $x'$ 和 $y'$ ($1 \le x', y' \le 10^9$)，描述一个询问。

保证所有测试用例中 $n$ 的总和不超过 $500\,000$，且所有 $q$ 的总和不超过 $500\,000$。

输出格式

对于每次询问，输出一行一个整数，表示可能减少的最大出租车费用。

样例

输入 1

1
3 4
1 5 7
5 1 6
2 3 9
1 5
2 2
4 3
10 10

输出 1

6
4
5
9