The Problem

Given your location, and the location of each smoothie store, sort the list by distance from you from shortest

to longest, breaking ties by x$-$coordinate $($lower comes first$),$ and then breaking those ties by y coordinate

$($lower comes first$).$

After sorting, answer several queries about points in the coordinate plane. Specifically, determine if a query

point contains a smoothie shop or not. If so$,$ determine that shop's ranking on the sorted list in distance from

you.

The Input $($to be read from standard input. Using file i$/$o on any submission $($either latest or history of

submissions while grading$)$ will result in zero in this assignment and $0$ in another past assignment$)$

The first line of the input contains $5$ integers separated by spaces. The first two of these values are x and y $(|$x$|,$

$|$y$|<=10000),$ representing your location. The third integer is n $(2<=$ n $<=106),$ representing the number of smoothie

shops. The fourth integer is s $(1<=$ s $<=2$x$105),$ representing the number of points to search for. The last integer,

t $(1<=$ t $<=30),$ represents the threshold to be used for determining whether you run Merge Sort of Insertion Sort.

The next n lines of the input contain x and y coordinate values, respectively, separated by spaces, representing

the locations of shops. Each of these values will be integers and the points will be distinct $($and also different

from your location$)$ and the absolute value of x and y for all of these coordinates will not exceed $10,000.$

Then the next s lines of the input contain x and y coordinate values for searching. Both values on each line

will be integers with an absolute value less than or equal to $10,000.$

The Output $($to be printed to standard console output$)$

The first n lines of output should contain the coordinates of the smoothie shops, sorted as previously mentioned.

These lines should have the x$-$coordinate, followed by a space, followed by the y$-$coordinate.

The last s lines of output will contain the answers to each of the s queries in the input. The answer for a single

query will be on a line by itself. If the point queried contains a smoothie shop, output a line with the following

format:

x y found at rank R

where $($x$,$ y$)$ is the query point, and R is the one$-$based rank of that smoothie shop in the sorted list. $($Thus$,$ R

will be $1$ more than the array index in which $($x$,$ y$)$ is located, after sorting.$)$

If the point queried does NOT contain a smoothie shop, output a line with the following format:

x y not found

Sample Input data $($Note: Query points in blue for

clarity.$)$

$001455$

$31$

$-6-2$

$-43$

$4-4$

$24$

$-13$

$22$

$0-5$

$-4-2$

$-66$

$44$

$-24$

$05$

$-46$

$2-1$

$31$

$0-5$

$05$

$-67$

Sample Output

$22$

$-13$

$31$

$-4-2$

$-24$

$24$

$-43$

$0-5$

$05$

$4-4$

$44$

$-6-2$

$-46$

$-66$

$2-1$ not found

$31$ found at rank $3$

$0-5$ found at rank $8$

$05$ found at rank $9$

$-67$ not found

Additional Requirement: