#include"lib.h"

char dbl[1000];
int skip[MAX], map[40], l;

int min(int a, int b){ return a < b ? a : b; }
int max(int a, int b){ return a > b ? a : b; }
int ceil32(int a, int b){ return (a+b-1)/b; }
int64_t ceil64(int64_t a, int64_t b){ return (a+b-1)/b; }

int pgcd(int a, int b){
  if((a < 0) || (b <= 0)){ printf("!!! pgcd: a=%d b=%d \n", a, b); exit(1); }
  while(a){
    l = a;
    a = b%a;
    b = l;
  }
  return b;
}//*/

void date(char* ch){
  printf("%s: ", ch);
  fflush(stdout);
  system("date \"+\%d/\%m/\%Y \%H/\%M/\%S\"");
}//*/

void my_mpf_root(mpf_t res, mpf_t a, int n){
  mpz_t zz;
  mpz_init(zz);
  mpz_set_f(zz, a);
  mpf_mul_2exp(res, a, 100*n);
  mpz_set_f(zz, res);
  mpz_root(zz, zz, n);
  mpf_set_z(res, zz);
  mpf_div_2exp(res, res, 100);
}

void my_mpz_root(mpf_t res, mpz_t a, int n){
  mpz_mul_2exp(a, a, 100*n);
  mpz_root(a, a, n);
  mpf_set_z(res, a);
  mpf_div_2exp(res, res, 100);
}

void mpz_sc_b(mpz_t res, mpz_t *a, tmat *b, int it){
  mpz_set_ui(res, 0);
  for(; --it >= 0; ) if(b[it>>3]&(1<<(it&7))) mpz_add(res, res, a[it]);
}

void mpz_sc(mpz_t res, mpz_t *a, mpz_t *b, int it){
  mpz_mul(res, *a, *b);
  for(; --it > 0; ) mpz_addmul(res, a[it], b[it]);
}

void mpz_v_swap(mpz_t **a, mpz_t **b){
  mpz_t *tmp = *a;
  *a = *b;
  *b = tmp;
}

mpz_t *alloc_vector(int it){
  mpz_t *tmp = (mpz_t*)malloc(it*sizeof(mpz_t));
  for(; it > 0; ) mpz_init(tmp[--it]);
  return tmp;
}

mpz_t *alloc_vector_1(int it){
  mpz_t *tmp = (mpz_t*)malloc(it*sizeof(mpz_t));
  for(; it > 0; ) mpz_init_set_ui(tmp[--it], 1);
  return tmp;
}

void iterations(tmat **a, int sm, int k, int l, char *ch){
  int j = 1, i;
  date("iterations");
  mpz_t *v1 = alloc_vector_1(sm), *v2 = alloc_vector(sm), sv;
  mpf_t f1, f2;
  mpf_init_set_ui(f1, sm); mpf_init(f2); mpz_init(sv);
  for(; ; j++){
    for(i = 0; i < sm; i++) mpz_sc_b(v2[i], v1, a[i], sm);
    mpz_set(sv, *v2);
    for(i = 1; i < sm; i++) mpz_add(sv, sv, v2[i]);
    mpf_set_z(f2, sv);
    mpf_div(f1, f2, f1);
    my_mpf_root(f1, f1, l);
    mpf_out_str(stdout, 10, 30, f1);
    printf(" it=%d sm=%d %s", j, sm, ch); date("");
    mpz_v_swap(&v1, &v2);
    mpf_set(f1, f2);
  }
}

int eq(int *g, int *d, int l){
  for(; --l >= 0; ) if(g[l] != d[l]) return 0;
  return 1;
}

int verif(int *t, int l, int p){
  FILE *tmp = fopen("new.txt", "w");
  char c = 'X';
  int k = 0;
  for(; k < l; k++){
    switch(t[k]){
      case 0: c = 'a'; break;
      case 1: c = 't'; break;
      case 2: c = 'c'; break;
      case 3: c = 'g'; break;
    }
    fprintf(tmp, "%c", c);
  }
  fprintf(tmp, "\n");
  fclose(tmp);
  sprintf(dbl, "mreps-2.5/mreps -exp 2 -minperiod %d -allowsmall -noprint new.txt | grep no > /dev/null", p);
  return !system(dbl);
}//*/

int carres(int *m, int i, int mn, int ml){ // mn==-1 pour compter tous les carres
  int nb = 0, a = i, j_c = i, b = i-1, i_c = i-1; // ml = |u| dans le carre uu
  skip[i_c] = j_c; l = i+1;
  while(b >= 0){
    if(m[a] == m[b])
      if(l == 2*a-b){
        if((ml != -1) && (l-a > ml)) return -1; // si tu veux pas de grands carres
        if(nb++ == mn) return -1; // on arrete si nb de carres>max
      }
      else{ a--; b--; continue;}
    if(a == i) b--;
    else{
      while(i_c > a)
        if(m[j_c] == m[i_c])
          // skip[--i_c] = --j_c; // non optimized
          {j_c--; i_c--; skip[i_c] = (m[i_c] == m[j_c] ? skip[j_c] : j_c);} // optimized
        else if(j_c == i) skip[--i_c] = j_c;
        else j_c = skip[j_c];
      a = skip[a];
      if(l < 2*(a-b)) return nb;
    }
  }
  return nb;
}//*/

int rep(int *m, int i, int n, int d, int plus, int lon){
  int x, y;
  for(; (x = ceil32(lon*n+plus, d)) <= i+1; lon++){
    for(y = i-lon; (y >= 0) && (m[y] == m[y+lon]); y--);
    if(i-y >= x) return 0;
  }
  return 1;
}//*/

int fl(int n_i, int d_i, int n_o, int d_o){
  int x, y;
  y = ceil32(2*(n_o-d_o)*(2*d_i-n_i),n_o-n_i)-1;
  x = (y*(n_i-d_i))/(2*d_i-n_i);
  return 2*x+y;
}//*/

