#include <stdio.h>
#include <malloc.h>
#include <unistd.h>
#include <string.h>

typedef unsigned char byte;
typedef unsigned short word;
typedef unsigned long lword;

#define NR_X  256
#define NR_Y  256

long count[NR_X][NR_Y];
#define ADD(X,Y) if (0 <= X && X < NR_X && 0 <= Y && Y < NR_Y) count[X][Y]++

void init_count()
{	for (int i = 0; i < NR_X; i++)
		for (int j = 0; j < NR_Y; j++)
			count[i][j] = 0;
}

void print_count()
{
	for (int j = NR_Y-1; j >= 0; j--)
	{	printf("\n%3d ", j);
		for (int i = 0; i < NR_X; i++)
			printf("%c",
				//i == j ? '/' :
				count[i][j] == 0 ? ' ' :
				count[i][j] < 3 ? '.' :
				count[i][j] < 10 ? '-' :
				count[i][j] < 100 ? ',' :
				count[i][j] < 1000 ? '+' :
				count[i][j] < 10000 ? '*' : '#');
	}
}

int wlen  =  9;
int wlen2 = 18;
int wlen3 = 27;
int wlen4 = 36;

char *buf = 0;
lword buflen;

int nr_pos = 0;
lword ps[22];
int vs[22];
char kinds[22];

int c = 0;
char line[90];

void process_line()
{	if (c == 0)
		return;
	line[c] = '\0';
	c = 0;
	
	int empty = 1;
	char *s;
	for (s = line; *s != '\0'; s++)
		if (*s != '_')
		{	empty = 0;
			break;
		}
	if (empty)
	{	if (strlen(line) > 4)
			printf("\n#");
		return;
	}

	int correct = 0;
	int warning = 0;
	char ch = 0;
	if (strncmp(s, "* * * * ", 8) == 0)
	{	s += 8;
		
		correct = 1;
		for (int i = 0, k = 0x01; i < 8; i++, s += 8, k=k*2)
		{
			if (strncmp(s, "_* * * * ", 8) == 0)
			{	s++;
				warning = 1;
			}
			
			if (strncmp(s, "* * * * ", 8) == 0)
				ch |= k;
			else if (strncmp(s, "________", 8) == 0)
				;
			else
			{	correct = 0;
				break;
			}
		}
	}
	if (correct)
	{	printf("\n1");
		for (int i = 0, k = 0x01; i < 8; i++, s += 8, k=k*2)
			printf("%d", (ch & k) != 0);
		if (warning)
			printf(" ! %s", line);
	}
	else
		printf("\n? %s", line);
}

void add_to_line(char *s)
{	while (*s != '\0')
		line[c++] = *s++;
	if (c >= 81)
		process_line();
}



char mode = ' ';

inline long min(long a, long b) { return a < b ? a : b; }
inline long max(long a, long b) { return a < b ? b : a; }

int many_s = 0;
int nr_l = 0;

