///kk to be reduced
#include<bits/stdc++.h>
#define endl '\n'
#define f first
#define s second
using namespace std;
typedef long long ll;
int n,k,nn;
int pos;
bool gfl;
int speeds;
int actual[100006];
int query[100006],tekcnt;
set <pair<ll,int>> x,y;
pair <int,int> positions[100006],initial[100006];
vector <pair<ll,ll>> tek;
pair <ll,ll>computers[100006];
double bestscore=DBL_MAX,score;
pair <double,int> raz[100006],speed[100006];
bool fl=0;
int uk=1,cnt;
int nachalni[100006];
int runners[100006],ans[100006];
int i,j,p,q,m;
ifstream fin("runners.in");
ofstream fout("runners.out");
clock_t T;
void input()
{
    cin>>n>>k;
    nn=n;
    for(i=0; i<k; i++)
        speed[i].s=i+1;
    for(i=0; i<k; i++)
        cin>>speed[i].f;
    for(i=1; i<=n; i++)
        cin>>computers[i].first>>computers[i].second;


    sort(speed,speed+k);
}
void finput()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    fin>>n>>k;
    nn=n;
    for(i=0; i<k; i++)
        speed[i].s=i+1;
    for(i=0; i<k; i++)
        fin>>speed[i].f;
    for(i=1; i<=n; i++)
        fin>>computers[i].first>>computers[i].second;

    sort(speed,speed+k);
}


void gen_perm()
{
    T=clock();
    if(cnt==1)
    {
        if(T>2500)
        {
            gfl=1;
            return ;
        }
    }
    pos++;
    cnt++;
    if(k>10000 && cnt==1)
        pos=k/2;
    else if(k>10000)
        pos=0;
    if(pos==k)
    {
        ///ne e zaduljitelno, moje da drupnem n edna poziciq nazad
        nn/=2;
        if(nn<2*k || k==1)
        {
            gfl=1;
            return;
        }
        pos=1;
    }
    // cout<<nn<<" "<<pos<<endl;
    for(i=1; i<=k-pos; i++)
        initial[i]=computers[i];
    for(i=1; i<=k-pos; i++)
        nachalni[i]=cnt;

    for(i=k-pos+1; i<=k; i++)
        initial[i]=computers[nn-(k-i)];
    for(i=k-pos+1; i<=k; i++)
        nachalni[nn-(k-i)]=cnt;

    for(i=0; i<k; i++)
        actual[i]=speed[i].second;
}
double calcc(pair <ll,ll> a,pair <ll,ll> b)
{
    double st = sqrt((long long)((a.f-b.f)*1ll*(a.f-b.f))+(long long)((a.s-b.s)*1ll*(a.s-b.s)));
    return st;
}
void foutput()
{
    //cout<<bestscore<<endl;
    for(i=1; i<=k; i++)
        fout<<positions[i].f<<" "<<positions[i].s<<endl;
    for(i=1; i<=n; i++)
        fout<<ans[i]<<endl;
}
int vr;
double mn = DBL_MAX;
void prv(int ind)
{
    double dist = calcc(tek[ind],computers[i])*speed[ind].first;
    //  cout<<dist<<" dist "<<endl;
    if(dist<mn)
    {
        mn=dist;
        vr=ind;
    }
}
void run_smaller()
{
    score=0.0;
    tek.clear();
    int ch=0;
    for(i=1; i<=n; i++)
    {
        T=clock();
        if(T>4700)
        {
            gfl=1;
            return ;
        }
        //  cout<<i<<" i "<<endl;
        ///num to be removed completely
        if(nachalni[i]==cnt)
        {
            runners[i]=ch;
            tek.push_back(computers[i]);

            ch++;
            continue;
        }
        
        int Rbound = tek.size()-1;
        if(cnt==1 && T>4300)
        	Rbound=min(Rbound,10);
        mn = DBL_MAX;
        for(j=0;j<=Rbound;j++)
        {
            double dist = calcc(tek[j],computers[i])*speed[j].first;
            //  cout<<dist<<" dist "<<endl;
            if(dist<mn)
            {
                mn=dist;
                vr=j;
            }
        }
        // cout<<"Runner "<<vr<<" will fix the "<<i<<" computer"<<" "<<mn<<endl;
        runners[i]=vr;
        score+=mn;
        tek[vr]=computers[i];
    }

}
void check_smaller()
{
    //cout<<score<<" score "<<endl;
    if(bestscore>score)
    {
        bestscore=score;
        //   cout<<ans[i]<<" "<<runners[i]<<" "<<actual[runners[i]]<<endl;
        for(i=1; i<=n; i++)
        {
            // cout<<i<<" "<<runners[i]<<" "<<actual[runners[i]]<<endl;
            ans[i]=actual[runners[i]];
        }
        for(i=1; i<=k; i++)
        {
            positions[actual[i-1]]=initial[i];
        }
    }
}
void output()
{
    cout<<bestscore<<endl;
    for(i=1; i<=k; i++)
        cout<<positions[i].f<<" "<<positions[i].s<<endl;
    for(i=1; i<=n; i++)
        cout<<ans[i]<<endl;
}

