#include <iostream>
#include <math.h>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <chrono>
#include <assert.h>
#include <time.h>
using namespace std;
typedef long long llong;
typedef long double ldouble;

uint64_t curMillisec()
{
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}

bool TimeIsOK(double TL=4.0)
{
    return (double)clock() / (double)CLOCKS_PER_SEC < TL;
}

struct kdNode
{
    int x1, y1, x2, y2;
    int pointId;
    double maxSpeed;

    int t1, t2;

    bool terminal()
    {
        return x1 == x2 && y1 == y2;
    }

    void show()
    {
        printf("[%d, %d - %d, %d] speed = %lf; id = %d\n", x1, y1, x2, y2, maxSpeed, pointId);
    }
};

struct location
{
    int x, y;
};

bool sortLocX(location &A, location &B)
{
    return A.x < B.x;
}

bool sortLocY(location &A, location &B)
{
    return A.y < B.y;
}

uint64_t totalTime = 0;

bool DEBUG_MODE = false;

int cnt1 = 0, cnt2 = 0, cnt3 = 0;
const int INT_INF = 2000000000;
const int MAXMEM = 1000000;
kdNode Mem[MAXMEM];
int curMemPtr = 1;
int allocNode()
{
    curMemPtr++;
    if (curMemPtr >= MAXMEM)
        exit(1337);
    return curMemPtr - 1;
}
void memPrep()
{
    Mem[0].t1 = Mem[0].t2 = 0;
    Mem[0].maxSpeed = 10000.0;
}

struct advancedKdTree
{
    int root;

    advancedKdTree()
    {
        root = allocNode();
        Mem[root].x1 = 1;
        Mem[root].y1 = 1;
        Mem[root].x2 = 1000000000;
        Mem[root].y2 = 1000000000;
        Mem[root].t1 = Mem[root].t2 = 0;
        Mem[root].maxSpeed = 10000.0;
    }

    void recalcNode(int nd)
    {
        Mem[nd].maxSpeed = min(Mem[ Mem[nd].t1 ].maxSpeed, Mem[ Mem[nd].t2 ].maxSpeed);
    }

    bool fitsNode(int nd, int x, int y)
    {
        return Mem[nd].x1 <= x && x <= Mem[nd].x2 && Mem[nd].y1 <= y && y <= Mem[nd].y2;
    }

    llong sqNodeDist(int nd, int x, int y)
    {
        int xDist = max(0, Mem[nd].x1 - x) + max(0, x - Mem[nd].x2);
        int yDist = max(0, Mem[nd].y1 - y) + max(0, y - Mem[nd].y2);
        return (llong)xDist * xDist + (llong)yDist * yDist;
    }

    int allocBareboneNode(int x1, int y1, int x2, int y2)
    {
        int id = allocNode();
        Mem[id].t1 = Mem[id].t2 = 0;
        Mem[id].maxSpeed = 1000.0;
        Mem[id].x1 = x1;
        Mem[id].y1 = y1;
        Mem[id].x2 = x2;
        Mem[id].y2 = y2;
        return id;
    }

    void recBuild(int ver, int n, location *locs, bool cutX)
    {
        kdNode &mver = Mem[ver];

        if (n == 1)
        {
            assert(mver.terminal());
            return;
        }

        if (cutX)
            sort(locs+1, locs+1+n, sortLocX);
        else
            sort(locs+1, locs+1+n, sortLocY);

        int mid = n / 2;

        if (cutX)
        {
            while(mid < n && locs[mid+1].x == locs[mid].x)
                mid++;
        }
        else
        {
            while(mid < n && locs[mid+1].y == locs[mid].y)
                mid++;
        }

        if (mid == n)
        {
            recBuild(ver, n, locs, !cutX);
            return;
        }

        int x1 = locs[1].x, y1 = locs[1].y, x2 = locs[1].x, y2 = locs[1].y;
        for (int i=2;i<=mid;i++)
        {
            x1 = min(x1, locs[i].x);
            x2 = max(x2, locs[i].x);
            y1 = min(y1, locs[i].y);
            y2 = max(y2, locs[i].y);
        }
        mver.t1 = allocBareboneNode(x1, y1, x2, y2);
        recBuild(mver.t1, mid, locs, !cutX);

        ///

        x1 = locs[mid+1].x;
        y1 = locs[mid+1].y;
        x2 = locs[mid+1].x;
        y2 = locs[mid+1].y;
        for (int i=mid+2;i<=n;i++)
        {
            x1 = min(x1, locs[i].x);
            x2 = max(x2, locs[i].x);
            y1 = min(y1, locs[i].y);
            y2 = max(y2, locs[i].y);
        }
        mver.t2 = allocBareboneNode(x1, y1, x2, y2);
        recBuild(mver.t2, n - mid, locs + mid, !cutX);
    }