int conjecture(int *m, int i){
  int a = i, j_c = i, b = i-1, i_c = i-1;
  skip[i_c] = j_c; l = i+1;
  while(b >= 0){
    if(m[a] == m[b])
      if((l-a)*(l-a)>=5*(a-b)) return 0;
      else{ a--; b--; continue;}
    if(a == i) b--;
    else{
      while(i_c > a)
        if(m[j_c] == m[i_c])
          {j_c--; i_c--; skip[i_c] = (m[i_c] == m[j_c] ? skip[j_c] : j_c);}
        else if(j_c == i) skip[--i_c] = j_c;
        else j_c = skip[j_c];
      a = skip[a];
      //if(d*l < n*(a-b)*ceil(lon, a-b)+plus) return 1;
    }
  }
  return 1;
}//*/

int aabaacbaab(int *m, int i){//|baab|<=36
  int a, b, c; l = i+1;
  for(b = 1; 3*b+7 <= l; b++)
  for(a = 1; a <= 2; a++) if(eq(m+l-2*a-b, m+l-a-b, a) && eq(m+l-2*a-2*b, m+l-b, b))
  for(c = 1; 6*a+3*b+c <= l; c++)
  if(eq(m+l-6*a-3*b-c, m+l-2*a-b, 2*a+b) &&
  eq(m+l-4*a-2*b-c, m+l-2*a-b, 2*a)) return 0;//*/
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 2, 1, 1, 2)) return 0;
  if(!rep(m, i, 25, 13, 1, 3)) return 0;//ok
  return 1;
}//*/

int aabaccb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 3+2*b+2*c <= l && c <= 2; c++) if(eq(m+l-2*c-b, m+l-c-b, c))
  for(a = 1; 3*a+2*b+2*c <= l && a <= 2; a++)
  if(eq(m+l-3*a-2*b-2*c, m+l-2*a-2*b-2*c, a) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b-2*c, a) &&
  eq(m+l-b, m+l-a-2*b-2*c, b)) return 0;
  return 1;
}//*/

int abbcacc(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 3*c+4 <= l && c <= 2; c++) if(eq(m+l-2*c, m+l-c, c))
  for(a = 1; 2*a+2+3*c <= l; a++) if(eq(m+l-a-3*c, m+l-c, c))
  for(b = 1; 2*a+2*b+3*c <= l && b <= 2; b++)
  if(eq(m+l-a-2*b-3*c, m+l-a-b-3*c, b) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-2*c, a)) return 0;
  return 1;
}//*/

int aabaccb(int *m, int i){
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 5, 2, 1, 2)) return 0;
  if(!rep(m, i, 15, 8, 1, 3)) return 0;//ok
  return aabaccb1(m, i) && abbcacc(m, i);
}//*/

int aabba1(int *m, int i){
  int a, b; l = i+1;
  for(a = 1; 3*a+2 <= l; a++)
  for(b = 1; 3*a+2*b <= l; b++)
  if(eq(m+l-a-2*b, m+l-a-b, b) &&
  eq(m+l-2*a-2*b, m+l-a, a) &&
  eq(m+l-3*a-2*b, m+l-a, a)) return 0;
  return 1;
}//*/

int abbaa(int *m, int i){
  int a, b; l = i+1;
  for(a = 1; 3*a+2 <= l; a++) if(eq(m+l-2*a, m+l-a, a))
  for(b = 1; 3*a+2*b <= l; b++)
  if(eq(m+l-2*a-2*b, m+l-2*a-b, b) &&
  eq(m+l-3*a-2*b, m+l-a, a)) return 0;
  return 1;
}//*/

int aabba(int *m, int i){
  if((i > 3) && (m[i] == m[i-2]) && (m[i] == m[i-4]) && (m[i-1] == m[i-3])) return 0; //xyxyx
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 7, 3, 1, 2)) return 0;
  if(!rep(m, i, 25, 13, 1, 4)) return 0;//ok
  return aabba1(m, i) && abbaa(m, i);
}//*/

#define Laabbcabba 27
int aabbcabba1(int *m, int i){//|abba|<=72 //|aabb|<=74
  int a, b, c; l = i+1;
  for(a = 1; 4*a+4 <= l && a < Laabbcabba; a++)
  for(b = 1; 4*a+4*b <= l && b < Laabbcabba; b++) if(eq(m+l-a-2*b, m+l-a-b, b) && eq(m+l-2*a-2*b, m+l-a, a))
  for(c = -2*a-2*b; 4*a+4*b+c <= l; c++)
  if(eq(m+l-2*a-4*b-c, m+l-a-2*b, 2*b) &&
  eq(m+l-3*a-4*b-c, m+l-a, a) &&
  eq(m+l-4*a-4*b-c, m+l-a, a)) return 0;
  for(b = 1; 4+4*b <= l && b < Laabbcabba; b++) if(eq(m+l-2*b, m+l-b, b)) //abba.aabb
  for(a = 1; 4*a+4*b <= l && a < Laabbcabba; a++) if(eq(m+l-2*a-2*b, m+l-a-2*b, a))
  for(c = -2*a-2*b; 4*a+4*b+c <= l; c++)
  if(eq(m+l-3*a-4*b-c, m+l-2*b, 2*b) &&
  eq(m+l-3*a-2*b-c, m+l-a-2*b, a) &&
  eq(m+l-4*a-4*b-c, m+l-a-2*b, a)) return 0;//*/
  return 1;
}//*/

int aabbcabba(int *m, int i){
  int a, b, c, l = i+1;
  for(b = 1; 2+2*b <= l; b++) if(eq(m+l-2*b, m+l-b, b)) //abba.aabb
  for(a = 1; 2*a+2*b <= l; a++) if(eq(m+l-2*a-2*b, m+l-a-2*b, a))
  for(c = -2*a-2*b; 4*a+4*b+c <= l; c++)
  if(eq(m+l-4*a-4*b-c, m+l-a-2*b, a+2*b) && eq(m+l-3*a-2*b-c, m+l-a-2*b, a)) return 0;
  for(a = 1; 2*a+2 <= l; a++) //aabb.abba
  for(b = 1; 2*a+2*b <= l; b++) if(eq(m+l-a-2*b, m+l-a-b, b) && eq(m+l-2*a-2*b, m+l-a, a))
  for(c = -2*a-2*b+1; 4*a+4*b+c <= l; c++)
  if(eq(m+l-3*a-4*b-c, m+l-2*a-2*b, a+2*b) && eq(m+l-4*a-4*b-c, m+l-a, a)) return 0;
  return 1;
}//*/

int aabbcabba2(int *m, int i){   //shows you can't avoid both aabb.abba and abbaa
  return aabbcabba(m, i) && abbaa(m, i); //try: FAILED cc=371 mmx=41: 15/08/2006 15/49/52
}//*/

int aabbcac1(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l && c <= l; c++)
  for(a = 1; 3*a+2+2+c <= l && a < 3; a++) if(eq(m+l-a-2*c, m+l-c, c))
  for(b = 1; 3*a+2*b+2*c <= l && b < 3; b++)
  if(eq(m+l-3*a-2*b-2*c, m+l-2*a-2*b-2*c, a) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-c, a) &&
  eq(m+l-a-2*b-2*c, m+l-a-b-2*c, b)) return 0;
  return 1;
}//*/

int abaccbb(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b < 3; b++) if(eq(m+l-2*b, m+l-b, b))
  for(c = 1; 2+3*b+2*c <= l && c < 3; c++) if(eq(m+l-2*b-2*c, m+l-2*b-c, c))
  for(a = 1; 2*a+3*b+2*c <= l && a <= l; a++)
  if(eq(m+l-2*a-3*b-2*c, m+l-a-2*b-2*c, a) &&
  eq(m+l-a-3*b-2*c, m+l-b, b)) return 0;
  return 1;
}//*/

int aabbcac(int *m, int i){
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 43, 22, 1, 3)) return 0;//ok
  return aabbcac1(m, i) && abaccbb(m, i);
  return 1;
}//*/

int aabbcbc(int *m, int i){
  if((i > 2) && (m[i] == m[i-3]) && (m[i-1] == m[i-2])) return 0; //xyyx & xxxx
  if((i > 7) && (m[i] == m[i-2]) && (m[i] == m[i-6]) && (m[i] == m[i-8]) && (m[i-1] == m[i-3]) && (m[i-1] == m[i-5]) && (m[i-1] == m[i-7])) return 0; //xyxyyyxyx
  if(!rep(m, i, 7, 2, 1, 1)) return 0;
  if(!rep(m, i, 33, 17, 1, 3)) return 0;
  return 1;
}//*/

int aabbcc(int *m, int i){
  if((i > 3) && (m[i] == m[i-2]) && (m[i] == m[i-4]) && (m[i-1] == m[i-3])) return 0; //xyxyx
  if((i > 4) && (m[i] == m[i-3]) && (m[i] == m[i-4]) && (m[i-1] == m[i-2]) && (m[i-1] == m[i-5])) return 0; //xyyxxy
  if((i > 5) && (m[i] == m[i-2]) && (m[i] == m[i-3]) && (m[i] == m[i-4]) && (m[i-1] == m[i-5]) && (m[i-1] == m[i-6])) return 0; //xxyyyxy
  if((i > 5) && (m[i] == m[i-1]) && (m[i] == m[i-5]) && (m[i-2] == m[i-3]) && (m[i-2] == m[i-4]) && (m[i-2] == m[i-6])) return 0; //xyxxxyy
  if((i > 6) && (m[i] == m[i-1]) && (m[i] == m[i-2]) && (m[i] == m[i-4]) && (m[i-3] == m[i-5]) && (m[i-3] == m[i-6]) && (m[i-3] == m[i-7])) return 0; //xxxyxyyy
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 2, 1, 1, 2)) return 0;
  if(!rep(m, i, 59, 30, 1, 3)) return 0;
  return 1;
}//*/

int aabcbc(int *m, int i){
  if((i > 3) && (m[i] == m[i-2]) && (m[i] == m[i-4])) return 0; //xyxyx && xyxxx && xxxyx
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 2, 1, 1, 2)) return 0;
  if(!rep(m, i, 367, 184, 1, 3)) return 0;//ok
  return 1;
}//*/

int aabccab1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(a = 1; 3*a+2*b+2 <= l && a < 4; a++)
  for(c = 1; 3*a+2*b+2*c <= l && c < 4; c++)
  if(eq(m+l-3*a-2*b-2*c, m+l-2*a-2*b-2*c, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-a-b, a+b) &&
  eq(m+l-a-b-2*c, m+l-a-b-c, c)) return 0;
  return 1;
}//*/

int abccabb(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b < 4; b++) if(eq(m+l-2*b, m+l-b, b))
  for(a = 1; 2*a+3*b+2 <= l; a++)
  for(c = 1; 2*a+3*b+2*c <= l && c < 4; c++)
  if(eq(m+l-a-2*b-2*c, m+l-a-2*b-c, c) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-2*b, a+b)) return 0;
  return 1;
}//*/

int aabccab(int *m, int i){
  if(!rep(m, i, 6, 1, 1, 1)) return 0;
  if(!rep(m, i, 3, 1, 1, 2)) return 0;
  if(!rep(m, i, 2, 1, 1, 3)) return 0;
  if(!rep(m, i, 257, 136, 1, 4)) return 0;//ok
  return aabccab1(m, i) && abccabb(m, i);
  return 1;
}//*/

int aabccba1(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 3*a+4 <= l && a < 3; a++)
  for(b = 1; 3*a+2*b+2 <= l; b++)
  for(c = 1; 3*a+2*b+2*c <= l && c < 3; c++)
  if(eq(m+l-3*a-2*b-2*c, m+l-2*a-2*b-2*c, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-a, a) &&
  eq(m+l-a-2*b-2*c, m+l-a-b, b) &&
  eq(m+l-a-b-2*c, m+l-a-b-c, c)) return 0;
  return 1;
}//*/

