/* ************************************************************************************
     memory required: 19*N*integers
 **************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long ulong;

ulong null;
ulong N, N_1;

#define F1(f) FStart[f]
#define F2(f) ((FStart[f]==null)?(null):(FNext[FStart[f]]))
#define F3(f) ((F2(f)==null)?(null):(FNext[F2(f)]))
#define Big(f) ((F2(f)==null)?(F1(f)):((CSize[F1(f)]>CSize[F2(f)])?(F1(f)):(F2(f))))

class STACK {
public:
	ulong* body;
	ulong Top;
	STACK() { body=0;}
	void init(ulong* b) { body=b; Top=null; }
	void Push(ulong a) {
		if (Top == null)
			body[Top=0]=a;
		else
			body[++Top]=a;
	}
	ulong Pop() {
		ulong x;
		if (Top == null) return null;
		x=body[Top];
		if (Top == 0)
			Top=null;
		else
			Top--;
		return x;
	}
	ulong& operator[] (ulong i) { return body[i]; }
};//end class STACK

class FIFO {
public:
	ulong* body;
	ulong First, Last;
	FIFO() { body=0; }
	void init(ulong* b) { body=b; First=Last=null; }
	void In(ulong a) {
		if (Last == null) 
			body[First=Last=0]=a;
		else
			body[++Last]=a;
	}
	ulong Out() {
		ulong x;
		
		if (First == null) return null;
		x = body[First];
		if (First == Last)
			First=Last=null;
		else
			First++;
		return x;
	}
	ulong& operator[] (ulong i) { return body[i]; }

};//end class FIFO



class CROCH {
private:
	ulong *block;
	ulong block_size;

	ulong* CStart;  // 1
	ulong* CEnd;	// 2
	ulong* CNext;	// 3
	ulong* CPrev;	// 4
	ulong* CMember;	// 5
	ulong* CSize;	// 6
	STACK CEmpty;	// 7

	STACK FStart;	// 8
	ulong* FNext;	// 9
	ulong* FPrev;    // 10
	ulong* FMember;	// 11

	ulong* Refine;	// 12
	STACK RStack;	// 13

	FIFO Sel;   	// 14
	FIFO Sc;		// 15

	ulong* Gap;		// 16
	ulong* GMember;	// 17
	ulong* GNext;	// 18
	ulong* GPrev;	// 19

public:
	CROCH() { block=0; block_size=0; }

	// method Process ---------------------------------------------------------------------
	// process the input string
	ulong Process(char* string,FILE* fp=stdout) {
		ulong L;
		bool done;
		ulong count=0;
		
		ulong n = strlen(string);
		init(n);
		showString(string,N);
		L = 1;
		done = Level_1(string);
		showRuns(string,L);
		count += countRuns(L);
		while(!done) {
			L++;
			done = Level(L);
			showRuns(string,L);
			count += countRuns(L);
		}
		fprintf(fp,"\n\nnumber of runs: %u\n",count);
		return count;
	}//end Process


	// method init ------------------------------------------------------------------------
	// allocate space and initilaize it
	void init(ulong n) {
		ulong* x;

		N=null=n;
		N_1=N-1;
		ulong size = 19*sizeof(ulong)*N;

		if (block_size < size) {
			if (block_size > 0)
				delete[] block;
			block_size=size;
			block = new ulong[block_size];
		}
		for(ulong i=0; i < block_size; block[i++]=null);
		CStart = block;
		CEnd = block+N;
		CNext = CEnd+N;
		CPrev = CNext+N;
		CMember = CPrev+N;
		CSize = CMember+N;
		x = CSize+N;
		CEmpty.init(x);
		x = x+N;
		FStart.init(x);
		FNext = x+N;
		FPrev = FNext+N;
		FMember = FPrev+N;

		Refine = FMember+N;
		x = Refine+N;
		RStack.init(x);

		x = x+N;
		Sel.init(x);
		x = x+N;
		Sc.init(x);

		Gap = x+N;
		GMember = Gap+N;
		GNext = GMember+N;
		GPrev = GNext+N;

		// all classes are empty
		for(ulong i=0; i < N; i++)
			CEmpty[i]=N_1-i;
		CEmpty.Top=N_1;
	}//end init

	/* **********************************************************************************
	 *                                auxiliary methods                                 *
	 ************************************************************************************ */

	#define showFStart() showArray(FStart.body)
	#define showFNext() showArray(FNext)
	#define showRefine() showArray(Refine)
	#define showRStack() showArray(RStack.body)

	void showArray(ulong *x, FILE *fp = stdout) {
		for(ulong i = 0; i < N; i++) {
			if (x[i]==null)
				fprintf(fp,"null ");
			else
				fprintf(fp,"%u ",x[i]);
		}
		fprintf(fp,"\n");
	}

	void showString(char* string,ulong n,FILE* fp=stdout) {
		ulong i;

		if (n >= 10) {
			for(i = 0; i < n; i++) {
				if (i < 10)
					fprintf(fp," ");
				else
					fprintf(fp,"%d",i/10);
			}
			fputc('\n',fp);
		}
		for(i = 0; i < n; i++) 
			fprintf(fp,"%d",i%10);
		fputc('\n',fp);
		for(i = 0; i < n; i++)
			fprintf(fp,"%c",string[i]);
		fputc('\n',fp);
		for(i = 0; i < n; i++)
			fputc('-',fp);
		fputc('\n',fp);
	}//end showString


	/* **********************************************************************************
	 *                             family handling methods                              *
	 ************************************************************************************ */

	// method showFamily -------------------------------------------------------------------
	void showFamily(ulong f,FILE *fp=stdout) {
		fprintf(fp,"f%u={c%u",f,FStart[f]);
		f = FStart[f];
		while ((f = FNext[f]) != null)
			fprintf(fp,",c%u",f);
		fprintf(fp,"}");
	}//end showFamily

	// method showFamilies -----------------------------------------------------------------
	void showFamilies(FILE *fp=stdout) {
		ulong f;
		bool empty;

		fprintf(fp,"families\n");
		for(empty = true, f = 0; f <= FStart.Top; f++) {
			if (FStart[f] != null) {
				showFamily(f,fp);
				fprintf(fp," ");
				empty = false;
			}
		}
		if (empty)
			fprintf(fp,"<empty>\n");
		else
			fprintf(fp,"\n");
	}//end showFamilies

	// method showSeeds --------------------------------------------------------------------
	void showSeeds(FILE *fp=stdout) {
		ulong f;
		bool empty;

		fprintf(fp,"seeds\n");
		for(empty = true, f = 0; f <= FStart.Top; f++) {
			if (FStart[f] != null) {
				showFamily(f,fp);
				fprintf(fp," ");
				empty = false;
			}
		}
		if (empty)
			fprintf(fp,"<empty>\n");
		else
			fprintf(fp,"\n");
	}//end showSeeds

	// method IT_Families -------------------------------------------------------------------
	// test integrity of families
	bool IT_Families(FILE *fp=stdout) {
		ulong f, f1, c, big;
		bool bad;

		if (FStart.Top == null) return true;

		for(bad = false, f = 0; f <= FStart.Top; f++) {
			if (FStart[f]==null) {
				fprintf(fp,"family %u failed top test\n",f);
				bad = true;
				getchar();
				continue;
			}
			big = Big(f);
			for(c = FStart[f]; c != null; c = FNext[c]) {
				if (c == FStart[f] && FPrev[c] != null) {
					fprintf(fp,"family %u failed link test 1\n",f);
					getchar();
					bad = true;
					break;
				}
				if (c != FStart[f] && FNext[FPrev[c]] != c ) {
					fprintf(fp,"family %u failed link test 2\n",f);
					bad = true;
					getchar();
					break;
				}
				if (FMember[c] != f) {
					fprintf(fp,"family %u failed integrity test\n",f);
					bad = true;
					getchar();
					break;
				}
				if (c != FStart[f] && c != big && CSize[c] > CSize[big]) {
					fprintf(fp,"family %u failed big test\n",f);
					bad = true;
					getchar();
					break;
				}
			}
			for(f1 = f+1; f1 <= FStart.Top; f1++) {
				if (! disjointF(f,f1)) {
					bad = true;
					fprintf(fp,"families %u and %u not disjoint\n",f,f1);
					showFamily(f,fp);
					fprintf(fp,"\n");
					showFamily(f1,fp);
					fprintf(fp,"\n");

					break;
				}
			}
		}
		if (! bad)
			fprintf(fp,"families passed integrity test\n");
		return ! bad;
	}//end IT_Families

	// method startFamily -------------------------------------------------------------------
	ulong startFamily(ulong c) {
		if (FStart.Top == null)
			FMember[c] = FStart.Top = 0;
		else
			FMember[c] = ++FStart.Top;
		FStart[FStart.Top] = c;
		FNext[c] = FPrev[c] = null;
		return FStart.Top;
	}//end startFamily

	// method addToFamily -------------------------------------------------------------------
	// add class c to family f, always as a second element
	void addToFamily(ulong c,ulong f) {
		ulong ff;

		// if size of c > size of F2(f), we make c F2(f)
		// otherwise we make c F3(f)

		FMember[c] = f;
		if (FNext[FStart[f]] == null) { // singleton family, so c will become F2(f)
			FNext[FStart[f]] = c;
			FNext[c] = null;
			FPrev[c] = FStart[f];
		}else{
			if (CSize[c] > CSize[F2(f)]) {  // c will become F2(f) and F2(f) will become F3(f)
				ff = F2(f);
				FNext[F1(f)] = c;
				FNext[c] = ff;
				if (ff != null) FPrev[ff] = c;
				FPrev[c] = F1(f);
			}else{ // c will become F3(f)
				ff = F3(f);
				FNext[F2(f)] = c;
				FNext[c] = ff;
				if (ff != null) FPrev[ff] = c;
				FPrev[c] = F2(f);
			}
		}
	}//end addToFamily

	// method isinF -------------------------------------------------------------------------
	// returns true if class e belongs to family f
	bool isinF(ulong e,ulong f) {
		ulong e1;
		bool in;

		for(in = false, e1 = FStart[f]; e1 != null; e1 = FNext[e1]) {
			if (e1 == e) {
				break;
				in = true;
			}
		}
		return in;
	}//end isinF

	/* ***********************************************************************************
	 *                          class handling methods                                   *
	 ************************************************************************************* */

	// method showClass ---------------------------------------------------------------------
	void showClass(ulong i,FILE *fp=stdout) {
		ulong j;

		j = CStart[i];
		fprintf(fp,"c%d={%u",i,j);
		if (j == CEnd[i]) {
			fprintf(fp,"}");
			return;
		}
		while(true) {
			j = CNext[j];
			fprintf(fp,",%u",j);
			if (j == CEnd[i]) {
				fprintf(fp,"}");
				break;
			}
		}
	}//end showClass

	// method showClasses ------------------------------------------------------------------
	void showClasses(FILE *fp=stdout) {
		ulong i;
		bool empty;

		fprintf(fp,"classes\n");
		for(empty = true, i = 0; i < N; i++) {
			if (CStart[i] == null) continue;
			showClass(i,fp);
			empty = false;
			fprintf(fp," ");
		}
		if (empty)
			fprintf(fp,"<empty>\n");
		else
			fprintf(fp,"\n");
	}//end showClasses

	// method isinC -------------------------------------------------------------------------
	// returns true if element e belongs to class c
	bool isinC(ulong e,ulong c) {
		ulong e1;
		bool in;

		for(in = false, e1 = CStart[c]; e1 != null; e1 = CNext[e1]) {
			if (e1 == e) {
				break;
				in = true;
			}
		}
		return in;
	}//end isinC

	// method disjointC --------------------------------------------------------------------
	// returns true if c1 and c2 are disjoint classes
	bool disjointC(ulong c1,ulong c2) {
		ulong e;

		for(e = CStart[c1]; e != null; e = CNext[e])
			if (isinC(e,c2)) return false;
		return true;
	}//end disjointC

	// method disjointF --------------------------------------------------------------------
	// returns true if f1 and f2 are disjoint families
	bool disjointF(ulong f1,ulong f2) {
		ulong e;

		for(e = FStart[f1]; e != null; e = FNext[e])
			if (isinF(e,f2)) 
				return false;
		return true;
	}//end disjointF

	// method IT_Classes --------------------------------------------------------------------
	bool IT_Classes(FILE *fp=stdout) {
		ulong i, j, e, prev, count;
		bool bad;

		for(bad = false, i = 0; i < N; i++) {
			if (CStart[i] == null) continue;
			prev = null;
			count = 0;
			for(e = CStart[i]; e != null; count++, prev = e, e = CNext[e]) {
				if (CMember[e] != i)  {
					bad = true;
					fprintf(fp,"class %u (element %u) failed membership test\n",i,e);
				}
				if (CPrev[e] != prev) {
					bad = true;
					fprintf(fp,"class %u (element %u) failed previous test\n",i,e);
				}
			}
			if (count != CSize[i]) {
				bad = true;
				fprintf(fp,"class %u failed size test\n",i);
			}
			for(j = i+1; j < N; j++) {
				if (CStart[j] == null) continue;
				if (! disjointC(i,j)) {
					bad = true;
					fprintf(fp,"classes %u and %u are not disjoint\n",i,j);
					showClass(i,fp);
					fprintf(fp,"\n");
					showClass(j,fp);
					fprintf(fp,"\n");
				}
			}
		}
		if (! bad)
			fprintf(fp,"classes passed integrity test\n");
		return ! bad;
	}//end IT_Classes

	// method showEmptyClasses --------------------------------------------------------------
	void showEmptyClasses(FILE *fp=stdout) {
		ulong i;
		bool empty;
		
		fprintf(fp,"empty classes\n");
		for(empty = true, i = 0; i <= CEmpty.Top; i++) {
			fprintf(fp,"%u ",CEmpty[i]);
			empty = false;
		}
		if (empty)
			fprintf(fp,"<empty>\n");
		else
			fprintf(fp,"\n");
	}//end showEmptyClasses

	// method showShowSmallClasses ----------------------------------------------------------
	void showSmallClasses(FILE *fp=stdout) {
		ulong f, c, big;
		bool empty;

		fprintf(fp,"small classes\n");
		for(empty = true, f=0; f <= FStart.Top; f++) {
			if (FNext[FStart[f]] == null)  {       // singleton family
				showClass(FStart[f],fp);
				fprintf(fp," ");
				continue;
			}
			empty = false;
			// determine the big class for family
			// it is either first or the second one
			big = Big(f);
			for(c = FStart[f];  c != null ; c = FNext[c]) {
				if (c == big) continue;
				showClass(c,fp);
				fprintf(fp," ");
			}
		}
		if (empty)
			fprintf(fp,"<empty>\n");
		else
			fprintf(fp,"\n");
	}//end showSmallClasses

	// method startNewClass -----------------------------------------------------------------
	// element e is put to a new class as a part of family f 	
	ulong startNewClass(ulong e,ulong f) {  
		ulong c = CEmpty.Pop();   // take first available empty class
		CStart[c] = CEnd[c] = e;
		CNext[e] = CPrev[e] = null;
		CSize[c] = 1;
		CMember[e] = c;
		if (f != null)
			addToFamily(c,f);
		return c;
	}//end startNewClass

	// method addToNewClass -----------------------------------------------------------------
	// element e is added to a new class c
	void addToNewClass(ulong e, ulong c, ulong f) {
		ulong l, r;
		
		CSize[c]++;
		if (F2(f) != c) {
			if (CSize[c] > CSize[F2(f)]) { // must move c to be F2(f)
				l = FPrev[c];
				r = FNext[c];
				if (l != null) FNext[l] = r;
				if (r != null) FPrev[r] = l;
				l = F2(f);
				FNext[F1(f)] = c;
				FNext[c] = l;
				if (l != null) FPrev[l] = c;
				FPrev[c] = F1(f);
			}
		}

		CNext[CEnd[c]] = e;
		CNext[e] = null;
		CPrev[e] = CEnd[c];
		CEnd[c] = e;
		CMember[e] = c;
		// now we have to add it to Gap
		insertGap(e,e-CPrev[e]);
	}//end addToNewClass 

	// method removeFromClass ----------------------------------------------------------------
	// element e is removed from an existing class
	void removeFromClass(ulong e) {
		ulong e1, e2, c, f, g;

		c = CMember[e];
		
		// first we have to adjust the gap for the right neighbour e1, if any
		e1 = CNext[e];
		if (e1 != null) {
			if (GMember[e1] != null) removeGap(e1,e1-e);
			e2 = CPrev[e];
			if (e2 != null) insertGap(e1,e1-e2);
		}

		CMember[e] = null; // removing e from class c
		CSize[c]--;        // class c shrinks
		// if a class in a family shrinks, it must be the parent, i.e.
		// the first class in the family
		if ((f = FMember[c]) != null) {
			if (FStart[f] != c) {
				printf("problem 1\n");
				exit(1);
			}
		}

		if (CSize[c] == 0) {
			if (f != null) {
				g = F2(f);
				FPrev[g] = null;
				FStart[f] = g;
				FNext[c] = FPrev[c] = null;
			}
			CEmpty.Push(c);
			CStart[c] = null;
		}else{
			if (CStart[c] == e) {
				e1 = CNext[e];
				CStart[c] = e1;
				CPrev[e1] = null;
			}else if (CEnd[c] == e) {
				e1 = CPrev[e];
				CEnd[c] = e1;
				CNext[e1] = null;
			}else{
				e1 = CPrev[e];
				e2 = CNext[e];
				CNext[e1] = e2;
				CPrev[e2] = e1;
			}
		}

		// now we have to remove e it from Gap, if it is there
		if ((g = GMember[e]) != null) {
			if (Gap[g] == e) {   // e is the first in Gap
				if (GNext[e] == null) {  // the list is {e}
					Gap[g] = null;
				}else{
					Gap[g]=GNext[e];
					GPrev[Gap[g]]=null;
					GNext[e]=null;
				}
			}else if (GNext[e] == null) { // e is the last in Gap
				// e has previous, otherwise e is the first as well
				GNext[GPrev[e]] = null;
				GPrev[e] = null;
			}else{ // e is in the middle of Gap
				GNext[GPrev[e]] = GNext[e];
				GPrev[GNext[e]] = GPrev[e];
				GNext[e] = GPrev[e] = null;
			}
			GMember[e] = null;
		}
	}//end RemoveFromClas

	/* ***********************************************************************************
	 *                          snapshot handling methods                                *
	 ************************************************************************************* */

	// method showSnapshot ------------------------------------------------------------------
	void showSnapshot(FILE *fp=stdout) {
		ulong send, e, sc_First, sc_Last, sel_First, sel_Last;
		char ind;

		fprintf(fp,"snapshot:\n");
		// we must preserve First and Last
		sc_First = Sc.First;
		sc_Last = Sc.Last;
		sel_First = Sel.First;
		sel_Last = Sel.Last;

		while((send = Sc.Out()) != null) {
			ind = '{';
			while((e = Sel.Out()) != send) {
				if (e == null) {
					printf("snapshot problem\n");
					exit(1);
				}
				fprintf(fp,"%c%u",ind,e);
				ind = ',';
			}//endwile
			fprintf(fp,"%c%u}",ind,e);
		}//endwhile
		fprintf(fp,"\n");

		// we must restore First and Last
		Sc.First = sc_First;
		Sc.Last = sc_Last;
		Sel.First = sel_First;
		Sel.Last = sel_Last;
	}//end showSnapshot

	// method createSnapshot -----------------------------------------------------------------
	bool createSnapshott(ulong L) { // Create snapshot from current level for level L
									// parent-seed new families
		ulong f, c, c1, big, s, e, sc;
		ulong maxd, x;
		
		// at this point RStack is not needed, we use it to seed new families
		RStack.Top = null;

		for(f = 0; f <= FStart.Top; f++) { // traverse all families
			s = FStart[f];
			if (FNext[s] == null) {				// *** singleton family
				if (CSize[s] == 1) {			// ** singleton family of a singleton class
					CMember[CStart[c]] = null;  // remove the singleton class
					CStart[s] = null;
					CSize[s] = 0;
					CEmpty.Push(s);
				}else{							// ** singleton family of a thick class
					RStack.Push(s);			// make seed
				}
				FMember[s] = null;			// remove from family
			}else{								// *** thick family
				// determine big class
				big = Big(f);
				c = s; 
				while(c != null) {					// traverse the family
					if (CSize[c] == 1) {		// singleton class
						if (c == big) {
							CMember[CStart[c]] = null;
							CStart[c] = null;   // remove the class
							CSize[c] = 0;
							CEmpty.Push(c); 
							// do not put in snapshot as it is big
						}else{
							Sel.In(CStart[c]);  // put in snapshot
							Sc.In(CStart[c]);
							CMember[CStart[c]] = null; // remove the class
							CStart[c] = null;  
							CSize[c] = 0;
							CEmpty.Push(c);
						}
					}else{						// thick class
						RStack.Push(c);         // make seed
						if (c != big) {			// put in snapshot
							for(sc = e = CStart[c]; e != null; sc = e, e = CNext[e])
								Sel.In(e);
							Sc.In(sc);
						}
					}
					c1 = FNext[c];
					FNext[c] = FPrev[c] = null;		// remove from family
					FMember[c] = null;
					c = c1;
				}//endwhile
			}// end of singleton / thick family
			FStart[f] = null;		// remove family
		}//endfor

		// at this point, FStart[], FNext[] and FBig[] ought to be empty
		FStart.Top = null;

		// now all seeds are in RStack
		if (RStack.Top == null)
			return true; // to indicate done

		// seed the families and decide if we need to continue;
		maxd = 0;
		while((c = RStack.Pop()) != null) {
			if ((x = CEnd[c] - CStart[c]) > maxd) maxd = x;
			FStart.Push(c);
			FMember[c] = FStart.Top;
		}
		if (maxd < L)
			return true; // to indicate done

		return false; // to indicate not done
	}//end createSnapshott

	/* ************************************************************************************
	 *                        Gap handling methods                                        *
	 ************************************************************************************** */
	// method showGaps ----------------------------------------------------------------------
	void showGaps(FILE* fp=stdout) {
		ulong g, p;

		fprintf(fp,"Gaps:\n");
		for(g = 0; g < N; g++) {
			if (Gap[g]==null) continue;
			fprintf(fp,"gap %u:",g);
			for(p = Gap[g]; p != null; p = GNext[p])
				fprintf(fp,"%d ",p);
			fprintf(fp,"\n");
		}
	}//end showGaps

	// method insertGap ---------------------------------------------------------------------
	void insertGap(ulong p,ulong g) { // insert position p into Gap g
		if (Gap[g]==null) {
			Gap[g]=p;
			GNext[p]=GPrev[p]=null;
		}else{
			GPrev[p]=null;
			GNext[p]=Gap[g];
			GPrev[Gap[g]]=p;
			Gap[g]=p;
		}
		GMember[p]=g;
	}//end insertGap

	// method removeGap --------------------------------------------------------------------
	void removeGap(ulong p,ulong g) { // remove position p from Gap g
		if (Gap[g] == p) {            // p is first
			if (GNext[p] == null)
				Gap[g]=null;
			else{
				Gap[g] = GNext[p];
				GPrev[Gap[g]]=null;
				GNext[p]=null;
			}
		}else if (GNext[p]==null) {   // p is last
			GNext[GPrev[p]]=null;
			GPrev[p]=null;
		}else{                        // p in the middle
			GNext[GPrev[p]]=GNext[p];
			GPrev[GNext[p]]=GPrev[p];
			GNext[p]=GPrev[p]=null;
		}
		GMember[p]=null;
	}//end removeGap

	// method IT_Gaps -------------------------------------------------------------------
	// integrity test of Gaps
	bool IT_Gaps(FILE* fp=stdout) {
		ulong c, p, g, last, first;
		bool bad=false;

		// check GMember
		for(c = 0; c < N; c++) {
			if (CStart[c]==null) continue;
			p = CStart[c];
			if (GMember[p] != null) {
				printf("starting position %u of class %u is in Gap\n",p,c);
				bad=true;
			}
			while((p = CNext[p]) != null) {
				if (GMember[p] != p-CPrev[p]) {
					printf("position %u of class %u not in correct Gap\n",p,c);
					bad=true;
				}
			}
		}
		// check links
		for(g = 0; g < N; g++) {
			if (Gap[g] == null) continue;
			// traverse the list in both directions
			for(p = Gap[g]; p != null; p=GNext[p]) last=p;
			for(p = last; p != null; p=GPrev[p]) first=p;
			if (first != Gap[g]) {
				printf("Gap[%u] wrong links\n",g);
				bad=true;
			}
		}
		if (! bad) fprintf(fp,"Gaps integrity OK\n");
		return bad;
	}//end IT_Gaps


	/* **********************************************************************************
	 *                         Refine handling methods                                  *
	 ************************************************************************************ */

	// method cleanRefine ---------------------------------------------------------------
	void cleanRefine() {
		ulong c;

		while((c = RStack.Pop()) != null)
			Refine[c] = null;
	}//end cleanRefine

	/* **********************************************************************************
	 *                               level handling methods                             *
	 ************************************************************************************ */

	// method Level_1 ----------------------------------------------------------------------
	bool Level_1(char* string) {
		ulong i, j, c, c1, last;
		ulong count; // count singletons on level 0

		// on level 0 we do not list the implicit singleton class {N}
		// and for the snapshot we consider all classes small and {N} big

		for(i = 0; i < N; i++) {
			c = find(string[i]);  // position i goes to class c
			if (CStart[c] == null) { // class c does not exist yet
				CStart[c] = CEnd[c] = i;
				CNext[i] = CPrev[i] = null;
				CMember[i] = c;
				CSize[c] = 1;
				c1 = CEmpty.Pop();
				if (c1 != c) {
					printf("problem 2\n");
					exit(1);
				}
			}else{ // class c already exists
				CNext[CEnd[c]] = i;
				CNext[i] = null;
				CPrev[i] = CEnd[c];
				CSize[c]++;
				CEnd[c] = i;
				CMember[i] = c;
				insertGap(i,i-CPrev[i]);
			}
		}

		//clean up
		Sel[0]=null;  // was used by find()
		for(i = 0; i < N; i++) // were used by find
			FStart[i]=FNext[i]=FPrev[i]=null;
		// create a snapshot of small classes, all classes are small
		// and seed families and count singletons
		count = 0;
		for(i = 0; i < N; i++) { 
			if (CStart[i] == null) 
				continue;
			last = j = CStart[i];
			Sel.In(j);
			while((j = CNext[j]) != null) {
				Sel.In(j);
				last = j;
			}
			Sc.In(last);
			if (CSize[i] == 1) { // remove singleton class
				count++;
				CMember[CStart[i]] = null;
				CStart[i] = null;
				CSize[i] = 0;
				CEmpty.Push(i);
			}else{
				FStart.Push(i);		// make parent-seed
				FMember[i] = FStart.Top;
			}
		}//endfor

		if (count == N)  // all small classes were singletons, hence all done
			return true;
		return false;
	}//end Level_1

	// method Level --------------------------------------------------------------------
	// used to create levels 1 and up
	bool Level(ulong L) {
		ulong s, e, e1, c, d, f;
		bool done;

		while((s = Sc.Out()) != null) {
			if (s == 0) {  // then the small class is {0}
				Sel.Out();
				continue;
			}
			while(true) {
				e = Sel.Out();  // element of the snapshot of a small class
				if (e == 0) 
					if (e == s) {
						cleanRefine();
						break;
					}else
						continue;
				e1 = e-1;
				c = CMember[e1];    // e1 is a memeber of class c
				if (c == null) {
					if (e == s) {
						cleanRefine();
						break;
					}else
						continue;
				}
				f = FMember[c];		// family seeded by c
				removeFromClass(e1);
				if (Refine[c] == null) {  // no destination yet for class c
					RStack.Push(c);
					Refine[c] = startNewClass(e1,f);
				}else{                // there is destination for class c
					d = Refine[c];    // d is the destination for c
				    addToNewClass(e1,d,f);
				}
				if (e == s) {
					cleanRefine();
					break;
				}
			}//endwhile
		}//endwhile
		done = createSnapshott(L+1);

		return done;
	}//end Level

	/* ***********************************************************************************
	 *                        maximal repetitions handling methods                       *
	 ************************************************************************************* */
	
	// method traceMaxRep -------------------------------------------------------------------
	void traceMaxRep(ulong g,ulong p,ulong& first,ulong& last) {
		ulong q;

		first = last = p;
		RStack.Push(p);
		Refine[p]=1;
		while((q = CPrev[first]) != null) {
			if ((first-q) == g) {
				first = q;
				if (GMember[first] != null) {
					RStack.Push(first);
					Refine[first]=1;
				}
			}else
				break;
		}//endwhile
		// so we have first
			
		while((q = CNext[last]) != null) {
			if ((q-last) == g) {
				last = q;
				if (GMember[last] != null) {
					RStack.Push(last);
					Refine[last]=1;
				}
			}else
				break;
		}//endwhile
		// so we have position of the last occurrence of the generator
		last = last+g-1; // last position
	}//end traceMaxRep

	// method showMaxReps -----------------------------------------------------------------------
	void showMaxReps(ulong g,FILE* fp=stdout) {
		ulong p, first, last;

		// we use RStack+Refine to indicate if we already visited it
		for(p = Gap[g]; p != null; p = GNext[p]) {
			if (Refine[p]!=null) continue;
			traceMaxRep(g,p,first,last);
			showMaxRep(first,g,(last-first)/g,fp);
		}//endfor
		cleanRefine();
	}//end showMaxReps


	// method showMaxReps -------------------------------------------------------------------
	void showMaxReps(char* string,ulong g,FILE* fp=stdout) {
		ulong p, first, last;

		// we use RStack+Refine to indicate if we already visited it
		for(p = Gap[g]; p != null; p = GNext[p]) {
			if (Refine[p]!=null) continue;
			traceMaxRep(g,p,first,last);
			showMaxRep(string,first,g,(last-first+1)/g,fp);
		}//endfor
		cleanRefine();
	}//end showMaxReps

	// method showMaxRep ----------------------------------------------------------------
	void showMaxRep(ulong s,ulong p,ulong e,FILE* fp) {
		fprintf(fp,"(%u,%u,%u)\n",s,p,e);
	}

	// method showMaxRep ----------------------------------------------------------------
	void showMaxRep(char* string,ulong s,ulong p,ulong e,FILE* fp) {
		ulong i, j, k;
		bool toggle = false;

		for(i = 0; i < s; i++)
			fputc('.',fp);
		for(j = 0;  j < e; j++) {
			if (toggle) 
				toggle=false;
			else
				toggle=true;
			for(k = 0; k < p; k++) {
				if (toggle)
					fputc(string[i++],fp);
				else
					fputc(string[i++]-'a'+'A',fp);
			}//endfor
		}//endfor
		for( ; i < N; i++)
			fputc('.',fp);
		fputc('\n',fp);
	}//end showMaxRep


	// method countMaxR----------------------------------------------------------------------
	ulong countMaxReps(ulong g) {
		ulong p, first, last;
		ulong count = 0;

		// we use RStack+Refine to indicate if we already visited it
		for(p = Gap[g]; p != null; p = GNext[p]) {
			if (Refine[p]!=null) continue;
			traceMaxRep(g,p,first,last);
			count++;
		}//endfor
		cleanRefine();

		return count;
	}//end countMaxReps


	/* **********************************************************************************
	 *                       runs handling methods                                      *
	 ************************************************************************************ */

	// method tarceRuns ------------------------------------------------------------------
	ulong traceRuns(char* string,ulong g,FILE* fp,bool _show) {
		ulong p, first, last, fi, la, x;
		ulong count = 0;
		
		// we use RStack+Refine to indicate if we already visited it
		for(p = Gap[g]; p != null; p = GNext[p]) {
			if (Refine[p]!= null) continue; // already done
			traceMaxRep(g,p,first,last);
			
			// so we have the first and the last occurrence of the max repeat
			// we have to check if we can shift left or right

			// first check left shift
			while(first > 0) {
				fi = first-1+g;
				if (GMember[fi] == g) {  // so we can shift left
				    traceMaxRep(g,fi,first,x);
					continue;
				}else
					break;
			}//endwhile

			// then check right shift
			while(last < N_1) {
				la = last+2-g;
				if (GMember[la] == g) {  // so we can shift right
					traceMaxRep(g,la,x,last);
					continue;
				}else
					break;
			}//endwhile

			count++;
			if (_show)
				if (string == 0)
					showRun(first,g,(last-first+1)/g,(last-first+1)%g);
				else
					showRun(string,first,g,(last-first+1)/g,(last-first+1)%g);
		}//end for
		cleanRefine();

		return count;
	}//end traceRuns

	// method showRuns --------------------------------------------------------------------
	void showRuns(ulong g,FILE* fp=stdout) {
		traceRuns(0,g,fp,true);
	}

	// method showRuns --------------------------------------------------------------------
	void showRuns(char* string,ulong g,FILE* fp=stdout) {
		traceRuns(string,g,fp,true);
	}

	// method countRuns --------------------------------------------------------------------
	ulong countRuns(ulong g) {
		return traceRuns(0,g,stdout,false);
	}

	// method showRun ------------------------------------------------------------------
	void showRun(ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) {
		fprintf(fp,"(%u,%u,%u,%u)\n",s,p,e,t);
	}

	// method showRun ------------------------------------------------------------------
	void showRun(char* string,ulong s,ulong p,ulong e,ulong t,FILE* fp=stdout) {
		ulong i, j, k;
		bool toggle = false;

		for(i = 0; i < s; i++)
			fputc('.',fp);
		for(j = 0;  j < e; j++) {
			if (toggle) 
				toggle=false;
			else
				toggle=true;
			for(k = 0; k < p; k++) {
				if (toggle)
					fputc(string[i++],fp);
				else
					fputc(string[i++]-'a'+'A',fp);
			}//endfor
		}//endfor
		if (toggle)
			toggle=false;
		else
			toggle=true;
		for(j = 0; j < t; j++)
			if (toggle)
				fputc(string[i++],fp);
			else
				fputc(string[i++]-'a'+'A',fp);
		for( ; i < N; i++)
			fputc('.',fp);
		fputc('\n',fp);
	}//end showRun


	/* ***********************************************************************************
	 *                             private methods                                       *
	 ************************************************************************************* */
