#include<iostream>
#include<bits/stdc++.h>
using namespace std;
pair<float,int> s[100010];
pair<float,int> travel[100010];
float interval[100010];
int used[100010];
int np[100010];
int out[100010];
pair<int,int> fin[100010];
pair<float,float> coords[100010];
struct points
{
    float x,y;
    int ind;
}p[100010];
struct side
{
    float val;
    int x1,x2;
};
vector<side> sides;
bool comp(points a, points b)
{
    if(a.x!=b.x)return a.x<b.x;
    else if(a.y!=b.y)return a.y<b.y;
    else return a.ind<b.ind;
}
bool comp2(side a, side b)
{
    if(a.val!=b.val)return a.val<b.val;
    else if(a.x1!=b.x1)return a.x1<b.x1;
    else return a.x2<b.x2;
}
bool comp3(pair<float,int> a, pair<float,int> b)
{
    if(a.first>b.first)return a.first>b.first;
    else return a.second>b.second;
}
int place(int ind, float &maxx)
{
    sort(sides.begin(),sides.end(),comp2);
    reverse(sides.begin(),sides.end());
    float v = sides[0].val;
    int x1 = sides[0].x1;
    int x2 = sides[0].x2;
    float dist1,best=INT_MAX,ls,rs,big,bls,brs;
    side NL,NR;
    int pos;
    dist1=interval[x1-1];
    for(int i=x1;i<=x2;i++)
    {
        ls=dist1-interval[i-1];
        rs=v-ls;
        big=max(ls,rs);
        if(maxx-big<best)
        {
            best=maxx-big;pos=i;
            NL.val=ls;NL.x1=x1+1;NL.x2=pos-1;
            NR.val=rs;NR.x1=pos+1;NR.x2=x2;
        }
        dist1+=interval[i-1];
    }
    sides.erase(sides.begin());
    sides.push_back(NL);
    sides.push_back(NR);
    maxx=max(NL.val,NR.val);
    return pos;
}
pair<pair<int,float>,int> findnearest(int ind, int n)
{
    int prev=ind,next=ind;
    float dp=0,dn=0;
    short ans;
    pair<pair<int,float>,int> res;
    while(1)
    {
        if(prev>0){prev--;dp+=interval[prev];}
        if(next<n){next++;dn+=interval[next-1];}
        if(used[prev]!=0 && used[next]!=0)
        {
            if(dp<dn){res.first.first=prev;res.first.second=dp;res.second=used[prev];return res;}
            else {res.first.first=next;res.first.second=dn;res.second=used[next];return res;}
        }
        else if(used[prev]!=0 && used[next]==0){res.first.first=prev;res.first.second=dp;res.second=used[prev];return res;}
        else {res.first.first=next;res.first.second=dn;res.second=used[next];return res;}
    }
}
int main()
{
    //!needs a way of sorting by speed!!!
    int n,k,st;
    float maxx=-1;
    /*ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(6);
    cin>>n>>k;*/
    FILE *F;
    F=fopen("runners.in","rt");
    fscanf(F,"%d %d",&n,&k);
    for(int i=1;i<=k;i++){fscanf(F,"%f",&s[i].first);s[i].second=i;travel[i].second=i;}
    for(int i=0;i<n;i++)
    {
        int x,y;
        fscanf(F,"%f %f",&p[i].x,&p[i].y);
        p[i].ind=i;
    }
    sort(p,p+n,comp);
    for(int i=0;i<n;i++)
    {
        int ns=p[i].ind;
        np[ns]=i;
    }
    float curr=0,left,right;
    bool lng; //0 = left, 1 =right;
    //find starting point
    for(int i=0;i<n-1;i++)
    {
        int i2=i;
        int i3=i+1;
        interval[i2]=(p[i2].x-p[i3].x)*(p[i2].x-p[i3].x);
        interval[i2]+=(p[i2].y-p[i3].y)*(p[i2].y-p[i3].y);
        interval[i2]=sqrt(interval[i2]);
        if(p[i].ind==0){st=i;left=curr;curr=0;}
        curr+=interval[i2];
    }
    used[st]=1;
    coords[1]={p[st].x,p[st].y};
    right=curr;
    //find locations of all points
    side L,R;
    L.val=left;
    L.x1-0;
    L.x2=st-1;
    R.val=right;
    R.x1=st+1;
    R.x2=n-1;
    maxx=max(left,right);
    sides.push_back(L);
    sides.push_back(R);
    lng=(left>right);
    for(int i=2;i<=k;i++)
    {
        int pos=place(i,maxx);
        used[pos]=i;
        coords[i]={p[pos].x,p[pos].y};
    }
    //calculate wait time
    for(int q=0;q<n;q++)
    {
        int i=np[q];
        if(used[i]==0)
        {
            pair<pair<int,float>,int> near=findnearest(i,n);
            int id=near.first.first;
            float dist=near.first.second;
            int person=near.second;
            used[id]=0;
            used[i]=person;
            out[q]=person;
            travel[person].first+=dist;
        }
        else out[q]=used[i];
    }
    sort(travel+1,travel+k+1,comp3);
    sort(s+1,s+k+1,comp3);
    for(int i=1;i<=k;i++)
    {
        int h=travel[i].second;
        int num=s[i].second;
        fin[num]=coords[h];
    }
    fclose(F);
    F = fopen("runners.out","wt");
    for(int i=1;i<=k;i++)
    {
        fprintf(F,"%d %d\n",fin[i].first,fin[i].second);
    }
    for(int i=0;i<n;i++)
    {
       fprintf(F,"%d\n",out[i]);
    }
    fclose(F);
    //cout.precision(6);
    //cout<<fixed<<left<<" "<<right<<"\n";
}
/*
5 2
1.300000
1.800000
3 8
6 7
9 4
10 2
1 5

3 2
1.000000
2.000000
1 2
1 3
1 1000
--------------------------
cout<<i<<"| ";
...
cout<<id<<" "<<person<<" ";
cout<<fixed<<dist<<"\n";
*/