#include <bits/stdc++.h>
using namespace std;
int n,k,poc[100005];
struct slog1{
    float s;
    long long x,y;
}runner[100005];
struct slog2{
    long long x,y,ID;
}pc[100005];

void input(){
    scanf("%d%d", &n, &k);
    for(int i=1;i<=k;i++){
        scanf("%f", &runner[i].s);
        runner[i].s*=runner[i].s;
    }
    for(int i=1;i<=n;i++){
        scanf("%lld%lld", &pc[i].x, &pc[i].y);
        pc[i].ID=i;
    }
}

bool cmp1(slog2 a, slog2 b){
    return a.ID<b.ID;
}

bool cmp2(slog2 a, slog2 b){
    if((a.x<b.x) or (a.x==b.x and a.y<b.y))return true;
    return false;
}

bool cmp3(slog1 a, slog1 b){
    return a.s>b.s;
}

float dist(long long x1, long long y1, long long x2, long long y2){
    long long X=(x1-x2)*(x1-x2);
    long long Y=(y1-y2)*(y1-y2);
    return (X*1.0+Y*1.0);
}

void postavi_runnere(){
    //cout<<"poostavlkja r aneere"<<endl;
    sort(pc+1,pc+n+1,cmp2);
    //cout<<"sort1"<<endl;
    sort(pc+1,pc+1+(n/2),cmp1);
    //cout<<"sort2"<<endl;
    for(int i=1;i<=(k/2);i++){
        runner[i].x=pc[i].x;
        runner[i].y=pc[i].y;
        poc[pc[i].ID]=i;
    }
    //cout<<"petlja 1"<<endl;
    //cout<<n<<endl;
    sort(pc+(n/2)+2,pc+n+1,cmp1);
    //cout<<"SORT"<<endl;
    for(int i=(n/2)+1,j=1;j<=(k/2)+(k%2);j++,i++){
        //cout<<i<<endl;
        runner[(k/2)+j].x=pc[i].x;
        runner[(k/2)+j].y=pc[i].y;
        poc[pc[i].ID]=(k/2)+j;
    }
    //cout<<"petlja2"<<endl;
//    for(int i=1,j=n;i<=k;i++){
//        if(i<=(k/2)){
//            runner[i].x=pc[i].x;
//            runner[i].y=pc[i].y;
//            continue;
//        }
//        runner[i].x=pc[j].x;
//        runner[i].y=pc[j].y;
//        j--;
//    }
    sort(pc+1,pc+n+1,cmp1);
    //cout<<"kraj"<<endl;
}

void solve(){
    postavi_runnere();
    for(int i=1;i<=k;i++){
        //cout<<runner[i].x<<" "<<runner[i].y<<endl;
        printf("%lld %lld\n",runner[i].x,runner[i].y);
    }
    for(int i=1;i<=n;i++){
        int id=1;
        float trens = runner[1].s*dist(runner[1].x,runner[1].y,pc[i].x,pc[i].y);
        for(int j=2;j<=k;j++){
            if((runner[j].s*dist(runner[j].x,runner[j].y,pc[i].x,pc[i].y))<trens){
                trens=(runner[j].s*dist(runner[j].x,runner[j].y,pc[i].x,pc[i].y));
                id=j;
            }
        }
        runner[id].x=pc[i].x;
        runner[id].y=pc[i].y;
        //cout<<id<<endl;
        printf("%d\n",id);
    }
}

void solve2(){
    postavi_runnere();
    //cout<<"postaviranere"<<endl;
    for(int i=1;i<=k;i++){
        //cout<<runner[i].x<<" "<<runner[i].y<<endl;
        printf("%lld %lld\n",runner[i].x,runner[i].y);
    }
    for(int i=1;i<=n;i++){
        if(poc[i])printf("%d\n",poc[i]);
        else{
            int id=1;
            float trens = runner[1].s*dist(runner[1].x,runner[1].y,pc[i].x,pc[i].y);
            for(int j=2;j<=1000;j++){
                if((runner[j].s*dist(runner[j].x,runner[j].y,pc[i].x,pc[i].y))<trens){
                    trens=(runner[j].s*dist(runner[j].x,runner[j].y,pc[i].x,pc[i].y));
                    id=j;
                }
            }
            runner[id].x=pc[i].x;
            runner[id].y=pc[i].y;
            //cout<<id<<endl;
            printf("%d\n",id);
        }
    }
}

int main(){
    freopen("runners.in","r",stdin);
    freopen("runners.out","w",stdout);
    input();
    if(k<=1000){
        solve();
    }
    else{
        solve2();
    }

return 0;}