You are given the location of all post offices on earth, and a set of destinations for various packages that need to be shipped. For each package, you need to find the maximal set of post offices that are suitable as destinations for the package --i.e. the set of post offices must satisfy the following constraints: \begin{itemize} \item The post office that is closest to the final destination must be in the result set. \item All post offices that are at most \textbf{2}\% farther than the closest post office must also be present in the result set. \end{itemize} For the purpose of this problem, the earth is approximated to be a perfectly flat sphere, with the radius \textbf{6381} Km. The distance between two points may be computed using the haversine formula: \textbf{A = sin( (lat1-lat2)/2)^2 + cos(lat1) · cos(lat2) · (sin((long1-long2)/2)^2)}; \textbf{DISTANCE = 6381 · 2 · atan2(sqrt(A), sqrt(1-A))}; (you may use other formulas if you please, but note that the arccosine formula has large rounding errors for small distances, and thus you may get wrong results). \InputFile The input file is a binary file; all numbers written in it are written in little-endian representation. It contains, in this order: \begin{itemize} \item \textbf{4} bytes that represent the number of post offices \textbf{N} -- integer number, no greater than \textbf{3000000} \item For each post office, the input file contains two numbers <\textbf{LAT LONG}> (\textbf{4} bytes each) representing the latitude and longitude (in degrees) of the post office. The numbers are single-precision \textbf{IEEE754} floating point numbers. All latitudes are between -\textbf{90} and \textbf{90} degrees; all longitudes are between \textbf{-180} and \textbf{180} degrees. \item \textbf{4} bytes representing the number of packages \textbf{M} (integer number, no greater than \textbf{500000}) \item For each package, the input file contains two numbers <\textbf{LAT LONG}> (\textbf{4} bytes each) representing the latitude and longitude (in degrees) of the destination. The numbers are single-precision \textbf{IEEE754} floating point numbers. All latitudes are between \textbf{-90} and \textbf{90} degrees; all longitudes are between \textbf{-180} and \textbf{180} degrees. \end{itemize} \OutputFile The output file is also a binary file, containing only \textbf{32}-bit integers written in little-endian representation. For each of the \textbf{M} lines in the input file, it must contain: \begin{itemize} \item One integer --the number \textbf{P} of post offices in the destination set \item \textbf{P} integers -- the indices of the post offices in the destination set, sorted in ascending order (lower indices first). The index of the first post office in the input file is considered to be \textbf{1} (and thus, all indices should be between \textbf{1} and \textbf{N}, inclusively) \end{itemize}