#include <bits/stdc++.h>
using namespace std;
int n, k;
struct nesto{
    double rast;
    int broj;
};
nesto najkrace;
int resenje[100005];

struct slog{
    long long x;
    long long y;
    bool status;
};
slog comp[100005];
slog runneri_ispis[100005];

struct runneriii{
    long long x;
    long long y;
    float speed;
    float broj;
};
runneriii popravljac[100005]; 

float niz_speed[100005];
map <float, int> speed;
map<float ,int>::iterator it;
float Eps = 0.0000001;

bool cmp(float r, float s){
    if(abs(r-s)<Eps) return 1;
    if(r<s) return 0;
    return 1;
}
/*void input(){
    fstream file;
    file.open("runners.in", ios::in);
    file >> n >> k;
    float a=0;
    for(int i=1;i<=k;i++){
        file >> a;
        niz_speed[i]=a;
        speed[a]=i;
    }
    for(int i=1;i<=n;i++){
        file >> comp[i].x >> comp[i].y;
        comp[i].status=0;
       // comp[i].br=i;
    }
    file.close();
    sort(niz_speed+1,niz_speed+k+1,cmp);

}*/
void input(){
    fstream file;
    file.open("runners.in", ios::in);
    file >> n >> k;
    double a=0;
    //int m;
    //float c;
    speed[12]=1e9;
    for(int i=1;i<=k;i++){
        //cout <<"i: "<< i << endl;
        file >> a;
        while(speed.find(a)!=speed.end()){
            a=a+Eps;
            //niz_speed[i]=a;
            //cout << i <<" " <<  a << endl;
            //cout << a <<" " <<  speed.size() << endl;
        }
        niz_speed[i]=a;
        speed[a]=i;
        for (it=speed.begin(); it!= speed.end(); ++it){
        cout << it->first << " => " << it->second << '\n';
        }
    }
    for(int i=1;i<=n;i++){
        file >> comp[i].x >> comp[i].y;
        comp[i].status=0;
       // comp[i].br=i;
    }
    file.close();
    for(int i=1;i<=k;i++){
        //cout << i << " "<<niz_speed[i] <<endl;
    }
    sort(niz_speed+1,niz_speed+k+1,cmp);
    for(int i=1;i<=k;i++){
        //cout << speed[niz_speed[i]] <<endl;
    }

}

float rastojanje(slog b, slog c){
    float a=sqrt(abs(b.x-c.x)*abs(b.x-c.x)+abs(b.y-c.y)*abs(b.y-c.y));
    cout << setprecision(6) << fixed;
    return a;
}

void ispis(){
    fstream file;
    file.open("runners.out", ios::out);
    for(int i=1;i<=k;i++){
        file << runneri_ispis[i].x << " " <<  runneri_ispis[i].y << endl;
    }
    for(int i=1;i<=n;i++){
        file << resenje[i] << endl;
    }
    file.close();
    
}

void opc1_K_100(){
    int con=560;
    int brojac_potrosenih_runnera=1;

    resenje[1]=speed[niz_speed[brojac_potrosenih_runnera]];
    runneri_ispis[1].x=comp[1].x;
    runneri_ispis[1].y=comp[1].y;

    for(int i=1;i<n;i++){
        if(comp[i+1].status==0){
            najkrace.rast=2e9;
            for(int j=i+1;j<=n and j<=(i+con);j++){
                if(comp[j].status==0){
                    if(rastojanje(comp[i],comp[j])<najkrace.rast){
                        najkrace.broj=j;
                        najkrace.rast=rastojanje(comp[i],comp[j]);
                    }
                }
            }
            if(n-i<=k-brojac_potrosenih_runnera){
                resenje[najkrace.broj]=speed[niz_speed[brojac_potrosenih_runnera]];
                brojac_potrosenih_runnera++;
                runneri_ispis[brojac_potrosenih_runnera].x=comp[i+1].x;
                runneri_ispis[brojac_potrosenih_runnera].y=comp[i+1].y;
                comp[najkrace.broj].status=1;     
                resenje[i+1]=speed[niz_speed[brojac_potrosenih_runnera]];
            }
            else if(najkrace.broj==i+1) resenje[i+1]=speed[niz_speed[brojac_potrosenih_runnera]];
            else{
                if(brojac_potrosenih_runnera<k){
                    resenje[najkrace.broj]=speed[niz_speed[brojac_potrosenih_runnera]];
                    brojac_potrosenih_runnera++;
                    runneri_ispis[brojac_potrosenih_runnera].x=comp[i+1].x;
                    runneri_ispis[brojac_potrosenih_runnera].y=comp[i+1].y;
                    comp[najkrace.broj].status=1;
                }
                resenje[i+1]=speed[niz_speed[brojac_potrosenih_runnera]];
            }
        }
        /*for(int i=1;i<=n;i++){
            cout << resenje[i] << " ";
        }
        cout << endl;*/
    }

    ispis();
}

// runner, gde treba stici, gde sam sad
double vreme(runneriii r1,int i, int j){
    slog komp;
    komp.x=r1.x;
    komp.y=r1.y;
    double vr=rastojanje(comp[j], komp)/r1.speed;
    cout << setprecision(6) << fixed;
    return vr;
}


void opc2_K__100(){
    //input();
    for(int i=1;i<=k;i++){
        popravljac[i].x=comp[i].x;
        popravljac[i].y=comp[i].y;
        popravljac[i].speed=niz_speed[i];
        popravljac[i].broj=speed[niz_speed[i]];
        resenje[i]=popravljac[i].broj;
       // cout << resenje[i] << endl;
        runneri_ispis[i].x=popravljac[i].x;
        runneri_ispis[i].y=popravljac[i].y;
        
    }

    nesto vr;
    int con=100;
    for(int i=k+1;i<=n;i++){
        vr.rast=1e25;
        for(int j=1;j<=con and j<=k;j++){
            // runner, gde treba stici, gde sam sad
            if(vreme(popravljac[j],i,j)<vr.rast){
                vr.rast=vreme(popravljac[j],i,j);
                vr.broj=popravljac[j].broj;
            }
            resenje[i]=vr.broj;
            popravljac[resenje[i]].x=comp[i].x;
            popravljac[resenje[i]].y=comp[i].y;
        }
    }
    fstream file;
    file.open("runners.out",ios::out);
    for(int i=1;i<=k;i++){
        file << runneri_ispis[i].x << " " << runneri_ispis[i].y << endl;
    }
    for(int i=1;i<=n;i++){
        file << resenje[i] << endl;
    }
    file.close();


}


int main(){
    input(); 
    int con=900;
    /*if(k<1000){
        opc1_K_100();
    }
    else*/
    opc1_K_100();
    return 0;
}