#include<fstream>
#include<cmath>
#include<algorithm>

using namespace std;

#define COORD_MAX 1e9

double f(unsigned long long x,unsigned long long y){
    return x+y/x*COORD_MAX;
}

unsigned long long* coords;

bool comp(unsigned int a,unsigned int b){
    return f(coords[2*a],coords[2*a+1])<f(coords[2*b],coords[2*b+1]);
}

unsigned long long* spots;

bool comp_pl(unsigned int a,unsigned int b){
    return f(spots[2*a],spots[2*a+1])<f(spots[2*b],spots[2*b+1]);
}

int main(){
    ifstream inp;
    inp.open("runners.in",ios::in);
    unsigned int n,k;
    inp>>n>>k;
    float* speeds=new float[k];
    double averageSpeed=0.0;
    for(unsigned int i=0;i<k;i++){
        inp>>speeds[i];
        averageSpeed+=speeds[i];
    }
    averageSpeed/=k;
    coords=new unsigned long long[2*n];
    double averageLength=0.0;
    for(unsigned int i=0;i<n;i++){
        inp>>coords[2*i]>>coords[2*i+1];
        if(i>=1)
            averageLength+=sqrt((coords[2*i]-coords[2*i-2])*(coords[2*i]-coords[2*i-2])+(coords[2*i+1]-coords[2*i-1])*(coords[2*i+1]-coords[2*i-1]));
    }
    inp.close();

    averageLength/=n-1;

    spots=new unsigned long long[2*k];
    double curX=coords[0];
    double curY=coords[1];
    unsigned int curPnt=0;
    int prevPnt=-1;
    double travel=0.0;
    double slope=((double)(signed int)(coords[2]-coords[0]))/((signed int)(coords[3]-coords[1]));;
    for(unsigned int i=0;i<k;i++){
        if(travel>0.0){
            double dist=sqrt((curX-coords[curPnt*2+2])*(curX-coords[curPnt*2+2])+
                             (curY-coords[curPnt*2+3])*(curY-coords[curPnt*2+3]));
            if(travel>=dist){
                curPnt++;
                slope=((double)(signed int)(coords[2*curPnt+2]-coords[2*curPnt]))/((signed int)(coords[2*curPnt+3]-coords[2*curPnt+1]));
                travel-=dist;
                curX=coords[2*curPnt];
                curY=coords[2*curPnt+1];
                i--;
                continue;
            }else{

/*              dx^2+dy^2=travel^2
                dx/dy=slope
                (dy*scope)^2+dy^2=travel^2
                dy^2*(scope^2+1)=travel^2
                dy=sqrt(travel^2/(scope^2+1))
                dx=slope*dy=slope*sqrt(travel^2/(slope^2+1))              */

                double dy=sqrt(travel*travel/(slope*slope+1));
                if(coords[2*curPnt+1]>coords[2*curPnt+3])
                    dy*=-1.0;
                curY+=dy;
                curX+=slope*dy;
                travel=0.0;
            }
        }else{
            travel=averageLength+speeds[i]-averageSpeed;
            i--;
            continue;
        }

        unsigned int writePnt=curPnt;
        if(abs(curX-coords[2*curPnt])<abs(curX-coords[2*curPnt+1])){
            if((signed)writePnt<=prevPnt)
                writePnt=prevPnt+1;
            spots[2*i]=coords[2*writePnt];
            spots[2*i+1]=coords[2*writePnt+1];
            prevPnt=writePnt;
        }else{
            if((signed)(writePnt+1)<=prevPnt)
                writePnt=prevPnt;
            spots[2*i]=coords[2*writePnt+2];
            spots[2*i+1]=coords[2*writePnt+3];
            prevPnt=writePnt+1;
        }
    }

    unsigned int* by_closeness=new unsigned int[n];
    for(unsigned int i=0;i<n;i++)
        by_closeness[i]=i;
    sort(by_closeness,by_closeness+n,&comp);

    unsigned int* by_closeness_pl=new unsigned int[k];
    for(unsigned int i=0;i<k;i++)
        by_closeness_pl[i]=i;
    sort(by_closeness_pl,by_closeness_pl+k,&comp_pl);

    unsigned int* pause_ls=new unsigned int[k];
    unsigned int runner_index=0;
    unsigned int counter=0;
    for(unsigned int i=0;i<n;i++){
        if(coords[2*by_closeness[i]]==spots[2*by_closeness_pl[runner_index]]&&
           coords[2*by_closeness[i]+1]==spots[2*by_closeness_pl[runner_index]+1]){
            pause_ls[by_closeness_pl[runner_index]]=counter;
            counter=0;
            runner_index++;
            if(runner_index==k) break;
        }
        counter++;
    }

    unsigned int* whose=new unsigned int[n];
    unsigned int pause_index=0;
    unsigned int cur_counter=0;
    for(unsigned int i=0;i<n;i++){
        if(by_closeness_pl[pause_index]<k){
            if(cur_counter==pause_ls[by_closeness_pl[pause_index]]){
                cur_counter=0;
                pause_index++;
            }
        }
        if(by_closeness_pl[pause_index]==0)
            whose[i]=0;
        else if(by_closeness_pl[pause_index]>=k-1)
            whose[i]=k-1;
        else if(cur_counter<((float)pause_ls[by_closeness_pl[pause_index]])*speeds[by_closeness[pause_index]]/
                 (speeds[by_closeness[pause_index]]+speeds[by_closeness[pause_index+1]]))
            whose[i]=by_closeness_pl[pause_index];
        else
            whose[i]=by_closeness_pl[pause_index+1];

        cur_counter++;
    }

    unsigned long long* start_pos=new unsigned long long[2*k];
    unsigned int last_pl=by_closeness_pl[0];
    unsigned int int_start=0;

    for(unsigned int i=0;i<n;i++){
        if(whose[by_closeness[i]]!=last_pl){
            unsigned long long smallestX=COORD_MAX,biggestX=0,smallestY=COORD_MAX,biggestY=0;
            for(unsigned int j=int_start;j<i;j++){
                if(coords[2*by_closeness[j]]<smallestX) smallestX=coords[2*by_closeness[j]];
                if(coords[2*by_closeness[j]]>biggestX) biggestX=coords[2*by_closeness[j]];
                if(coords[2*by_closeness[j]+1]<smallestY) smallestY=coords[2*by_closeness[j]+1];
                if(coords[2*by_closeness[j]+1]>biggestY) biggestY=coords[2*by_closeness[j]+1];
            }
            unsigned long long LUx=biggestX,LUy=biggestY,RDx=smallestX,RDy=smallestY,
                               RUx=smallestX,RUy=biggestY,LDx=biggestX,LDy=smallestY;
            double averageX=0.0,averageY=0.0;
            for(unsigned int j=int_start;j<i;j++){
                if(coords[2*by_closeness[j]]*coords[2*by_closeness[j]]+coords[2*by_closeness[j]+1]*coords[2*by_closeness[j]+1]<
                   LUx*LUx+LUy*LUy){
                    LUx=coords[2*by_closeness[j]];
                    LUy=coords[2*by_closeness[j]+1];
                }
                if((biggestX-coords[2*by_closeness[j]])*(biggestX-coords[2*by_closeness[j]])+
                   (biggestY-coords[2*by_closeness[j]+1])*(biggestY-coords[2*by_closeness[j]+1])<
                   (biggestX-LUx)*(biggestX-LUx)+(biggestY-LUy)*(biggestY-LUx)){
                    RDx=coords[2*by_closeness[j]];
                    RDy=coords[2*by_closeness[j]+1];
                }
                if((biggestX-coords[2*by_closeness[j]])*(biggestX-coords[2*by_closeness[j]])+
                   coords[2*by_closeness[j]+1]*coords[2*by_closeness[j]+1]<
                   (biggestX-LUx)*(biggestX-LUx)+LUy*LUx){
                    RUx=coords[2*by_closeness[j]];
                    RUy=coords[2*by_closeness[j]+1];
                }
                if(coords[2*by_closeness[j]]*coords[2*by_closeness[j]]+
                   (biggestY-coords[2*by_closeness[j]+1])*(biggestY-coords[2*by_closeness[j]+1])<
                   LUx*LUx+(biggestY-LUy)*(biggestY-LUx)){
                    LDx=coords[2*by_closeness[j]];
                    LDy=coords[2*by_closeness[j]+1];
                }
                averageX+=coords[2*by_closeness[j]];
                averageY+=coords[2*by_closeness[j]+1];
            }
            averageX/=i-int_start;
            averageY/=i-int_start;

            unsigned long long longestX1,longestY1,longestX2,longestY2;
            if((RUx-LDx)*(RUx-LDx)+(RUy-LDy)*(RUy-LDy)<(LUx-RDx)*(LUx-RDx)+(LUy-RDy)*(LUy-RDy)){
                longestX1=RUx;
                longestY1=RUy;
                longestX2=LDx;
                longestY2=LDy;
            }else{
                longestX1=LUx;
                longestY1=RUy;
                longestX2=RDx;
                longestY2=RDy;
            }

            if((longestX1-averageX)*(longestX1-averageX)+(longestY1-averageY)*(longestY1-averageY)<
               (longestX2-averageX)*(longestX2-averageX)+(longestY2-averageY)*(longestY2-averageY)){
                start_pos[2*last_pl]=longestX1;
                start_pos[2*last_pl+1]=longestY1;
            }else{
                start_pos[2*last_pl]=longestX2;
                start_pos[2*last_pl+1]=longestY2;
            }

            last_pl=whose[by_closeness[i]];
            int_start=i;
        }
    };

    ofstream out;
    out.open("runners.out",ios::out);
    for(unsigned int i=0;i<k;i++){
        out<<start_pos[2*i]<<' '<<start_pos[2*i+1]<<'\n';
    }
    for(unsigned int i=0;i<n;i++){
        out<<whose[i]+1<<'\n';
    }
    out.close();
    return 0;
}