#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;

const int maxn=1e5+10;
const int maxk=1e5+10;
const int maxa=1e9+10;
const int max_speed_segments=10;
const int max_binary_iterations=20;
const int brute_lim=1000;
pdi speed[maxk];
int grp[maxk];
double max_speed,min_speed;
struct point{
    int x,y;

    point(){
        x=y=0;
    }
    point(int x,int y){
        this->x=x;
        this->y=y;
    }

    double dist(point b){
        return sqrt(((double)x-b.x)*((double)x-b.x)+((double)y-b.y)*((double)y-b.y));/// OVO MOZDA VRATITI NA DOUBLE
    }
    /*double sqdist(point b){
        return ((double)x-b.x)*((double)x-b.x)+((double)y-b.y)*((double)y-b.y);
    }*/

    void ispis(){
        printf("%d %d\n",x,y);
    }

}pts[maxn];
int n,k;

struct scaller{

    vector<int>a;

    scaller(){}
    scaller(vector<int>b){
        a=b;
        a.pb(-maxa*2+10);
        a.pb(maxa*2+10);
        sort(a.begin(),a.end());
        a.resize( unique(a.begin(),a.end())-a.begin() );
    }
    int get_scalled(int x){
        int pos=lower_bound(a.begin(),a.end(),x)-a.begin();
        if(a[pos]!=x)return -1;
        return pos+1;
    }
    int get_real(int x){
        return a[x-1];
    }
    int get_loweq(int x){

        int l=0;
        int r=a.size();
        int sr,ret=-1;
        while(l<=r){
            sr=(l+r)/2;
            if(a[sr]<=x){
                l=sr+1;
                ret=sr;
            }
            else r=sr-1;
        }
        return ret+1;
    }
    int get_higheq(int x){

        int l=0;
        int r=a.size();
        int sr,ret=-1;
        while(l<=r){
            sr=(l+r)/2;
            if(a[sr]>=x){
                r=sr-1;
                ret=sr;
            }
            else l=sr+1;
        }
        return ret+1;
    }
}x_scaler,y_scaler;

struct solution{

    vector<int>a;
    double score;

    void calc_score(){

        score=0;
        vector<int>prv(k,-1);
        for(int i=0;i<n;i++){

            int id=a[i];
            int p=prv[id];

            if(p==-1){}
            else score=score+pts[p].dist(pts[i])*speed[id].ff;

            prv[id]=i;
        }

    }

    solution(){score=2e18;}
    solution(vector<int>b){
        a=b;
        score=2e18;
        calc_score();
    }

    void ispis(){

        vector<point>begpt(k);

        ///printf("ISPAO %d\n",a.size());
        ///cout<<score<<endl;

        for(int i=0;i<n;i++){
            int id=a[i];
           /// printf("%d ID\n",id);
            if(begpt[id].x==0)
                begpt[id]=pts[i];
        }
        for(int i=0;i<k;i++){
            if(begpt[i].x==0){
                begpt[i].x=1;
                begpt[i].y=1;
            }
        }
        ///printf("ISPAO\n");
        for(int i=0;i<k;i++)
            begpt[i].ispis();
        ///printf("ISPAO\n");
        for(int i=0;i<n;i++)
            printf("%d ",a[i]+1);
        printf("\n");
    }

    bool operator <(const solution &s)const{
        return score<s.score;
    }

}rez;


bool srt_x(int a,int b){
    return (pts[a].x<pts[b].x)||(pts[a].x==pts[b].x && pts[a].y<pts[b].y);
}
bool srt_y(int a,int b){
    return (pts[a].y<pts[b].y)||(pts[a].y==pts[b].y && pts[a].x<pts[b].x);
}
struct seg_points{

    struct node{

        node *l,*r;
        int pid,sz,flag,runner_id;

        node(){
            l=r=NULL;
            pid=-1;
            sz=0;
            flag=0;
            runner_id=-1;
        }

    };
    typedef node* pnode;

    int sz(pnode x){
        if(x==NULL)return 0;
        return x->sz;
    }

    pnode root=NULL;
    int *pos;

    void build(pnode &x,int l,int r,vector<int>&v,int tip){

        if(l>r)return;
        if(x==NULL)x=new node();

        if(tip==0)sort( (&v[0])+l,(&v[0])+r+1, srt_x );
        else sort( (&v[0])+l,(&v[0])+r+1, srt_y );
        int mid=(l+r)/2;
        x->pid=v[mid];

        build(x->l,l,mid-1,v,tip^1);
        build(x->r,mid+1,r,v,tip^1);
    }
    void re_build(pnode &r,pnode x){
        if(x==NULL)return;
        r=new node();
        r->pid=x->pid;
        re_build(r->l,x->l);
        re_build(r->r,x->r);
    }

