#include<bits/stdc++.h>
using namespace std;
double dist(long long x,long long y,long long x1,long long y1) {
    x-=x1;
    y-=y1;
    double c=x*x+y*y;
    return sqrt(c);
}
int main() {
    freopen("runners.in","r",stdin);
    freopen("runners.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,k;
    cin>>n>>k;
    if(k<=1000) {
        double s[k+1];
        for(int i=1; i<=k; i++)cin>>s[i];
        pair<long long,long long>curind[k+1];
        for(int i=1; i<=k; i++)curind[i]= {-1,-1};
        vector<int>ans(n);
        pair<int,int>beg[k+1];
        for(int i=0; i<n; i++) {
            long long x,y;
            cin>>x>>y;
            double minans=1e14;
            int minind=-1;
            for(int j=1; j<=k; j++) {
                if(curind[j].first==-1 && (minind==-1 || s[minind]<s[j] || minans>0)) {
                    minans=0;
                    minind=j;
                    break;
                } else if(curind[j].first!=-1 && dist(curind[j].first,curind[j].second,x,y)*s[j]<minans) {
                    minans=dist(curind[j].first,curind[j].second,x,y)*s[j];
                    minind=j;
                }
            }
            if(curind[minind].first==-1)beg[minind]= {x,y};
            ans[i]=minind;
            curind[minind]= {x,y};
        }
        for(int i=1; i<=k; i++) {
            if(beg[i].first==-1) {
                beg[i]= {3,3};
            }
            cout<<beg[i].first<<' '<<beg[i].second<<'\n';
        }
        for(int j:ans)cout<<j<<'\n';
    } else {
        double s[k+1];
        for(int i=1; i<=k; i++)cin>>s[i];
        int cnt=sqrt(k);
        pair<int,int>first[k+1];
        int ans[n];
        for(int i=1; i<=k; i++)first[i]= {-1,-1};
        vector<int>extra;
        vector<int>used(k+1,0);
        int num=(1000000000+cnt-1)/cnt;
        vector<pair<int,int> >what;
        for(int i=0; i<n; i++) {
            int x,y;
            cin>>x>>y;
            what.push_back({x,y});
            int cur=1+cnt*(x/num)+(y/num);
            if(used[cur]==0) {
                used[cur]=1;
                first[cur]= {x,y};
                ans[i]=cur;
            } else {extra.push_back(i);ans[i]=cur;}
        }
        for(int i=1; i<=k; i++) {
            if(first[i].first<=0) {
                if(extra.size()>0) {
                    int ind=extra.back();
                    extra.pop_back();
                    ans[ind]=i;
                    cout<<what[i].first<<' '<<what[i].second<<'\n';
                } else cout<<500000000<<' '<<500000000<<'\n';
            } else cout<<first[i].first<<' '<<first[i].second<<'\n';
        }
        for(int i=0; i<n; i++)cout<<ans[i]<<'\n';
    }
    return 0;
}
/**
5 2
3
3
3 354
32 2
345 2
239 298
2 1
*/