[HNOI2005]汤姆的游戏

汤姆是个好动的孩子。一天，他突然对圆规和直尺产生了兴趣，于是开始在一张很大的白纸上画许多矩形和圆。画着画着，他不小心将爆米花撒在了纸上。这些爆米花看起来就像平面上的一个个点，其中一些点位于矩形或圆的内部，另一些点则位于外部。

汤姆想知道每个点位于多少个图形的内部，但点和图形的数量实在太多，因此他向你求助。

给定平面上的 $N$ 个图形和 $M$ 个点，请求出每个点位于多少个图形的内部。每个图形可能是矩形或圆，并且所有矩形的边均与坐标轴平行。若一个点恰好位于图形的边界上，则认为该点不在这个图形的内部。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示图形数量和点的数量。

接下来 $N$ 行描述各个图形，其中第 $i+1$ 行描述第 $i$ 个图形：

• 若该行以字符 r 开头，则该图形为矩形。其后包含 $4$ 个实数 $x_1,y_1,x_2,y_2$，表示矩形的一对对角顶点坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$；
• 若该行以字符 c 开头，则该图形为圆。其后包含 $3$ 个实数 $x,y,r$，表示圆心坐标为 $(x,y)$，半径为 $r$。

最后 $M$ 行描述各个点，每行包含两个实数 $x,y$，表示该点的坐标为 $(x,y)$。

输出格式

输出 $M$ 行，每行包含一个整数。

其中第 $i$ 行表示第 $i$ 个点位于多少个图形的内部。若该点位于某个图形的边界上，则不计入该图形。

样例输入

3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000

样例输出

1
2
0
1

数据范围

• $1\le N\le 2.5\times 10^5$；
• $1\le M\le 10^4$；
• 所有坐标及圆的半径均以十进制形式给出，小数部分至多有 $3$ 位；
• 所有坐标的绝对值均不超过 $5\times 10^5$；
• 所有圆的半径满足 $0<r\le 10^4$；
• 将所有坐标和半径乘以 $10^3$ 后，相关坐标差的平方和不会超过有符号 $64$ 位整数的表示范围；
• 每个点所在图形的数量不超过 $N$。

来源与许可

本题为 HNOI 2005 试题「汤姆的游戏」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000

输出

1
2
0
1