<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

305. Exhibition
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The exhibition of arithmetical progressions will be opened in Berland soon. Each of N presented progressions is characterized by two integer numbers Ai and Bi. These numbers mean that all numbers X belong to the i-th progression if X = Ai*K+Bi for some non-negative integer K. Organizers decided that each sequence will be given a unique number from 1 to M. The organizers want as much as possible progressions to be assigned such a number, that would be a member of this progression. They hired you to do this job.

Input
The first line of the input contains two integer numbers N and M (1≤ N≤ 300; N≤ M≤ 109). Each of the following N lines contains the pair of numbers Ai and Bi (-109≤ Ai, Bi≤ 109).

Output
Write to the output distribution of numbers among sequences — N numbers delimited by spaces. All numbers should be unique. If there are several solutions output any of them.

Example(s)
sample input
sample output
5 6
1 1
2 1
3 1
3 1
6 4
2 3 1 6 4

<|response|>
## 1. Abridged Problem Statement

You are given **N** arithmetic progressions. Progression *i* contains all integers of the form:

X = A_i · K + B_i for some integer K ≥ 0

You must assign **each** progression a **distinct** integer from **1..M** (so all chosen numbers are unique). The goal is to make **as many progressions as possible** receive a number that actually belongs to their progression. (The remaining progressions may receive any unused numbers from 1..M.)

Output any valid assignment of **N** unique numbers in **[1, M]**.

Constraints: 1 ≤ N ≤ 300, N ≤ M ≤ 10⁹, A_i, B_i up to 10⁹ by absolute value.

---

## 2. Detailed Editorial

### Key idea: maximize "good" assignments via bipartite matching

We want to pick for each progression a distinct number in [1..M]. If a progression gets a number from its own set, call it a **good** assignment. We want to **maximize** the number of good assignments.

This is a classical setup for **maximum bipartite matching**:

- Left side: progressions i = 0..N-1
- Right side: numbers x ∈ [1..M]
- Edge (i, x) exists if x is in progression i

Then a matching corresponds to assigning distinct numbers to some progressions, and maximum matching size is the maximum number of progressions that can be "satisfied".

### Problem: M can be huge (up to 10⁹)

We cannot build nodes for all numbers 1..M. We need to shrink the right side **without losing optimality**.

### Why only the first N feasible numbers per progression are enough

For each progression i, consider the list of its elements that lie in [1..M], in increasing order:

```text
x_0 < x_1 < x_2 < ...
```

Claim: in a maximum matching with only N left nodes, it is enough to consider at most the first N candidates per progression. There are only N progressions total. If some matched number for a progression is "too far" in its list, there are many earlier numbers that could be swapped in unless they are all blocked by other matches — but only N-1 other progressions exist.

Thus we can restrict each left node to a bounded number (≤ N) of candidate right nodes and still allow an optimal matching.

The provided solution uses exactly that: for each progression, it generates up to N valid values in [1..M], starting from the first one inside the interval.

### Generating candidates for one progression

Progression: x = A·k + B, k ≥ 0.

- If A = 0: the progression is constant x = B. If 1 ≤ B ≤ M, the only candidate is B.
- If A ≠ 0:
  - We need the smallest k ≥ 0 such that x falls inside [1..M].
  - For A > 0, if B < 1, increase k to reach at least 1.
  - For A < 0, values decrease with k; to get into [1..M], if B > M, increase k to drop down to M.
  - After finding this starting k, generate x = A·(start_k + j) + B for j = 0..N-1, stopping when x leaves [1..M].

So each progression yields at most N candidates.

### Coordinate compression of candidate values

Different progressions may generate the same numeric candidates. We collect all candidates across all progressions, sort and unique them. Suppose there are V unique candidate values (with V ≤ N²).

Now the bipartite graph is:

- Left: N progressions
- Right: V compressed candidate values
- Edge if the value is a candidate for that progression

Then run **Hopcroft-Karp** to compute maximum matching in O(E√V), where E ≤ N·N = 90,000 (since each left has ≤ N edges). This fits easily.

### Completing the full assignment

After matching:
- For matched progressions, output their matched candidate value (these are guaranteed in the progression and unique).
- For unmatched progressions, assign any still-unused numbers from 1..M (scan from 1 upwards). Since M ≥ N, there will always be enough unused numbers.

