#include <bits/stdc++.h>
#define _nhatminh  int main()
#define ll long long
#define str string
#define fir first
#define sec second
#define ld long double
#define pb push_back
#define MOD 100000009
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
#define ALL(x) (x).begin(),(x).end()
#define piint pair < int , int >
#define piL pair < int , ll>
#define pLL pair < ll , ll >
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
using namespace std;
const int Max_n=1000;
// int x ;
// piint id[5 + 3 ] ;
int tinh_eculid (int x , int y , int x1 , int y1) {
	return sqrt ( ( x - x1) * ( x - x1) + ( y - y1 ) * ( y - y1 ) ) ;  
}
int x[Max_n+3] ;
int res = -1e9 ; 
std::vector<int > ans ;
	int n ; int m ;
	struct phandinhphongxa
	 {
	 	int x , y ;
	 }; 
	 phandinhphongxa a[Max_n+3];
		vector < piint > id[6] ;
	int kt[5+1] ;
void TRY ( int i ,int dem ) {
	if ( i > n ){
		// id[0] = id[1] = id[2] = id[3] = id[4] = id[5] = {-1e7 , -1e7 } ;
		
		int min_euclid = 1e9 ;
		// vector < int > result ;
		// int dem = 0 ;
		if ( dem < m ) return ; 
		for (int i = 1 ; i <= n ; i ++ )
		{
			// result.pb(x[i]) ;
			if (!id[x[i]].empty()) {
				for (int j = 0 ; j < (int)id[x[i]].size() ; j ++)
				min_euclid = min ( min_euclid , tinh_eculid ( a[i].x , a[i].y , id[x[i]][j].fir , id[x[i]][j].sec) ) ;
			}
			id[x[i]].pb(make_pair( a[i].x , a[i].y) );
		}
		for (int i = 1 ;i <= m ; i ++ ) {
			id[i].clear() ; 
		}
		if ( dem < m ){
			return ;
		}
		if ( min_euclid > res ){ 
			res = min_euclid ; 
			ans.clear() ;
			for (int i = 1 ; i <= n ; i ++ ) ans.pb(x[i]);
		}
		return ;
	}
	for (int j = 1 ; j <= m ; j ++){
		x[i] = j ;
		kt[j]++;
		int new_dem = dem ; 
		if ( kt[j] == 1 ) new_dem ++ ;
		TRY ( i + 1 ,new_dem) ; 
		kt[j]--;
	}
}
void sub1(){
	TRY(1, 0 ) ;
	for (int i = 0 ; i < ans.size() ; i ++){
		cout << ans[i] << ' '; 
	}
}
// int b[Max_n+3] ;
void sub2(){
	int id_for_fir , check = 0 ;
	
	for (int i = 1 ; i <= n ; i ++ ){
		int res1 = -1e9 , res2 =  -1e9 ; 
		if ( i < n ) res1 = tinh_eculid ( a[i+1].x , a[i+1].y , a[i].x , a[i].y) ;
		if ( i < n - 1 ) res2 = tinh_eculid ( a[i+2].x , a[i+2].y , a[i].x , a[i].y) ;
		int check_now = 0 ;
		if (res1 >= res2 && res1 != -1e9 ){
			check = 1 ;
		}
		else if ( res2 != -1e9 ) check = 2 ;
		if ( max ( res1 , res2) > res){
			res = max ( res1 , res2 ) ;
			check = check_now ;
			id_for_fir = i ;
		}
	}
	// cerr << 1 << '\n';
	// int dem = 0 ;
	for (int i = 1 ; i <= n ; i ++ ){
		if ( id_for_fir != i ){
			cout << 2 << ' ' ; 
		}
		else if ( id_for_fir == i ){
			cout << 1 << ' ' ; 
			if ( check == 1 ){
				cout << 1 << ' '; i ++ ;
			}
			else {
				cout << 2 << ' ' << 1 << ' ';
				i += 2 ; 
			}
		}
	}
}
int b[Max_n+3] ;
int cp[Max_n+3] ;
int ans_1 = -1e9 ; 
void sub3(){
	for (int i = 1 ; i <= n ; i ++ ){ b[i] = i ; }
		sort ( b + 1 , b + n + 1 , [&] ( int x, int y) { return a[x].x < a[y].x; }) ;
	int j = 1 ; 
	int min_euclid = 1e9 ;
	map < int , int > mp ; 
	for (int i = 1 ; i <= n ; i ++ ){
		if ( j <= m ){
			cp[b[i]] = j++ ;
			if ( mp[j-1] != 0 ) min_euclid = min ( min_euclid , tinh_eculid (a[mp[j-1]].x , a[mp[j-1]].y , a[b[i]].x , a[b[i]].y)) ;  
			mp[j-1] = b[i] ; 
		}
		if ( j > m ) j = 1 ; 
	}
	ans_1 = min_euclid ; 
	for (int i = 1 ; i <= n ; i ++ ){
		cout << cp[i] << ' ' ;  
	}
}
void solve(){
	cin >> n ;
	cin >> m ; 
	for (int i = 1; i <= n ; i ++ ){
		cin >> a[i].x >> a[i].y
 ;	}
 	// if ( n <= 10 && m != 2){
 	// 	sub1() ;
 	// }
 	// else if ( m == 2 ) {
 	// 	// for (int i = 1 ; i <= n ; i ++ ){
 	// 	// 	b[i] = i ;
 	// 	// m = 2 
 	// 	// thi se co 2 truong hop la 1 1 
 	// 	// va 1 2 1 
 	// 	// = > xem cai nao max nhat ghi la 
 	// 	// sau may cai kia thi cout nhu nao cung duoc
 	// 	// }
 	// 	sub2() ; 
 	// }
 	// // else sub3();
 	// sub1() ; 
 	// cout << res ; 
 	// cout << '\n' ;
 	// sub3() ; 
 	// cout << ans_1 << '\n';
 	// sub 3 
 	// khi y = 0 , = > sort ( lai mang x )
 	// roi xem la max khi dat theo kieu 1 2 3 4 5 1 2 3 4 5 
 	// dung mot cai bien id truoc khi sort 
 	// khieu nhu the 
 	// cout << ra ans 
 	if ( n <= 10 && m != 2){
 		sub1() ;
 	}
 	else if ( m == 2 ) {
 		// for (int i = 1 ; i <= n ; i ++ ){
 		// 	b[i] = i ;
 		// m = 2 
 		// thi se co 2 truong hop la 1 1 
 		// va 1 2 1 
 		// = > xem cai nao max nhat ghi la 
 		// sau may cai kia thi cout nhu nao cung duoc
 		// }
 		sub2() ; 
 	}
 	else sub3();
}
_nhatminh{
freopen("");
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int q=1;
// cin >> q;
while (q--)
	solve();
cerr << '\n' << "Time elapsed " << TIME << "s.\n";
return (0);
}