    void buildStructure(int n, location *locs)
    {
        recBuild(root, n, locs, true);
    }

    vector< pair<ldouble, int> > activeSet;
    int asL;
    void searchClosest(int ver, int x, int y, int k)
    {
        if (ver == 0)
            return;

        kdNode &mver = Mem[ver];

        if (mver.maxSpeed > 11.0)
            return;

        double sqSpeed = mver.maxSpeed * mver.maxSpeed;

        ldouble curDist;
        if (asL == k)
        {
            curDist = sqSpeed * sqNodeDist(ver, x, y);
            if (activeSet[asL-1].first <= curDist)
                return;
        }

        cnt3++;
        if (mver.terminal())
        {
            if (asL != k)
                curDist = sqSpeed * sqNodeDist(ver, x, y);

            if (asL == k)
                asL--;

            activeSet[asL] = make_pair(curDist, mver.pointId);
            asL++;

            for (int i = asL - 2; i >= 0; i--)
            {
                if (activeSet[i].first > activeSet[i+1].first)
                    swap(activeSet[i], activeSet[i+1]);
                else
                    break;
            }

            if (false)
            {
                fprintf(stderr, "k = %d\n", k);
                for (int i = 0; i < asL; i++)
                {
                    fprintf(stderr, "%lf [%d]\n", (double)activeSet[i].first, activeSet[i].second);
                }
                fprintf(stderr, "\n\n");
            }

            return;
        }

        llong distLeft = (llong)INT_INF * INT_INF;
        if (mver.t1 != 0)
            distLeft = sqNodeDist(mver.t1, x, y);
        llong distRight = (llong)INT_INF * INT_INF;
        if (mver.t2 != 0)
            distRight = sqNodeDist(mver.t2, x, y);

        if (distLeft < distRight)
        {
            searchClosest(mver.t1, x, y, k);
            searchClosest(mver.t2, x, y, k);
        }
        else
        {
            searchClosest(mver.t2, x, y, k);
            searchClosest(mver.t1, x, y, k);
        }
    }

    vector<int> getClosest(int x, int y, int k)
    {
        uint64_t stamp = curMillisec();

        activeSet.clear();
        activeSet.resize(k);
        asL = 0;
        searchClosest(root, x, y, k);
        vector<int> res;
        for (int i = 0; i < asL; i++)
        {
            res.push_back(activeSet[i].second);
        }

        totalTime += curMillisec() - stamp;

        return res;
    }

    void iterAdd(int x, int y, double spd, int pid)
    {
        kdNode *mver = &Mem[root];

        while(!mver->terminal())
        {
            mver->maxSpeed = min(mver->maxSpeed, spd);
            if (mver->t1 != 0 && fitsNode(mver->t1, x, y))
                mver = &Mem[mver->t1];
            else
            {
                mver = &Mem[mver->t2];
            }
        }

        mver->maxSpeed = spd;
        mver->pointId = pid;
    }

    void addPoint(int x, int y, double spd, int pid)
    {
        iterAdd(x, y, spd, pid);
    }

    void recDrop(int ver, int x, int y)
    {
        kdNode &mver = Mem[ver];

        if (x < mver.x1 || x > mver.x2 || y < mver.y1 || y > mver.y2)
            return;

        if (mver.terminal())
        {
            mver.maxSpeed = 10000.0;
            mver.pointId = 0;
            return;
        }

        if (mver.t1 != 0)
            recDrop(mver.t1, x, y);
        if (mver.t2 != 0)
            recDrop(mver.t2, x, y);

        recalcNode(ver);
    }

