Description

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

小 Q 想充分利用他的 VIP 卡。他会给你若干次询问，每次询问给出他所在的位置，你需要选择一座城镇，使得 VIP 卡减免的车费最多。

Format

Input

第一行包含一个整数 $T$（$1 \leq T \leq 100$），表示测试数据的组数。对于每组测试数据：

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

接下来 $n$ 行，每行包含三个整数 $x_i, y_i$ 和 $w_i$（$1 \leq x_i, y_i, w_i \leq 10^9$），描述一座城镇。

接下来 $q$ 行，每行包含两个整数 $x'$ 和 $y'$（$1 \leq x', y' \leq 10^9$），描述一次询问。

保证所有测试数据的 $n$ 之和不超过 $500\,000$，$q$ 之和不超过 $500\,000$。

Output

对于每次询问，输出一行一个整数，表示最多能减免的车费。

Samples

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

6
4
5
9

Source

Super League of Chinese College Students Algorithm Design 2022, Contest 3