int abccbaa(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 3*a+4 <= l && a < 3; a++) if(eq(m+l-2*a, m+l-a, a))
  for(b = 1; 3*a+2*b+2 <= l; b++)
  for(c = 1; 3*a+2*b+2*c <= l && c < 3; c++)
  if(eq(m+l-2*a-b-2*c, m+l-2*a-b-c, c) &&
  eq(m+l-3*a-2*b-2*c, m+l-a, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-2*a-b, b)) return 0;
  return 1;
}//*/

int aabccba(int *m, int i){
  if(!rep(m, i, 3, 1, 1, 1)) return 0;
  if(!rep(m, i, 2, 1, 1, 2)) return 0;
  if(!rep(m, i, 36, 19, 1, 3)) return 0;//ok
  return aabccba1(m, i) && abccbaa(m, i);
  return 1;
}//*/

int abaab1(int *m, int i){
  int a, b; l = i+1;
  for(b = 1; 3+2*b <= l; b++)
  for(a = 1; 3*a+2*b <= l && a < 3; a++)
  if(eq(m+l-2*a-2*b, m+l-b, b) &&
  eq(m+l-2*a-b, m+l-a-b, a) &&
  eq(m+l-3*a-2*b, m+l-a-b, a)) return 0;
  return 1;
}//*/

int abbab(int *m, int i){
  int a, b; l = i+1;
  for(b = 1; 2+3*b <= l && b < 3; b++)
  for(a = 1; 2*a+3*b <= l; a++)
  if(eq(m+l-a-2*b, m+l-b, b) &&
  eq(m+l-a-3*b, m+l-b, b) &&
  eq(m+l-2*a-3*b, m+l-a-b, a)) return 0;
  return 1;
}//*/

int abaab(int *m, int i){
  if(!rep(m, i, 4, 1, 1, 1)) return 0;
  if(!rep(m, i, 2, 1, 1, 2)) return 0;
  if(!rep(m, i, 23, 12, 1, 3)) return 0;//ok
  return abaab1(m, i) && abbab(m, i);
}//*/

int abaacbc1(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l && c <= 19; c++)
  for(b = 1; 3+2*b+2*c <= l && b <= 22; b++) if(eq(m+l-b-2*c, m+l-c, c))
  for(a = 1; 3*a+2*b+2*c <= l && a <= 6; a++)
  if(eq(m+l-3*a-2*b-2*c, m+l-a-b-2*c, a) &&
  eq(m+l-2*a-b-2*c, m+l-a-b-2*c, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-b-c, b)) return 0;
  return 1;
}//*/

int abaccbc(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 3*c+4 <= l && c <= 6; c++)
  for(b = 1; 2+2*b+3*c <= l && b <= 22; b++) if(eq(m+l-b-3*c, m+l-c, c) && eq(m+l-b-2*c, m+l-c, c))
  for(a = 1; 2*a+2*b+3*c <= l && a <= 19; a++)
  if(eq(m+l-2*a-2*b-3*c, m+l-a-b-3*c, a) &&
  eq(m+l-a-2*b-3*c, m+l-b-c, b)) return 0;
  return 1;
}//*/

int abaacbc(int *m, int i){
  //if(!rep(m, i, 4, 1, 1, 1)) return 0;
  //if(!rep(m, i, 5, 2, 1, 3)) return 0;
  //if(!rep(m, i, 7, 3, 1, 5)) return 0;
  //if(!rep(m, i, 13, 7, 1, 7)) return 0;
  //if(!rep(m, i, 7, 4, 1, 8)) return 0;
  //if(!rep(m, i, 8, 5, 1, 9)) return 0;
  //if(!rep(m, i, 3, 2, 1, 16)) return 0;
  //if(!rep(m, i, 28, 19, 1, 17)) return 0;
  //if(!rep(m, i, 23, 16, 1, 20)) return 0;//ok
  //return abaccbc(m, i) && abaacbc1(m, i);
  return 1;
}//*/

int abaaccb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 3+2*b+2*c <= l && c < 3; c++) if(eq(m+l-b-2*c, m+l-b-c, c))
  for(a = 1; 3*a+2*b+2*c <= l && a < 3; a++)
  if(eq(m+l-3*a-2*b-2*c, m+l-a-b-2*c, a) &&
  eq(m+l-2*a-b-2*c, m+l-a-b-2*c, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-b, b)) return 0;
  return 1;
}//*/

int abbccac(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 3*c+4 <= l && c < 3; c++)
  for(a = 1; 2*a+2+3*c <= l; a++) if(eq(m+l-a-3*c, m+l-c, c) && eq(m+l-a-2*c, m+l-c, c))
  for(b = 1; 2*a+2*b+3*c <= l && b < 3; b++)
  if(eq(m+l-2*a-2*b-3*c, m+l-a-c, a) &&
  eq(m+l-a-2*b-3*c, m+l-a-b-3*c, b)) return 0;
  return 1;
}//*/

int abaaccb(int *m, int i){
  if(!rep(m, i, 5, 1, 1, 1)) return 0;
  if(!rep(m, i, 5, 2, 1, 2)) return 0;
  if(!rep(m, i, 193, 104, 0, 3)) return 0;//ok
  return abaaccb1(m, i) && abbccac(m, i);
  return 1;
}//*/

int abacacb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 3+2*b+2*c <= l && 1+c < 3; c++)
  for(a = 1; 3*a+2*b+2*c <= l && a+c < 3; a++)
  if(eq(m+l-2*a-b-2*c, m+l-a-b-c, a+c) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b-c, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-b, b)) return 0;
  return 1;
}//*/

int abcbcac(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 3*c+4 <= l && 1+c < 3; c++)
  for(a = 1; 2*a+2+3*c <= l; a++) if(eq(m+l-a-2*c, m+l-c, c))
  for(b = 1; 2*a+2*b+3*c <= l && b+c < 3; b++)
  if(eq(m+l-a-2*b-3*c, m+l-a-b-2*c, b+c) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-c, a)) return 0;
  return 1;
}//*/