void process()
{
	//if (mode != kinds[0])
	//	printf("\n");
	//mode = kinds[0];
	//printf("\n%c", kinds[0] - 'a' + 'A');
	if (kinds[0] == 's')
	{	if (many_s < 1000)
			many_s++;
		add_to_line("_");
		nr_l = 0;
	}
	else
	{	if (many_s > 90 || many_s == 9)
			process_line();
		many_s = 0;
		add_to_line("* ");
		nr_l = (nr_l + 1) % 4;
		
	}
	
	if (nr_pos == 1)
		return;

#ifdef USE_NEW_ALGORITHM	

	lword len1 = (kinds[0] == 's' ? wlen2 : wlen4);
	lword begin1 = ps[0];
	lword end1 = begin1 + len1; 
	lword np = end1 + wlen2;
	int max_v = 0;
	int best_i = -1;
	int met_higher = 0;
	for (int i = 1; i < nr_pos /*&& ps[i] < np*/; i++)
	{	lword len2 = (kinds[i] == 's' ? wlen2 : wlen4);
		lword begin2 = ps[i];
		lword end2 = begin2 + len2;
		
		lword a = begin1;
		lword b = end1;
		lword c = begin2;
		lword d = end2;

		lword av = 0;
		if (end2 < end1)
		{	// second inside first
			if (vs[i] < vs[0])
				b = c = d = a;  // there is no gain
			else
			{	av = vs[0];
				b = begin2;	
				d = c = end2;
			}
		}
		else if (begin2 < end1)
		{	// overlap
			av = vs[i] < vs[0] ? vs[i] : vs[0];
			b = begin2;
			c = end1;						
		}
		
		if (a < d)
		{ 
			lword v = ((b - a) * vs[0] + (c - b) * av + (d - c) * vs[i])/(d - a);
			
			if (v > max_v)
			{	best_i = i;
				max_v = v;
			}
		}
	}

#else // USE OLD ALGORITHM

	long len1 = (kinds[0] == 's' ? wlen2 : wlen4);
	long begin1 = ps[0];
	long end1 = begin1 + len1;
	long v1 = vs[0];
	
	lword np = end1 + wlen + wlen/2;
	int max_v = 0;
	int max_v_s = 0;
	int best_i = -1;
	int met_higher = 0;

	int debug = 0;

	if (debug)
		printf("\n%c:%ld", kinds[0],vs[0]);
	for (int i = 1; i < nr_pos && ps[i] < np; i++)
	{	long begin2 = ps[i];
		long len2 = (kinds[i] == 's' ? wlen2 : wlen4);
		long end2 = begin2 + len2;
		long v2 = vs[i];

		if (debug)
			printf(" %c:%2ld:%4d", kinds[i], ps[i] - ps[0], vs[i]);
		if (kinds[i] == 'l' && nr_l > 1)
			v2 *= nr_l;
			
		if (end2 <= end1 && v2 <= v1)
		{	// ignore, completely inside
			if (debug)
				printf("=i"); 
		}
		else
		{	long v;
		
			if (end1 <= begin2)
			{	v = v2 - max(v1,v2) * (begin2 - end1) / min(len1,len2);
				if (debug)
					printf("=g%ld", v);
			}
			else // end1 > begin2
			{
				v = v2 - v1 * (end1 - begin2) / len1;
				if (debug)
					printf("=o%ld", v);
			}
			if (v > max_v)
			{	best_i = i;
				max_v = v;
				if (debug)
					printf("!");
			}
			//if (kinds[i] == 's' && v2 > max_v_s)
			//	max_v_s = v2;
		}
	}
	
#endif	

	/*
	printf("%c", met_higher ? '!' : ' ');
	*/
	
	//printf("\n");
	//for (int l = 0; l <= best_i; l++)
	//	printf(" %c:%2ld:%4d", kinds[l], ps[l] - ps[0], vs[l]);
	
	
	if (debug)
		printf(" %d:%2ld", best_i,ps[best_i]-ps[0]);

	if (best_i == -1)
		best_i = 1;
	nr_pos -= best_i;
	for (int i = 0; i < nr_pos; i++)
	{	ps[i] = ps[i+best_i];
		vs[i] = vs[i+best_i];
		kinds[i] = kinds[i+best_i];
	}
}


void insert(lword p, int v, char k)
{	if (nr_pos == 20)
		process();
	int i;
	for (i = 0; i < nr_pos; i++)
		if (ps[i] >= p)
			break;
	if (i < nr_pos && ps[i] == p)
	{	if (vs[i] < v)
			kinds[i] = k;
		return;
	}
	
	for (int j = nr_pos; j > i; j--)
	{	ps[j] = ps[j-1];
		vs[j] = vs[j-1];
		kinds[j] = kinds[j-1];
	}
	nr_pos++;
	ps[i] = p;
	vs[i] = v;
	kinds[i] = k;
}

void start_signal(lword p)
{	//printf("\n<%ld",p);
	printf("\n<");
	c = 0;
	nr_l = 0;
	many_s = 0;
}

