It turns out that Railgun loves geometry problems. His mentor in this matter, fractal, gave him a set of $$$N$$$ points on the plane, some of which can be made anime-like. The peculiarity of an anime-like point (for example $$$H$$$) is that, having an arbitrary point $$$P$$$, you can turn it into a point $$$P'$$$ in one operation by rotating it around $$$H$$$ by any angle. In other words, if we describe a circle $$$\omega$$$ around point $$$H$$$ with a radius of $$$dist(H, P)$$$, then $$$P' \in \omega$$$ must hold.
fractal also gave him $$$Q$$$ independent requests: having an arbitrary point $$$A(x, y)$$$, say whether it is possible to move from it to point $$$B(-x, -y)$$$ by rotating it around anime-like points. Initially, Railgun has no anime-like points. And since it takes a long time to make them, he asked you to tell him the minimum number of anime-like points that he will need (if, of course, fractal's request is feasible). And also tell him how many ways there are to choose them. Since this number can be large, he asked you to output it modulo $$$10^9 + 7$$$.
You don't need to minimize the number of operations.
The first line of the input contains two integers $$$N$$$, $$$Q$$$ $$$(1 \le N, Q \le 10^5)$$$.
The next $$$N$$$ lines describe the points of the set and contain two integers $$$x$$$, $$$y$$$ $$$(-10^9 \le x, y \le 10^9)$$$. It is guaranteed that all points of the set are distinct.
The next $$$Q$$$ lines describe the queries and contain two integers $$$Ax$$$, $$$Ay$$$ $$$(-10^9 \le Ax, Ay \le 10^9)$$$.
For each query on a separate line, output $$$-1$$$ $$$-1$$$ if the fractal query is impossible. Otherwise, output two integers — the minimum number of points that need to be made anime-style and the number of ways to choose them modulo $$$10^9 + 7$$$.
Anime-style points are not preserved between queries.
5 31 12 23 -34 40 5-1 13 0-1 -1
1 3 1 1 1 1
| Almaty Code Cup 2024 |
|---|
| Finished |
