typedef unsigned char uc;
typedef unsigned int ui;
static const uc irp = 27;
static uc fmul(char a, ui b){uc sm=0;
  while(b) {if(b&1) sm ^= a; a = (a<<1)^((a>>7)&irp); b>>=1;}
  return sm;}
uc dt[]={
   0,   1, 141, 246, 203,  82, 123, 209, 232,  79,  41, 192, 176, 225, 229, 199,
 116, 180, 170,  75, 153,  43,  96,  95,  88,  63, 253, 204, 255,  64, 238, 178,
  58, 110,  90, 241,  85,  77, 168, 201, 193,  10, 152,  21,  48,  68, 162, 194,
  44,  69, 146, 108, 243,  57, 102,  66, 242,  53,  32, 111, 119, 187,  89,  25,
  29, 254,  55, 103,  45,  49, 245, 105, 167, 100, 171,  19,  84,  37, 233,   9,
 237,  92,   5, 202,  76,  36, 135, 191,  24,  62,  34, 240,  81, 236,  97,  23,
  22,  94, 175, 211,  73, 166,  54,  67, 244,  71, 145, 223,  51, 147,  33,  59,
 121, 183, 151, 133,  16, 181, 186,  60, 182, 112, 208,   6, 161, 250, 129, 130,
 131, 126, 127, 128, 150, 115, 190,  86, 155, 158, 149, 217, 247,   2, 185, 164,
 222, 106,  50, 109, 216, 138, 132, 114,  42,  20, 159, 136, 249, 220, 137, 154,
 251, 124,  46, 195, 143, 184, 101,  72,  38, 200,  18,  74, 206, 231, 210,  98,
  12, 224,  31, 239,  17, 117, 120, 113, 165, 142, 118,  61, 189, 188, 134,  87,
  11,  40,  47, 163, 218, 212, 228,  15, 169,  39,  83,   4,  27, 252, 172, 230,
 122,   7, 174,  99, 197, 219, 226, 234, 148, 139, 196, 213, 157, 248, 144, 107,
 177,  13, 214, 235, 198,  14, 207, 173,   8,  78, 215, 227,  93,  80,  30, 179,
  91,  35,  56,  52, 104,  70,   3, 140, 221, 156, 125, 160, 205,  26,  65,  28};

void LagCoef(int n, uc r, uc av[n], uc coef[n]){
  for(int i=0; i<n; ++i) {uc p=1, q=1;
    for(int j=0; j<n; ++j) if(i^j) {
      p = fmul(p, r^av[j]);
      q = fmul(q, av[i]^av[j]);}
    coef[i] = fmul(p, dt[q]);}}

// Demos:
#if 0
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void rp(int n, uc ans[n]){ // Random permutation geberator
  uc ra[n]; {int j=n; while(j--) ra[j]=j;}
  {int i=n; while(i--){
     int f = random()%(i+1); ans[i] = ra[f]; ra[f] = ra[i];}}}

uc val(int n, uc coef[n], uc v[n]){uc s=0;
  for(int j=0; j<n; ++j) s ^= fmul(coef[j], v[j]);
return s;}

void p(char * m, int n, uc w[n]){for(int j=0; j<n; ++j) printf("%d ", w[j]);
  printf("%s\n", m);}

static void tc(int n, int q) { // n = payload, q = quorum
assert(n+q <= 256);
uc a[256];
for(int j=0; j<256; ++j) a[j] = j;
if(1) rp(256, a);
uc d[n+q]; for(int j=0; j<n; ++j) d[j] = random()&255;
if(0) p("d", n, d);
for(int j=n; j<n+q; ++j) {uc c[n]; LagCoef(n, a[j], a, c);
if(0) p("lc", n, c);
  d[j] = val(n, c, d);} // that produced the aux portions.
if(0) p("aux", q, d+n);
uc A[n+q], D[n+q];
{uc pr[n+q]; if(1) rp(n+q, pr); else for(int j=0; j<n+q; ++j) pr[j]=j;
   if(0) p("pr", n+q, pr);
   for(int j=0; j<n+q; ++j) {A[j] = a[pr[j]]; D[j] = d[pr[j]];}}
if(0) p("D", n+q, D);
if(0) p("A", n+q, A);
for(int j=n; j<n+q; ++j) {uc c[n]; LagCoef(n, A[j], A, c);
  if(0) p("c", n, c);
  {uc r = D[j], C = val(n, c, D); if(r^C) exit(printf("bug %d %d\n", r, C));}}}

int main(){
for(int y=0; y<601; ++y) tc(17, 5);
  printf("Good\n");
  return 0;}
#endif

#if 0 // sanity check and reciprocal generation (dt).
#include <stdio.h>
#include <assert.h>
int main(){
uc dt[256]; for(int j=0; j<256; ++j) dt[j]=0;
for(int a=0; a<256; ++a) {assert(fmul(1, a) == a);
for(int b=0; b<256; ++b) {uc ab = fmul(a, b);
for(int c=0; c<256; ++c) {
    assert(fmul(ab, c) == fmul(a, fmul(b, c)));
    assert(fmul(a, b^c) == (ab^fmul(a, c)));}
assert(ab == fmul(b, a)); if(ab==1) dt[a]=b;}}
for(int j=1; j<256; ++j) if(!dt[j]) printf("no div: %02x\n", j);
for(int j=0; j<256; ++j) {if (!(j&15)) printf("\n"); printf("%4d,", dt[j]);}
printf("\n");
return 0;}
#endif

#if 0
(define (p m v) (write (list m v)) (newline) v)
(define (p->i P) (let ((w (vector-length P))) (let m ((n 0))
        (if (= w n) 0 (+ (vector-ref P n) (* 2 (m (+ n 1))))))))
(define (i->p n) (let r ((k n)(s 0)) (if (zero? k) (make-vector s)
         (let ((x (r (quotient k 2)(+ s 1)))) (vector-set! x s (remainder k 2)) x))))
(define gf ((fileVal "GFpq") 2 8 "fuzz"))
(define Lc (apply (fileVal "LagCoef") gf))
(define (LC S a) (map p->i (Lc (map i->p S) (i->p a))))
(define coe (LC (list 0 1) 2))
[apply (lambda (sg zer zer? one add negate times invert) 
 (let ((add (lambda A (p->i (apply add (map i->p A)))))
       (times (lambda A (p->i (apply times (map i->p A))))))
(letrec ((ip (lambda (a b) (if (null? a) 0 (add (times (car a) (car b))
     (ip (cdr a)(cdr b)))))))
  (LC (list 2 1) 0)))) gf]
#endif