#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
struct point { int x, y; };
int n, k;
vector<double> s;
vector<point> pcs;
vector<point> rs;

struct k_node
{
    bool x;
    double mid;
    int l;
    int mink, maxk;
    point minp, maxp;
    int left, right;
};
vector<k_node> k_array;

void split(vector<k_node>& arr, k_node& n, vector<point>& rs)
{
    if (n.mink < n.maxk)
    {
        if(n.x)
            n.mid = (n.maxp.x + n.minp.x) / 2;
        else
            n.mid = (n.maxp.y + n.minp.y) / 2;

        int midk = (n.maxk + n.mink) / 2;
        if (n.mink <= midk)
        {
            arr.push_back(k_node());
            k_node& nl = arr.back();
            n.left = arr.size() - 1;
            nl.x = !n.x;
            nl.mink = n.mink;
            nl.maxk = midk;
            nl.minp = n.minp;
            nl.maxp = n.maxp;
            nl.left = nl.right = -1;
            if (n.x)
                nl.maxp.x = n.mid;
            else
                nl.maxp.y = n.mid;
            if (nl.mink < nl.maxk)
                split(arr, nl, rs);
            else
                rs[nl.mink] = { (nl.minp.x + nl.maxp.x) / 2, (nl.minp.y + nl.maxp.y) / 2 };
        }
        if (midk + 1 <= n.maxk)
        {
            arr.push_back(k_node());
            k_node& nr = arr.back();
            n.right = arr.size() - 1;
            nr.x = !n.x;
            nr.mink = midk + 1;
            nr.maxk = n.maxk;
            nr.minp = n.minp;
            nr.maxp = n.maxp;
            nr.left = nr.right = -1;
            if (n.x)
                nr.minp.x = n.mid;
            else
                nr.minp.y = n.mid;
            if (nr.mink < nr.maxk)
                split(arr, nr, rs);
            else
                rs[nr.mink] = { (nr.minp.x + nr.maxp.x) / 2, (nr.minp.y + nr.maxp.y) / 2 };
        }
    }
    else
    {
        n.left = n.right = -1;
    }
}

void solve(ifstream& in, ofstream& out)
{
    in >> n >> k;
    s.resize(k);
    for (int i = 0; i < k; i++)
        in >> s[i];
    pcs.resize(n);
    point minp = { INT32_MAX, INT32_MAX }, maxp = { INT32_MIN, INT32_MIN };
    for (int i = 0; i < n; i++)
    {
        int x, y;
        in >> x >> y;
        pcs[i].x = x; pcs[i].y = y;
        minp.x = min(minp.x, x);
        minp.y = min(minp.y, y);
        maxp.x = max(maxp.x, x);
        maxp.y = max(maxp.y, y);
    }

    rs.resize(k);
    k_array.reserve(2 * k);
    k_array.push_back(k_node());
    k_node& root = k_array.back();
    root.mink = 0;
    root.maxk = k - 1;
    root.minp = minp;
    root.maxp = maxp;
    root.left = root.right = -1;
    root.x = true;
    root.l = 0;
    split(k_array, root, rs);

    for (int i = 0; i < k; i++)
        out << rs[i].x << " " << rs[i].y << endl;

    for (int i = 0; i < n; i++)
    {
        point& p = pcs[i];
        int l = 0;
        while (k_array[l].mink < k_array[l].maxk)
        {
            k_node& n = k_array[l];
            if (n.x)
            {
                if (p.x < n.mid)
                    l = n.left;
                else
                    l = n.right;
            }
            else
            {
                if (p.y < n.mid)
                    l = n.left;
                else
                    l = n.right;
            }
        }
        out << k_array[l].mink + 1 << endl;
    }
}

int main()
{
    ifstream in("runners.in");
    ofstream out("runners.out");
    solve(in, out);
    return 0;
}