题目描述

平面上有$n$个点$(X_i,Y_i)$。 现在有$q$个询问，每次给定三个点$A(x + d, y), B(x, y), C(x, y + d)$，回答有多少个点$(X_i,Y_i)$在这个三角形的边界或者内部。

输入格式

第一行，两个整数$n, q$。 接下来$n$行，每行两个整数$X_i,Y_i$，表示点的坐标。 接下来$q$行，每行三个整数$x,y,d$，表示一个询问。

输出格式

输出$q$行，每行一个整数，表示答案。

5 3
1 3
1 5
3 6
4 4
2 6
1 5 3
1 5 4
1 1 1

3
3
0

样例输入输出 2

见下发文件。

数据规模

共 10 组数据。 测试点 1,2 满足 $1 ≤ n, q ≤ 10^3$。

测试点 3,4 满足 $1 ≤ n, q ≤ 5 × 10^4$。

测试点 5,6,7 满足 $1 ≤ n, q ≤ 2 × 10^5$。

对于 100% 的数据，满足 $1 ≤ n, q ≤ 10^6, 1 ≤ X_i,Y_i,x,y,d ≤ 10^6$。

附件

附件下载