private:
	// method find ------------------------------------------------------------------------
	// it is only used for creation of level 0.
	// FStart, FNext, FBig are used to emulate a binary earch tree 
	// to sort out the letters in the input string; SelQu[0] is used 
	// as a static variable to remember the last node used
	ulong find(char c) {
		if (Sel[0] == null) {
			Sel[0] = 0;    // root
			FStart[0] = ulong(c);  // root
			FNext[0]=FPrev[0] = null;  // children
			return 0;
		}
		ulong n = 0;
		while(true) {
			if (ulong(c) == FStart[n]) 
				return n;   // character c belongs to class n
			if (ulong(c) < FStart[n]) { // go left
				if (FNext[n] == null) {
					Sel[0]++;
					FNext[n] = Sel[0];
					FStart[Sel[0]]=ulong(c);
					FNext[Sel[0]]=FPrev[Sel[0]]=null;
					return Sel[0];
				}else{
					n = FNext[n];
					continue;
				}	
			}else{ // go right
				if (FPrev[n] == null) {
					Sel[0]++;
					FPrev[n] = Sel[0];
					FStart[Sel[0]] = ulong(c);
					FNext[Sel[0]] = FMember[Sel[0]] = null;
					return Sel[0];
				}else{
					n = FPrev[n];
					continue;
				}	
			}
		}
	}//end find
};//end class CROCH

//#define _a1

int main() {

#ifdef _a1
	char string[] = "ababb";
#endif

	CROCH c;
	
#ifdef _a1
	c.Process(string);
#else
	FILE *fpi;
	char string[300];
	ulong max, i;

	fpi = fopen("xxx.asc","r");
	while(fgets(string,300,fpi) != 0) {
		for(i = 0; string[i] != ','; i++);
		string[strlen(string)-1]='\0';
		string[i]='\0';
		max = atoi(string);
		if (c.Process(&string[i+1]) != max) {
			printf("max should be %d\n",max);
			break;
		}
		printf("\n-----------------------------------------\n");
	}
#endif

	return 0;
}