# import numpy as np
 
# def heuristic(n, rng=None):
#     if rng is None or isinstance(rng, int):
#         rng = np.random.default_rng(rng)
#     S = set()
#     candidates = list(range(1, n+1))
#     # Prioritize numbers with fewer representations as part of an AP
#     # Here, we simply use the count of APs they can form, but more sophisticated methods exist
#     candidates.sort(key=lambda x: sum(1 for y in S if 2*y-x in S or 2*x-y in S or y+x in [2*z for z in S]))
#     for x in candidates:
#         if not any((2*x - y in S and y in S) or (2*y - x in S and y in S) for y in S):
#             S.add(x)
#     return S
import numpy as np
 
def count_3ap_memberships(N: int) -> np.ndarray:
    """
    counts[x] = number of 3-APs (a,b,c) with a<b<c in [1..N] where x is one of {a,b,c}.
    Time: O(N^2) via iterating (middle b, step d).
    """
    counts = np.zeros(N + 1, dtype=np.int64)  # 1-indexed
    for b in range(1, N + 1):
        max_d = min(b - 1, N - b)
        for d in range(1, max_d + 1):
            a = b - d
            c = b + d
            counts[a] += 1
            counts[b] += 1
            counts[c] += 1
    return counts
 
def would_create_3ap(S: set[int], x: int) -> bool:
    """
    Check whether adding x to S would create any 3-term AP entirely in S ∪ {x}.
    Equivalent: exists y in S such that (2*y - x) in S OR (2*x - y) in S.
    """
    for y in S:
        if (2 * y - x) in S:
            return True  # (x, y, 2y-x) with y middle
        if (2 * x - y) in S:
            return True  # (y, x, 2x-y) with x middle
    return False
 
def salem_spencer_greedy(N: int, rng=None, tie_break="random", verbose=False):
    """
    Greedy Salem-Spencer construction on [1..N]:
    - Precompute global 3-AP membership counts for each integer as sorting key.
    - Iterate candidates in ascending key order; add x if it does not create a 3-AP.
 
    tie_break:
      - "random": shuffle within same-key bucket using rng
      - "asc": smaller x first within same-key bucket
      - "desc": larger x first within same-key bucket
    """
    if rng is None or isinstance(rng, int):
        rng = np.random.default_rng(rng)
 
    counts = count_3ap_memberships(N)
    candidates = list(range(1, N + 1))
 
    # Tie-breaking strategy
    if tie_break == "random":
        rng.shuffle(candidates)
        candidates.sort(key=lambda x: counts[x])  # stable sort keeps shuffled order within ties
    elif tie_break == "asc":
        candidates.sort(key=lambda x: (counts[x], x))
    elif tie_break == "desc":
        candidates.sort(key=lambda x: (counts[x], -x))
    else:
        raise ValueError("tie_break must be one of: 'random', 'asc', 'desc'")
 
    if verbose:
        print("candidate -> key(count_3ap_memberships)")
        for x in candidates:
            print(f"{x:>4} -> {counts[x]}")
 
    S: set[int] = set()
    for x in candidates:
        if not would_create_3ap(S, x):
            S.add(x)
 
    return S, counts, candidates
 
# -----------------------
# Example usage
# -----------------------
if __name__ == "__main__":
    N = 82
    S, counts, order = salem_spencer_greedy(N, rng=0, tie_break="asc", verbose=False)
    print("N =", N)
    print("|S| =", len(S))
    print("S (sorted) =", sorted(S))
    # show first 15 candidates with their keys
    print("First 15 candidates (x, key):", [(x, int(counts[x])) for x in order])
 
 
 
 
# X = heuristic(1094)
 
# print(X, len(X))