    void dropPoint(int x, int y)
    {
        recDrop(root, x, y);
    }

    void recClear(int ver)
    {
        kdNode &mver = Mem[ver];

        mver.maxSpeed = 10000.0;
        mver.pointId = 0;

        if (mver.t1 != 0)
            recClear(mver.t1);
        if (mver.t2 != 0)
            recClear(mver.t2);
    }

    void clearAll()
    {
        recClear(root);
    }
};


struct runner
{
    int id;
    double speed;

    int x, y;
};

int n, k;
runner runners[100111];
location locs[100111];

ldouble totalPath[100111];
int counts[100111];

int assignment[100111];

ldouble sq(ldouble x)
{
    return x * x;
}

void printStartLocations(int *ass)
{
    vector< pair<int, int> > starts;
    vector< pair<int, int> > cur;
    starts.resize(n + 1);
    cur.resize(n + 1);
    for (int i = 1; i <= k; i++)
    {
        starts[i] = make_pair(0, 0);
        cur[i] = make_pair(0, 0);
    }

    ldouble totalCost = 0.0;
    vector<ldouble> costs;
    for (int i = 1; i <= n; i++)
    {
        if (starts[ ass[i] ] == make_pair(0, 0))
        {
            starts[ ass[i] ] = make_pair(locs[i].x, locs[i].y);
        }
        else
        {
            ldouble curCost = runners[ ass[i] ].speed * sqrt( sq(cur[ ass[i] ].first - locs[i].x) + sq(cur[ ass[i] ].second - locs[i].y) );
            costs.push_back(curCost);

            totalCost += curCost;
        }

        cur[ ass[i] ] = make_pair(locs[i].x, locs[i].y);
    }

    sort(costs.begin(), costs.end());
    reverse(costs.begin(), costs.end());

    fprintf(stderr, "Average: %lf\n", (double)totalCost / (double)n);

    for (int i = 1; i <= k; i++)
    {
        if (starts[i] == make_pair(0, 0))
            starts[i] = make_pair(1, 1);

        printf("%d %d\n", starts[i].first, starts[i].second);
    }

    fprintf(stderr, "Total cost: %.4lf\n", (double)totalCost);
}

ldouble moveCost(int x1, int y1, int x2, int y2, ldouble spd)
{
    return spd * sqrt(sq(x1 - x2) + sq(y1 - y2));
}

vector<int> paths[100111];
int nextPtr[100111];
bool placed[100111];

void preparePass()
{
    int i;

    for (i=1;i<=k;i++)
    {
        paths[i].clear();
        nextPtr[i] = 0;
        placed[i] = false;
    }

    for (i=1;i<=n;i++)
    {
        paths[ assignment[i] ].push_back(i);
    }
}