    seg_points(seg_points *p){
        if(p==NULL){
            vector<int>v(n);
            for(int i=0;i<n;i++)v[i]=i;
            build(root,0,n-1,v,0);
        }
        else{
            re_build(root,p->root);
        }
    }

    void upd1(pnode x,int px,int py,int val,int tip,bool invert){

        if(x==NULL){
            printf("Auf...\n");
            x->pid=1;
            return;
        }

        if(pts[x->pid].x==px && pts[x->pid].y==py){
            if(!invert){
                x->runner_id=val;
                x->flag=1;
                x->sz++;
            }
            else{
                x->runner_id=-1;
                x->flag=0;
                x->sz--;
            }
            return;
        }

        int qx=pts[x->pid].x;
        int qy=pts[x->pid].y;

        if(tip==0){
            if( (px<qx)||(px==qx && py<qy) )upd1(x->l,px,py,val,tip^1,invert);
            else upd1(x->r,px,py,val,tip^1,invert);
        }
        else{
            if( (py<qy)||(py==qy && px<qx) )upd1(x->l,px,py,val,tip^1,invert);
            else upd1(x->r,px,py,val,tip^1,invert);
        }

        x->sz=sz(x->l)+sz(x->r)+x->flag;

    }
    void update(int x,int y,int runner,bool invert){
        upd1(root,x,y,runner,0,invert);
    }