int abacacb(int *m, int i){
  if(!rep(m, i, 5, 1, 1, 1)) return 0;
  if(!rep(m, i, 5, 2, 1, 2)) return 0;
  if(!rep(m, i, 15, 8, 1, 3)) return 0;//ok
  return abacacb1(m, i) && abcbcac(m, i);
}//*/

int abacbc(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 4+2*c <= l && c < 291; c++)
  for(b = 1; 2+2*b+2*c <= l && b < 291; b++) if(eq(m+l-b-2*c, m+l-c, c))
  for(a = 1; 2*a+2*b+2*c <= l && a < 291; a++)
  if(eq(m+l-2*a-2*b-2*c, m+l-a-b-2*c, a) && eq(m+l-a-2*b-2*c, m+l-b-c, b)) return 0;//*/
  //if(!rep(m, i, 4, 3, 1, 346)) return 0;
  if(!rep(m, i, 41, 29, 1, 291)) return 0;
  return 1;
}//*/

int abaccab1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(a = 1; 3*a+2*b+2 <= l; a++)
  for(c = 1; 3*a+2*b+2*c <= l && c < 5; c++)
  if(eq(m+l-a-b-2*c, m+l-a-b-c, c) &&
  eq(m+l-2*a-b-2*c, m+l-a-b, a) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abccbab(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l; b++)
  for(a = 1; 2*a+3*b+2 <= l; a++) if(eq(m+l-a-2*b, m+l-b, b))
  for(c = 1; 2*a+3*b+2*c <= l && c < 5; c++)
  if(eq(m+l-a-2*b-2*c, m+l-a-2*b-c, c) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abaccab(int *m, int i){
  if(!rep(m, i, 6, 1, 1, 1)) return 0;
  if(!rep(m, i, 3, 1, 1, 2)) return 0;
  if(!rep(m, i, 5, 2, 1, 3)) return 0;
  if(!rep(m, i, 35, 19, 1, 5)) return 0;//ok
  //return abaccab1(m, i) && abccbab(m, i);
  return 1;
}//*/

int abaccba1(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 3*a+4 <= l && a <= 1; a++) /////OPTIMIZED
  for(b = 1; 3*a+2*b+2 <= l; b++)
  for(c = 1; 3*a+2*b+2*c <= l && c < 3; c++)
  if(eq(m+l-a-b-2*c, m+l-a-b-c, c) &&
  eq(m+l-3*a-2*b-2*c, m+l-a, a) &&
  eq(m+l-2*a-2*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abccaba(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 3*a+4 <= l && a <= 1; a++) /////OPTIMIZED
  for(b = 1; 3*a+2*b+2 <= l; b++) if(eq(m+l-2*a-b, m+l-a, a))
  for(c = 1; 3*a+2*b+2*c <= l && c < 3; c++)
  if(eq(m+l-2*a-b-2*c, m+l-2*a-b-c, c) &&
  eq(m+l-3*a-2*b-2*c, m+l-2*a-b, a+b)) return 0;
  return 1;
}//*/

int abaccba(int *m, int i){
  if(!rep(m, i, 4, 1, 1, 1)) return 0;
  if(!rep(m, i, 5, 2, 1, 2)) return 0;
  if(!rep(m, i, 53, 28, 1, 3)) return 0;//ok
  return abaccba1(m, i) && abccbab(m, i);
  return 1;
}//*/

int abbacca(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 3*a+4 <= l; a++)
  for(c = 1; 3*a+2+2*c <= l && c < 4; c++) if(eq(m+l-a-2*c, m+l-a-c, c) && eq(m+l-2*a-2*c, m+l-a, a))
  for(b = 1; 3*a+2*b+2*c <= l && b < 4; b++)
  if(eq(m+l-2*a-2*b-2*c, m+l-2*a-b-2*c, b) &&
  eq(m+l-3*a-2*b+2*c, m+l-a, a)) return 0;//*/
  if(!rep(m, i, 31, 16, 1, 4)) return 0;//ok
  return 1;
}//*/

int abbaccb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b < 3; b++)
  for(c = 1; 2+3*b+2*c <= l && c < 3; c++) if(eq(m+l-b-2*c, m+l-b-c, c))
  for(a = 1; 2*a+3*b+2*c <= l; a++)
  if(eq(m+l-a-3*b-2*c, m+l-b, b) &&
  eq(m+l-a-2*b-2*c, m+l-b, b) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-b-2*c, a)) return 0;
  return 1;
}//*/

int abbcaac(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l; c++)
  for(a = 1; 3*a+2+2*c <= l && a < 3; a++) if(eq(m+l-2*a-c, m+l-a-c, a) && eq(m+l-2*a-2*c, m+l-c, c))
  for(b = 1; 3*a+2*b+2*c <= l && b < 3; b++)
  if(eq(m+l-2*a-2*b-2*c, m+l-2*a-b-2*c, b) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-c, a)) return 0;
  return 1;
}//*/

int abbaccb(int *m, int i){
  if(!rep(m, i, 4, 1, 1, 1)) return 0;
  if(!rep(m, i, 3, 1, 1, 2)) return 0;
  if(!rep(m, i, 53, 28, 1, 3)) return 0;//ok
  return abbaccb1(m, i) && abbcaac(m, i);
  return 1;
}//*/

int abbcacb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b < 4; b++)
  for(c = 1; 2+3*b+2*c <= l; c++)
  for(a = 1; 2*a+3*b+2*c <= l && a+b < 161; a++)
  if(eq(m+l-a-2*b-2*c, m+l-b, b) &&
  eq(m+l-a-3*b-2*c, m+l-b, b) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-b-c, a) &&
  eq(m+l-a-b-2*c, m+l-b-c, c)) return 0;
  return 1;
}//*/