location locCopy[100111];
int main()
{
    freopen("runners.in", "r", stdin);
    freopen("runners.out", "w", stdout);
    //freopen("test.txt", "r", stdin);

    memPrep();

    int i, j;
    long double totalCost = 0.0;

    scanf("%d %d", &n, &k);

    for (i=1;i<=k;i++)
    {
        scanf("%lf", &runners[i].speed);
        runners[i].id = i;
    }

    advancedKdTree kd;
    int unusedPtr = 2;

    for (i=1;i<=n;i++)
    {
        scanf("%d %d", &locs[i].x, &locs[i].y);
        locCopy[i] = locs[i];
    }

    kd.buildStructure(n, locCopy);

    fprintf(stderr, "Memory used: %d\n", curMemPtr);

    runners[1].x = locs[1].x;
    runners[1].y = locs[1].y;
    kd.addPoint(runners[1].x, runners[1].y, runners[1].speed, 1);
    assignment[1] = 1;
    paths[1].push_back(1);
    for (i=2;i<=n;i++)
    {
        int bestId = kd.getClosest(locs[i].x, locs[i].y, 1)[0];

        if (runners[bestId].x == locs[i].x && runners[bestId].y == locs[i].y)
        {
            assignment[i] = bestId;
            continue;
        }

        if (unusedPtr <= k)
        {
            runners[unusedPtr].x = locs[i].x;
            runners[unusedPtr].y = locs[i].y;
            kd.addPoint(runners[unusedPtr].x, runners[unusedPtr].y, runners[unusedPtr].speed, unusedPtr);
            assignment[i] = unusedPtr;
            unusedPtr++;
        }
        else
        {
            kd.dropPoint(runners[bestId].x, runners[bestId].y);
            runners[bestId].x = locs[i].x;
            runners[bestId].y = locs[i].y;

            kd.addPoint(runners[bestId].x, runners[bestId].y, runners[bestId].speed, bestId);

            assignment[i] = bestId;
        }
    }

    kd.clearAll();

    /// Second pass
    bool anyGain = true;
    for (int iteration = 1; anyGain; iteration++)
    {
        if (!TimeIsOK())
            break;

        fprintf(stderr, "Iteration %d\n", iteration);
        anyGain = false;
        preparePass();

        for (i=1;i<=n;i++)
        {
            if ((i & 127) == 0 && !TimeIsOK())
                break;

            int ass = assignment[i];

            vector<int> candidates = kd.getClosest(locs[i].x, locs[i].y, 10);
            ldouble maxGain = 0;
            int bestCand = ass;

            for (int cand : candidates)
            {
                if (cand == ass)
                    continue;

                ldouble curCost = 0.0;
                if (placed[ass])
                {
                    curCost += moveCost(runners[ass].x, runners[ass].y, locs[i].x, locs[i].y, runners[ass].speed);
                }
                if (nextPtr[ass] + 1 < paths[ass].size())
                {
                    int nextAssNode = paths[ass][ nextPtr[ass] + 1 ];
                    curCost += moveCost(locs[i].x, locs[i].y, locs[nextAssNode].x, locs[nextAssNode].y, runners[ass].speed);
                }
                if (placed[cand] && nextPtr[cand] < paths[cand].size())
                {
                    int nextCandNode = paths[cand][ nextPtr[cand] ];
                    curCost += moveCost(runners[cand].x, runners[cand].y, locs[nextCandNode].x, locs[nextCandNode].y, runners[cand].speed);
                }

                ldouble newCost = 0.0;
                if (placed[ass] && nextPtr[ass] + 1 < paths[ass].size())
                {
                    int nextAssNode = paths[ass][ nextPtr[ass] + 1 ];
                    newCost += moveCost(runners[ass].x, runners[ass].y, locs[nextAssNode].x, locs[nextAssNode].y, runners[ass].speed);
                }
                if (placed[cand])
                    newCost += moveCost(runners[cand].x, runners[cand].y, locs[i].x, locs[i].y, runners[cand].speed);
                if (nextPtr[cand] < paths[cand].size())
                {
                    int nextCandNode = paths[cand][ nextPtr[cand] ];
                    newCost += moveCost(locs[i].x, locs[i].y, locs[nextCandNode].x, locs[nextCandNode].y, runners[cand].speed);
                }

                ldouble gain = curCost - newCost;

                if (gain > maxGain)
                {
                    maxGain = gain;
                    bestCand = cand;
                }
            }

            if (placed[bestCand])
                kd.dropPoint(runners[bestCand].x, runners[bestCand].y);

            if (ass != bestCand)
                anyGain = true;

            kd.addPoint(locs[i].x, locs[i].y, runners[bestCand].speed, bestCand);
            placed[bestCand] = true;
            runners[bestCand].x = locs[i].x;
            runners[bestCand].y = locs[i].y;

            assignment[i] = bestCand;
            nextPtr[ass]++;
        }
    }

    printStartLocations(assignment);
    for (i=1;i<=n;i++)
    {
        printf("%d\n", assignment[i]);
    }

    fprintf(stderr, "Time spent in measurement: %lld\n", totalTime);
    fprintf(stderr, "Counts %d %d %d\n", cnt1, cnt2, cnt3);
    fprintf(stderr, "Memory used: %d\n", curMemPtr);

    return 0;
}