IyBpbXBvcnQgbnVtcHkgYXMgbnAKCiMgZGVmIGhldXJpc3RpYyhuLCBybmc9Tm9uZSk6CiMgICAgIGlmIHJuZyBpcyBOb25lIG9yIGlzaW5zdGFuY2Uocm5nLCBpbnQpOgojICAgICAgICAgcm5nID0gbnAucmFuZG9tLmRlZmF1bHRfcm5nKHJuZykKIyAgICAgUyA9IHNldCgpCiMgICAgIGNhbmRpZGF0ZXMgPSBsaXN0KHJhbmdlKDEsIG4rMSkpCiMgICAgICMgUHJpb3JpdGl6ZSBudW1iZXJzIHdpdGggZmV3ZXIgcmVwcmVzZW50YXRpb25zIGFzIHBhcnQgb2YgYW4gQVAKIyAgICAgIyBIZXJlLCB3ZSBzaW1wbHkgdXNlIHRoZSBjb3VudCBvZiBBUHMgdGhleSBjYW4gZm9ybSwgYnV0IG1vcmUgc29waGlzdGljYXRlZCBtZXRob2RzIGV4aXN0CiMgICAgIGNhbmRpZGF0ZXMuc29ydChrZXk9bGFtYmRhIHg6IHN1bSgxIGZvciB5IGluIFMgaWYgMip5LXggaW4gUyBvciAyKngteSBpbiBTIG9yIHkreCBpbiBbMip6IGZvciB6IGluIFNdKSkKIyAgICAgZm9yIHggaW4gY2FuZGlkYXRlczoKIyAgICAgICAgIGlmIG5vdCBhbnkoKDIqeCAtIHkgaW4gUyBhbmQgeSBpbiBTKSBvciAoMip5IC0geCBpbiBTIGFuZCB5IGluIFMpIGZvciB5IGluIFMpOgojICAgICAgICAgICAgIFMuYWRkKHgpCiMgICAgIHJldHVybiBTCmltcG9ydCBudW1weSBhcyBucAoKZGVmIGNvdW50XzNhcF9tZW1iZXJzaGlwcyhOOiBpbnQpIC0+IG5wLm5kYXJyYXk6CiAgICAiIiIKICAgIGNvdW50c1t4XSA9IG51bWJlciBvZiAzLUFQcyAoYSxiLGMpIHdpdGggYTxiPGMgaW4gWzEuLk5dIHdoZXJlIHggaXMgb25lIG9mIHthLGIsY30uCiAgICBUaW1lOiBPKE5eMikgdmlhIGl0ZXJhdGluZyAobWlkZGxlIGIsIHN0ZXAgZCkuCiAgICAiIiIKICAgIGNvdW50cyA9IG5wLnplcm9zKE4gKyAxLCBkdHlwZT1ucC5pbnQ2NCkgICMgMS1pbmRleGVkCiAgICBmb3IgYiBpbiByYW5nZSgxLCBOICsgMSk6CiAgICAgICAgbWF4X2QgPSBtaW4oYiAtIDEsIE4gLSBiKQogICAgICAgIGZvciBkIGluIHJhbmdlKDEsIG1heF9kICsgMSk6CiAgICAgICAgICAgIGEgPSBiIC0gZAogICAgICAgICAgICBjID0gYiArIGQKICAgICAgICAgICAgY291bnRzW2FdICs9IDEKICAgICAgICAgICAgY291bnRzW2JdICs9IDEKICAgICAgICAgICAgY291bnRzW2NdICs9IDEKICAgIHJldHVybiBjb3VudHMKCmRlZiB3b3VsZF9jcmVhdGVfM2FwKFM6IHNldFtpbnRdLCB4OiBpbnQpIC0+IGJvb2w6CiAgICAiIiIKICAgIENoZWNrIHdoZXRoZXIgYWRkaW5nIHggdG8gUyB3b3VsZCBjcmVhdGUgYW55IDMtdGVybSBBUCBlbnRpcmVseSBpbiBTIOKIqiB7eH0uCiAgICBFcXVpdmFsZW50OiBleGlzdHMgeSBpbiBTIHN1Y2ggdGhhdCAoMip5IC0geCkgaW4gUyBPUiAoMip4IC0geSkgaW4gUy4KICAgICIiIgogICAgZm9yIHkgaW4gUzoKICAgICAgICBpZiAoMiAqIHkgLSB4KSBpbiBTOgogICAgICAgICAgICByZXR1cm4gVHJ1ZSAgIyAoeCwgeSwgMnkteCkgd2l0aCB5IG1pZGRsZQogICAgICAgIGlmICgyICogeCAtIHkpIGluIFM6CiAgICAgICAgICAgIHJldHVybiBUcnVlICAjICh5LCB4LCAyeC15KSB3aXRoIHggbWlkZGxlCiAgICByZXR1cm4gRmFsc2UKCmRlZiBzYWxlbV9zcGVuY2VyX2dyZWVkeShOOiBpbnQsIHJuZz1Ob25lLCB0aWVfYnJlYWs9InJhbmRvbSIsIHZlcmJvc2U9RmFsc2UpOgogICAgIiIiCiAgICBHcmVlZHkgU2FsZW0tU3BlbmNlciBjb25zdHJ1Y3Rpb24gb24gWzEuLk5dOgogICAgLSBQcmVjb21wdXRlIGdsb2JhbCAzLUFQIG1lbWJlcnNoaXAgY291bnRzIGZvciBlYWNoIGludGVnZXIgYXMgc29ydGluZyBrZXkuCiAgICAtIEl0ZXJhdGUgY2FuZGlkYXRlcyBpbiBhc2NlbmRpbmcga2V5IG9yZGVyOyBhZGQgeCBpZiBpdCBkb2VzIG5vdCBjcmVhdGUgYSAzLUFQLgoKICAgIHRpZV9icmVhazoKICAgICAgLSAicmFuZG9tIjogc2h1ZmZsZSB3aXRoaW4gc2FtZS1rZXkgYnVja2V0IHVzaW5nIHJuZwogICAgICAtICJhc2MiOiBzbWFsbGVyIHggZmlyc3Qgd2l0aGluIHNhbWUta2V5IGJ1Y2tldAogICAgICAtICJkZXNjIjogbGFyZ2VyIHggZmlyc3Qgd2l0aGluIHNhbWUta2V5IGJ1Y2tldAogICAgIiIiCiAgICBpZiBybmcgaXMgTm9uZSBvciBpc2luc3RhbmNlKHJuZywgaW50KToKICAgICAgICBybmcgPSBucC5yYW5kb20uZGVmYXVsdF9ybmcocm5nKQoKICAgIGNvdW50cyA9IGNvdW50XzNhcF9tZW1iZXJzaGlwcyhOKQogICAgY2FuZGlkYXRlcyA9IGxpc3QocmFuZ2UoMSwgTiArIDEpKQoKICAgICMgVGllLWJyZWFraW5nIHN0cmF0ZWd5CiAgICBpZiB0aWVfYnJlYWsgPT0gInJhbmRvbSI6CiAgICAgICAgcm5nLnNodWZmbGUoY2FuZGlkYXRlcykKICAgICAgICBjYW5kaWRhdGVzLnNvcnQoa2V5PWxhbWJkYSB4OiBjb3VudHNbeF0pICAjIHN0YWJsZSBzb3J0IGtlZXBzIHNodWZmbGVkIG9yZGVyIHdpdGhpbiB0aWVzCiAgICBlbGlmIHRpZV9icmVhayA9PSAiYXNjIjoKICAgICAgICBjYW5kaWRhdGVzLnNvcnQoa2V5PWxhbWJkYSB4OiAoY291bnRzW3hdLCB4KSkKICAgIGVsaWYgdGllX2JyZWFrID09ICJkZXNjIjoKICAgICAgICBjYW5kaWRhdGVzLnNvcnQoa2V5PWxhbWJkYSB4OiAoY291bnRzW3hdLCAteCkpCiAgICBlbHNlOgogICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoInRpZV9icmVhayBtdXN0IGJlIG9uZSBvZjogJ3JhbmRvbScsICdhc2MnLCAnZGVzYyciKQoKICAgIGlmIHZlcmJvc2U6CiAgICAgICAgcHJpbnQoImNhbmRpZGF0ZSAtPiBrZXkoY291bnRfM2FwX21lbWJlcnNoaXBzKSIpCiAgICAgICAgZm9yIHggaW4gY2FuZGlkYXRlczoKICAgICAgICAgICAgcHJpbnQoZiJ7eDo+NH0gLT4ge2NvdW50c1t4XX0iKQoKICAgIFM6IHNldFtpbnRdID0gc2V0KCkKICAgIGZvciB4IGluIGNhbmRpZGF0ZXM6CiAgICAgICAgaWYgbm90IHdvdWxkX2NyZWF0ZV8zYXAoUywgeCk6CiAgICAgICAgICAgIFMuYWRkKHgpCgogICAgcmV0dXJuIFMsIGNvdW50cywgY2FuZGlkYXRlcwoKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQojIEV4YW1wbGUgdXNhZ2UKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgTiA9IDgyCiAgICBTLCBjb3VudHMsIG9yZGVyID0gc2FsZW1fc3BlbmNlcl9ncmVlZHkoTiwgcm5nPTAsIHRpZV9icmVhaz0iYXNjIiwgdmVyYm9zZT1GYWxzZSkKICAgIHByaW50KCJOID0iLCBOKQogICAgcHJpbnQoInxTfCA9IiwgbGVuKFMpKQogICAgcHJpbnQoIlMgKHNvcnRlZCkgPSIsIHNvcnRlZChTKSkKICAgICMgc2hvdyBmaXJzdCAxNSBjYW5kaWRhdGVzIHdpdGggdGhlaXIga2V5cwogICAgcHJpbnQoIkZpcnN0IDE1IGNhbmRpZGF0ZXMgKHgsIGtleSk6IiwgWyh4LCBpbnQoY291bnRzW3hdKSkgZm9yIHggaW4gb3JkZXJdKQoKCgoKIyBYID0gaGV1cmlzdGljKDEwOTQpCgojIHByaW50KFgsIGxlbihYKSk=