This preserves maximal "good" count because we already maximized it with matching; the rest are forced to be "bad" anyway.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/hopcroft_karp.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class HopcroftKarp {
  private:
    int n, m;
    vector<int> dist;

    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for(int u = 0; u < n; u++) {
            if(inv_match[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }

        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                int m = match[v];
                if(m == -1) {
                    found = true;
                } else if(dist[m] == -1) {
                    dist[m] = dist[u] + 1;
                    q.push(m);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        for(int v: adj[u]) {
            int m = match[v];
            if(m == -1 || (dist[m] == dist[u] + 1 && dfs(m))) {
                inv_match[u] = v;
                match[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

  public:
    vector<int> match, inv_match;
    vector<vector<int>> adj;

    HopcroftKarp(int _n, int _m = -1) : n(_n), m(_m == -1 ? _n : _m) {
        adj.assign(n, vector<int>());
        clear(false);
    }

    void clear(bool clear_adj = true) {
        match.assign(m, -1);
        inv_match.assign(n, -1);
        if(clear_adj) {
            adj.assign(n, vector<int>());
        }
    }

    void add_edge(int u, int v) { adj[u].push_back(v); }

    int max_matching(bool shuffle_edges = false) {
        if(shuffle_edges) {
            for(int i = 0; i < n; i++) {
                shuffle(
                    adj[i].begin(), adj[i].end(),
                    mt19937(
                        chrono::steady_clock::now().time_since_epoch().count()
                    )
                );
            }
        }

        int ans = 0;
        while(bfs()) {
            for(int u = 0; u < n; u++) {
                if(inv_match[u] == -1 && dfs(u)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    vector<pair<int, int>> get_matching() {
        vector<pair<int, int>> matches;
        for(int u = 0; u < n; u++) {
            if(inv_match[u] != -1) {
                matches.emplace_back(u, inv_match[u]);
            }
        }
        return matches;
    }

    pair<vector<int>, vector<int>> minimum_vertex_cover() {
        vector<int> left_cover, right_cover;
        bfs();

        for(int u = 0; u < n; u++) {
            if(dist[u] == -1) {
                left_cover.push_back(u);
            }
        }

        for(int v = 0; v < m; v++) {
            if(match[v] != -1 && dist[match[v]] != -1) {
                right_cover.push_back(v);
            }
        }

        return {left_cover, right_cover};
    }
};

using BipartiteMatching = HopcroftKarp;

int n, m;
vector<pair<int, int>> p;

void read() {
    cin >> n >> m;
    p.resize(n);
    cin >> p;
}

void solve() {
    // We can solve this with matching. Create a graph where on one side we have
    // the progressions, while on the other we keep the 1...m values. The main
    // issue is that m might be fairly large, but we can get the first n
    // numbers in the arithmetic progression. We then want the maximum matching.

    vector<vector<int64_t>> candidates(n);
    for(int i = 0; i < n; i++) {
        int64_t a = p[i].first, b = p[i].second;
        if(a == 0) {
            if(b >= 1 && b <= m) {
                candidates[i].push_back(b);
            }
        } else {
            int64_t start_k = 0;
            if(a > 0) {
                if(b < 1) {
                    start_k = (1 - b + a - 1) / a;
                }
            } else {
                if(b > m) {
                    start_k = (b - m + (-a) - 1) / (-a);
                }
            }
            for(int j = 0; j < n; j++) {
                int64_t x = a * (start_k + j) + b;
                if(x < 1 || x > m) {
                    break;
                }
                candidates[i].push_back(x);
            }
        }
    }

    vector<int64_t> all_vals;
    for(int i = 0; i < n; i++) {
        for(int64_t v: candidates[i]) {
            all_vals.push_back(v);
        }
    }
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    int num_vals = all_vals.size();

    auto compress = [&](int64_t v) {
        return lower_bound(all_vals.begin(), all_vals.end(), v) -
               all_vals.begin();
    };

    BipartiteMatching bm(n, num_vals);
    for(int i = 0; i < n; i++) {
        for(int64_t v: candidates[i]) {
            bm.add_edge(i, compress(v));
        }
    }
    bm.max_matching();

    set<int64_t> used;
    vector<int64_t> ans(n, -1);
    for(int i = 0; i < n; i++) {
        if(bm.inv_match[i] != -1) {
            ans[i] = all_vals[bm.inv_match[i]];
            used.insert(ans[i]);
        }
    }

    int64_t next_free = 1;
    for(int i = 0; i < n; i++) {
        if(ans[i] == -1) {
            while(used.count(next_free)) {
                next_free++;
            }
            ans[i] = next_free;
            used.insert(next_free);
            next_free++;
        }
    }

    for(int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
from collections import deque

# Hopcroft–Karp maximum bipartite matching:
# Left side: 0..n-1, Right side: 0..m-1
class HopcroftKarp:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.adj = [[] for _ in range(n)]  # edges from left to right
        self.match = [-1] * m              # match[v] = u
        self.inv_match = [-1] * n          # inv_match[u] = v
        self.dist = [-1] * n               # BFS layers for left nodes

    def add_edge(self, u, v):
        self.adj[u].append(v)

    def bfs(self):
        q = deque()
        self.dist = [-1] * self.n

        # Start BFS from all free left nodes
        for u in range(self.n):
            if self.inv_match[u] == -1:
                self.dist[u] = 0
                q.append(u)

        found_free_right = False

        # BFS over alternating edges:
        # left u -> right v (unmatched edge), right v -> left match[v] (matched edge)
        while q:
            u = q.popleft()
            for v in self.adj[u]:
                mu = self.match[v]  # left node matched with v (or -1)
                if mu == -1:
                    found_free_right = True
                else:
                    if self.dist[mu] == -1:
                        self.dist[mu] = self.dist[u] + 1
                        q.append(mu)

        return found_free_right

    def dfs(self, u):
        for v in self.adj[u]:
            mu = self.match[v]
            # Either v is free, or we can recurse to rematch mu in next layer
            if mu == -1 or (self.dist[mu] == self.dist[u] + 1 and self.dfs(mu)):
                self.inv_match[u] = v
                self.match[v] = u
                return True

        # Mark u as dead end for this phase
        self.dist[u] = -1
        return False

    def max_matching(self):
        res = 0
        while self.bfs():
            for u in range(self.n):
                if self.inv_match[u] == -1 and self.dfs(u):
                    res += 1
        return res


def solve():
    it = iter(sys.stdin.read().strip().split())
    n = int(next(it))
    M = int(next(it))

    prog = []
    for _ in range(n):
        a = int(next(it)); b = int(next(it))
        prog.append((a, b))

    # Build up to n candidate values per progression that lie in [1..M]
    candidates = [[] for _ in range(n)]

    for i, (a, b) in enumerate(prog):
        if a == 0:
            # Constant progression: x = b
            if 1 <= b <= M:
                candidates[i].append(b)
        else:
            start_k = 0

            if a > 0:
                # Need smallest k >= 0 with a*k + b >= 1
                if b < 1:
                    # ceil((1-b)/a)
                    start_k = (1 - b + a - 1) // a
            else:
                # a < 0 decreasing: need a*k + b <= M
                if b > M:
                    # ceil((b-M)/(-a))
                    start_k = (b - M + (-a) - 1) // (-a)

            # Generate first up to n values from start_k, stop if out of bounds
            for j in range(n):
                x = a * (start_k + j) + b
                if x < 1 or x > M:
                    break
                candidates[i].append(x)

    # Coordinate compress all candidate values to a small right side
    all_vals = []
    for i in range(n):
        all_vals.extend(candidates[i])

    all_vals = sorted(set(all_vals))  # unique sorted
    idx = {v: k for k, v in enumerate(all_vals)}  # value -> compressed id

    # Build matching graph
    hk = HopcroftKarp(n, len(all_vals))
    for i in range(n):
        for v in candidates[i]:
            hk.add_edge(i, idx[v])

    hk.max_matching()

    # Construct final assignment
    ans = [-1] * n
    used = set()

    # Matched ones get their progression member
    for i in range(n):
        j = hk.inv_match[i]
        if j != -1:
            val = all_vals[j]
            ans[i] = val
            used.add(val)

    # Unmatched ones get smallest unused numbers in [1..M]
    nxt = 1
    for i in range(n):
        if ans[i] == -1:
            while nxt in used:
                nxt += 1
            ans[i] = nxt
            used.add(nxt)
            nxt += 1

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed Editorial

- Model "good assignments" as a bipartite graph: left = progressions, right = numbers; edge if number belongs to progression.
- Need maximum number of satisfied progressions => **maximum bipartite matching**.
- M is huge, so for each progression generate only the **first ≤ N** values in [1..M] (starting from the first feasible k); this is enough for optimal matching because there are only N left nodes.
- Collect all generated values, **coordinate compress** them to size V ≤ N².
- Run **Hopcroft-Karp** on graph with N left and V right.
- Output matched values for satisfied progressions; fill the rest with smallest unused numbers from 1..M (possible since M ≥ N).
