#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const double TIME_LIMIT = 4.9;
const double INF = 1e18;
const clock_t START_T = clock();

double time_running(){
    return (double)(clock() - START_T) / CLOCKS_PER_SEC;
}

inline LL sqr(LL x){
    return x*x;
}

struct Point {
    int x = 0, y = 0;

    double distance_to(const Point& p) const {
        return sqrt(sqr(x - p.x) + sqr(y - p.y));
    }
};

struct Runner {
    int id;
    double speed;
    Point pos;

    double calc_time(const Point& pc){
        return speed * pos.distance_to(pc);
    }

    bool operator < (const Runner& other) const {
        return speed < other.speed;
    }
};

struct QuadTree {
    struct Node {
        int left, right, top, bottom;
        Node* children[2][2] = {{nullptr, nullptr}, {nullptr, nullptr}};
        map<double, map<int, Runner>> runners;
        Node(int left, int right, int top, int bottom){
            this->left = left;
            this->right = right;
            this->top = top;
            this->bottom = bottom;
        }
    };

    Node* head;

    QuadTree(int left, int right, int top, int bottom){
        head = new Node(left, right, top, bottom);
    }

    void insert(const Runner runner, Node& cur){
//        cout << "Inserting runnner " << runner.id << " in quadrant " << cur.left << ' ' << cur.right << ' ' << cur.top << ' ' << cur.bottom << endl;
        if (cur.runners.empty() || cur.left == cur.right && cur.top == cur.bottom){
            cur.runners[runner.speed][runner.id] = runner;
            return;
        }
        int mh = (cur.left + cur.right) / 2;
        int mv = (cur.top + cur.bottom) / 2;
        V<Runner> q = {runner};
        if (cur.children[0][0] == nullptr){
            assert(SZ(cur.runners) == 1);
            assert(SZ(cur.runners.begin()->second) == 1);
            q.push_back(cur.runners.begin()->second.begin()->second);
            cur.children[0][0] = new Node(cur.left, mh, cur.top, mv);
            cur.children[0][1] = new Node(mh+1, cur.right, cur.top, mv);
            cur.children[1][0] = new Node(cur.left, mh, mv+1, cur.bottom);
            cur.children[1][1] = new Node(mh+1, cur.right, mv+1, cur.bottom);
        }
        cur.runners[runner.speed][runner.id] = runner;
        for(auto r: q){
            if (r.pos.x <= mh && r.pos.y <= mv){
                insert(r, *cur.children[0][0]);
                continue;
            }
            if (r.pos.y <= mv){
                insert(r, *cur.children[0][1]);
                continue;
            }
            if (r.pos.x <= mh){
                insert(r, *cur.children[1][0]);
                continue;
            }
            insert(r, *cur.children[1][1]);
        }
    }

    void remove(const Runner runner, Node& cur){
        if (cur.children[0][0] != nullptr){
            int mh = (cur.left + cur.right) / 2;
            int mv = (cur.top + cur.bottom) / 2;
            if (runner.pos.x <= mh && runner.pos.y <= mv)
                remove(runner, *cur.children[0][0]);
            else if (runner.pos.y <= mv)
                remove(runner, *cur.children[0][1]);
            else if (runner.pos.x <= mh)
                remove(runner, *cur.children[1][0]);
            else
                remove(runner, *cur.children[1][1]);

        }
//        cout << "Removing runnner " << runner.id << " in quadrant " << cur.left << ' ' << cur.right << ' ' << cur.top << ' ' << cur.bottom << endl;
        cur.runners[runner.speed].erase(runner.id);
        if (cur.runners[runner.speed].empty())
            cur.runners.erase(runner.speed);
        if (cur.runners.empty()){
            FORI(i,0,2){
                FORI(j,0,2){
                    delete cur.children[i][j];
                    cur.children[i][j] = nullptr;
                }
            }
        }
    }

