"""dualrs.py -- the chain law's depth side through a class the chain's
step keeps: does a hidden window always hold a k with q g_k = 0?

QUESTION. dualn.py's setting: f monic of degree n, f(0) = +/-q, O =
Z[x]/(f), G = O/I, g_k = beta^k mod I, D = {0, ..., q - 1}, T_W the
sums over k in W of D g_k. The class RS: a finite abelian G with a
sequence g_0, g_1, ... generating it and satisfying
sum_m a_m g_(k+m) = 0 for every k >= 0 (a_m f's coefficients) and
g_k = 0 for k >= some t. O/I read at depth t is in RS, and so is
G/<g_k> with the images. GC: in RS, if T_W is uniform on G != 0, then
q g_k = 0 for some k in W.

HAND (frozen before the runs).
  H1 If q g_k = 0, D g_k is q/r copies of <g_k>, r its order, so T_W is
     uniform on G iff T_(W - k) is on G/<g_k>, and a chain step in the
     quotient is one in G; GC therefore gives the depth side by
     induction on |G| + |W|. Uniformity is monotone in W, so GC iff
     W* = {k : q g_k != 0} never hides G != 0.
  R1 q = l^e. U = O/beta^t O is an l-group, so U = O0/beta^t O0 with
     O0 = Z_l[x]/(f0), f0 the factor of f over Z_l with f0 = x^r mod l
     (Hensel; beta is a unit on the other factor). So a G in RS(f)
     carries a sequence obeying f0's recurrence, f0 = x^r + a_(r-1)
     x^(r-1) + ... + a_0, l | a_i, v_l(a_0) = e, read mod exp(G); and
     every such f0 mod exp(G) is the factor, mod exp(G), of an integer
     f with f(0) = +/-q, f = f0 (x + c) with c a unit and the constant
     term set to +/-q. One sweep over f0 of degree r covers every
     integer base whose local factor has degree r, and only those. In
     an l-group each f0-sequence reaches 0 (g_(k+r) lies in
     l <g_k, ..., g_(k+r-1)>), and G has rank <= r.
  R2 A cyclic G never hides: a faithful chi has q chi(g_k) != 0 at
     every k in W*. Skipped, with every G of exponent <= q (W* empty).
  R3 g_k -> v^k g_k, v a unit of Z_l, keeps every order, so W* and
     hiding, and maps f0 to a_i v^(r-i). At l = 2, r = 3 cubing is onto
     the units: a_0 = q. At l = 3, r = 3: a_0 = 9u, u in {1, 4, 7}.
  R4 chi in B_k iff chi in (q g_k)^perp - g_k^perp; W* hides iff the
     B_k, q g_k != 0, cover every chi != 0. One bitmask per element.
  R7 On (Z/l^m)^d, GL_d(Z/l^m) is transitive on the elements of each
     order and commutes with the recurrence, so g_0 runs over 0 and
     (l^j, 0, ..., 0) only.

PREDICTIONS (frozen). Every initial r-tuple, run until it reaches 0.
  K  integer cubics f = x^3 + a2 x^2 + a1 x + c0, c0 = +/-q, a1, a2 in
     -2..2, G every product of cyclic l-groups of order <= 16 (q = 2,
     4) or 27 (q = 3), and q = 4 at order 32 with a1, a2 even, every
     triple of G^3 run to 64 terms, kept iff it reaches 0: 0 hiding.
  A  q = 4, r = 3, G of order 64, rank <= 3, exp >= 8, every a_1, a_2
     even mod exp(G), a_0 = 4;
  B  q = 8, r = 3, G of order 64, exp >= 16, a_1, a_2 even, a_0 = 8;
  C  q = 9, r = 3, G of order 81, exp >= 27, a_1, a_2 in 3Z mod exp,
     a_0 = 9u, u in {1, 4, 7};
  D  q = 4, r = 4, G of order <= 32, exp >= 8, a_1..a_3 even mod exp,
     a_0 = 4u, u odd;
  E  the groups every invariant factor of which exceeds q, past order
     64: q = 4 at (16, 8), (16, 16), (8, 8, 8), (32, 32); q = 8 at
     (16, 16); q = 9 at (27, 27), a_0 = 9.
  Predicted 0 hiding everywhere. KILL: any hiding sequence, printed
  with G, f0 and its r-tuple; GC then dies.
  L2 (frozen with T2 below, before its code) every noncyclic rank-2
     l-group of order <= 256 at q = 2, 4, 8 and <= 243 at q = 3, 9,
     f0 = x^2 + a_1 x + q u (u over the units mod squares, a_1 in lZ
     mod exp G), and (added after the first run, whose q = 9 arm held
     no group with both factors above q) (32, 32) at q = 4, 8 and
     (27, 27) at q = 9; every (g_0, g_1) run to 0: at most 2 distinct lines
     <q g_k> with ord q g_k = l. KILL: a sequence with 3. Its own
     print: the sequences at 2, which must be > 0 for the bound to be
     tested.
  S2 r = 2 with no nilpotence: q = 2, 4 at order 16, 32, 64, q = 3 at
     27, 81, every group, every a_0 = q u and every a_1 mod exp G, W*
     cut to [0, 8) and [0, 12): 0 hiding (T2 reads any window).
  L3 (frozen with R12, before its code) every initial triple under R7's
     cut, run to 0, f0 = x^3 + a2 x^2 + a1 x + a0, a1, a2 in lZ mod
     exp G: (4, 4, 4) q 2, a0 = 2; (8, 8, 8) q 2, a0 = 2; (8, 8, 8) q 4,
     a0 = 4 (R3); (9, 9, 9) q 3, a0 in {3, 6}. KILL: a sequence hitting
     more than B(l, 3) lines, 4 at l = 2 (of 7), 5 at l = 3 (of 13).
     Its own print: each arm's histogram.
  L4 (frozen with R13, after L3's run, before its code) at rank 2
     inside cubic f0, case B, every triple under R7's cut: q 2 at
     (4, 4), (8, 8); q 4 at (8, 8), (16, 16) and at (8, 8) with
     x^3 + 4 alone; q 3 at (9, 9), a0 in {3, 6}, and (27, 27), a0 = 3,
     a1, a2 in {0, 3, 6}. R13 read by brute span at every sequence
     hitting all l + 1 lines, 2000 drawn per arm when more. KILL: one
     with g_i off V_(i+1). TRANSPLANT from l = 2, predicted: some q 3
     sequence hits all 4 lines.
  BN (frozen with T4, before its engine) f0 = x^3 + a0, a0 = q u at
     every unit u mod exp G, every rank-2 l-group of exponent above q:
     every initial triple at order <= 32 at q = 2, 4 and <= 27 at q = 3,
     and (--full) 3000 drawn per (G, a0) at the others of order <= 256
     at q = 2, 4, 8 and <= 243 at q = 3, 9: T4's K is closed. KILL: one
     sequence where it is not.
  G  (frozen with R16-T5 by hand, before the gate engine) e = 1, rank 2,
     a1, a2 in lZ mod exp G, generating sequences only: q 2 at (4, 4),
     (8, 4), (8, 8), every triple under R7's cut, a0 = 2, and (16, 8),
     (16, 16), 2000 drawn; q 3 at (9, 9) every triple under R7's cut,
     a0 = 3, (27, 27) 2000 drawn at each a0 in {3, 6, 12} (R3) and
     (27, 9) 2000 drawn, a0 = 3; q 5 at (25, 25), 2000 drawn, a0 = 5.
     G1 R's gates come from at most one non-D class, at most one per
        depth. KILL: both
        non-D classes in R, or two X gates at one depth.
     G2 at most one non-degenerate D gate per depth in R, at its
        level's X depth when both lie in R. KILL: two at one depth, or
        one off its level's X depth (this clause, and C12's reach to
        every <h> of order l^N2, added after the freeze, before the run).
     G3 g_d <= l at every depth leaves a closed <h> in R. KILL: one
        sequence without. T5 proves it, so its print checks the engine.
     G4 (census) a closed <h> in R at every sequence read; the depths
        with g_d > l counted, with their degenerate D gates, and (added
        after the first run) the sequences where some |A_d|, d >= 1,
        falls to 1; (added with this section's engine, before its run)
        the sequences at each D, R16's three cases.
CONTROLS (read first).
  C1 "reaches 0" dropped, W* cut to [0, 8), q = 2, order 16, integer
     cubics: hiding sequences exist.
  C2 O/I at every ideal read at some depth, cubic bases of dualn.py at
     q^J <= 128, W* over [0, t): no hiding.
  C3 R7's cut at (4, 4), C1's only hiding group: one g_0 per order,
     and each hides iff its order class does.
  CB the nil arm, which no hiding reaches: the engine's witness count
     (characters no B_k covers) against a brute-force count over every
     character and every k in W*, at sampled eventually-zero sequences
     of (8, 8), (16, 8) at q = 4 and (27, 9) at q = 9, and at r = 2 of
     (8, 8) at q = 4 and (9, 9) at q = 3; equal at every one.
  C4 L2's code at r = 3: (8, 8), q = 4, x^3 + 4, every triple: some
     sequence puts q g_k on all 3 lines (the example closing DERIVED).
     Below 3, L2 is void.
  C5 the line counter itself: q = 1, f = x^7 on (Z/2)^3, seven free
     terms: some sequence hits all 7 lines (a counter reading only the
     first l + 1 line bits stops at 3).
  C6 R12 with l | f0(0) dropped: q = 1, f0 = x^3 + x + 1 on (2, 2, 2),
     beta a unit of period 7, 7 terms: some sequence hits all 7 lines,
     above B(2, 3) = 4.
  C7 (added with L4's code, after its freeze) R13's reader on (8, 8),
     q 4, x^3 + 4, g = (1, 0), (0, 1), 0, where V_1 misses (1, 0): no.
  C11 T4's K at x^3 + 2x + 2 (a1 = 2) on (8, 8), q 2, every triple:
     open at some sequence, so BN's reader can print a fail and K
     leans on a1 = 0 (dualpw.py reads a closed <h> at every generating
     sequence there).
  C12 G's bitmask closure reader agrees with a brute character reader
     (the character with kernel <h> a witness, read off character
     values, R15) at every <h>, h not in lG, of order l^N2, on C4's
     sequence and one generating sequence of each default q 2 arm.
  C13 G's no: a bare list in (8, 8), q 2, with no closed <h> among all
     twelve, found by search, printed with its largest g_d (above l, by
     T5's count with l + 1 children at the root).
  C14 G1's reader fires with R widened to every <h> of both sides of e,
     x^3 + 2 on (8, 8).
  C15, C16 each a planted break in G2's own reader: C15 counts the
     degenerate D gates with the rest, C16 reads the level clause one
     level off. Each fires.

FINDINGS (entered after the run, from its printed output).
  C1 6144 hiding sequences without nilpotence. C2 0 of 1948 ideals
     read at some depth hidden by their W*. C3 12 hiding (pair, order)
     cells, 0 off, every order held. CB 1080 sequences, 0 off, 31
     distinct witness counts, the least 12. C4 24576 triples of (8, 8)
     hit all 3 lines. C5 most 7 lines. C6 {0: 1, 1: 49, 3: 294, 7: 168}:
     168 sequences hit all 7. C7 says no.
  L2 most 2 lines, 3095568 sequences at 2 under R7's cut: q 2, 861
     (G, f0) pairs, 2047632 at 2; q 4, 849, 640640; q 8, 689, 13312;
     q 3, 103, 385236; q 9, 115, 8748. S2 26392 runs, 0 hiding.
  L3 most 4 at l = 2, 3 at l = 3; the kill misses. Sequences by lines
     hit: (4, 4, 4) q 2, 4 f0, {0: 512, 1: 11776, 2: 29184, 3: 7680};
     (8, 8, 8) q 2, 16 f0, {0: 2048, 1: 1624064, 2: 8699904,
     3: 6057984, 4: 393216}; (8, 8, 8) q 4, 16 f0, {0: 196608,
     1: 4390912, 2: 10223616, 3: 1966080}; (9, 9, 9) q 3, 18 f0,
     {0: 26244, 1: 2847474, 2: 18895680, 3: 6928416}. B(2, 3) = 4 is
     reached at (8, 8, 8) q 2; B(3, 3) = 5 is not reached.
  L4 R13 0 off, read at 8640 sequences hitting all l + 1 lines (every
     one at (8, 8) q 4 x^3 + 4, 512, and (4, 4) q 2, 128; 2000 drawn of
     39936 at (8, 8) q 2, of 8192 at (8, 8) q 4, of 458752 at (16, 16)
     q 4, of 314928 at (27, 27) q 3). (9, 9) q 3, 18 f0: most 3 lines,
     {0: 2916, 1: 106434, 2: 209952, 3: 34992}; (27, 27) q 3, 9 f0:
     {0: 1458, 1: 3209058, 2: 9430344, 3: 6176088, 4: 314928}, so the
     TRANSPLANT held: q 3 reaches all 4 lines, at (27, 27) only. (9, 9)
     cannot (by hand): a generating sequence reads its factors l^(e+1),
     so M_C = C (a non-generating one spans a group whose qH is cyclic,
     one line), and beta^k lies in lO0 for k >= 3 (f0 = x^3 mod l), so
     hits fall at k = 0, 1, 2 only, at most 3 lines. The same count caps
     L3's (4, 4, 4) q 2, (8, 8, 8) q 4 and (9, 9, 9) q 3 at 3, which is
     why B(3, 3) = 5 is not reached; B(2, 3) = 4 is, above l^(e+1).
  BN C11: open at 84096 sequences. 0 open: default 351174 sequences
     over 16 (G, a0) pairs; --full 1014174 over 237.
  G  C12 passes (15 closed <h> in all), C13 prints a bare list of eight
     with no closed <h>, largest g_d 5; C14 fires at 7680 of 7680, C15
     at 6511, C16 at 20662: each reader can say no. G1, G2, G3 0 fails
     over 604952 generating sequences: 1536 (4, 4), 344064 (8, 4),
     122880 (8, 8) q 2, 122472 (9, 9) q 3, and 2000 drawn at each of
     the seven drawn arms. D = 0, 1, 2 at 410548, 131362, 63042, each
     class at every arm. G4: a closed <h> in R at every one. g_d > l at
     3174, all at q 2 (3072 (8, 8), 13 (16, 8), 89 (16, 16)), each
     over-full depth holding a degenerate D gate (by G1 and G2's zero
     fails; the print sums 3072, 13, 90 such terms there); some |A_d| falls to 1
     at 3072, 13 and 38 of them, never to 0. A degenerate D gate lies in
     R at q 3 only in the (27, 27) draws (96, 93, 111), never over-full,
     and at none of q 5's.
  K  0 hiding: kept 419112 (q 2, order <= 16), 144012 (q 3, <= 27),
     419112 (q 4, <= 16), 4128768 (q 4, order 32, a1, a2 even); each
     count holds every initial triple reaching 0, the zero sequence,
     the non-generating ones (which cannot hide) and automorphic
     copies among them.
  A  0 hiding: 416 (G, f0) pairs, 105119744 sequences under R7's cut.
  B  0 hiding: 384 pairs, 100663296 sequences.
  C  0 hiding: 81 pairs, 43046721 sequences (at exp 27, a_0 = 9u reads
     u mod 3 only, so the three u are one).
  D  (--full) 0 hiding: 1216 pairs, 1212153856 sequences.
  E  (--full) 0 hiding: q = 4, 400 pairs, 1782579200 sequences under
     R7's cut; q = 8, 64 pairs, 20971520; q = 9, 81 pairs, 172186884.
  The kill misses at every family: GC holds at this scale, a pattern
  at r >= 3; at r <= 2 it is T2 below, at x^3 + a0 T4.

DERIVED (by hand: GC at r <= 2, T2; not at full rank, T3; at x^3 + a0,
T4; toward r >= 3).
  D1 RS is the quotients of U = O/beta^t O by its subgroups H, g_k the
     class of beta^k: U is generated by 1, ..., beta^(t-1) under f's
     relations and beta^t = 0. T_t is a complete residue system of U
     (O/beta O = Z/q), so with Z = [0, t) - W*, T_(W*) + T_Z = U once
     each, and W* hides U/H iff T_(W*) + H covers U m = |H|/q^|Z| times.
  D2 V_k = <g_k, g_(k+1), ...> has V_k/V_(k+1) cyclic on g_k of order
     n_k | q, as in the ring. A character built down from V_(t-1) meets
     a constraint only at k in W* with n_k < q: there q chi(g_k) =
     (q/n_k) chi(n_k g_k) is fixed before chi(g_k) is chosen.
  D3 The filtration alone does not carry GC: a no-depth miss's g_0,
     ..., g_5 with elements z, q z = 0, appended to span the q g_k
     satisfies q y_i in <y_(i+1), ...> for every i, and its window
     still hides. A proof must use f's recurrence past u = max W*.
  D4 In a least counterexample every nonzero subgroup K has a chain
     over W* started at K that reaches G (the quotient G/K is smaller),
     so every subgroup of order l is <q g_k> for some k in W*.
  R5 S <= G is CLOSED when k in W*, q g_k in S imply g_k in S. A
     nonzero proper closed S reduces GC at G to GC at G/S (in RS): a
     witness chi of G/S for W*(G/S) lifts, since at k in W* with
     q g_k in S, g_k is in S and chi(g_k) = 0. So a least
     counterexample has none (D4 is |S| = l).
  R6 (case A) If an invariant factor of G has order <= q, (qG)[l] is
     not G[l], and a line of G[l] outside qG is closed (no q g_k lies
     in it). So a least counterexample is CASE B: every invariant
     factor exceeds q, every line of G[l] is <q g_k> with o_k = e + 1
     (ord g_k = l^(o_k)).
  R8 The closure of qG (the least closed subgroup over it) is qG +
     <g_k : k in W*>: every k in W* enters at once. So in a least
     counterexample the g_k, k in W*, generate G.
  R9 T_t = T_(W*) + T_Z is a complete residue system of U (D1), so in
     G, mu_(W*) * mu_Z = |H| u_G (mu_S the image of T_S counted with
     multiplicity, u_G uniform). For k in Z, D g_k covers <g_k>
     q/ord(g_k) times, and a sum of uniform measures on subgroups is
     uniform on their sum: mu_Z is a multiple of u_(G_Z), G_Z =
     <g_k : q g_k = 0>. So W* hides G iff mu_(W*) is invariant under
     translation by G_Z, and a witness is nonzero on G_Z.
  R10 (the dual) U^ is the f0-sequences c in Q_l/Z_l with c_k = 0 for
     k >= t, G^ a subgroup of it, c_k = chi(g_k). q c_k is fixed by
     c_(k+1), ..., c_(k+r) (a_0 = q times a unit), so the last nonzero
     term of every c is killed by q, and a witness's last nonzero term
     sits off W*.
  R12 For a full lattice M in O0 (x) Q_l, the beta^k (k >= 0) in
     M - lM put their images on at most B(l, r) = 1 + (l^(r-1) - 1)/
     (l - 1) lines of M/lM. With i the least such k, every later one
     lies in N = beta^(i+1) O0 cap M, whose image in M/lM is proper:
     else N + lM = M, so N = M (Nakayama), beta^i lies in
     beta^(i+1) O0 and, f0(0) != 0 (R1) letting beta^i cancel, beta
     is a unit of O0, but l | f0(0). So the
     later lines lie in a hyperplane. No window and no nilpotence is
     read. L2 prints the bound at r = 2, L3 at r = 3, where C6 shows
     the hypothesis l | f0(0) bites.
  T2 (GC at r <= 2) q = l^e, f0 monic of degree <= 2 over Z_l,
     l | f0(0), G a finite l-group, g_k obeying f0's recurrence, W
     finite: W* never hides G != 0; no nilpotence is used (S2 sweeps
     it). If the g_k span a proper subgroup, a chi != 0 vanishing on
     it is a witness; else G = O0/L, L the kernel of x^k -> g_k (a
     Z_l-lattice, not always an ideal), rank <= 2. R5 and R6 read
     only G, the g_k and W*, and a quotient keeps f0 and W, so a
     least counterexample is case B of rank 2 (R2), each of the l + 1
     >= 3 lines of G[l] some <q g_k>. Both invariant factors above q
     put L in l^(e+1) O0; with M = l^-(e+1) L, x -> l^e x maps M/lM
     onto G[l] = l^e M / l^(e+1) M, and <q g_k> is a line iff beta^k
     lies in M - lM, the line of beta^k mod lM. R12 allows two. No
     invertibility of lattices enters, so a double root of f0 costs
     nothing. With H1, the depth side holds wherever f's local factor
     has degree <= 2.
  T3 (no least counterexample at full rank) q = l^e, f0 monic of
     degree r over Z_l, l | f0(0): a least counterexample has
     2 <= rank G <= r - 1. At rank r it is case B (R6), L lies in
     l^(e+1) O0 and T2's map carries M/lM onto G[l], whose
     (l^r - 1)/(l - 1) lines are each some <q g_k> (D4); R12 reaches
     l^(r-1) - 1 fewer. Rank 1 is R2; at r = 2, T3 is T2.
  R13 (rank 2 <= s < r, case B) A Smith basis puts L = P + L_C, P
     spanned by r - s basis vectors, L_C inside l^(e+1) C, C spanned by
     the rest; pi: O0 -> C along P. Then M cap O0 = P + M_C and
     lM cap O0 = P + l M_C (e >= 1), M_C = l^-(e+1) L_C, so q g_k spans
     a line iff pi(beta^k) lies in M_C - l M_C, read in M_C/l M_C.
     With i the least such k, later hits lie in
     N_C = pi(beta^(i+1) O0) cap M_C; if its image is proper they lie
     in a hyperplane, too few lines; else N_C = M_C (Nakayama) and
     beta^i lies in beta^(i+1) O0 + P: P, inside L, holds
     beta^i - beta^(i+1) y, so g_i lies in V_(i+1). A least
     counterexample of rank s < r has V_i = V_(i+1). Where
     l^(s-1) >= 3 the next hit i' must pass the same test (else at
     most 2 + (l^(s-1) - 1)/(l - 1) lines, l^(s-1) - 2 too few), so at
     s = r - 1, P a line, beta^(i' - i) = l^m eta, eta a unit of O0;
     at e = 1 (f0 Eisenstein) beta^3 is l times a unit, so this alone
     kills nothing. L4 reads R13. The rank-2 case is open: at r = 3
     beta^m mod l ranges over <beta, beta^2>, and G = Z/8 x Z/8,
     f0 = x^3 + 4, g = (1,0), (0,1), (1,1) puts q g_0, q g_1, q g_2 on
     all three lines (C4).
  R14 (the closure reduction) Every nonzero closed S holds a line of
     G[l] and that line's closure (S <- S + <g_k : k in W*, q g_k in S>,
     to a fixed point), so by R5 a least counterexample is CLOSURE-FREE:
     every line's closure is G, l + 1 of them at rank 2. That puts every
     line hit (an unhit line is closed) and the g_k, k in W*, generating
     G, so it subsumes D4, R6, R8 and R13. W* read over the whole
     sequence is the hardest case: a window's closures are smaller. In
     R13's lattices at s = 2, P = Z_l p, c_k = pi(beta^k), G = C/L_C: W*
     = {k : c_k not in lM_C}, the hits are the c_k in M_C - lM_C, and a
     lattice X, L_C <= X <= C, is closed iff no k in W* has c_k in (l^-e
     X cap C) - X. With R2 and T3, GC at every cubic local factor
     follows from: no rank-2 case-B sequence is closure-free (dualpw.py
     reads PW, which implies it, at q = 2, 4, 8, exponent <= 32). At G =
     (Z/l^(e+1))^2 none is: g_k lies in lG for k >= 3 (l | a_i),
     so W* lies in {0, 1, 2}; where a line is unhit (always at l >= 3),
     any <h>, h not in lG, through it is closed (each q g_k, k in W*,
     has order l off that line); at l = 2 with three lines hit <g_0> is
     closed, q g_1
     and q g_2 lying off its line, and g_0 is not in lG.
  R15 (the primitive witness) If G/K is cyclic, the character chi with
     kernel K is a witness iff K is closed: at k in W*, chi(g_k) = 0 iff
     g_k is in K, and q chi(g_k) = 0 iff q g_k is. At rank 2, <h> is
     such a K, K != G, whenever h is not in lG. In R14's lattices h
     lifts to a primitive d, Z_l d = ker rho with rho a primitive functional
     and n = v(rho(L_C)) >= e + 1; g_k lies in <h> iff v(rho(c_k)) >= n
     and q g_k does iff v(rho(c_k)) >= n - e. So PW (some such <h>
     closed, read by dualpw.py) says: some scalar f0-sequence rho(c_k)
     avoids the valuations n - e, ..., n - 1 on W*.
  T4 (the binomial factor) At f0 = x^3 + a0 mod exp G, GC holds. Here
     g_(3a+i) = (-a0)^a g_i, so every term lies in <g_0>, <g_1> or
     <g_2>, and a chi != 0 that is 0 or injective on each of the three
     is a witness: at k in W*, q g_k != 0 lies in some <g_i>, so
     q chi(g_k) != 0 unless chi kills <g_i>. At rank 2 take chi with
     kernel K = <h>, h not in lG (R15). Every line of G[l] is some
     <h>[l] (on Z/l^m1 x Z/l^m2, m1 >= m2: h = (1, 0) gives
     (l^(m1-1), 0), and h = (l^(m1-m2) t, 1) gives (l^(m1-1) t,
     l^(m2-1))), and K meets <g_i> trivially iff K[l] is not the line
     L_i of <g_i>. If some line is no L_i, K goes through it; else l = 2
     and L_0, L_1, L_2 are the three lines, and any K holding g_0 (some
     does: g_0 = l^a h) kills <g_0> and meets the others trivially.
     The step reads only that the terms lie in at most l + 1 cyclic
     subgroups: no invariant factor, generation or nilpotence. Rank 1 is
     R2, rank 3 T3, and a quotient keeps a1 = a2 = 0, so GC holds
     wherever f's l-adic factor is x^3 + a0 (among integer cubics f =
     x^3 +/- q); with H1 so does the depth side. BN reads K.
  R16 (the edge) Let q = l (e = 1), so f0 is Eisenstein, O0 = Z_l[beta]
     a DVR with l O0 = beta^3 O0; G = O0/L of rank 2 with invariant
     factors l^N1 >= l^N2 >= l^2; p in L spans L mod l, p = beta^D eps
     (D <= 2, eps a unit). C = (O0 (x) Q_l)/Q_l p, pi the projection,
     c_k = pi(beta^k), O_C = pi(O0), L_C = pi(L), G = O_C/L_C (p
     primitive, so Q_l p cap O0 = Z_l p). Omega_k = pi(beta^k O0) =
     <c_k, c_(k+1), c_(k+2)>, Omega_(k+3) = l Omega_k, each step of index
     <= l, and pi(l^a p) = 0 gives xi_0 c_(D+3a) + xi_1 c_(D+3a+1) +
     xi_2 c_(D+3a+2) = 0, xi = w^a eps (w = l/beta^3), xi_0 a unit: the
     step at D+3a is trivial, the other two have index l. So every
     Omega_k is l^a Omega or l^a Omega' (Omega = Omega_D, Omega' =
     Omega_(D+2)), the two ends of one edge e of the Bruhat-Tits tree
     of C, and o = [O_C] is [Omega] at D = 0, 2, [Omega'] at D = 1.
  R17 (the sides) c_(D+3a+1) lies in l^a Omega - l^a Omega', c_(D+3a+2)
     in l^a Omega' - l^(a+1) Omega: the end [c_k] of the D+1 class lies
     on Omega's side of e, of the D+2 class on Omega''s side. A D-class
     c_(D+3a) = gamma_1 c_(D+3a+1) + gamma_2 c_(D+3a+2), gamma_i =
     -xi_i/xi_0, lies on Omega's side iff l does not divide gamma_1, else
     on Omega''s side or, where l divides both (DEGENERATE; then g_k
     lies in V_(k+3)), in l^(a+1) Omega, a level up.
  R18 (the gates) The subgroups of G are the lattices L_C <= M <= O_C,
     the cyclic ones of order l^d the vertices at distance d from
     v0 = [L_C], and the <h>, h not in lG, of order l^N2 those at
     distance N2 with v0 on the geodesic from o (the CONE; at N1 = N2,
     v0 = o and every vertex at distance N2). Such an <h> is closed (R5)
     iff its chain l^j <h> never passes a GATE, the vertex <l g_k> at
     depth n_k - 1 (k in W*, l^(n_k) = ord g_k), without taking its
     direction <g_k>.
  R19 (the region) R is the cone, or at N1 = N2 the <h> on o's side
     (h not in H', H' the one V_k of index l in G). R lies on one side
     of e, and only ends on that side put gates on R's chains, so one
     non-D class X gives gates, the other none. An end l^j x0 in the
     cone, x0 primitive in O_C, has order l^(N2 - j), and the X term at
     level a has j = a + const: one X gate per depth. A non-degenerate
     D term sits at its level's X depth. So a depth holds at most 2
     gates unless a degenerate D term LANDS there from a deeper level:
     it rises m(a) >= 1 levels, w^(-a) eps^(-1) in Z_l + l^m O0.
  T5 (survival) R's root has l children in R (the cone: all but the one
     toward o; at v0 = o, all but o'), every later vertex l. With A_d the
     depth-d vertices some chain of R reaches past no broken gate, a
     gate removes at most l - 1 children and two at one vertex all
     l <= 2(l - 1), so |A_(d+1)| >= l |A_d| - (l - 1) g_d, g_d the
     distinct gates at depth d, none at depth 0. If g_d <= l at every
     depth, |A_d| >= l throughout: some <h> in R is closed, a witness
     (R15). With R19 that holds at every sequence with no degenerate D
     gate in R, and wherever at most l - 1 D gates share a depth.
  R20 (the landers; derived after G's run, never run) g_(D+3a) =
     l^a pi(beta^D w^(-a)), so a D term rises m(a) = delta(w^(-a)
     eps^(-1)) levels, delta(u) = max{m : u in Z_l + l^m O0}, which is
     an ultrametric closeness on O0^x/Z_l^x. The degenerate levels are
     one class mod P or none, P the order of w in (O0/l)^x/F_l^x (P | l
     at l odd, P | 4 at l = 2), all or none at P = 1. Two D terms land on
     one level a < a' only if t = a' - a has P | t and m(a) = t + m(a'),
     m(a') = delta(w^(-t)) (at l odd mu + v_l(t/P), mu = delta(w^P)). At
     l = 3 a depth over-fills (X, its level's D and two landers, or three
     landers) only at exponent >= 3^6 (P = 3, mu = 1, t = 3, m(a) = 4);
     at l = 2 one lander beside its level's X and D already does, and
     there no count of gates alone decides.
  Case B stays open at 2 <= rank G <= r - 1, r >= 3, past T4 and, at
  e = 1, past T5's hypothesis. The aim,
  seen and not printed here: at r = 3, over the cubic local factors
  (a_0 = q, a_1, a_2 even), every
  generating eventually-zero sequence of (8, 8), (16, 8), (16, 16),
  (8, 8, 8) at q = 4 and (16, 16) at q = 8, under R7's cut, had a
  witness chi with chi(g_s) != 0, s the sequence's last k with
  g_k != 0, and one of order exp G, each found apart. The sequences
  with every line of G[l] some <q g_k> have q^|W*| = |G| at (8, 8),
  where Hajos's theorem kills a hiding, and q^|W*| > |G| at (16, 8) at
  q = 4 and (16, 16) at q = 4, 8, where it does not reach.

RUN RECORD. G alone: 24.1 s, 37.4 MB. Default 26/26, 133.4 s,
86.3 MB; D 288.3 s, 67.6 MB, under a memory guard. E (--full), its
three family() calls run alone: 400, 64, 81 (G, f0) pairs, hiding 0
at each, 1789.5 s, peak 249.4 MB, nearly all of it q = 4.
"""