    void check(int x,int y,int &best,int qr){
        if(best==-1){
            best=qr;
            return;
        }

        int id1=pos[best];
        int id2=pos[qr];

        point f(x,y);

        double pom1=pts[id1].dist(f)*speed[best].ff;
        double pom2=pts[id2].dist(f)*speed[qr].ff;
        if(pom1>pom2)best=qr;
    }
    void qry(pnode x,int px,int py,int tip,int &best){

        if(x==NULL)return;
        if(x->sz==0)return;

        ///printf("%d | %d %d | %d %d\n",x->pid,pts[x->pid].x,pts[x->pid].y,px,py );

        int qx=pts[x->pid].x;
        int qy=pts[x->pid].y;

        if(x->flag)check(px,py,best,x->runner_id);

        pnode nxt_node;
        pnode other_node;

        if(tip==0){
            if( (px<qx)||(px==qx && py<qy) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }
        else{
            if( (py<qy)||(py==qy && px<qx) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }

        qry(nxt_node,px,py,tip^1,best);

        if(best==-1){
            qry(other_node,px,py,tip^1,best);
        }
        else{
            double d;
            if(tip==0){
                d=abs(pts[pos[best]].x-pts[x->pid].x);
            }
            else{
                d=abs(pts[pos[best]].y-pts[x->pid].y);
            }
            point pom(px,py);
            ///cout<<d<<" "<<pom.sqdist(pts[pos[best]])<<" "<<(pts[pos[best]].y-pts[x->pid].y)<<" "<<(pts[pos[best]].x-pts[x->pid].x)<<endl;
            if(d<pom.dist(pts[pos[best]]))qry(other_node,px,py,tip^1,best);
        }

    }
    int query(int x,int y){
        int ret=-1;
        qry(root,x,y,0,ret);
        return ret;
    }

    void check2(int x,int y,int &best,int qr){
        if(best==-1){
            best=qr;
            return;
        }

        int id1=best;
        int id2=qr;

        point f(x,y);

        double pom1=pts[id1].dist(f);
        double pom2=pts[id2].dist(f);
        if(pom1>pom2)best=qr;
    }
    void qry2(pnode x,int px,int py,int tip,int &best){

        if(x==NULL)return;
        if(x->sz==0)return;

        ///printf("%d | %d %d | %d %d\n",x->pid,pts[x->pid].x,pts[x->pid].y,px,py );

        int qx=pts[x->pid].x;
        int qy=pts[x->pid].y;

        if(x->flag)check2(px,py,best,x->pid);

        pnode nxt_node;
        pnode other_node;

        if(tip==0){
            if( (px<qx)||(px==qx && py<qy) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }
        else{
            if( (py<qy)||(py==qy && px<qx) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }

        qry2(nxt_node,px,py,tip^1,best);

        if(best==-1){
            qry2(other_node,px,py,tip^1,best);
        }
        else{
            double d;
            if(tip==0){
                d=abs(pts[best].x-pts[x->pid].x);
            }
            else{
                d=abs(pts[best].y-pts[x->pid].y);
            }
            point pom(px,py);
            ///cout<<d<<" "<<pom.sqdist(pts[pos[best]])<<" "<<(pts[pos[best]].y-pts[x->pid].y)<<" "<<(pts[pos[best]].x-pts[x->pid].x)<<endl;
            if(d<pom.dist(pts[best]))qry2(other_node,px,py,tip^1,best);
        }

    }
    int query2(int x,int y){
        int ret=-1;
        qry2(root,x,y,0,ret);
        return ret;
    }


     void check_max(int x,int y,int &best,int qr){
        if(best==-1){
            best=qr;
            return;
        }

        int id1=best;
        int id2=qr;

        point f(x,y);

        double pom1=pts[id1].dist(f);
        double pom2=pts[id2].dist(f);
        if(pom1<pom2)best=qr;
    }
    void max_qry(pnode x,int px,int py,int tip,int &best,bool onpath){

        if(x==NULL)return;
        if(x->sz==0)return;

        ///printf("%d | %d %d | %d %d\n",x->pid,pts[x->pid].x,pts[x->pid].y,px,py );

        int qx=pts[x->pid].x;
        int qy=pts[x->pid].y;

        if(x->flag)check_max(px,py,best,x->pid);

        pnode nxt_node;
        pnode other_node;

        if(tip==0){
            if( (px<qx)||(px==qx && py<qy) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }
        else{
            if( (py<qy)||(py==qy && px<qx) ){
                nxt_node=x->l;
                other_node=x->r;
            }
            else{
                nxt_node=x->r;
                other_node=x->l;
            }
        }
        swap(nxt_node,other_node);

        max_qry(nxt_node,px,py,tip^1,best,0);
        if(onpath || sz(nxt_node)==0)max_qry(other_node,px,py,tip^1,best,1);

        /*if(best==-1){
            qry(other_node,px,py,tip^1,best);
        }
        else{
            double d;
            if(tip==0)d= abs((ll)pts[pos[best]].x-pts[x->pid].x);
            else d= abs((ll)pts[pos[best]].y-pts[x->pid].y);
            point pom(px,py);
            if(d<pom.dist(pts[pos[best]]))qry(other_node,px,py,tip^1,best);
        }*/

    }
    int max_query(int x,int y){
        int ret=-1;
        max_qry(root,x,y,0,ret,1);
        return ret;
    }


    void go_reset(pnode x){
        if(x==NULL)return;
        x->flag=0;
        x->runner_id=-1;
        x->sz=0;
        go_reset(x->l);
        go_reset(x->r);
    }
    void reset(){
        go_reset(root);
    }

}*structure[max_speed_segments+1];


int get_grp(int runner){
    double d=(max_speed-min_speed)/max_speed_segments;
    return (int)( (speed[runner].ff-min_speed)/d );
}

void input(){

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

    scanf("%d %d",&n,&k);
    max_speed=0;
    min_speed=10;
    for(int i=0;i<k;i++){
        cin>>speed[i].ff;
        speed[i].ss=i;
        max_speed=max(max_speed,speed[i].ff);
        min_speed=min(min_speed,speed[i].ff);
    }
    ///sort(speed+1,speed+n+1);
    if(max_speed-min_speed<1)max_speed+=1;

    for(int i=0;i<n;i++){
        scanf("%d %d",&pts[i].x,&pts[i].y);
        ///if(i>0)cout<<pts[i].dist(pts[i-1])<<endl;
    }

}
void preprocess(){

    vector<int>xx,yy;
    for(int i=0;i<n;i++){
        xx.pb(pts[i].x);
        yy.pb(pts[i].y);
    }

    x_scaler=scaller(xx);
    y_scaler=scaller(yy);


    for(int i=0;i<k;i++)
        grp[i]=get_grp(i);

}

void calc_take(vector<int>&v){

    int prefix_lim=min(k,1);

    if(k<=10000)prefix_lim=k;

    int window=k*4;
    vector<pair<double,int> >cand;

    for(int i=0;i<n;i++){

        if(i>=prefix_lim){
            int ppom=structure[0]->query2(pts[i].x,pts[i].y);
            cand.pb({pts[ppom].dist(pts[i]),i});
        }
        else{
            v[i]=1;
        }


        if(i-window<0){}
        else{
            structure[0]->update(pts[i-window].x,pts[i-window].y,0,1);
        }
        structure[0]->update(pts[i].x,pts[i].y,0,0);
    }

    sort(cand.begin(),cand.end());
    for(int i=0;i<k-prefix_lim;i++){
        v[cand.back().ss]=1;
        cand.pop_back();
    }

    int c=0;
    for(int i=0;i<n;i++){
        if(v[i]){
            ///printf("%d %d \n",i,v[i]);
            c++;
        }
    }
    ///printf(" %d CCC\n",c);

}

solution go(){

    ///printf("OP\n");
    ///cout<<d<<"  QD"<<endl;

    for(int i=0;i<=max_speed_segments;i++){
        if(i==0)structure[i]=new seg_points(NULL);
        else structure[i]=new seg_points(structure[0]);
        ///structure[i]=new seg_points(NULL);
    }

    vector<pdi>pom_speed;
    for(int i=0;i<k;i++)pom_speed.pb(speed[i]);
    sort(pom_speed.begin(),pom_speed.end());


    vector<int>take(n,0);
    calc_take(take);
    for(int i=0;i<=max_speed_segments;i++)
        structure[i]->reset();


    int currk=0;
    vector<int>ret,prv(k,-1);
    for(int i=0;i<=max_speed_segments;i++)
        structure[i]->pos=(&prv[0]);

    /*for(int i=0;i<k;i++){
        prv[i]=i;
        ret.pb(i);
        structure[grp[i]]->update(pts[prv[i]].x,pts[prv[i]].y,i,0);
    }*/

    currk=0;
    for(int i=0;i<n;i++){

        if(take[i]){
            int id=pom_speed[currk].ss;
            structure[grp[id]]->update(pts[i].x,pts[i].y,id,0);
            prv[id]=i;
            ret.pb(id);
            currk++;
            continue;
        }


        vector<int>cand;
        if(currk>brute_lim){
            for(int j=0;j<=max_speed_segments;j++){
                ///cout<<d_new<<" "<<delta<<" "<<min_speed<<" "<<max_speed<<" newd"<<endl;
               /// printf("%d CC\n",j);
                int pom=structure[j]->query(pts[i].x,pts[i].y);
                if(pom!=-1)cand.pb(pom);
                ///printf("%d %d CC\n",j,pom);
            }
        }

        if(currk<=brute_lim){
            for(int j=0;j<currk;j++)cand.pb(pom_speed[j].ss);
        }


        int mink=-1;
        double mindist=1e18;
        for(int j=0;j<cand.size();j++){
            int id=cand[j];
            if(pts[prv[id]].dist(pts[i])*speed[id].ff<mindist){
                mindist=pts[prv[id]].dist(pts[i])*speed[id].ff;
                mink=id;
            }
        }

        structure[grp[mink]]->update(pts[prv[mink]].x,pts[prv[mink]].y,mink,1);
        prv[mink]=i;
        ret.pb(mink);
        structure[grp[mink]]->update(pts[prv[mink]].x,pts[prv[mink]].y,mink,0);


       /// printf("%d RET\n",ret.back());

    }
    ///printf("\n");

    solution r(ret);
    ///printf("OPALA\n");
   /// cout<<r.score<<endl;
    ///r.ispis();
    return r;

}

int main(){

    input();
    preprocess();

    rez=go();

    if(rez.a.size()==0)return 10;
    ///cout<<rez.score<<"  SCORE"<<endl;
    rez.ispis();

return 0;
}
/**

    posto razlika bude velika, mozes uzeti samo i brute najbrzih X i to je to

    probaj onu prvu ideju sa binarnom ali sa kd tree gde nadje najbrzeg u datom pravougaoniku
    ali ako nema vise ovih za postavljanje, samo nastavi dalje sa racunicom
    binarna da ne bude po udaljenosti nego po necemu drugom

    nesto na foru: treba izabrati najbolja mesta za ubacivanje novih, svako ubacivanje bi
    trebalo recimo biti na prvih najvecih K prelaza
    odredis te pozicije i onda ti ne treba binarna vise uopste
    za svaki point odredis koliki otp on moze prelaz velik da napravi heuristicki,
    i uzmes najvecik K prelaza


    probaj razlicite windowe

    probaj ipak onu binarnu kako radi u lokalu,testiraj sa ovim resenjem

*/