Description

Tom is an energetic child, and today he becomes interested in a compass and a straightedge. He starts drawing many rectangles and circles on a very large sheet of white paper. While drawing, he accidentally spills his popcorn, and now there are many popcorn pieces on the paper. Tom notices that the popcorn looks like points on the plane: some points fall inside rectangles or circles, while others fall outside. He begins counting how many rectangles or circles each point lies inside. Since Tom is still a child and there are many points, rectangles, and circles, he cannot finish counting and asks you for help.

Your task is: given $N$ shapes (rectangles or circles) and $M$ points on the plane, determine for each point how many rectangles or circles contain it. Assume that each rectangle has sides parallel to the coordinate axes.

Input Format

The first line contains two positive integers $N$ and $M$, where $N$ is the number of shapes (rectangles or circles) and $M$ is the number of points.

The next $N$ lines describe the shapes. Specifically, the $(i+1)$-th line describes the $i$-th shape. It starts with a letter: if the letter is r, the shape is a rectangle, followed by $4$ real numbers $x1,y1,x2,y2$, which are the coordinates of a pair of opposite vertices $(x1,y1)$ and $(x2,y2)$; if the letter is c, the shape is a circle, followed by $3$ real numbers $x,y,r$, meaning the circle is centered at $(x,y)$ with radius $r$.

The last $M$ lines describe the points. Each of these lines contains two real numbers $x,y$, representing a point at coordinates $(x,y)$.

Output Format

Output $M$ lines. The integer on the $i$-th line is the number of shapes that contain the $i$-th point. If a point lies on the boundary of a shape, it is considered not inside that shape.

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

Hint

For $100\%$ of the testdata, $N, M \le 500$.

Translated by ChatGPT 5