J Exhibition

#define _USE_MATH_DEFINES

#include <iostream>
#include <math.h>
#include <string.h>
#include <string>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <functional>
#include <algorithm>
#include <bitset>
#include <set>
#include <stack>

using namespace std;

#define y1 y12345

#define REP(i,n) for(long long int i = 0; i < int(n); ++i)
#define REPV(i, n) for (long long int i = (n) - 1; (int)i >= 0; --i)
#define FOR(i, a, b) for(long long int i = (int)(a); i < (int)(b); ++i)

#define ALL(v) (v).begin(), (v).end()
#define PF push_front
#define PB push_back
#define MP make_pair
#define F first
#define S second

#define lli long long int

int N = 500;

int n, m;

struct Progression {
    lli a, b;
    int index;
    vector<int> members;

    void generate() {
        if (a <= 0 && b <= 0) return;
        if (a == 0) {
            if (b <= m) members.push_back(b);
        } else if (a < 0) {
            if (b <= m) members.push_back(b);
            lli k = (-b)/(a);
            int i = 0;
            while (i < N) {
                lli x = a*k + b;
                if (x > 0 && x <= m && k >=0 ) members.push_back(x);
                ++i; --k;
            }
        } else if (b <= 0) {
            lli k = (-b)/a;
            int i = 0;
            while (i < N) {
                lli x = a*k + b;
                if (x > 0 && x <= m && k >=0 ) members.push_back(x);
                ++i; ++k;
            }
        } else {
            for(int i = 0; i < N; ++i) {
                lli x = a*i + b;
                if (x <= m) members.push_back(x);
                else break;
            }
        }
    }
};

Progression progressions[302];

map<int, int> matching;
bool used[302];

bool dfs(int v) {
    if (used[v]) return false;
    used[v] = true;
    for(int i = 0; i < progressions[v].members.size(); ++i) {
        int to = progressions[v].members[i];
        map<int, int>::iterator it = matching.find(to);
        if (it == matching.end() || dfs((*it).second)) {
            matching[to] = v;
            return true;
        }
    }
    return false;
}

int ans[305];
bool usedM[1000];
int k = 1;

int getFirst() {
    while (usedM[k]) ++k;
    usedM[k] = true;
    return k;
}

int main()
{
ios_base::sync_with_stdio(0);
#ifdef FILE_IO
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> n >> m;
    REP(i, n) {
        cin >> progressions[i].a >> progressions[i].b;
        progressions[i].generate();
    }
    REP(i, n) {
        memset(used, 0, 302*sizeof(bool));
        dfs(i);
    }
    for(map<int, int>::iterator i = matching.begin(); i != matching.end(); ++i) {
        int value = (*i).first;
        ans[(*i).second] = value;
        if (value < 1000) usedM[value] = true;
    }
    for(int i = 0; i < n; ++i) {
        cout << (ans[i] != 0 ? ans[i] : getFirst()) << " ";
    }
    return 0;
}