#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define Size(x) ((x).size())
#define rep(i, l, r) for(int (i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for(int (i) = (r); (i) >= (l); --(i))
#define chkmax(x, y) (x) = max((x), (y))
#define chkmin(x, y) (x) = min((x), (y))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> VI;
inline char gc() {
	static char now[1 << 16], *S, *T;
	if (S == T) {T = (S = now) + fread(now, 1, 1 << 16, stdin); if (S == T) return EOF;}
	return *S ++;
}
inline int readint() {
	int x = 0, f = 1; char c = gc();
	while (c < '0' || c > '9') {(c == '-') ? (f = 0) : 0; c = gc();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
	return f ? x : ((~ x) + 1);
}
inline ll readll() {
	ll x = 0, f = 1; char c = gc();
	while (c < '0' || c > '9') {(c == '-') ? (f = 0) : 0; c = gc();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
	return f ? x : ((~ x) + 1);
}
struct frac {
	ll x, y;
};
inline ll floor(const frac &A) {
	return A.x / A.y;
}
inline ll ceil(const frac &A) {
	return A.x / A.y + (A.x % A.y != 0);
}
inline bool operator < (const frac &A, const ll &B) {
	return (ld) A.x / A.y < (ld) B;
}
inline bool operator < (const frac &A, const frac &B) {
	return (ld) A.x / A.y < (ld) B.x / B.y;
}
inline frac make(const ll &x, const ll &y) {
	return (y > 0) ? (frac) {x, y} : (frac) {- x, - y};
}
const int N = 100010;
const ll inf = 1ll << 60;
int n, ans[N];
struct item {
	int k, id; ll b;
} a[N], stk[N];
int top;
inline bool operator < (const item &A, const item &B) {
	return (A.k ^ B.k) ? (A.k < B.k) : (A.b > B.b);
}
inline frac inter(const item &A, const item &B) {
	return make(B.b - A.b, A.k - B.k);
}
inline void halfplane() {
	top = 0;
	rep(i, 1, n) {
		if (ans[a[i].id] != -1) continue ;
		while (top >= 2 && inter(a[i], stk[top - 1]) < inter(stk[top], stk[top - 1])) -- top;
		if (top == 1 && a[i].b > stk[top].b) -- top;
		if (top == 0 || a[i].k != stk[top].k) stk[++ top] = a[i];
	}
}
pair<ll, int> que[N << 1]; int cnt;
int main() {
	n = readint(); int m = readint();
	rep(i, 1, n) {
		a[i].k = readint();
		a[i].b = readll();
		a[i].id = i;
		ans[i] = -1;
	}
	sort(a + 1, a + n + 1);
	rep(nowm, 1, m) {
		halfplane();
		if (!top) break ;
		stk[0] = stk[1]; stk[0].k = 0;
		int now = 0; cnt = 0;
		rep(i, 1, n) if (ans[a[i].id] != -1) {
			int l = 0, r = top;
			while (l < r) {
				int mid = (l + r + 1) >> 1;
				if (a[i].k <= stk[mid].k || inter(a[i], stk[mid - 1]) < inter(stk[mid], stk[mid - 1])) r = mid - 1;
				else l = mid;
			}
			if (l == 0) ++ now;
			else que[++ cnt] = mk(floor(inter(a[i], stk[l])) + 1, 1);
			if (a[i].k < stk[top].k) {
				l = 1, r = top + 1;
				while (l < r) {
					int mid = (l + r) >> 1;
					if (a[i].k >= stk[mid].k || (mid != top && inter(stk[mid], stk[mid + 1]) < inter(a[i], stk[mid + 1]))) l = mid + 1;
					else r = mid;
				}
				que[++ cnt] = mk(ceil(inter(a[i], stk[l])), -1);
			}
		}
		sort(que + 1, que + cnt + 1);
		int pos = 1;
		rep(i, 1, top) {
			ll l = ceil(inter(stk[i], stk[i - 1])),
			   r = i == top ? inf : floor(inter(stk[i], stk[i + 1]));
			if (l > r) continue;
			while (pos <= cnt && que[pos].fi <= l) {
				ll val = que[pos].fi;
				while (pos <= cnt && que[pos].fi == val) now += que[pos ++].se;
			}
			int mn = now;
			while (pos <= cnt && que[pos].fi <= r) {
				ll val = que[pos].fi;
				while (pos <= cnt && que[pos].fi == val) now += que[pos ++].se;
				chkmin(mn, now);
			}
			if (mn == nowm - 1) ans[stk[i].id] = nowm;
		}
	}
	for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
	return 0;
}