// Arup Guha
// 6/14/2020
// Solution to COP 3502 Program #3: Contact Tracing

// Note: On my machine, when I try to use leak detector, it says there are no memory leaks
//       for arrays of size 30,000 or less, but on the large test cases it says there are a
//       ton of memory leaks. This doesn't make sense based on the structure of code for
//       merge sort. Thus, I think this is an issue with the leak detector itself, or an issue
//       with what happens when we start using a lot of memory with the leak detector. Or maybe
//       if things are happening in parallel in the system, something weird is happening. I think
//       the memory allocation and freeing of memory is fairly straight-forward, and analytically,
//       I just don't see where a leak is happening. Only for the large cases, it reports leaks on
//       the line I malloc a single point struct and assign it to people[i] and also the first line
//       of the merge function where I allocate space for the array of pointers, tmp. It's clear I
//       free this space and that the function can't prematurely return. I also have the freeArray
//       function which frees the original mallocs.

#include <stdio.h>
#include <stdlib.h>

// Stores a Cartesian Point.
typedef struct pt {
    int x;
    int y;
    int distSq;
} pt;

// Functions for sorting.
int compareTo(pt* ptA, pt* ptB);
void sort(pt** array, int length, int threshold);
void insertionSort(pt** array, int sI, int eI);
void mergeSort(pt** array, int sI, int eI, int threshold);
void merge(pt** array, int s1, int s2, int e2);
void initPt(pt* ptr, int thisx, int thisy, int myx, int myy);

// Binary Search Functions.
int binarySearch(pt** array, int length, pt* searchPt);
int binarySearchRec(pt** array, int sI, int eI, pt* searchPt);

// Frees all dynamically allocated memory associated with array.
void freeArray(pt** array, int length);

int main(void) {

	// This stores where I am. They don't actually have to be global.
	int myx, myy;

    // Read where I am.
    scanf("%d%d", &myx, &myy);

    // Read in the number of people, queries and the threshold.
    int numPeople, numQueries, threshold;
    scanf("%d%d%d", &numPeople, &numQueries, &threshold);

    // Allocate memory for people pointers.
    pt** people = malloc(numPeople*sizeof(pt*));

    // Read the people.
    for (int i=0; i<numPeople; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        people[i] = malloc(sizeof(pt));
        initPt(people[i], x, y, myx, myy);
    }

    // Sort it!
    sort(people, numPeople, threshold);

    // Print the sorted list.
    for (int i=0; i<numPeople; i++)
        printf("%d %d\n", people[i]->x, people[i]->y);

    // Process Queries.
    for (int i=0; i<numQueries; i++) {

        // Read x,y and make pt struct.
        int x, y;
        scanf("%d%d", &x, &y);
        pt search;
        initPt(&search, x, y, myx, myy);

        // Look for the point.
        int loc = binarySearch(people, numPeople, &search);

        // Not found.
        if (loc == -1)
            printf("%d %d not found\n", x, y);

        // Found it! Offset print by 1 to match specification.
        else
            printf("%d %d found at rank %d\n", x, y, loc+1);
    }

    // Free the memory...
    freeArray(people, numPeople);
    return 0;
}

// Initializes the point pointed to by ptr with (thisx, thisy).
void initPt(pt* ptr, int thisx, int thisy, int myx, int myy) {

    // Set up where this person is.
    ptr->x = thisx;
    ptr->y = thisy;

    // Set their distance squared from me!
    ptr->distSq = (myx-thisx)*(myx-thisx) + (myy-thisy)*(myy-thisy);
}

// Returns a negative integer if the point pointed to by ptA comes before the point pointed to by
// ptB, according to the problem definition. A positive integer if the point pointed to by ptA comes
// after the one pointed to by ptB, and 0 if they are the same point
int compareTo(pt* ptA, pt* ptB) {

    // First tie is broken based on distance from the reference point.
    if (ptA->distSq != ptB->distSq) return ptA->distSq - ptB->distSq;

    // Then, by x coordinate.
    if (ptA->x != ptB->x) return ptA->x - ptB->x;

    // All other ties are broken by y coordinate.
    return ptA->y - ptB->y;
}

// Runs an insertion sort on the subarray array[sI..eI].
void insertionSort(pt** array, int sI, int eI) {

    // i is the index of the item to be inserted.
    for (int i=sI+1; i<=eI; i++) {

        int j = i;

        // Continue swapping the new item until it finds its correct place.
        while (j > sI && compareTo(array[j], array[j-1]) < 0) {
            pt* tmp = array[j];
            array[j] = array[j-1];
            array[j-1] = tmp;
            j--;
        }
    }
}

// Wrapper function that sorts the array of length length using the value of threshold to determine when
// to use an insertion sort instead of a merge sort.
void sort(pt** array, int length, int threshold) {
    mergeSort(array, 0, length-1, threshold);
}

// Runs a modified merge sort on array[sI..eI]. The modification is that if the subarray size
// is threshold or less, the whole subarray is sorted via insertion sort.
void mergeSort(pt** array, int sI, int eI, int threshold) {

    // Our base case - sort the whole subarray via insertion sort.
    if (eI-sI+1 <= threshold) {
        insertionSort(array, sI, eI);
        return;
    }

    // Find halfway point.
    int mid = (sI+eI)/2;

    // Recursively sort the left.
    mergeSort(array, sI, mid, threshold);

    // And the right.
    mergeSort(array, mid+1, eI, threshold);

    // Merge into one sorted array.
    merge(array, sI, mid+1, eI);
}

// Merges the subarrays array[s1..s2-1] and array[s2..e2] and stores the resulting array
// back into array[s1..e2].
void merge(pt** array, int s1, int s2, int e2) {

    // Make a temporary array the exact size of the sum of the sizes of the two arrays to be merged.
    pt** tmp = malloc(sizeof(pt*)*(e2-s1+1));

    // i is index into left subarray, j is index into right subarray, k is index into tmp (new array).
    int i = s1, j = s2, k = 0;

    // We know we want exactly this many steps...
    while (k <= e2-s1) {

        // Case where we take from the second array.
        if (i == s2 || (j <= e2 && compareTo(array[j], array[i]) < 0))
            tmp[k++] = array[j++];

        // If not the second array, then the first!
        else
            tmp[k++] = array[i++];
    }

    // Now copy everything back into array from tmp.
    for (int i=s1; i<=e2; i++)
        array[i] = tmp[i-s1];

    // Now, this array can be freed.
    free(tmp);
}

// Returns the index where searcPt is found in array (which has length items), or -1 if the element is
// not in array. The precondition is that array is sorted as specified in the assignment. This is just
// a wrapper function for the recursive function.
int binarySearch(pt** array, int length, pt* searchPt) {
    return binarySearchRec(array, 0, length-1, searchPt);
}

// Recursive function which returns the index in which searchPt is in array[sI, eI], or -1 if it isn't.
// The precondition is that array is sorted as defined in the assignment.
int binarySearchRec(pt** array, int sI, int eI, pt* searchPt) {

    // Not found.
    if (sI > eI) return -1;

    // Compare with the middle item in the range.
    int mid = (sI+eI)/2;
    int cmp = compareTo(searchPt, array[mid]);

    // Go left...
    if (cmp < 0) return binarySearchRec(array, sI, mid-1, searchPt);

    // Go right.
    else if (cmp > 0) return binarySearchRec(array, mid+1, eI, searchPt);

    // Found it at index mid!
    else return mid;
}

// Frees all the dyanamically allocated memory pointed to by array, which is an array of size length.
void freeArray(pt** array, int length) {
    for (int i=0; i<length; i++)
        free(array[i]);
    free(array);
}