#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
const  int height=400;
const  int width=400;//resolution
const int para_n[]={0,0,19,11,9,8,7,6};
const int para_s[]={1,2,4,8,16,32,64,128};
char* tested;
char signs[8];
double R;
int N;

typedef struct complex_num{double r;double i;}cpln;
cpln z;
const cpln one={1,0};
const cpln zero={0,0};

inline double ab(cpln c){return c.r*c.r+c.i*c.i;}//absolute value
inline cpln ad(cpln c,double x){c.r+=x;return c;}//adding real number
inline cpln adc(cpln c,cpln d){c.r+=d.r;c.i+=d.i;return c;}//cplx addition
inline cpln subc(cpln c,cpln d){c.r-=d.r;c.i-=d.i;return c;}
inline cpln mt(cpln c,cpln d){cpln r={c.r*d.r-c.i*d.i,c.r*d.i+c.i*d.r};return r;}//multiplication
inline cpln inv(cpln c){double u=c.r*c.r+c.i*c.i;cpln r={c.r/u,-c.i/u}; return r;}//1/z
inline cpln neg(cpln c){cpln r={-c.r,-c.i}; return r;}
inline cpln i2c(int i){cpln r={(double)i,0}; return r;}

int f(cpln c,cpln d,int i,long sym,int m){
  if(i<N && ab(ad(c,-1))*height*width<ab(d))
      return 1;
  else if(i==0)
       return 0;
  
  cpln nc=mt(z,c);
  cpln nd=adc(c,mt(z,d));
  int t=sym%m;
  if(signs[t]){nc=subc(i2c(t+1),nc);nd=neg(nd);}
  else nc=subc(nc, i2c(t));
  if(c.r>m/2)
  {
    for(int j=m-1;j>-1;j--)
    if(f(nc,nd,i-1,sym*m+j,m))return 1;
  }
  else{
    for(int j=0;j<m;j++)
    if(f(nc,nd,i-1,sym*m+j,m))return 1;
  }
  return 0;
}

int chk(double x,double y, int m){
  z.r=x;
  z.i=y;
  if(x*x+y*y>1||(m+1)*(m+1)*(x*x+y*y)<1)return 0;
  if(f(one,zero,N,m-1,m))
          return 1;
   return 0;
}

int main()
{ long time=clock(); 
  char* data=(char*)malloc(width*height);//pixels of the graph we are drawing
  for(int i=0;i<width*height;i++)data[i]=0;
  //check Gora's condition

  for(int m=2;m<4;m++){
  for(int s=0;s<para_s[m];s++){
    printf("m=%d, s=%d\n",m,s);
    long time2=clock();
    
  N=para_n[m];
  int s1=s;
  for(int i=0;i<m;i++){signs[i]=s1%2;s1/=2;}

  //find roots
  for(int i=0;i<width;i++){
    if(i%20==0)printf("%d\n",i);
     for(int j=0;j<height;j++)
       if(data[i+width*j]);
       else if(j>height-j)data[i+width*j]=data[i+width*(height-j)];
       else data[i+width*j]=m*chk(((double)i)*2/width-1,((double)j)*2/height-1, m);
  }
  free(tested);

    printf("%ld\n",clock()-time2);
  }
}

  
  //output
  int datas[]={0,255,210,170,130,90,50};
  FILE* out=fopen("out.pgm","wb");
  fprintf(out, "P2\n%d %d\n255\n",width, height);
  for(int i=0;i<width*height;i++){
     fprintf(out,"%d",datas[data[i]]);    
     if(i==width*height-1); else if(i%64==63)fputc('\n',out);else fputc(' ',out);}
   fputc('\n',out);
  fclose(out);
  printf("%ld\n",clock()-time);
}