int abcbaac(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l; c++)
  for(a = 1; 3*a+2+2*c <= l && a < 4; a++) if(eq(m+l-2*a-c, m+l-a-c, a))
  for(b = 1; 3*a+2*b+2*c <= l && b+c < 161; b++)
  if(eq(m+l-3*a-2*b-2*c, m+l-a-c, a) &&
  eq(m+l-2*a-b-2*c, m+l-c, c) &&
  eq(m+l-2*a-2*b-2*c, m+l-2*a-b-c, b)) return 0;
  return 1;
}//*/

int abbcacb(int *m, int i){
  if(!rep(m, i, 9, 5, 1, 4)) return 0;
  if(!rep(m, i, 10, 7, 1, 161)) return 0;
  return abbcacb1(m, i) && abcbaac(m, i);
}//*/

int abbcbac1(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l; c++)
  for(a = 1; 2*a+3+2*c <= l && a+c < 140; a++)
  for(b = 1; 2*a+3*b+2*c <= l && b < 7; b++)
  if(eq(m+l-a-2*b-2*c, m+l-a-b-c, b) &&
  eq(m+l-a-3*b-2*c, m+l-a-b-c, b) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-c, a) &&
  eq(m+l-a-b-2*c, m+l-c, c)) return 0;
  return 1;
}//*/

int abcaccb(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 2+2*b+3*c <= l && c < 7; c++) if(eq(m+l-b-2*c, m+l-b-c, c))
  for(a = 1; 2*a+2*b+3*c <= l && a+b < 140; a++)
  if(eq(m+l-a-b-3*c, m+l-b-c, c) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-b-2*c, a) &&
  eq(m+l-a-2*b-3*c, m+l-b, b)) return 0;
  return 1;
}//*/

int abbcbac(int *m, int i){
  if(!rep(m, i, 5, 3, 1, 7)) return 0;
  if(!rep(m, i, 13, 9, 1, 141)) return 0;
  return abbcbac1(m, i) && abcaccb(m, i);
  return 1;
}//*/

int abbcbca1(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 2*a+5 <= l; a++)
  for(c = 1; 2*a+3+2*c <= l && 1+c < 3; c++)
  for(b = 1; 2*a+3*b+2*c <= l && b+c < 3; b++)
  if(eq(m+l-a-2*b-2*c, m+l-a-b-c, b+c) &&
  eq(m+l-a-3*b-2*c, m+l-a-b-c, b) &&
  eq(m+l-2*a-3*b-2*c, m+l-a, a)) return 0;
  return 1;
}//*/

int abcbcca(int *m, int i){
  int a, b, c; l = i+1;
  for(a = 1; 2*a+5 <= l; a++)
  for(c = 1; 2*a+2+3*c <= l && 1+c < 3; c++) if(eq(m+l-a-2*c, m+l-a-c, c))
  for(b = 1; 2*a+2*b+3*c <= l && b+c < 3; b++)
  if(eq(m+l-a-2*b-3*c, m+l-a-b-2*c, b+c) &&
  eq(m+l-2*a-2*b-3*c, m+l-a, a)) return 0;
  return 1;
}//*/

int abbcbca(int *m, int i){
  if(!rep(m, i, 7, 2, 1, 1)) return 0;
  if(!rep(m, i, 173, 88, 1, 3)) return 0;//ok
  return abbcbca1(m, i) && abcbcca(m, i);
}//*/

int abbccab1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b < 4; b++)
  for(a = 1; 2*a+3*b+2 <= l; a++)
  for(c = 1; 2*a+3*b+2*c <= l && c < 4; c++)
  if(eq(m+l-a-2*b-2*c, m+l-b, b) &&
  eq(m+l-a-b-2*c, m+l-a-b-c, c) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abccaab(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(a = 1; 3*a+2*b+2 <= l && a < 4; a++) if(eq(m+l-2*a-b, m+l-a-b, a))
  for(c = 1; 3*a+2*b+2*c <= l && c < 4; c++)
  if(eq(m+l-2*a-b-2*c, m+l-2*a-b-c, c) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abbccab(int *m, int i){
  if(!rep(m, i, 5, 1, 1, 1)) return 0;
  if(!rep(m, i, 3, 1, 1, 2)) return 0;
  if(!rep(m, i, 15, 8, 1, 4)) return 0;//ok
  return abbccab1(m, i) && abccaab(m, i);
}//*/

int abcaacb1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 3+2*b+2*c <= l; c++)
  for(a = 1; 3*a+2*b+2*c <= l && a < 4 /*&& 2*a+c < 96*/; a++)
  if(eq(m+l-2*a-b-c, m+l-a-b-c, a) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b-c, a) &&
  eq(m+l-2*a-b-2*c, m+l-b-c, c) &&
  eq(m+l-2*a-2*b-2*c, m+l-b, b)) return 0;
  return 1;
}//*/

int abccbac(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 3*c+5 <= l && c < 4; c++)
  for(a = 1; 2*a+2+3*c <= l; a++)
  for(b = 1; 2*a+2*b+3*c <= l /*&& 2*c+b < 96*/; b++)
  if(eq(m+l-a-b-2*c, m+l-c, c) &&
  eq(m+l-a-b-3*c, m+l-c, c) &&
  eq(m+l-a-2*b-3*c, m+l-a-b-c, b) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-c, a)) return 0;
  return 1;
}//*/

int abcaacb(int *m, int i){
  l = i+1;
  /*int a, b; static int raaa = 0;//ABBA
  for(a = 1; 2*a+2 <= l; a++)
  for(b = 1; 2*a+2*b <= l && b < 4; b++)
  if(eq(m+l-2*a-2*b, m+l-a, a) &&
  eq(m+l-a-2*b, m+l-a-b, b) &&
  (2*a+2*b > raaa)) printf("raaa=%d a=%d b=%d\n", raaa = 2*a+2*b, a, b);*/
  //if(!rep(m, i, 5, 1, 1, 1)) return 0;
  //if(!rep(m, i, 7, 2, 1, 2)) return 0;
  //if(!rep(m, i, 2, 1, 1, 3)) return 0;
  //if(!rep(m, i, 13, 7, 1, 4)) return 0;//ok
  if(!rep(m, i, 2, 1, 0, 4)) return 0;//ok
  if(!rep(m, i, 13, 7, 1, 40)) return 0;//ok
  return abcaacb1(m, i) && abccbac(m, i);
  return 1;
}//*/

