#include<iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#include <algorithm>
#include <time.h>
using namespace std;
class comp {
  public:
    pair<int, int> pt;
    int runnerId;
};

class runner {
  public:
    pair<int, int> firstPt;
    pair<int, int> lastPt;
    double skorost;
    double maxTime;
    long long maxDst;
    int id;
};

FILE* in;
FILE* out;

int n, k;
long long area;
long long totalSkorost;
runner runners[100001];
comp comps[100001];
string result_comps="";

long long getMaxDst(double skorost){
    return ceil((sqrt(area)*skorost/totalSkorost)*100.0)/100;
}

long long getDst(pair<int,int>pt1, pair<int,int>pt2){
    return ceil((sqrt((pt1.first - pt2.first)*(pt1.first - pt2.first)
    + (pt1.second - pt2.second)*(pt1.second - pt2.second)))*100.0)/100;
}

int main()
{
    ///in =stdin;
    ///out =stdout;

    in =fopen("runners.in","rt");
    out =fopen("runners.out","wt");
    fscanf(in,"%d %d\n",&n, &k);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    const clock_t TIME_LIMIT = (clock_t) (4.5* CLOCKS_PER_SEC);

    clock_t BEGIN_TIME;
    BEGIN_TIME = clock();

    int maxScorost=0,maxScorostNum;
    for (int i=0; i<k; i++) {
            double v;
            fscanf(in,"%lf\n",&v);
            runners[i].id=i;
            runners[i].skorost=ceil(v*100)/100;
            if (runners[i].skorost > maxScorost){
                maxScorost = runners[i].skorost;
                maxScorostNum = i;
            }
            totalSkorost += runners[i].skorost;
    }


    int x1=0,y1=0,x0=INT_MAX,y0=INT_MAX;
    for (int i=0; i<n; i++) {
        pair<int, int> curr;
        fscanf(in,"%d %d",&curr.first, &curr.second);

        if(curr.first<x0){
            x0=curr.first;
        }
        if(curr.first>x1){
            x1=curr.first;
        }
        if(curr.second<y0){
            y0=curr.second;
        }
        if(curr.second>y1){
            y1=curr.second;
        }

        comps[i].pt=curr;
        comps[i].runnerId = -1;
    }

    area=(x1-x0)*(y1-y0);

    int lastComp;
    int lastRunner=-1;
    //////
    /////

    for (int i=0; i<n; i++) {
        lastComp=i;
        bool found=false;
        long long minTm=LONG_MAX;
        for (int j=0; j<=lastRunner; j++){
            runners[j].maxDst=getMaxDst(runners[j].skorost);
            runners[j].maxTime=runners[j].maxDst/runners[j].skorost;
            long long dst=getDst(runners[j].lastPt, comps[i].pt);
            long long tm=ceil((dst/runners[j].skorost)*100.0)/100;
            if(tm<minTm){
                minTm=tm;
                comps[i].runnerId=j+1;
            }
            if(clock()-BEGIN_TIME>TIME_LIMIT)break;
        }

        if(minTm<=runners[comps[i].runnerId-1].maxTime){
            result_comps+=to_string(comps[i].runnerId)+"\n";
            runners[comps[i].runnerId-1].lastPt=comps[i].pt;
            found = true;
        }

        if(!found && lastRunner<k-1){
            runners[lastRunner+1].lastPt=comps[i].pt;
            runners[lastRunner+1].maxDst=getMaxDst(runners[lastRunner+1].skorost);
            fprintf(out,"%d %d\n",comps[i].pt.first,comps[i].pt.second);
            result_comps+=to_string(lastRunner+2)+"\n";
            lastRunner++;
        }
        if(lastRunner==k-1){
            break;
        }
        if(k-lastRunner==n-lastComp){
            break;
        }
        if(clock()-BEGIN_TIME>TIME_LIMIT){
            break;
        }
    }

    for(int i=lastRunner+1; i<k; i++){
            fprintf(out,"%d %d\n",comps[lastComp+1].pt.first,comps[lastComp+1].pt.second);
            result_comps+=to_string(i+1)+"\n";
            runners[i].lastPt=comps[lastComp+1].pt;
            if(lastComp<n-1 && i<k-1)lastComp++;
            lastRunner++;
    }

    for (int i=lastComp+1; i<n; i++) {
        lastComp=i;;
        long long minTm=LONG_MAX;
        for (int j=0; j<k; j++){
            long long dst=getDst(runners[j].lastPt, comps[i].pt);
            long long tm=ceil((dst/runners[j].skorost)*100.0)/100;
            if(tm<minTm){
                minTm=tm;
                comps[i].runnerId=j+1;
            }
            if(clock()-BEGIN_TIME>TIME_LIMIT)break;
        }

        if(comps[i].runnerId>0)
            runners[comps[i].runnerId-1].lastPt=comps[i].pt;
        //else
        //    comps[i].runnerId=maxScorostNum+1;

        result_comps+=to_string(comps[i].runnerId)+"\n";
        if(clock()-BEGIN_TIME>TIME_LIMIT)break;
    }

    for(int i=lastRunner+1; i<k; i++){
            fprintf(out,"%d %d\n",comps[lastComp+1].pt.first,comps[lastComp+1].pt.second);
            result_comps+=to_string(i+1)+"\n";
            if(lastComp<n-1 && i<k-1)lastComp++;
    }

    for(int i=lastComp+1; i<n; i++){
        if(comps[i].runnerId>0){
            result_comps+=to_string(comps[i].runnerId)+"\n";
        }
        else{
            result_comps+=to_string(maxScorostNum+1)+"\n";
        }
    }

    fprintf(out,"%s",result_comps.c_str());

    return 0;
}