Taxi

There are $n$ towns in Byteland, labeled by $1,2,\dots,n$. The $i$-th town's location is $(x_i,y_i)$. Little Q got a taxi VIP card, he can use the VIP card to cut down the taxi fare. Formally, assume Little Q is at $(x',y')$, if he calls a taxi to drive him to the $k$-th town, the VIP card will reduce $\min(|x'-x_k|+|y'-y_k|,w_k)$ dollars.

Little Q wants to make full use of his VIP card. He will give you $q$ queries, in each query you will be given his location, and you need to choose a town such that the VIP card will reduce the most taxi fare.

The first line contains a single integer $T$ ($1 \leq T \leq 100$), the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1 \leq n,q \leq 100\,000$), denoting the number of towns and the number of queries.

Each of the following $n$ lines contains three integers $x_i$, $y_i$ and $w_i$ ($1 \leq x_i,y_i,w_i \leq 10^9$), describing a town.

Each of the following $q$ lines contains two integers $x'$ and $y'$ ($1 \leq x',y' \leq 10^9$), describing a query.

It is guaranteed that the sum of all $n$ is at most $500\,000$, and the sum of all $q$ is at most $500\,000$.

For each query, print a single line containing an integer, denoting the maximum possible reduced taxi fare.

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

6
4
5
9

2022“杭电杯”中国大学生算法设计超级联赛（3）