"""Counting upper bound on f(n) = max lines in an n-subset of AG(4,3).

Facts (W = 40 parallel classes of hyperplanes, (a,b,c) = slice sizes in class W):
  (I)  L = (1/18) * sum_W abc - C(n,3)/2           [equivalently sum_W sum_i C(k_i,3) = 4C(n,3) + 9L]
  (II) sum_W (ab+bc+ca) = 27 * C(n,2)
  (III) for every W:  L <= g(a)+g(b)+g(c) + min(ab,bc,ca) =: U(a,b,c)
Given a target L* : any S with L >= L* has all 40 profiles in P(L*) = {p : U(p) >= L*}, and
  sum_W abc = 18 L + 9 C(n,3) >= 18 L* + 9 C(n,3).
Exact integer DP over multisets of 40 profiles from P(L*) satisfying (II): max sum abc.
If max < 18 L* + 9 C(n,3)  =>  f(n) < L*.   (Inequality form: valid for all L >= L*.)
UB(n) = largest L* for which the check is NOT infeasible ... i.e. the least L* with infeasibility, minus 1.
"""
import sys
from math import comb
import numpy as np

g = [0, 0, 0, 1, 1, 2, 3, 5, 8, 12, 12, 13, 14, 16, 19, 23, 26, 30, 36, 41, 47, 54, 62, 71, 81, 92, 104, 117]

def partitions(n):
    out = []
    for a in range(min(27, n), -1, -1):
        for b in range(min(a, n - a), -1, -1):
            c = n - a - b
            if c < 0 or c > b: continue
            out.append((a, b, c))
    return out

def U(p):
    a, b, c = p
    return g[a] + g[b] + g[c] + min(a * b, b * c, c * a)

def e2(p):
    a, b, c = p
    return a * b + b * c + c * a

def abc(p):
    a, b, c = p
    return a * b * c

NEG = -10**9

def max_sum_abc(n, Lstar, filt=True):
    """max of sum_W abc over 40-multisets of admissible profiles with sum e2 = 27 C(n,2); NEG if infeasible."""
    P = [p for p in partitions(n) if (not filt or U(p) >= Lstar)]
    if not P: return NEG, P
    E = 27 * comb(n, 2)
    # dp[s] = max sum abc using current number of classes with sum e2 = s
    dp = np.full(E + 1, NEG, dtype=np.int64); dp[0] = 0
    for _ in range(40):
        nd = np.full(E + 1, NEG, dtype=np.int64)
        for p in P:
            e, v = e2(p), abc(p)
            if e > E: continue
            cand = dp[:E + 1 - e] + v
            np.maximum(nd[e:], cand, out=nd[e:])
        dp = nd
    return int(dp[E]), P

def upper_bound(n, filt=True, Lmax=None):
    """largest L such that the counting system is feasible; f(n) <= this."""
    if Lmax is None: Lmax = comb(n, 2) // 3 + 1
    # feasibility is monotone decreasing in L*: find least infeasible L*
    lo, hi = 0, Lmax + 1  # invariant: feasible(lo) true (L*=0 always feasible for n>=0), infeasible(hi)
    def feasible(Ls):
        m, _ = max_sum_abc(n, Ls, filt)
        return m >= 18 * Ls + 9 * comb(n, 3)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if feasible(mid): lo = mid
        else: hi = mid
    return lo

def lb_construction(n):
    """n <= 27: g(n). n >= 27: full hyperplane + extremal 3D sets of sizes b, c in the two parallel hyperplanes."""
    if n <= 27: return g[n]
    best = 0
    for b in range(0, 28):
        c = n - 27 - b
        if 0 <= c <= 27:
            best = max(best, 117 + g[b] + g[c] + b * c)
    return best

if __name__ == "__main__":
    ns = range(int(sys.argv[1]), int(sys.argv[2]) + 1) if len(sys.argv) > 2 else range(3, 82)
    for n in ns:
        ub = upper_bound(n)
        lb = lb_construction(n)
        exact = None
        if n >= 61:
            m = 81 - n; exact = 1080 - 40 * m + comb(m, 2)
        flag = "EXACT" if ub == lb else f"gap {ub - lb}"
        extra = f"  (cap-complement exact {exact})" if exact is not None else ""
        print(f"n={n:2d}  LB={lb:4d}  UB={ub:4d}  {flag}{extra}", flush=True)