void end_signal(lword p)
{	
	for(; nr_pos > 0; nr_pos--)
	{	process();
		
		nr_pos--;
		for (int i = 0; i < nr_pos; i++)
		{	ps[i] = ps[i+1];
			vs[i] = vs[i+1];
			kinds[i] = kinds[i+1];
		}
	}
	process_line();
	printf("\n>");
}

void add_max_s_at(lword p, int v)
{	insert(p,v,'s');
}  

void add_max_l_at(lword p, int v)
{	insert(p,v,'l');
}  

long ext_at_s;
int max_s;
int prev_max_s;
int sign_s[50];
long ext_at_l;
int max_l;
int prev_max_l;
int sign_l[50];

int main(int argc, char *argv[])
{
	init_count();
	
	if (argc != 2)
	{	printf("usage: waves <fn>");
		return 0;
	}
		
	{		
		FILE *f = fopen(argv[1], "rb");
		if (f == NULL)
		{	printf("Cannot open first file\n");
			return 0;
		}
	
		// Determine file size (in length)
		int fh = fileno(f);
		buflen = lseek(fh, 0L, SEEK_END);
		lseek(fh, 0L, SEEK_SET);
	
		buf = (char*)malloc(buflen);
	
		// Read the whole file into buffer
		if (buflen != fread(buf, 1, buflen, f))
		{	printf("Reading error\n");
			return 0;
		}
		fclose(f);
	}

	byte have_signal = 0;
	byte signal_count = 0;
	
	ext_at_s = 0;
	max_s = 0;
	ext_at_l = 0;
	max_l = 0;
	
	{	int i;
		for (i = 0; i < wlen; i++)
		{	sign_s[0*wlen + i] =  1;
			sign_s[1*wlen + i] = -1;
			sign_s[2*wlen + i] =  1;
			sign_s[3*wlen + i] = -1;
			sign_l[0*wlen + i] =  1;
			sign_l[1*wlen + i] =  1;
			sign_l[2*wlen + i] = -1;
			sign_l[3*wlen + i] = -1;
		}
	}
		
	int sum_s = 0;
	int sum_l = 0;

	for (lword p = 0; p < buflen - wlen4-2 /*&& p < 1000000L*/; p++)
	//for (lword p = 5415000; p < 5998000; p++)
	{
		if (buf[p] > 10 || buf[p] < -10)
		{	if (have_signal == 0)
			{	start_signal(p);
				signal_count = 0;
				int i;
				sum_s = 0;
				sum_l = 0;
				for (i = 0; i < wlen4; i++)
				{	sum_s += sign_s[i] * buf[p + i];
					sum_l += sign_l[i] * buf[p + i];
				}
			}
			have_signal = 50;
		}
		else if (have_signal > 0)
		{	have_signal--;
			if (have_signal == 0)
				end_signal(p);
		}
		
		if (have_signal)
		{
			if (sum_s < 0 && max_s > 0)
			{	if (max_s > 100)
					add_max_s_at(ext_at_s, max_s);
				max_s = 0;
			}
			else if (sum_s > max_s)
			{	max_s = sum_s;
				ext_at_s = p;
			}

			if (sum_l < 0 && max_l > 0)
			{	if (max_l > 100)
					add_max_l_at(ext_at_l, max_l);
				max_l = 0;
			}
			else if (sum_l > max_l)
			{	max_l = sum_l;
				ext_at_l = p;
			}
			
			// differential
			sum_s += -   sign_s[0    ] * buf[p        ]
			         - 2*sign_s[wlen ] * buf[p + wlen ]
			         - 2*sign_s[wlen2] * buf[p + wlen2]
			         - 2*sign_s[wlen3] * buf[p + wlen3]
			         +   sign_s[wlen3] * buf[p + wlen4];
			sum_l += -   sign_l[0    ] * buf[p        ]
			         - 2*sign_l[wlen2] * buf[p + wlen2]
			         +   sign_l[wlen3] * buf[p + wlen4];
		}
	}
	printf("\n");
	
	//print_count();
}