int abcacab1(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(a = 1; 3*a+2*b+2 <= l && a <= 1; a++) /////OPTIMIZED
  for(c = 1; 3*a+2*b+2*c <= l && a+c < 3; c++)
  if(eq(m+l-2*a-b-2*c, m+l-a-b-c, a+c) &&
  eq(m+l-3*a-2*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abcbcab(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 3*b+4 <= l && b <= 1; b++) /////OPTIMIZED
  for(a = 1; 2*a+3*b+2 <= l; a++)
  for(c = 1; 2*a+3*b+2*c <= l && b+c < 3; c++)
  if(eq(m+l-a-3*b-2*c, m+l-a-2*b-c, b+c) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-b, a+b)) return 0;
  return 1;
}//*/

int abcacab(int *m, int i){
  if(!rep(m, i, 3, 1, 1, 3)) return 0;
  if(!rep(m, i, 79, 40, 1, 3)) return 0;
  if(!rep(m, i, 149, 80, 1, 41)) return 0;
  return abcacab1(m, i) && abcbcab(m, i);
  return 1;
}//*/

//#define Labcacb 3241
#define Labcacb 200
int abcacb(int *m, int i){
  if((i > 3) && (m[i] != m[i-1]) && (m[i] != m[i-2]) && (m[i] == m[i-3]) && (m[i] == m[i-4])) return 0; //xxyyx
  l = i+1;
  int abc, a, b;
  for(abc = 3; 2*abc <= l; abc++)
  for(a = 1; (a < abc-1) && (m[i-2*abc+a] == m[i-abc+a]); a++)
  for(b = 1; b < abc-a; b++)
  if(eq(m+l-2*abc+a, m+l-b, b) && eq(m+l-2*abc+a+b, m+l-abc+a, abc-a-b)) return 0;//*/
  //return rep(m, i, 4, 3, 1, Labcacb);
  return rep(m, i, 34, 25, 1, Labcacb);
}//*/

int abcbbac1(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 2*c+5 <= l; c++)
  for(a = 1; 2*a+3+2*c <= l; a++)
  for(b = 1; 2*a+3*b+2*c <= l && b < 7; b++)
  if(eq(m+l-a-2*b-c, m+l-a-b-c, b) &&
  eq(m+l-a-3*b-2*c, m+l-a-b-c, b) &&
  eq(m+l-2*a-3*b-2*c, m+l-a-c, a) &&
  eq(m+l-a-2*b-2*c, m+l-c, c)) return 0;
  return 1;
}//*/

int abccacb(int *m, int i){
  int a, b, c; l = i+1;
  for(b = 1; 2*b+5 <= l; b++)
  for(c = 1; 2+2*b+3*c <= l && c < 7; c++)
  for(a = 1; 2*a+2*b+3*c <= l; a++)
  if(eq(m+l-a-b-2*c, m+l-b-c, c) &&
  eq(m+l-a-b-3*c, m+l-b-c, c) &&
  eq(m+l-2*a-2*b-3*c, m+l-a-b-c, a) &&
  eq(m+l-a-2*b-3*c, m+l-b, b)) return 0;
  return 1;
}//*/

int abcbbac(int *m, int i){
  if(!rep(m, i, 13, 7, 1, 7)) return 0;
  if(!rep(m, i, 17, 12, 1, 181)) return 0;
  return abcbbac1(m, i) && abccacb(m, i);
}//*/

int fs(int *m, int i){// 00, 11, 0101
  if(i < 3) return 1;
  if(!m[i] && !m[i-2] && (m[i-1] == m[i-3])) return 0; //x0x0
  if(m[i] && m[i-2] && m[i-1] && m[i-3]) return 0; //1111
  return rep(m, i, 37, 19, 1, 3);
}//*/

int sim3(int *m, int i){
  return rep(m, i, 3, 1, 1, 1) && rep(m, i, 5, 2, 1, 2) && rep(m, i, 59, 32, 1, 3);
}//*/

int sim4(int *m, int i){
  return rep(m, i, 5, 2, 1, 1) && rep(m, i, 7, 3, 1, 3) && rep(m, i, 823, 412, 1, 4);
}//*/

int sim7(int *m, int i){
  return rep(m, i, 7, 3, 1, 1) && rep(m, i, 79, 40, 1, 7);
}//*/

int rt3p(int *m, int i){ return rep(m, i, 7, 4, 1, 1) && rep(m, i, 3, 2, 1, 10); }//possible try

int rt4p(int *m, int i){ return rep(m, i, 7, 5, 1, 1) && rep(m, i, 61, 44, 1, 11); }//possible try

int sqf(int *m, int i){// squarefree
  int a = i, j_c = i, b = i-1, i_c = i-1;
  skip[i_c] = j_c; l = i+1;
  while(b >= 0){
    if(m[a] == m[b])
      if(l == 2*a-b) return 0;
      else{ a--; b--; }
    else if(a == i) b--;
    else{
      while(i_c > a)
        if(m[j_c] == m[i_c])
          // skip[--i_c] = --j_c; // non optimized
          {j_c--; i_c--; skip[i_c] = (m[i_c] == m[j_c] ? skip[j_c] : j_c);} // optimized
        else if(j_c == i) skip[--i_c] = j_c;
        else j_c = skip[j_c];
      a = skip[a];
      if(2*(a-b) > l) return 1;
    }
  }
  return 1;
}//*/

