// gcc -O3 -o xhx xhx.c && ./xhx
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#include<math.h>
#include<inttypes.h>
#include<string.h>

int m[1000000], i;

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

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

int abbbab(){
 int a, b, l = i+1;
 for(b = 1; 2+4*b <= l; b++) for(a = 1+(b == 1); 2*a+4*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-4*b, m+l-a-b, a+b)) return 1;
 return 0;
}//*/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int forb(int *m, int i, char *ch){ // tests if ch is a suffix of m
 int a, x, l = i+1;
 x = strlen(ch);
 if(l < x) return 0;
 for(a = 0; a < x && m[l-x+a] == ch[a]-'0'; a++);
 return a == x;
}

int forbc(int *m, int i, char *ch){ // tests if bar{ch} is a suffix of m
 int a, x, l = i+1;
 x = strlen(ch);
 if(l < x) return 0;
 for(a = 0; a < x && m[l-x+a] != ch[a]-'0'; a++);
 return a == x;
}

int containsc(char *ch){ // tests if ch or bar{ch} is a factor of m
 int j = strlen(ch)-1;
 for(; j <= i; j++) if(forb(m, j, ch) || forbc(m, j, ch)) return 1;
 return 0;
}

int ok(){
 int a, l = i+1;
 for(a = 0; a < l-6 ; a++) if(neq(m+a, m+l-6, 6)) return 0;// tests if m contains bar{s}
 if(forb(m, i, "0000")) return 0;
 if(forb(m, i, "1111")) return 0;
 if(containsc("010101") && ababab()) return 0;
 if(containsc("001100") && aabbaa()) return 0;
 if(containsc("001001") && aabaab()) return 0;
 if(containsc("011011") && abbabb()) return 0;
 if(containsc("001010") && aababa()) return 0;
 if(containsc("010100") && ababaa()) return 0;
 if(containsc("011101") && abbbab()) return 0;
 if(containsc("010001") && abaaab()) return 0;
 if(containsc("011100") && abbbaa()) return 0;
 if(containsc("001110") && aabbba()) return 0;
 if(containsc("011000") && abbaaa()) return 0;
 if(containsc("000110") && aabbaa()) return 0;
 if(containsc("010111") && ababbb()) return 0;
 if(containsc("000101") && aaabab()) return 0;
 if(containsc("010110") && ababba()) return 0;
 if(containsc("011010") && abbaba()) return 0;
 return 1;
}

int A(){
 for(*m = i = 0; i < 200000;) if(ok(m, i)) m[++i] = 0; else{
  while(m[i]) if(!--i) return 1;
  m[i]++;
 }
 return 0;
}

int main(int ac, char **av){
 if(A()) printf("Backtracking finishes\n"); else printf("Backtracking reaches i=%d\n", i);
 return 0;
}