#include<bits/stdc++.h>
using namespace std;

int const MAXN=1000001;
int n, k, ans[MAXN];

struct edge
{
    int x, y, idx;
};

edge a[MAXN];

bool cmp(edge i, edge j)
{
    if(i.x == j.x) return i.y < j.y;
    else return i.x < j.y;
}

void read()
{
    double s, minn = 100.0;
    int x, y, dot;
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>s;
        if(minn > s)
        {
            minn = s;
            dot = i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].idx = i;
    }
    sort(a+1, a+n+1, cmp);
    int pos = 1;
    for(int i=1;i<k;i++)
    {
        if(pos == dot)
        {
            pos++;
        }
        ans[a[i].idx] = pos;
        pos++;
    }
    ans[a[k].idx] = dot;
    for(int i=k+1;i<=n;i++)
    {
        ans[a[i].idx] = dot;
    }
    for(int i=1;i<dot;i++)
    {
        cout<<a[i].x<<" "<<a[i].y<<endl;
    }
    for(int i=dot+1;i<=k;i++)
    {
        cout<<a[i].x<<" "<<a[i].y<<endl;
    }
    cout<<a[dot].x<<" "<<a[dot].y<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
}

int main()
{
    freopen("runners.in", "r", stdin);
    freopen("runners.out", "w", stdout);
    read();
	return 0;
}