/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxk = 1e5 + 10, maxn = 1e5 + 10;

struct point
{
    ll x, y;
} p[maxn], r[maxk];

double distance(point p1, point p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) +
                (p1.y - p2.y) * (p1.y - p2.y));
}

const int maxp = 400;

int n, k, ridx[maxk], pos[maxn], to[maxn];
double s[maxk];
mt19937 rng;
vector < int > g[maxn];
bool cmp(int a, int b)
{
    return s[a] < s[b];
}

bool cmp2(int a, int b)
{
    return g[a].size() > g[b].size();
}
const int maxcor = 1e9;
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= k; i ++)
    {
        ridx[i] = i;
        pos[i] = i;
        cin >> s[i];
    }

    for (int i = 1; i <= n; i ++)
    {
        ///p[i].x = rand() % (int)(1e9) + 1;
        ///p[i].y = rand() % (int)(1e9) + 1;
        cin >> p[i].x >> p[i].y;
    }


    if (k <= 2e3)
    {
    sort(ridx + 1, ridx + k + 1, cmp);
    for (int i = 1; i <= k; i ++)
    {
        r[ridx[i]] = p[i];
        //cout << p[i].x << " " << p[i].y << endl;
    }
    for (int i = 1; i <= k; i ++)
    {
        cout << r[i].x << " " << r[i].y << endl;
    }
    for (int i = 1; i <= n; i ++)
    {
        int best = 1;
        if (i > k)
        {
            double d = distance(p[i], r[best]) * s[best];
            for (int j = 0; j < maxp / 2; j ++)
            {
                int idx = ridx[rng() % k + 1];
                double cur = distance(p[i], r[idx]) * s[idx];
                if (cur < d)
                {
                    best = idx;
                    d = cur;
                }
            }

            for (int j = 0; j < maxp / 2; j ++)
            {
                int idx = ridx[rng() % min(100, k) + 1];
                double cur = distance(p[i], r[idx]) * s[idx];
                if (cur < d)
                {
                    best = idx;
                    d = cur;
                }
            }
        }
        else
            best = ridx[i];
        ///sum = sum + distance(p[i], r[best]) * s[best];
        ///cout << best << " " << distance(p[i], r[best]) * s[best] << endl;
        r[best] = p[i];
        cout << best << endl;

    }

    }
    else
    {
    sort(ridx + 1, ridx + 1 + k, cmp);
    ///reverse(ridx + 1, ridx + 1 + k);

    //for (int i = 1; i <= 1000; i ++)
      //  cout << s[ridx[i]] << endl;
    ///exit(0);
    for (int i = 1; i <= n; i ++)
    {
        ///p[i].x = rand() % (int)(1e9) + 1;
        ///p[i].y = rand() % (int)(1e9) + 1;
        cin >> p[i].x >> p[i].y;
    }

    int block = sqrt(k), block_size = maxcor / max(1, block - 1);
    ///cout << block << endl;
    for (int i = 1; i <= n; i ++)
    {
        int idx = (p[i].x / block_size) * block + p[i].y / block_size;
        g[idx].push_back(i);

    }

        for (int i = 1; i <= k; i ++)
    {
        if (g[i].size() == 0)
        {
            swap(g[i], g[0]);
            break;
        }
    }
    sort(pos + 1, pos + k + 1, cmp2);

    for (int i = 0; i <= k; i ++)
    {
        int idx = pos[i];

        if (g[idx].size() == 0)
        {
            ///cout << 1 << " " << 1 << endl;
            r[ridx[i]].x = 1;
            r[ridx[i]].y = 1;
        }
        else
        {
            ///cout << g[idx].size() << endl;
            ///cout << p[g[i][0]].x << " " << p[g[i][0]].y << endl;
            r[ridx[i]] = p[g[idx][0]];
            for (int v : g[idx])
                to[v] = ridx[i];
        }
    }
    for (int i = 1; i <=k ; i ++)
        cout << r[i].x << " " << r[i].y << endl;
    double ans = 0.0;
    for (int i = 1; i <= n; i ++)
    {
        double dis = s[to[i]] * distance(r[to[i]], p[i]);

        ans = ans + dis;
        ///cout << to[i] << " " << dis << " " << s[to[i]] << " " << distance(r[to[i]], p[i]) << endl;
               r[to[i]] = p[i];
               cout << to[i] << endl;
    }
    ///cout << "Ans: " << ans << endl;
    }
    ///cout << "Sum: " << sum << endl;
}

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

    solve();
    return 0;
}