    Runner search_closest(const Point& p, Node& cur){
//        cout << "Search in quadrant " << cur.left << ' ' << cur.right << ' ' << cur.top << ' ' << cur.bottom << endl;
        auto closest_runner = cur.runners.begin()->second.begin()->second;
        if (cur.children[0][0] == nullptr){
            return closest_runner;
        }
        int mh = (cur.left + cur.right) / 2;
        int mv = (cur.top + cur.bottom) / 2;
        if (p.x <= mh && p.y <= mv)
            return cur.children[0][0]->runners.empty() ? closest_runner : search_closest(p, *cur.children[0][0]);
        if (p.y <= mv)
            return cur.children[0][1]->runners.empty() ? closest_runner : search_closest(p, *cur.children[0][1]);
        if (p.x <= mh)
            return cur.children[1][0]->runners.empty() ? closest_runner : search_closest(p, *cur.children[1][0]);
        return cur.children[1][1]->runners.empty() ? closest_runner : search_closest(p, *cur.children[1][1]);
    }

    Runner search_fastest(const Point& p, Node& cur){
//        cout << "Search in quadrant " << cur.left << ' ' << cur.right << ' ' << cur.top << ' ' << cur.bottom << endl;
        auto fastest_runner = cur.runners.begin()->second.begin()->second;
        if (cur.children[0][0] == nullptr){
            return fastest_runner;
        }
        int mh = (cur.left + cur.right) / 2;
        int mv = (cur.top + cur.bottom) / 2;
        if (p.x <= mh && p.y <= mv)
            return cur.children[0][0]->runners.empty() || cur.children[0][0]->runners.begin()->first > 2 * fastest_runner.speed ? fastest_runner : search_fastest(p, *cur.children[0][0]);
        if (p.y <= mv)
            return cur.children[0][1]->runners.empty() || cur.children[0][1]->runners.begin()->first > 2 * fastest_runner.speed ? fastest_runner : search_fastest(p, *cur.children[0][1]);
        if (p.x <= mh)
            return cur.children[1][0]->runners.empty() || cur.children[1][0]->runners.begin()->first > 2 * fastest_runner.speed ? fastest_runner : search_fastest(p, *cur.children[1][0]);
        return cur.children[1][1]->runners.empty() || cur.children[1][1]->runners.begin()->first > 2 * fastest_runner.speed ? fastest_runner : search_fastest(p, *cur.children[1][1]);
    }
};

int main(){
    ifstream cin("runners.in");
    ofstream cout("runners.out");
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int n, k;
    cin >> n >> k;
//    assert(n == 1e5 && k <= n);
    V<Runner> runners(k);
    FORI(i,0,k){
        cin >> runners[i].speed;
        runners[i].id = i;
    }
    V<Point> pc(n);
    // todo: assign runners to clusters of points
    FORI(i,0,n){
        cin >> pc[i].x >> pc[i].y;
        if (i < k){
            runners[i].pos = pc[i];
        }
    }
    auto hall = QuadTree(1, 1e9, 1, 1e9);
    FORI(i,0,k){
        cout << runners[i].pos.x << ' ' << runners[i].pos.y << '\n';
        if (k > 1e4)
            hall.insert(runners[i], *hall.head);
    }
    FORI(i,0,k){
        cout << i+1 << '\n';
    }
    if (k <= 1e4)
        sort(ALL(runners));
    FORI(i,k,n){
        if (k > 1e4){
            auto runner = hall.search_fastest(pc[i], *hall.head);
            cout << runner.id+1 << '\n';
            hall.remove(runner, *hall.head);
            runner.pos = pc[i];
            hall.insert(runner, *hall.head);
        }
        else {
            double min_time = INF;
            int best_runner = -1;
            FORI(r,0,min(1000, k)){
                double time = runners[r].calc_time(pc[i]);
                if (time < min_time){
                    min_time = time;
                    best_runner = r;
                }
            }
            assert(best_runner >= 0);
            cout << runners[best_runner].id+1 << '\n';
            runners[best_runner].pos = pc[i];
        }
    }

    cin.close();
    cout.close();
    cerr << "Runtime: " << fixed << time_running() << endl;
    return 0;
}