Migrated from Lutece 2926 买买买

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

保证数据随机
本题解法:K-D Tree
Maets 商城有 $n$ 款游戏即将打折。每款游戏的属性为两个正整数 $s, p$ ,分别代表评分和价格。

有 $m$ 个玩家浏览了所有即将打折的游戏。

他们希望购买的游戏评分尽量高，同时价格不至于太贵，但每个玩家各自有不同的权重和心理预期。具体来说，每个玩家的属性可以用三个正整数 $x,y,z$ 表示,如果一款游戏满足$xs-yp\ge z$,那么这款游戏就会被玩家加入愿望单。

给出 $n$ 款游戏和 $m$ 个玩家的属性，求出每个玩家把多少游戏加入了愿望单。

Input

第一行两个正整数 $n$ 和 $m$ ，分别表示游戏数量和玩家数量。

接下来 $n$ 行，第 $i$ 行两个正整数 $s_i, p_i$ , 分别表示第 $i$ 款游戏的评分和价格。

接下来 $m$ 行，第 $i$ 行三个正整数 $x_i, y_i, z_i$，表示第 $i$ 个玩家的属性。

Output

输出 $m$ 行，其中第 $i$ 行表示第 $i$ 个玩家加入愿望单的游戏数量。

Samples

2 4
90 100
60 40
100 1 7000
100 60 3500
20 10 800
1 114514 1919810

1
1
2
0

Constraints

$1 \le n,m \le 2 \times 10^5, 1 \le s,p,x,y,z \le 10^9$

Resources

2023 UESTC ICPC Training for Data Structures