void run()
{
    speeds=0;
    score=0.0;
    tek.clear();
    int ch=0;
    x.clear();
    y.clear();
    for(i=1; i<=n; i++)
    {
        //cout<<i<<endl;
        if(nachalni[i]==cnt)
        {
            speeds++;
            x.insert({computers[i].f,ch});
            y.insert({computers[i].s,ch});
            runners[i]=ch;
            tek.push_back(computers[i]);
            ch++;
            continue;
        }
        T=clock();
        mn = DBL_MAX;
        if(T>=4700)
        {
            gfl=1;
            return ;
        }
        int br=0;
        ///za x
        tekcnt++;
        auto pos=x.lower_bound({computers[i].f,1});
        int lst=0;

        int obshto=70;
        if(k>=10000)obshto=100;
        if(cnt==1 && T>3500)
            obshto=50;
        for(auto it=pos; it!=x.end() && br<obshto; it++,br++)
        {
            auto p=*it;
            //num.push_back(p.second);
            prv(p.second);
            lst=p.first;
            query[p.second]=tekcnt;
        }
        for(auto it=pos; it!=x.begin() && br<2*obshto; it--,br++)
        {

            auto p=*it;
            if(query[p.second]==tekcnt)continue;
            //num.push_back(p.second);
            prv(p.second);
            query[p.second]=tekcnt;
        }
        auto itt = x.lower_bound({lst,1});
        for(auto it=itt; it!=x.end() && br<2*obshto; it++,br++)
        {
            auto p=*it;
            if(query[p.second]==tekcnt)continue;
            //num.push_back(p.second);
            prv(p.second);
            query[p.second]=tekcnt;
        }


        ///za y
        pos=y.lower_bound({computers[i].s,1});
        for(auto it=pos; it!=y.end() && br<3*obshto; it++,br++)
        {
            auto p=*it;
            lst=p.first;
            if(query[p.second]==tekcnt)continue;
            //num.push_back(p.second);
            prv(p.second);
            query[p.second]=tekcnt;
        }
        for(auto it=pos; it!=y.begin() && br<4*obshto; it--,br++)
        {

            auto p=*it;
            if(query[p.second]==tekcnt)continue;
            //num.push_back(p.second);
            prv(p.second);
            query[p.second]=tekcnt;
        }
        itt=y.lower_bound({lst,1});
        for(auto it=itt; it!=y.end() && br<4*obshto; it++,br++)
        {
            auto p=*it;
            if(query[p.second]==tekcnt)continue;
           // num.push_back(p.second);
            prv(p.second);
            query[p.second]=tekcnt;
        }
        ///da se napravri erase funkciq i add na novite koordinati

        int kk=50;
        int mnn=min(speeds,kk);
        for(j=0;j<mnn;j++)
        {
            if(query[j]!=tekcnt)
                prv(j);
        }

        ///tuka sum propusnal da napravq
        score+=mn;
        // cout<<"Runner "<<vr<<" will fix the "<<i<<" computer"<<" "<<mn<<endl;
        runners[i]=vr;

        x.erase({tek[vr].f,vr});
        y.erase({tek[vr].s,vr});

        tek[vr]=computers[i];

        x.insert({tek[vr].f,vr});
        y.insert({tek[vr].s,vr});

    }

}
void check()
{

    for(i=1; i<=n; i++)
    {
        // cout<<i<<" "<<runners[i]<<" "<<actual[runners[i]]<<endl;
        ans[i]=actual[runners[i]];
    }
    for(i=1; i<=k; i++)
    {
        positions[actual[i-1]]=initial[i];
    }
}


void solve()
{
    score=0.0;
    pos=-1;
    while(1)
    {
        gen_perm();
        if(gfl)
            return ;
        run();
        if(gfl)
            return ;
        check_smaller();
        // cout<<endl;
    }
}
void solve_smaller()
{
    score=0.0;
    pos=-1;
    while(1)
    {
        gen_perm();
        if(gfl)
            return ;
        run_smaller();
        if(gfl)
            return ;
        check_smaller();
        // cout<<endl;
    }
}
int main()
{
    //input();
    finput();
    if(k>1000)
        solve();
    else solve_smaller();
    //output();
    foutput();
    return 0;
}
/**
10 1
1.5
1 10
2 9
23 17
5 6
9 12
170 83
247 23
3 4
7 2
9 1

5 1
1.300000
3 8
6 7
9 4
10 2
1 5

5 2
1.3
1.8
3 8
6 7
9 4
10 2
1 5
*/