#P9159. Taxi

    ID: 5241 传统题 2000ms 512MiB 尝试: 17 已通过: 10 难度: 6 上传者: 标签>CF2000提高坐标变换前后缀最值单调判定二分查找2022杭电多校

Taxi

Description

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

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

Format

Input

第一行包含一个整数 TT(1≤T≤1001 \leq T \leq 100),表示测试数据的组数。对于每组测试数据:

第一行包含两个整数 nn 和 qq(1≤n,q≤100 0001 \leq n, q \leq 100\,000),分别表示城镇的数量和询问的数量。

接下来 nn 行,每行包含三个整数 xi,yix_i, y_i 和 wiw_i(1≤xi,yi,wi≤1091 \leq x_i, y_i, w_i \leq 10^9),描述一座城镇。

接下来 qq 行,每行包含两个整数 x′x' 和 y′y'(1≤x′,y′≤1091 \leq x', y' \leq 10^9),描述一次询问。

保证所有测试数据的 nn 之和不超过 500 000500\,000,qq 之和不超过 500 000500\,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