int var(int *m, int i){ return rep(m, i, 17, 10, 1, 1); }//*/ may vary:
int rt2(int *m, int i){ return rep(m, i, 2, 1, 1, 1); }//*/overlap-free
int rt3(int *m, int i){ return rep(m, i, 7, 4, 1, 1); }//*/rep_threshold(3)=R(3,1)=7/4
int rt4(int *m, int i){ return rep(m, i, 7, 5, 1, 1); }//*/R(4,1)=7/5
int rt5(int *m, int i){ return rep(m, i, 5, 4, 1, 1); }//*/R(5,1)=5/4
int rt6(int *m, int i){ return rep(m, i, 6, 5, 1, 1); }//*/R(6,1)=6/5
int grt23(int *m, int i){ return rep(m, i, 8, 5, 1, 3); }//*/ //R(2,3)=8/5
int grt24(int *m, int i){ return rep(m, i, 3, 2, 1, 4); }//*/ //R(2,4)=3/2
int grt25(int *m, int i){ return rep(m, i, 7, 5, 1, 5); }//*/ //R(2,5)=7/5
int grt26(int *m, int i){ return rep(m, i, 4, 3, 1, 6); }//*/ //R(2,6)=4/3
int grt27(int *m, int i){ return rep(m, i, 31, 24, 1, 7); }//*/ //R(2,7)=31/24
int grt32(int *m, int i){ return rep(m, i, 3, 2, 1, 2); }//*/ //R(3,2)=3/2
int grt33(int *m, int i){ return rep(m, i, 4, 3, 1, 3); }//*/ //R(3,3)=4/3
int grt34(int *m, int i){ return rep(m, i, 5, 4, 1, 4); }//*/ //R(3,4)=5/4
//int grt34(int *m, int i){ return rep(m, i, 79, 60, 1, 4); }//*/ //R(3,4)=5/4 !!!
int grt38(int *m, int i){ return rep(m, i, 29, 26, 1, 8); }//*/ //R(3,8)=9/8
int grt42(int *m, int i){ return rep(m, i, 5, 4, 1, 2); }//*/ //R(4,2)=5/4
//int grt42(int *m, int i){ return rep(m, i, 21, 16, 0, 2); }//*/ //R(4,2)=5/4 !!!
int grt72(int *m, int i){ return rep(m, i, 9, 8, 1, 7); }//*/ //R(7,2)=9/8

int loc_abacbc(int *m, int i){
  int a, b, c; l = i+1;
  for(c = 1; 4+2*c <= l; c++)
  for(b = 1; 2+2*b+2*c <= l; b++) if(eq(m+l-b-2*c, m+l-c, c))
  for(a = 1; 2*a+2*b+2*c <= l; a++)
  if(eq(m+l-2*a-2*b-2*c, m+l-a-b-2*c, a) && eq(m+l-a-2*b-2*c, m+l-b-c, b)) return 0;
  return 1;
}//*/

int loc_abcacb(int *m, int i){
  int abc, a, b; l = i+1;
  if((i > 3) && (m[i] != m[i-1]) && (m[i] != m[i-2]) && (m[i] == m[i-3]) && (m[i] == m[i-4])) return 0; //xxyyx
  for(abc = 3; 2*abc <= l; abc++)
  for(a = 1; (a < abc-1) && (m[i-2*abc+a] == m[i-abc+a]); a++)
  for(b = 1; b < abc-a; b++)
  if(eq(m+l-2*abc+a, m+l-b, b) && eq(m+l-2*abc+a+b, m+l-abc+a, abc-a-b)) return 0;
  return 1;
}//*/

int lex(int *m, int i){
  int key, j;
  skip[i] = -1;
  for(l = 1; l <= i; l++){
    if(skip[l] >= i) skip[l] = -1;
    else if(skip[l] != -1) continue;
    for(j = 0; j < 40; map[j++] = -1);
    for(key = 0, j = l; j <= i; j++){
      if(map[m[j]] < 0) map[m[j]] = key++;
      if(map[m[j]] < m[j-l]) return 0;
      if(map[m[j]] > m[j-l]){ skip[l] = j; break; }
    }
  }
  return 1;
}//*/

int absq(int *m, int i, int lon){
  for(l = 0; l < 10; l++) map[l] = 0;
  for(l = 1; 2*l <= i+1; l++){
    map[m[i-2*l+1]]++;
    map[m[i-2*l+2]]++;
    map[m[i-l+1]] -= 2;
    if(l >= lon && !map[0] && !map[1] && !map[2] && !map[3]) return 0;
  }
  return 1;
}//*/

int abeq(int *g, int *d, int lon){
  for(l = 0; l < 10; l++) map[l] = 0;
  for(; --lon >= 0; ){
    map[g[lon]]++;
    map[d[lon]]--;
  }
  return map[0] || map[1] || map[2] || map[3];
}

int aas_mul3(int *m, int i){
  int a, b, c, l = i+1;
  for(b = 1; 2*b <= l; b++){
    for(c = a = 0; 4*c <= 3*b && a < b; a++) c += m[l-2*b+a] == m[l-b+a];
    if(4*c > 3*b) return 0;
  }
  return 1;
}

int aas_mul4(int *m, int i){
  int a, b, c, l = i+1;
  for(b = 1; 2*b <= l; b++){
    for(c = a = 0; 2*c <= b && a < b; a++) c += m[l-2*b+a] == m[l-b+a];
    if(2*c > b) return 0;
  }
  return 1;
}

int aas_mul5(int *m, int i){
  int a, b, c, l = i+1;
  for(b = 1; 7*b <= 5*l; b++){
    for(c = a = 0; 5*c <= 2*b && a < b; a++) c += m[l-2*b+a] == m[l-b+a];
    if(5*c > 2*b) return 0;
  }
  return 1;
}

int abr(int *m, int i, int n, int d, int plus, int lon){
  int x;
  for(; (x = ceil32(lon*n+plus, d)) <= i+1; lon++) if(!abeq(m+i+1-x, m+i+1-x+lon, x-lon)) return 0;
  return 1;
}//*/

// after fgets: ch[strlen(ch)-1] = 0;