#!/usr/bin/env python3
"""Test generator for JELLY FUSION, reverse-engineered from the original
2026 ICPC North America Championship package categories, plus two new
categories for the Bulgarian subtasks:

    constw / consth  -> S4 (one dimension constant; merging never helps)
    monotone         -> S5 (h non-decreasing AND w non-increasing)

Usage:  python3 gen.py <category> <N> <seed> [extra...]
Prints a valid input (1<=h,w<=10^6, 1<=N<=3e5) to stdout.
"""
import sys, random

VMAX = 10**6

def emit(pairs):
    out = [str(len(pairs))]
    out += [f"{h} {w}" for (h, w) in pairs]
    sys.stdout.write("\n".join(out) + "\n")

def rnd_val(rng):
    return rng.randint(1, VMAX)

def cat_random(rng, n, *_):
    return [(rnd_val(rng), rnd_val(rng)) for _ in range(n)]

def digit_val(rng):
    d = rng.randint(1, 6)
    lo, hi = 10**(d-1), min(VMAX, 10**d - 1)
    if d == 1:
        lo = 1
    return rng.randint(lo, hi)

def cat_digitlength(rng, n, *_):
    return [(digit_val(rng), digit_val(rng)) for _ in range(n)]

def cat_smallint(rng, n, *extra):
    mx = int(extra[0]) if extra else 100
    return [(rng.randint(1, mx), rng.randint(1, mx)) for _ in range(n)]

def rotate(p, k):
    k %= len(p)
    return p[k:] + p[:k]

def cat_sorted(rng, n, *_):
    p = [(rnd_val(rng), rnd_val(rng)) for _ in range(n)]
    p.sort(key=lambda x: x[0])
    return rotate(p, rng.randrange(n))

def cat_sorted_xy(rng, n, *_):
    hs = sorted(rnd_val(rng) for _ in range(n))
    ws = sorted(rnd_val(rng) for _ in range(n))
    p = list(zip(hs, ws))
    return rotate(p, rng.randrange(n))

def cat_alt(rng, n, *_):
    p = []
    for i in range(n):
        if i % 2 == 0:
            p.append((rng.randint(VMAX//2, VMAX), rng.randint(1, VMAX//1000 + 1)))
        else:
            p.append((rng.randint(1, VMAX//1000 + 1), rng.randint(VMAX//2, VMAX)))
    return p

def cat_maxalt(rng, n, *_):
    return [((VMAX, 1) if i % 2 == 0 else (1, VMAX)) for i in range(n)]

def cat_spiky(rng, n, *extra):
    # probability (in %) of a spike; default ~33
    pct = int(extra[0]) if extra else 33
    p = []
    for _ in range(n):
        if rng.randint(1, 100) <= pct:
            p.append((1, VMAX) if rng.random() < 0.5 else (VMAX, 1))
        else:
            p.append((rng.randint(1, 30), rng.randint(1, 30)))
    return p

def cat_biggaps(rng, n, *extra):
    k = int(extra[0]) if extra else 32           # number of distinct values
    base = list(range(1, max(1, k - 2) + 1)) + [100000, VMAX]
    vals = sorted(set(base))
    return [(rng.choice(vals), rng.choice(vals)) for _ in range(n)]

def cat_maxans(rng, n, *_):
    return [(VMAX, VMAX) for _ in range(n)]

def _distinct_sorted(rng, n, lo, hi, reverse=False):
    if hi - lo + 1 < n:
        hi = lo + n - 1            # widen if needed; clamp later by caller
    vals = rng.sample(range(lo, hi + 1), n)
    vals.sort(reverse=reverse)
    return vals

def cat_increasing(rng, n, *_):
    lo = max(1, VMAX - 300000 + 1)
    hs = _distinct_sorted(rng, n, lo, VMAX)
    ws = _distinct_sorted(rng, n, lo, VMAX)
    return list(zip(hs, ws))

def cat_decreasing(rng, n, *_):
    lo = max(1, VMAX - 300000 + 1)
    hs = _distinct_sorted(rng, n, lo, VMAX, reverse=True)
    ws = _distinct_sorted(rng, n, lo, VMAX, reverse=True)
    return list(zip(hs, ws))

def cat_onlyhull(rng, n, *_):
    # n points on a convex curve: h increasing, w convex-decreasing -> all on hull.
    c = rng.randint(300000, 600000)
    p = []
    for i in range(n):
        h = c + i
        w = c + int(round((n - 1 - i) * (n - 1 - i) / max(1, n)))  # convex decreasing
        h = min(VMAX, max(1, h)); w = min(VMAX, max(1, w))
        p.append((h, w))
    return p

# ---- NEW categories for the Bulgarian subtasks ----
def cat_constw(rng, n, *extra):
    C = int(extra[0]) if extra else rng.randint(1, VMAX)
    return [(rnd_val(rng), C) for _ in range(n)]

def cat_consth(rng, n, *extra):
    C = int(extra[0]) if extra else rng.randint(1, VMAX)
    return [(C, rnd_val(rng)) for _ in range(n)]

def cat_monotone(rng, n, *_):
    # S5: h non-decreasing AND w non-increasing (anti-monotone "staircase").
    hs = sorted(rng.randint(1, VMAX) for _ in range(n))                 # ascending
    ws = sorted((rng.randint(1, VMAX) for _ in range(n)), reverse=True) # descending
    return list(zip(hs, ws))

CATS = {
    "random": cat_random, "digitlength": cat_digitlength, "smallint": cat_smallint,
    "sorted": cat_sorted, "sorted_xy": cat_sorted_xy, "alt": cat_alt, "maxalt": cat_maxalt,
    "spiky": cat_spiky, "biggaps": cat_biggaps, "maxans": cat_maxans,
    "increasing": cat_increasing, "decreasing": cat_decreasing, "onlyhull": cat_onlyhull,
    "constw": cat_constw, "consth": cat_consth, "monotone": cat_monotone,
}

def main():
    if len(sys.argv) < 4:
        sys.exit("usage: gen.py <category> <N> <seed> [extra...]  (categories: %s)"
                 % ", ".join(sorted(CATS)))
    cat, n, seed = sys.argv[1], int(sys.argv[2]), int(sys.argv[3])
    extra = sys.argv[4:]
    if cat not in CATS:
        sys.exit("unknown category: " + cat)
    rng = random.Random((seed * 1000003) ^ (hash(cat) & 0xffffffff))
    pairs = CATS[cat](rng, n, *extra)
    # safety clamp to the validator's bounds
    pairs = [(min(VMAX, max(1, h)), min(VMAX, max(1, w))) for (h, w) in pairs][:n]
    emit(pairs)

if __name__ == "__main__":
    main()
