#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXN = 100000 + 5;
const int MAXK = 100000 + 5;

struct Computer
{
    int x, y;
    int num;
    int runner;
    int dist;
    Computer () {};
    Computer (int _x, int _y)
    {
        x = _x;
        y = _y;
        num = 0;
    }
    Computer (int _x, int _y, int _num)
    {
        x = _x;
        y = _y;
        num = _num;
    }
};

struct Runner
{
    double s;
    int num;
    int x, y;
    Runner () {};
    Runner (double _s, int _num)
    {
        s = _s;
        num = _num;
        x = y = 0;
    }
};
Runner runners[MAXN];

bool operator < (Runner a, Runner b)
{
    return a.s < b.s;
}

Computer computers[MAXN];
Computer center;

int n, k;
int minX = 2e9, maxX = -2e9, minY = 2e9, maxY = -2e9;

void input()
{
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
    {
        double s;
        cin >> s;
        runners[i] = Runner(s, i);
    }
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        computers[i] = Computer(x, y, i);
    }
}

int getDistFromCenter(Computer a)
{
    return sqrt(abs((long long)(a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)));
}

long long getDist(Computer a, Runner b)
{
    return (long long)(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long getDist(Computer a, Computer b)
{
    return (long long)(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmp(Computer a, Computer b)
{
    return getDistFromCenter(a) > getDistFromCenter(b);
}

bool cmp2(Computer a, Computer b)
{
    return a.num < b.num;
}

bool cmp3(Runner a, Runner b)
{
    return a.num < b.num;
}

void prepare()
{
    for (int i = 1; i <= n; i++)
    {
        minX = min(minX, computers[i].x);
        minY = min(minY, computers[i].y);
        maxX = max(maxX, computers[i].x);
        maxY = max(maxY, computers[i].y);
    }

    center = Computer((maxX - minX + 1) / 2, (maxY * minY + 1) / 2);

//    sort(runners + 1, runners + k + 1);
//    sort(computers + 1, computers + n + 1, cmp);
}

double getTime(Runner a, Computer b)
{
    return (double)((long long)(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) * a.s * a.s;
}

long long distConst = 0;

Runner runnersAns[MAXK];

pair <long long, int> runnerCnt[MAXK];
int swapped[MAXK];

void solve()
{
    int cntRunners = 0;

    for (int i = 2; i <= n; i++)
        distConst += getDist(computers[i-1], computers[i]) / (n + 50);

    for (int i = 1; i <= n; i++)
    {
        int bestRunner = 0;
        long long bestDist = 1e18;

        for (int j = 1; j <= cntRunners; j++)
        {
            long long p = getDist(computers[i], runners[j]);
            if (p < bestDist)
            {
                bestDist = p;
                bestRunner = j;
            }
        }

        if (cntRunners < k && bestDist > distConst)
        {
            cntRunners++;
            bestRunner = cntRunners;
            bestDist = 0;

            runnersAns[bestRunner].x = computers[i].x;
            runnersAns[bestRunner].y = computers[i].y;
        }

        runners[bestRunner].x = computers[i].x;
        runners[bestRunner].y = computers[i].y;
        computers[i].runner = bestRunner;

        runnerCnt[bestRunner].first += sqrt(bestDist);
    }

    for (int i = cntRunners+1; i <= k; i++)
    {
        runnersAns[i].x = computers[n - k + i].x;
        runnersAns[i].y = computers[n - k + i].y;
//        cerr << "* * * " << n - k + i << endl;
        computers[n - k + i].runner = i;
    }

    for (int i = 1; i <= k; i++)
        runnerCnt[i].second = i;

    sort(runnerCnt+1, runnerCnt + k + 1);
    sort(runners+1, runners+k+1);

    for (int i = 1; i <= n; i++)
    {
        swapped[runners[i].num] = runnerCnt[i].second;
    }

    for (int i = 1; i <= k; i++)
        cout << runnersAns[swapped[i]].x << " " << runnersAns[swapped[i]].y << endl;

    for (int i = 1; i <= n; i++)
        cout << swapped[computers[i].runner] << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("runners.in", "r", stdin);
    freopen("runners.out", "w", stdout);

    input();
    prepare();
    solve();
}
/**
5 2
1.300000
1.800000
3 8
6 7
9 4
10 2
1 5

3 8
6 7
1
2
2
2
1
*/