#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m;
int ans[N + 5];
struct frac
{
    long long x,y;
    long long z;
    inline frac(long long a = 0,long long b = 1)
    {
        b < 0 && (a = -a,b = -b);
        z = a / b,x = a % b,y = b;
        x < 0 && (x += y,--z);
    }
    inline long long floor()
    {
        return z;
    }
    inline long long ceil()
    {
        return z + (x > 0);
    }
    inline bool operator<=(const frac &o) const
    {
        return z < o.z || (z == o.z && (x * o.y <= o.x * y));
    }
} inter[N + 5];
struct Linear
{
    long long k,b;
    int id;
    inline Linear(long long x = 0,long long y = 0,int z = 0)
    {
        k = x,b = y,id = z;
    }
    inline bool operator<(const Linear &o) const
    {
        return k < o.k || (k == o.k && b > o.b);
    }
} a[N + 5],s[N + 5];
int top;
inline frac intersection(const Linear &a,const Linear &b)
{
    return frac(b.b - a.b,a.k - b.k);
}
pair<long long,int> t[(N << 1) + 5];
int cnt;
void solve(int k)
{
    top = cnt = 0;
    for(register int i = 1;i <= n;++i)
        if(ans[a[i].id] == -1 && (!top || a[i].k > s[top].k))
        {
            for(;top && a[i].b >= s[top].b;--top);
            for(;top > 1 && intersection(a[i],s[top]).floor() < inter[top].ceil();--top);
            s[++top] = a[i];
            top > 1 && (inter[top] = intersection(s[top - 1],s[top]),1);
        }
    inter[top + 1] = frac(1e18,1);
    for(register int i = 1;i <= n;++i)
        if(~ans[a[i].id])
        {
            int l = 1,r = top,mid,L = 0,R = 0;
            while(l <= r)
                mid = l + r >> 1,
                (s[mid].k >= a[i].k || intersection(s[mid],a[i]) <= inter[mid + 1]) ? (L = mid,r = mid - 1) : (l = mid + 1);
            t[++cnt] = make_pair(s[L].k >= a[i].k ? 0 : intersection(s[L],a[i]).floor() + 1,1);
            l = 1,r = top;
            while(l <= r)
                mid = l + r >> 1,
                (s[mid].k <= a[i].k || inter[mid] <= intersection(s[mid],a[i])) ? (R = mid,l = mid + 1) : (r = mid - 1);
            t[++cnt] = make_pair(s[R].k <= a[i].k ? 1e18 + 1 : intersection(s[R],a[i]).ceil(),-1);
        }
    sort(t + 1,t + cnt + 1);
    for(register int i = 1,j = 1,rk = 0;i <= top;++i)
    {
        for(;j <= cnt && t[j].first <= inter[i].ceil();rk += t[j++].second);
        rk == k - 1 && (ans[s[i].id] = k);
        for(register int x;j <= cnt && t[j].first <= inter[i + 1].floor();j = x)
        {
            for(x = j;x <= cnt && t[x].first == t[j].first;rk += t[x++].second);
            rk == k - 1 && (ans[s[i].id] = k);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m),memset(ans,-1,sizeof ans);
    for(register int i = 1;i <= n;++i)
        scanf("%lld%lld",&a[i].k,&a[i].b),a[i].id = i;
    sort(a + 1,a + n + 1);
    for(register int i = 1;i <= m;++i)
        solve(i);
    for(register int i = 1;i <= n;++i)
        printf("%d%c",ans[i]," \n"[i == n]);
}