#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <random>
#include <cmath>
#include <chrono>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>

#define NUMBER_OF_CLUSTERS_FOR_SLOW_SOLUTION 900

using namespace std;

int number_of_points, number_of_clusters;

const int INITIAL_CLUSTERS = 100;
const double TIME_LIMIT = 3000;


int random_number(int lo, int hi) {
	int dist = hi - lo + 1;
	if (RAND_MAX > dist) {
		return rand() % dist + lo;
	}
	if (RAND_MAX * RAND_MAX > dist) {
		return (rand() * rand()) % dist + lo;
	}
}

const double INF = 1e300;


double sqr(double x) {
	return x * x;
}

struct point {
	int x; int y;
};

double distanceF(double speed, point a, point b) {
	return speed * speed * (sqr(a.x - b.x) + sqr(a.y - b.y));
}

struct cluster {
	point position; // center of the cluster
	// the bigger the worse
	double speed;
	int starting_point_index;
};

point points[100000];
cluster clusters[100000];
int result_cluster_to_assign_a_point[100000];

double globalMinDistance = INF;

int minx = 1e9, miny = 1e9, maxx = 0, maxy = 0;

int main() {
	
	auto begin = chrono::steady_clock::now();

	freopen("runners.in", "r", stdin); freopen("runners.out", "w", stdout);

	cin >> number_of_points >> number_of_clusters;
	for (int i = 0; i < number_of_clusters; ++i) {
		cin >> clusters[i].speed;
	}

	for (int i = 0; i < number_of_points; ++i) {
		cin >> points[i].x >> points[i].y;
	}

	double total_distance_travelled = 0;
	uniform_int_distribution<int> random_point_generator(0, number_of_points - 1);
	if (number_of_clusters < NUMBER_OF_CLUSTERS_FOR_SLOW_SOLUTION) {

		// assign clusters starting point
		for (int i = 0; i < number_of_clusters; ++i) {
			int pointIdx = random_number(0, number_of_points - 1);
			clusters[i].starting_point_index = pointIdx;
			clusters[i].position = points[pointIdx];
		}

		for (int i = 0; i < number_of_points; ++i) {
			double mindist = INF;
			int cluster_index = -1;
			for (int j = 0; j < number_of_clusters; ++j) {
				cluster& cl = clusters[j];
				double distance = distanceF(cl.speed, cl.position, points[i]);
				if (mindist > distance) {
					mindist = distance;
					cluster_index = j;
				}
			}
			if (i < clusters[cluster_index].starting_point_index) {
				clusters[cluster_index].starting_point_index = i;
			}
			else {
				total_distance_travelled += mindist;
			}
			clusters[cluster_index].position = points[i];
			result_cluster_to_assign_a_point[i] = cluster_index;
		}

		for (int i = 0; i < number_of_clusters; ++i) {
			cout << points[clusters[i].starting_point_index].x
				<< ' ' << points[clusters[i].starting_point_index].y << endl;
		}
		for (int i = 0; i < number_of_points; ++i) {
			cout << result_cluster_to_assign_a_point[i] + 1 << endl;
		}
		return 0;
	}
	else {
		// assign clusters starting point
		for (int i = 0; i < number_of_clusters; ++i) {
			int pointIdx = random_number(0, number_of_points - 1);
			clusters[i].starting_point_index = pointIdx;
			clusters[i].position = points[pointIdx];
		}
		int accumClusterIdx = 0;
		for (int i = 0; i < number_of_points; ++i) {
			double mindist = INF;
			int cluster_index = -1;
			for (int j = 0; j < NUMBER_OF_CLUSTERS_FOR_SLOW_SOLUTION; ++j) {
				int clIdx = accumClusterIdx;
				accumClusterIdx = (accumClusterIdx + 1) % number_of_clusters;
				cluster& cl = clusters[clIdx];
				double distance = distanceF(cl.speed, cl.position, points[i]);
				if (mindist > distance) {
					mindist = distance;
					cluster_index = clIdx;
				}
			}
			if (i < clusters[cluster_index].starting_point_index) {
				clusters[cluster_index].starting_point_index = i;
			}
			else {
				total_distance_travelled += mindist;
			}
			clusters[cluster_index].position = points[i];
			result_cluster_to_assign_a_point[i] = cluster_index;
		}

		for (int i = 0; i < number_of_clusters; ++i) {
			cout << points[clusters[i].starting_point_index].x
				<< ' ' << points[clusters[i].starting_point_index].y << endl;
		}
		for (int i = 0; i < number_of_points; ++i) {
			cout << result_cluster_to_assign_a_point[i] + 1 << endl;
		}
		return 0;
	}
	return 0;
}