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

const int MAXN=1e5+5;
const int MAXK=1e5+5;

random_device rd;
mt19937 g(rd());
uniform_int_distribution<> randNum(1,1e9);

int n,k;
pair<double,int> r[MAXK];
pair<int,int> pos[MAXK];
pair<int,int> p[MAXN];

long double curr=0;
long double best=1e18;
vector<int> v;
pair<int,int> solPos[MAXK];
int solR[MAXN];

multiset<pair<int,int> > mx;
multiset<pair<int,int> > my;

double dist(int i,int j)
{
    return r[j].x*sqrt((p[i].x-pos[j].x)*(p[i].x-pos[j].x)+
                       (p[i].y-pos[j].y)*(p[i].y-pos[j].y));
}

void calc()
{
    curr=0;
    for(int i=1;i<=n;i++)
    {
        double tmp=0,mint=1e12;
        int minR=0;
        for(int j=1;j<=k;j++)
        {
            tmp=dist(i,j);
            if(tmp<mint)
            {
                mint=tmp;
                minR=i;
            }
        }
        curr+=mint;
        v.push_back(minR);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("runners.in","r",stdin);
    freopen("runners.out","w",stdout);

    cin>>n>>k;
    for(int i=1; i<=k; i++)
    {
        cin>>r[i].x;
        r[i].y=i;
    }
    int X,Y;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i].x>>p[i].y;
        pos[i]=p[i];
        X=max(X,p[i].x);
        Y=max(Y,p[i].y);
    }

    for(int i=1;i<=k;i++)
    {
        mx.insert({pos[i].x,i});
        my.insert({pos[i].y,i});
    }

    int t=0;
    if(k<=10) t=1;
    else if(k<=100) t=2;
    else if(k<=1000) t=3;
    else if(k<=10000) t=4;
    else if(k<=100000) t=5;

    for(int i=1;i<=k;i++)
    {
        solPos[i]=p[i];
        solR[i]=i;
    }

    const int C=10;
    for(int i=k+1;i<=n;i++)
    {
        int tmp=1,bst=1;
        double d=0,bst_d=1e12;
        auto it=mx.lower_bound({p[i].x,0});
        auto itx=it, ity=it;
        int j=C;
        for(auto it2=it; j>0;it2--, j--)
        {
            if(it2==mx.end()) break;
            tmp=(*it2).second;
            d=dist(i,tmp);
            if(d<bst_d)
            {
                bst_d=d;
                bst=tmp;
                itx=it2;
                X=(*it2).first;
            }
            if(it2==mx.begin()) break;
        }
        j=0;
        for(auto it2=it; j<C;it2++, j++)
        {
            if(it2==mx.end()) break;
            tmp=(*it2).second;
            d=dist(i,tmp);
            if(d<bst_d)
            {
                bst_d=d;
                bst=tmp;
                itx=it2;
                X=(*it2).first;
            }
        }

        it=my.lower_bound({p[i].y,0});
        j=C;
        for(auto it2=it; j>0;it2--, j--)
        {
            if(it2==my.end()) break;
            tmp=(*it2).second;
            d=dist(i,tmp);
            if(d<bst_d)
            {
                bst_d=d;
                bst=tmp;
                ity=it2;
                Y=(*it2).first;
            }
            if(it2==my.begin()) break;
        }
        j=0;
        for(auto it2=it; j<C;it2++, j++)
        {
            if(it2==my.end()) break;
            tmp=(*it2).second;
            d=dist(i,tmp);
            if(d<bst_d)
            {
                bst_d=d;
                bst=tmp;
                ity=it2;
                Y=(*it2).first;
            }
        }
        solR[i]=bst;
        pos[bst]=p[i];

        mx.erase({X,bst});
        my.erase({Y,bst});

        mx.insert({pos[bst].x,bst});
        my.insert({pos[bst].y,bst});
        //curr+=dist(i,solR[i]);
    }
    //best=curr;

    for(int i=1;i<=k;i++) cout<<solPos[i].x<<" "<<solPos[i].y<<endl;
    for(int i=1;i<=n;i++) cout<<solR[i]<<endl;

    return 0;
}