import os
import random
import sys
import time
from itertools import product

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import numpy as np  # noqa: E402

CHECKS = []
CHUNK = 1 << 18


def check(name, ok, detail=""):
    CHECKS.append(bool(ok))
    print(f"  {'PASS' if ok else 'FAIL'}  {name}" +
          (f"  ({detail})" if detail else ""), flush=True)


def groups(l, top, exact=False):
    """Every product of cyclic l-groups of order <= top (== top if
    exact), as moduli lists, largest first."""
    out = []

    def rec(rest, cap, cur):
        if cur and (not exact or rest == 0):
            out.append(tuple(l ** x for x in cur))
        for e in range(min(cap, rest), 0, -1):
            rec(rest - e, e, cur + [e])
    e = 0
    while l ** (e + 1) <= top:
        e += 1
    rec(e, e, [])
    return out


class Group:
    """G = prod Z/m_i, elements as indices 0..N-1 (0 the identity)."""

    def __init__(self, ms):
        self.ms = ms
        self.E = max(ms)
        self.els = np.array(list(product(*[range(m) for m in ms])),
                            dtype=np.int64)
        self.N = N = len(self.els)
        st = np.cumprod([1] + [m for m in ms[::-1]])[:-1][::-1]
        self.st = np.array(st, dtype=np.int64)
        self.add = self.index(self.els[:, None, :] +
                              self.els[None, :, :]).ravel()
        R = self.els * np.array([self.E // m for m in ms], dtype=np.int64)
        zero = (self.els @ R.T) % self.E == 0          # [x, chi]
        self.W = (N + 63) // 64
        bits = np.zeros((N, self.W * 64), dtype=bool)
        bits[:, :N] = zero
        self.perp = np.packbits(bits.reshape(N, self.W, 64)[:, :, ::-1],
                                axis=2, bitorder="big") \
            .view(">u8").astype(np.uint64).reshape(N, self.W)
        full = np.ones(self.W * 64, dtype=bool)
        full[N:] = False
        full[0] = False                                 # chi = 0
        self.full = np.packbits(full.reshape(self.W, 64)[:, ::-1],
                                axis=1, bitorder="big") \
            .view(">u8").astype(np.uint64).reshape(self.W)

    def index(self, v):
        return ((v % np.array(self.ms, dtype=np.int64)) @ self.st)

    def mul(self, c):
        return self.index(c * self.els)


def homocyclic_firsts(G):
    """R7: on (Z/l^m)^d, g_0 in {0, (l^j, 0, ..., 0)} up to Aut."""
    m, d = G.ms[0], len(G.ms)
    if any(x != m for x in G.ms):
        return None
    out, c = [0], 1
    while c < m:
        out.append(int(G.index(np.array([c] + [0] * (d - 1)))))
        c *= [p for p in range(2, m + 1) if m % p == 0][0]
    return out


def block(G, q, a, ids, nil=True, window=None, terms=64):
    """Run the sequences whose initial r-tuples are the base-N digits
    of ids, g_(k+r) = -(a_0 g_k + ... + a_(r-1) g_(k+r-1)). Returns
    (cover, keep): cover the B_k's union as bitmasks over chi, keep
    whether the sequence reaches 0 (the last r of `terms` zero; run
    until all reach 0 when nil); window: cover only k < window."""
    r, N = len(a), G.N
    mula = [G.mul(-c) for c in a]
    qm = G.mul(q)
    seq = [ids // N ** (r - 1 - j) % N for j in range(r)]
    cover = np.zeros((len(ids), G.W), dtype=np.uint64)
    k = 0
    while True:
        g = seq[k]
        if window is None or k < window:
            qg = qm[g]
            m = G.perp[qg] & ~G.perp[g]
            m[qg == 0] = 0
            cover |= m
        nxt = mula[0][seq[k]]
        for j in range(1, r):
            nxt = G.add[nxt * N + mula[j][seq[k + j]]]
        seq.append(nxt)
        k += 1
        if nil and window is None and k >= r and \
                not any(np.any(s) for s in seq[k:k + r]):
            break
        if k + r >= terms:
            break
    if nil:
        keep = np.all(np.stack([seq[j] == 0 for j in
                                range(len(seq) - r, len(seq))]), axis=0)
    else:
        keep = np.ones(len(ids), dtype=bool)
    return cover, keep


def sweep(G, q, a, nil=True, window=None, terms=64, firsts=None):
    """Every r-tuple of G (g_0 in firsts if given). Returns (kept,
    hiding, first hiding tuple)."""
    r, N = len(a), G.N
    rest = N ** (r - 1)
    blocks = [(f * rest, (f + 1) * rest) for f in firsts] if firsts \
        else [(0, N ** r)]
    kept = hid = 0
    first = None
    for b0, hi in blocks:
        for lo in range(b0, hi, CHUNK):
            ids = np.arange(lo, min(hi, lo + CHUNK), dtype=np.int64)
            cover, keep = block(G, q, a, ids, nil, window, terms)
            hides = np.all(cover == G.full, axis=1) & keep
            kept += int(keep.sum())
            hid += int(hides.sum())
            if first is None and hides.any():
                i = int(ids[np.argmax(hides)])
                first = tuple(tuple(G.els[i // N ** (r - 1 - j) % N])
                              for j in range(r))
    return kept, hid, first


def local_coeffs(l, E, n):
    """Every (a_1..a_n) with l | a_i, read mod E."""
    return list(product(range(0, E, l), repeat=n))


def integer_cubics(q, even=False):
    rng = (-2, 0, 2) if even else range(-2, 3)
    for c0 in (q, -q):
        for a1 in rng:
            for a2 in rng:
                yield (c0, a1, a2)


def popcount(x):
    """Bits set per row of a uint64 array."""
    v = x.view(np.uint8)
    return np.unpackbits(v, axis=-1).reshape(x.shape[0], -1).sum(axis=1)


def brute_witnesses(ms, q, a, tup):
    """Characters chi != 0 with chi(g_k) = 0 or q chi(g_k) != 0 at every
    k with q g_k != 0, by direct arithmetic; the sequence run to 0."""
    E, r = max(ms), len(a)
    s = [list(x) for x in tup]
    while any(any(x) for x in s[-r:]):
        s.append([(-sum(a[j] * s[-r + j][i] for j in range(r))) % m
                  for i, m in enumerate(ms)])
    W = [x for x in s if any((q * xi) % m for xi, m in zip(x, ms))]
    n = 0
    for c in product(*[range(m) for m in ms]):
        if not any(c):
            continue
        vals = [sum(ci * xi * (E // m) for ci, xi, m in zip(c, x, ms)) % E
                for x in W]
        n += all(v == 0 or (q * v) % E for v in vals)
    return n


def control():
    print("C  controls", flush=True)
    t0 = time.time()
    hid = 0
    for ms in groups(2, 16, exact=True):
        G = Group(ms)
        for a in integer_cubics(2):
            hid += sweep(G, 2, a, nil=False, window=8, terms=11)[1]
    check("C1 no nilpotence, W* cut to [0, 8), q 2 order 16: hiding "
          "exists", hid > 0, f"{hid}, {time.time() - t0:.1f} s")
    G = Group((4, 4))
    order = [int(np.lcm.reduce([m // np.gcd(int(x), m) for x, m in
                                zip(e, G.ms)])) for e in G.els]
    cells = off = 0
    for a in integer_cubics(2):
        for f in homocyclic_firsts(G):
            orbit = [x for x in range(G.N) if order[x] == order[f]]
            whole = sweep(G, 2, a, nil=False, window=8, terms=11,
                          firsts=orbit)[1]
            rep = sweep(G, 2, a, nil=False, window=8, terms=11,
                        firsts=[f])[1]
            cells += whole > 0
            off += (whole > 0) != (rep > 0)
    span = {order[f] for f in homocyclic_firsts(G)} == set(order)
    check("C3 R7: one representative per order of g_0, and it hides iff "
          "its orbit does, (4, 4)", span and cells > 0 and off == 0,
          f"{cells} hiding (pair, order) cells, {off} off, every order "
          f"{span}")
    rnd = random.Random(7)
    pairs = [((8, 8), 4, (4, 0, 0)), ((8, 8), 4, (4, 2, 6)),
             ((16, 8), 4, (4, 6, 8)), ((16, 8), 4, (12, 2, 4)),
             ((27, 9), 9, (9, 3, 6)), ((8, 8), 4, (4, 2)),
             ((8, 8), 4, (12, 6)), ((9, 9), 3, (3, 3)), ((9, 9), 3, (6, 0))]
    seen = bad = 0
    counts = set()
    for ms, q, a in pairs:
        G = Group(ms)
        r = len(a)
        ids = np.array(rnd.sample(range(G.N ** r), 3000), dtype=np.int64)
        cover, keep = block(G, q, a, ids, terms=10 ** 6)
        eng = popcount(G.full & ~cover)
        for i in np.where(keep)[0][:120]:
            tup = [tuple(int(x) for x in G.els[int(ids[i]) //
                                              G.N ** (r - 1 - j) % G.N])
                   for j in range(r)]
            b = brute_witnesses(ms, q, a, tup)
            seen += 1
            bad += b != int(eng[i])
            counts.add(b)
    check("CB the nil arm's witness count matches brute force",
          seen > 0 and bad == 0 and len(counts) > 3,
          f"{seen} sequences, {bad} off, {len(counts)} distinct counts, "
          f"least {min(counts)}, {time.time() - t0:.1f} s")
    return time.time() - t0


def section_c2():
    from dualdeg import powers
    from dualn import Base, cubic_bases
    from dualmult import depth
    t0 = time.time()
    n_id = hid = 0
    for a in cubic_bases():
        B = Base(a, 128)
        q = B.q
        for L in B.Is:
            t = depth(L, a, B.pw[1])
            if t is None or L.N == 1:
                continue
            n_id += 1
            pw = powers(a, t + 1)
            gk = [pw[k] for k in range(t)]
            Ws = [k for k in range(t)
                  if any(L.key(tuple(q * x for x in gk[k])))]
            chars = L.characters()[1:]
            N = L.N
            ok = True
            for c in chars:
                vals = [sum(ci * xi for ci, xi in zip(c, gk[k])) % N
                        for k in Ws]
                if not any(v and (q * v) % N == 0 for v in vals):
                    ok = False
                    break
            hid += ok
    check("C2 no ring ideal read at some depth is hidden by its W*",
          n_id > 0 and hid == 0,
          f"{hid} of {n_id}, {time.time() - t0:.1f} s")


def section_k():
    print("K  integer cubics, every triple to 64 terms", flush=True)
    t0 = time.time()
    total = 0
    for q, l, top, even, exact in [(2, 2, 16, False, False),
                                   (3, 3, 27, False, False),
                                   (4, 2, 16, False, False),
                                   (4, 2, 32, True, True)]:
        kept = hid = 0
        for ms in groups(l, top, exact=exact):
            G = Group(ms)
            for a in integer_cubics(q, even):
                k_, h_, _ = sweep(G, q, a)
                kept += k_
                hid += h_
        total += hid
        print(f"    q {q}, order {'' if exact else '<= '}{top}"
              f"{', a1, a2 even' if even else ''}: kept {kept}, hiding "
              f"{hid}, {time.time() - t0:.1f} s", flush=True)
    check("K  no eventually-zero sequence has W* hiding G", total == 0,
          f"{total}")


def line_bits(G, l):
    """Element index -> the bit of its line of G[l] (0 off G[l] - 0),
    and the number of lines."""
    lm, muls = G.mul(l), [G.mul(c) for c in range(1, l)]
    bit = np.zeros(G.N, dtype=np.int64)
    n = 0
    for x in range(1, G.N):
        if lm[x] == 0 and bit[x] == 0:
            for m in muls:
                bit[m[x]] = 1 << n
            n += 1
    return bit, n


def lines_hit(G, q, a, l, firsts=None, terms=None, every=None):
    """Every r-tuple (g_0 in firsts if given), run to 0, or to `terms`
    terms if given: per sequence the number of distinct lines <q g_k>
    with ord q g_k = l, as a histogram {count: sequences}. every: a list
    collecting the ids of the sequences hitting all lines."""
    r, N = len(a), G.N
    bit, n = line_bits(G, l)
    bit = bit[G.mul(q)]
    mula = [G.mul(-c) for c in a]
    rest = N ** (r - 1)
    blocks = [(f * rest, (f + 1) * rest) for f in firsts] if firsts \
        else [(0, N ** r)]
    hist = {}
    for b0, hi in blocks:
        for lo in range(b0, hi, CHUNK):
            ids = np.arange(lo, min(hi, lo + CHUNK), dtype=np.int64)
            seq = [ids // N ** (r - 1 - j) % N for j in range(r)]
            acc = np.zeros(len(ids), dtype=np.int64)
            k = 0
            while (k < terms) if terms else \
                    any(np.any(x) for x in seq[k:k + r]):
                acc |= bit[seq[k]]
                nxt = mula[0][seq[k]]
                for j in range(1, r):
                    nxt = G.add[nxt * N + mula[j][seq[k + j]]]
                seq.append(nxt)
                k += 1
            cnt = sum((acc >> b) & 1 for b in range(n))
            if every is not None:
                every.extend(int(x) for x in ids[cnt == n])
            for c, m in zip(*np.unique(cnt, return_counts=True)):
                hist[int(c)] = hist.get(int(c), 0) + int(m)
    return hist


def span(G, gens):
    """The subgroup of G generated by gens, as a set of indices."""
    out, frontier = {0}, [0]
    while frontier:
        nxt = []
        for x in frontier:
            for g in gens:
                y = int(G.add[x * G.N + g])
                if y not in out:
                    out.add(y)
                    nxt.append(y)
        frontier = nxt
    return out


def run(G, a, i0):
    """The sequence of the initial tuple with id i0, run to 0."""
    r, N = len(a), G.N
    mula = [G.mul(-c) for c in a]
    seq = [i0 // N ** (r - 1 - j) % N for j in range(r)]
    k = 0
    while any(seq[k:k + r]):
        nxt = int(mula[0][seq[k]])
        for j in range(1, r):
            nxt = int(G.add[nxt * N + mula[j][seq[k + j]]])
        seq.append(nxt)
        k += 1
    return seq


def r13(G, q, a, l, i0):
    """Whether g_i lies in V_(i+1), i least with ord q g_k = l."""
    seq = run(G, a, i0)
    qm, lm = G.mul(q), G.mul(l)
    i = next(k for k, g in enumerate(seq)
             if qm[g] != 0 and lm[qm[g]] == 0)
    return seq[i] in span(G, set(seq[i + 1:]))


def section_l2():
    print("L2 lines <q g_k> of order l, r = 2", flush=True)
    t0 = time.time()
    h7 = lines_hit(Group((2, 2, 2)), 1, (0,) * 7, 2, firsts=[1])
    check("C5 the counter reads all 7 lines of (2, 2, 2): q = 1, f = x^7, "
          "seven free terms", max(h7) == 7, f"most {max(h7)}")
    h3 = lines_hit(Group((8, 8)), 4, (4, 0, 0), 2)
    check("C4 r = 3, (8, 8), q 4, x^3 + 4: some sequence hits all 3 "
          "lines", max(h3) == 3, f"histogram {h3}")
    top = two = 0
    for l, q, order, us, extra in [(2, 2, 256, (1, 3, 5, 7), []),
                                   (2, 4, 256, (1, 3, 5, 7), [(32, 32)]),
                                   (2, 8, 256, (1, 3, 5, 7), [(32, 32)]),
                                   (3, 3, 243, (1, 2), []),
                                   (3, 9, 243, (1, 2), [(27, 27)])]:
        pairs, hist = 0, {}
        for ms in [x for x in groups(l, order) if len(x) == 2] + extra:
            G = Group(ms)
            firsts = homocyclic_firsts(G)
            for a0 in sorted({q * u % G.E for u in us}):
                for (a1,) in local_coeffs(l, G.E, 1):
                    for c, n in lines_hit(G, q, (a0, a1), l,
                                          firsts).items():
                        hist[c] = hist.get(c, 0) + n
                    pairs += 1
        top = max(top, max(hist))
        two += hist.get(2, 0)
        print(f"    q {q}, rank 2, order <= {order}"
              f"{''.join(f', {x}' for x in extra)}: {pairs} (G, f0) pairs, "
              f"sequences by lines hit {dict(sorted(hist.items()))}, "
              f"{time.time() - t0:.1f} s", flush=True)
    check("L2 r = 2: no sequence puts q g_k on 3 lines", top <= 2 and
          two > 0, f"most {top}, {two} sequences at 2 under R7's cut")


def section_l3():
    print("L3 lines <q g_k> of order l, r = 3, full rank", flush=True)
    t0 = time.time()
    h = lines_hit(Group((2, 2, 2)), 1, (1, 1, 0), 2, terms=7)
    check("C6 l | f0(0) dropped: q 1, x^3 + x + 1 on (2, 2, 2), 7 terms, "
          "some sequence hits all 7 lines", max(h) == 7, f"histogram {h}")
    top = {}
    for ms, l, q, a0s in [((4, 4, 4), 2, 2, (2,)), ((8, 8, 8), 2, 2, (2,)),
                          ((8, 8, 8), 2, 4, (4,)), ((9, 9, 9), 3, 3, (3, 6))]:
        G = Group(ms)
        firsts = homocyclic_firsts(G)
        hist, pairs = {}, 0
        for a0 in a0s:
            for a1, a2 in local_coeffs(l, G.E, 2):
                for c, n in lines_hit(G, q, (a0, a1, a2), l,
                                      firsts).items():
                    hist[c] = hist.get(c, 0) + n
                pairs += 1
        top[l] = max(top.get(l, 0), max(hist))
        print(f"    {ms} q {q}: {pairs} f0, sequences by lines hit "
              f"{dict(sorted(hist.items()))}, {time.time() - t0:.1f} s",
              flush=True)
    check("L3 full rank r = 3: at most B lines, 4 at l = 2, 5 at l = 3",
          top[2] <= 4 and top[3] <= 5, f"most {top}")


def section_l4(rng):
    print("L4 rank 2 inside cubic f0, case B", flush=True)
    t0 = time.time()
    G = Group((8, 8))
    g0, g1 = (int(G.index(np.array(v))) for v in ((1, 0), (0, 1)))
    check("C7 R13's reader says no: (8, 8) q 4 x^3 + 4, g = (1, 0), "
          "(0, 1), 0 has g_0 off V_1", not r13(G, 4, (4, 0, 0), 2,
                                               g0 * G.N ** 2 + g1 * G.N))
    bad = top3 = 0
    for ms, l, q, a0s, a12 in [
            ((8, 8), 2, 4, (4,), [(0, 0)]),
            ((4, 4), 2, 2, (2,), None), ((8, 8), 2, 2, (2,), None),
            ((8, 8), 2, 4, (4,), None), ((16, 16), 2, 4, (4,), None),
            ((9, 9), 3, 3, (3, 6), None),
            ((27, 27), 3, 3, (3,), [(x, y) for x in (0, 3, 6)
                                    for y in (0, 3, 6)])]:
        G = Group(ms)
        firsts = homocyclic_firsts(G)
        hist, pairs, every, read = {}, 0, [], 0
        for a0 in a0s:
            for a1, a2 in a12 or local_coeffs(l, G.E, 2):
                found = []
                for c, n in lines_hit(G, q, (a0, a1, a2), l, firsts,
                                      every=found).items():
                    hist[c] = hist.get(c, 0) + n
                every.append(((a0, a1, a2), found))
                pairs += 1
        total = sum(len(f) for _, f in every)
        cells = [(a, x) for a, f in every for x in f]
        if total > 2000:
            cells = rng.sample(cells, 2000)
        for a, x in cells:
            read += 1
            bad += not r13(G, q, a, l, x)
        if l == 3:
            top3 = max(top3, max(hist))
        tag = " x^3 + 4" if a12 == [(0, 0)] else ""
        print(f"    {ms} q {q}{tag}: {pairs} f0, sequences by lines hit "
              f"{dict(sorted(hist.items()))}, R13 read at {read} of "
              f"{total} hitting all, {time.time() - t0:.1f} s", flush=True)
    check("L4 R13: every sequence read hitting all l + 1 lines has g_i "
          "in V_(i+1)", bad == 0, f"{bad} off")
    print(f"    q 3, rank 2: most {top3} lines of 4 (TRANSPLANT predicted "
          f"4)", flush=True)


def primitive_cyclics(G, l):
    """R15: every <h> with h not in lG, each once."""
    lG = set(int(x) for x in G.mul(l))
    out, seen = [], set()
    for h in range(G.N):
        if h not in lG:
            S = frozenset(span(G, [h]))
            if S not in seen:
                seen.add(S)
                out.append(S)
    return out


def is_closed(qm, S, elems):
    """R5: k in W*, q g_k in S give g_k in S; elems the W* terms."""
    return all(g in S or int(qm[g]) not in S for g in elems)


def binomial_k(G, seq, cyc, lines):
    """T4's K: a cyclic <h>, h not in lG, through a line no <g_i>[l]
    (i < 3) is, else one holding g_0."""
    taken = set()
    for g in seq[:3]:
        if g:
            taken.add(next(x for x in span(G, [g]) if lines[x]))
    free = [S for S in cyc if not any(x in taken for x in S if lines[x])]
    return free[0] if free else next(S for S in cyc if seq[0] in S)


def section_w(rng_bn, full):
    print("W rank 2 inside cubic f0, x^3 + a0: T4's closed <h>", flush=True)
    t0 = time.time()

    def binomial(G, l, q, a, seqs):
        qm, lm = G.mul(q), G.mul(l)
        lines = [bool(x) and lm[x] == 0 for x in range(G.N)]
        cyc = primitive_cyclics(G, l)
        return sum(not is_closed(qm, binomial_k(G, s, cyc, lines),
                                 [g for g in s if qm[g]]) for s in seqs)

    G = Group((8, 8))
    ctl = binomial(G, 2, 2, (2, 2, 0),
                   (run(G, (2, 2, 0), i0) for i0 in range(G.N ** 3)))
    check("C11 T4's K at x^3 + 2x + 2 on (8, 8), q 2, is open somewhere",
          ctl > 0, f"{ctl} sequences")
    total = fails = pairs = 0
    for l, q, small, big in [(2, 2, 32, 256), (2, 4, 32, 256),
                             (2, 8, 0, 256), (3, 3, 27, 243),
                             (3, 9, 0, 243)]:
        for ms in [x for x in groups(l, big if full else small)
                   if len(x) == 2]:
            G = Group(ms)
            if G.E <= q:
                continue
            for a0 in sorted({q * u % G.E for u in range(1, G.E) if u % l}):
                a = (a0, 0, 0)
                if G.N <= small:
                    ids = range(G.N ** 3)
                else:
                    ids = [rng_bn.randrange(G.N ** 3) for _ in range(3000)]
                fails += binomial(G, l, q, a, (run(G, a, i0) for i0 in ids))
                total += len(ids)
                pairs += 1
        print(f"    BN q {q}: {pairs} (G, a0) pairs so far, {total} "
              f"sequences, {fails} open, {time.time() - t0:.1f} s",
              flush=True)
    check("BN T4's K is closed at every binomial sequence read",
          fails == 0, f"{total} sequences, {pairs} (G, a0) pairs")


def mask_of(idx):
    m = 0
    for i in idx:
        m |= 1 << int(i)
    return m


class Tree:
    """T5's engine: G's cyclic subgroups as bitmasks, the <h>, h not in
    lG, of order l^N2, and a memo for the joins V_k = V_(k+1) + <g_k>."""

    def __init__(self, G, l):
        self.G, self.l, N, E = G, l, G.N, G.E
        self.A2 = G.add.reshape(N, N)
        self.M = np.array([G.mul(j) for j in range(E)])     # [j, x]
        self.ml = ml = G.mul(l)
        ordx = np.zeros(N, dtype=np.int64)
        for x in range(1, N):
            y, o = x, 0
            while y:
                y, o = int(ml[y]), o + 1
            ordx[x] = o
        self.ordx = ordx
        self.cyc = [mask_of(set(self.M[:, x])) for x in range(N)]
        ids = {}
        self.cid = [ids.setdefault(c, len(ids)) for c in self.cyc]
        lG = set(int(v) for v in self.ml)
        self.n1 = int(ordx.max())
        self.n2 = int(min(ordx[G.index(np.eye(len(G.ms), dtype=np.int64)
                                       [i])] for i in range(len(G.ms))))
        seen, self.P = set(), []
        for h in range(N):
            if h in lG or self.cyc[h] in seen:
                continue
            seen.add(self.cyc[h])
            if ordx[h] == self.n2:
                self.P.append((h, self.cyc[h]))
        self.memo = {}

    def join(self, V, g):
        key = (V, g)
        if key not in self.memo:
            els = [i for i in range(self.G.N) if V >> i & 1]
            mul = self.M[:, g]
            self.memo[key] = mask_of(np.unique(self.A2[np.ix_(els, mul)]))
        return self.memo[key]


def suffixes(T, seq):
    """V_k as bitmasks, k = 0..len(seq) (V_len = 0)."""
    V = [0] * (len(seq) + 1)
    V[-1] = 1
    for k in range(len(seq) - 1, -1, -1):
        V[k] = T.join(V[k + 1], seq[k])
    return V


def closed_ks(T, R, seq, q):
    """The <h> in R (as (h, mask)) closed for W* = {k : q g_k != 0}."""
    mq = T.G.mul(q)
    W = [(int(mq[g]), g) for g in seq if mq[g]]
    return [K for K in R
            if not any(K[1] >> x & 1 and not K[1] >> g & 1 for x, g in W)]


def brute_closed(T, R, seq, q):
    """The <h> in R whose character (a generator of <h>^perp) is a
    witness, by direct arithmetic on character values."""
    G, E = T.G, T.G.E
    sc = np.array([E // m for m in G.ms], dtype=np.int64)
    vals = (G.els * sc) @ G.els.T % E                  # [chi, x]
    mq = G.mul(q)
    W = [g for g in seq if mq[g]]
    out = []
    for h, Km in R:
        perp = np.flatnonzero(vals[:, h] == 0)
        chi = perp[np.argmax(T.ordx[perp])]
        if all(vals[chi, g] == 0 or (q * vals[chi, g]) % E for g in W):
            out.append((h, Km))
    return out


def gates(T, R, seq, V, D):
    """R18's gates in R: (depth, key, class, level, degenerate)."""
    out = []
    for k, g in enumerate(seq):
        if T.ordx[g] < 2:
            continue
        x = int(T.ml[g])
        if not any(K[1] >> x & 1 for K in R):
            continue
        c, a = (k - D) % 3, (k - D) // 3
        deg = c == 0 and bool(V[min(k + 3, len(seq))] >> g & 1)
        out.append((int(T.ordx[g]) - 1, (T.cid[x], T.cid[g]), c, a, deg))
    return out


def g1_fails(gs):
    """G1's reader: gates of both non-D classes, or two X at one depth."""
    xs = {}
    for d, key, c, a, deg in gs:
        if c:
            xs.setdefault(d, set()).add(key)
    return (len({c for d, key, c, a, deg in gs if c}) > 1 or
            any(len(v) > 1 for v in xs.values()))


def g2_fails(gs, deg_as_d=False, shift=0):
    """G2's reader: two non-degenerate D gates at one depth, or one off
    its level's X depth. Its plants: deg_as_d counts the degenerate ones
    too (C15), shift reads the level clause that many levels off (C16)."""
    xdep = {a: d for d, key, c, a, deg in gs if c}
    per = {}
    for d, key, c, a, deg in gs:
        if c:
            continue
        if not deg or deg_as_d:
            per.setdefault(d, set()).add(key)
        if not deg and a + shift in xdep and xdep[a + shift] != d:
            return True
    return any(len(v) > 1 for v in per.values())


def reach(T, R, seq):
    """|A_d|, d = 0..N2: the depth-d vertices of R's chains no gate
    above depth d has broken."""
    l, n2 = T.l, T.n2
    W = [(int(T.ml[x]), x) for x in seq if T.ordx[x] >= 2]
    out = [set() for _ in range(n2 + 1)]
    for h, Km in R:
        kd = min((int(T.ordx[g]) for x, g in W
                  if Km >> x & 1 and not Km >> g & 1), default=n2 + 1)
        for d in range(min(kd, n2 + 1)):
            out[d].add(T.cid[int(T.M[l ** (n2 - d) % T.G.E, h])])
    return [len(a) for a in out]


def gate_read(T, seq, tally):
    l, N = T.l, T.G.N
    V = suffixes(T, seq)
    if bin(V[0]).count("1") != N:
        return
    tally["seqs"] += 1
    size = [bin(v).count("1") for v in V]
    D = next(k for k in range(3) if size[k] == size[k + 1])
    tally[f"D{D}"] += 1
    if T.n1 == T.n2:
        Hp = next(V[k] for k in (1, 2) if size[k] * l == N)
        R = [K for K in T.P if not Hp >> K[0] & 1]
    else:
        R = T.P
    gs = gates(T, R, seq, V, D)
    tally["g1"] += g1_fails(gs)
    tally["g2"] += g2_fails(gs)
    tally["c15"] += g2_fails(gs, deg_as_d=True)
    tally["c16"] += g2_fails(gs, shift=1)
    per = {}
    for d, key, c, a, deg in gs:
        per.setdefault(d, [set(), 0])[0].add(key)
        per[d][1] += deg
    gmax = max((len(p[0]) for p in per.values()), default=0)
    closed = closed_ks(T, R, seq, l)
    tally["g3"] += gmax <= l and not closed
    tally["g4"] += not closed
    tally["degseq"] += any(x[4] for x in gs)
    if gmax > l:
        tally["over"] += 1
        tally["over_deg"] += sum(p[1] for p in per.values()
                                 if len(p[0]) > l)
        tally["over_open"] += not closed
        tally["over_thin"] += min(reach(T, R, seq)[1:]) == 1


def section_g(rng):
    print("G rank 2 at e = 1: the gate count (R16-T5)", flush=True)
    t0 = time.time()
    G = Group((8, 8))
    T = Tree(G, 2)
    ix = lambda *v: int(G.index(np.array(v)))  # noqa: E731
    seq = run(G, (4, 0, 0), ix(1, 0) * G.N ** 2 + ix(0, 1) * G.N + ix(1, 1))
    a, b = closed_ks(T, T.P, seq, 4), brute_closed(T, T.P, seq, 4)
    ok, n = a == b, len(a)
    for ms in ((4, 4), (8, 4), (8, 8)):
        Gm = Group(ms)
        Tm = Tree(Gm, 2)
        for i0 in range(1, Gm.N ** 3, 97):
            s = run(Gm, (2, 2, 0), i0)
            if bin(suffixes(Tm, s)[0]).count("1") == Gm.N:
                break
        ca, cb = closed_ks(Tm, Tm.P, s, 2), brute_closed(Tm, Tm.P, s, 2)
        ok &= ca == cb
        n += len(ca)
    check("C12 the closure reader agrees with the brute character reader "
          "on C4's sequence and one sequence per q 2 arm", ok,
          f"{n} closed <h> in all, {len(T.P)} <h> per (8, 8) sequence")
    crng, plant = random.Random(17241), None
    for _ in range(200000):
        lst = [crng.randrange(1, G.N) for _ in range(crng.randrange(3, 9))]
        if not closed_ks(T, T.P, lst, 2):
            plant = lst
            break
    gm = 0
    if plant is not None:
        per = {}
        for g in plant:
            if T.ordx[g] >= 2:
                per.setdefault(int(T.ordx[g]) - 1, set()).add(
                    (T.cid[int(T.ml[g])], T.cid[g]))
        gm = max(len(v) for v in per.values())
    check("C13 the reader's no: a bare list in (8, 8) with no closed <h> "
          "among all twelve, its largest g_d above l", gm > 2,
          f"{[tuple(int(c) for c in G.els[g]) for g in plant or []]}, "
          f"largest g_d {gm}")
    fired = read = 0
    for f in homocyclic_firsts(G):
        for rest in range(G.N ** 2):
            s = run(G, (2, 0, 0), f * G.N ** 2 + rest)
            V = suffixes(T, s)
            if bin(V[0]).count("1") != G.N:
                continue
            read += 1
            size = [bin(v).count("1") for v in V]
            D = next(k for k in range(3) if size[k] == size[k + 1])
            fired += g1_fails(gates(T, T.P, s, V, D))
    check("C14 G1's reader fires with R widened to both sides of e "
          "(x^3 + 2 on (8, 8))", fired > 0, f"{fired} of {read} sequences")
    arms = [((4, 4), 2, (2,), None), ((8, 4), 2, (2,), None),
            ((8, 8), 2, (2,), None), ((16, 8), 2, (2,), 2000),
            ((16, 16), 2, (2,), 2000), ((9, 9), 3, (3,), None),
            ((27, 27), 3, (3, 6, 12), 2000), ((27, 9), 3, (3,), 2000),
            ((25, 25), 5, (5,), 2000)]
    keys = ("seqs", "D0", "D1", "D2", "g1", "g2", "g3", "g4", "c15",
            "c16", "over", "over_deg", "over_open", "over_thin", "degseq")
    tot = dict.fromkeys(keys, 0)
    for ms, l, a0s, draw in arms:
        G = Group(ms)
        T = Tree(G, l)
        for a0 in a0s:
            fs = [(a0, a1, a2) for a1 in range(0, G.E, l)
                  for a2 in range(0, G.E, l)]
            t = dict.fromkeys(keys, 0)
            if draw is None:
                firsts = homocyclic_firsts(G) or range(G.N)
                for a in fs:
                    for f in firsts:
                        for rest in range(G.N ** 2):
                            gate_read(T, run(G, a, f * G.N ** 2 + rest), t)
            else:
                while t["seqs"] < draw:
                    gate_read(T, run(G, rng.choice(fs),
                                     rng.randrange(G.N ** 3)), t)
            for k in keys:
                tot[k] += t[k]
            print(f"    {ms} q {l} a0 {a0}: {t['seqs']} generating "
                  f"sequences{' (drawn)' if draw else ''} (D = 0, 1, 2 at "
                  f"{t['D0']}, {t['D1']}, {t['D2']}), |R| <= {len(T.P)}; "
                  f"G1 fails {t['g1']}, G2 {t['g2']}, G3 {t['g3']}; no "
                  f"closed <h> in R at {t['g4']}; a degenerate D gate at "
                  f"{t['degseq']}; g_d > l at {t['over']} ({t['over_deg']} "
                  f"degenerate D terms there, {t['over_open']} with no closed "
                  f"<h>, {t['over_thin']} with some |A_d| = 1); "
                  f"{time.time() - t0:.1f} s", flush=True)
    check("C15 G2's count clause fires with degenerate D gates counted",
          tot["c15"] > 0, f"{tot['c15']} sequences")
    check("C16 G2's level clause fires read one level off",
          tot["c16"] > 0, f"{tot['c16']} sequences")
    check("G1 R's gates: at most one non-D class, one per depth", tot["g1"] == 0,
          f"{tot['g1']} sequences")
    check("G2 one non-degenerate D gate per depth, at its level's X depth",
          tot["g2"] == 0, f"{tot['g2']} sequences")
    check("G3 g_d <= l at every depth leaves a closed <h> in R",
          tot["g3"] == 0, f"{tot['g3']} sequences")
    print(f"  G4 (census) no closed <h> in R at {tot['g4']} of "
          f"{tot['seqs']} (D = 0, 1, 2 at {tot['D0']}, {tot['D1']}, "
          f"{tot['D2']}); g_d > l at {tot['over']}, some |A_d| = 1 at "
          f"{tot['over_thin']}; {time.time() - t0:.1f} s", flush=True)


def section_s2():
    t0 = time.time()
    scan = runs = 0
    for q, l, tops in [(2, 2, (16, 32, 64)), (4, 2, (16, 32, 64)),
                       (3, 3, (27, 81))]:
        for top in tops:
            for ms in groups(l, top, exact=True):
                G = Group(ms)
                for u in range(1, G.E):
                    if u % l == 0:
                        continue
                    for a1 in range(G.E):
                        for win in (8, 12):
                            scan += sweep(G, q, (q * u % G.E, a1), nil=False,
                                          window=win, terms=win + 3)[1]
                            runs += 1
    check("S2 r = 2 without nilpotence, every a_1, W* cut to [0, 8) and "
          "[0, 12): no hiding", runs > 0 and scan == 0,
          f"{runs} runs, {scan} hiding, {time.time() - t0:.1f} s")


def family(name, l, q, r, orders, a0s, only=None):
    t0 = time.time()
    seqs = hid = pairs = 0
    for top in orders:
        for ms in only or groups(l, top, exact=True):
            if len(ms) == 1 or len(ms) > r or max(ms) <= q:
                continue
            G = Group(ms)
            firsts = homocyclic_firsts(G)
            for a0 in sorted({a % G.E for a in a0s}):
                for rest in local_coeffs(l, G.E, r - 1):
                    kept, h, first = sweep(G, q, (a0,) + rest,
                                           terms=10 ** 6, firsts=firsts)
                    seqs += kept
                    pairs += 1
                    if h:
                        hid += h
                        print(f"    HIDES  G {ms}, f0 coeffs "
                              f"{(a0,) + rest}, {h} tuples, first {first}",
                              flush=True)
    print(f"  {name}: {pairs} (G, f0) pairs, {seqs} sequences, hiding "
          f"{hid}, {time.time() - t0:.1f} s", flush=True)
    check(f"{name.split()[0]}  no hiding", hid == 0, f"{hid}")


def main():
    t0 = time.time()
    full = "--full" in sys.argv
    control()
    section_c2()
    section_l2()
    section_l3()
    section_l4(random.Random(4))
    section_w(random.Random(6), full)
    section_g(random.Random(1724))
    section_s2()
    section_k()
    family("A q 4 cubic, order 64", 2, 4, 3, [64], [4])
    family("B q 8 cubic, order 64", 2, 8, 3, [64], [8])
    family("C q 9 cubic, order 81", 3, 9, 3, [81], [9, 36, 63])
    if full:
        family("D q 4 quartic, order <= 32", 2, 4, 4, [16, 32],
               [4 * u for u in range(1, 16, 2)])
        family("E q 4, every invariant factor above q", 2, 4, 3, [0], [4],
               only=[(16, 8), (16, 16), (8, 8, 8), (32, 32)])
        family("E q 8, (16, 16)", 2, 8, 3, [0], [8], only=[(16, 16)])
        family("E q 9, (27, 27)", 3, 9, 3, [0], [9], only=[(27, 27)])
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass, "
          f"{time.time() - t0:.1f} s")
    return 0 if all(CHECKS) else 1


if __name__ == "__main__":
    sys.exit(main())