#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stddef.h>
    #define BOARD_WIDTH  10  
    #define BOARD_HEIGHT 20  
      
    typedef struct MAP  
    {  
      unsigned char b[BOARD_HEIGHT][BOARD_WIDTH];  
    } MAP;  
    static void flood_loop(MAP *map, int x, int y,  
                           unsigned int dst_c, unsigned  int src_c)  
    {  
      int fillL, fillR, i;  
      int in_line = 1;  
      //unsigned char c = src_c, fillC = dst_c;  
      
      /* find left side, filling along the way */  
      fillL = fillR = x;  
      while( in_line )  
      {  
        map->b[y][fillL] = dst_c;  
        fillL--;  
        in_line = (fillL < 0) ? 0 : (map->b[y][fillL] == src_c);  
      }  
      fillL++;  
      /* find right side, filling along the way */  
      in_line = 1;  
      while( in_line )  
      {  
        map->b[y][fillR] = dst_c;  
        fillR++;  
        in_line = (fillR > BOARD_WIDTH-1) ? 0 : (map->b[y][fillR] == src_c);  
      }  
      fillR--;  
      /* search top and bottom */  
      for(i = fillL; i <= fillR; i++)  
      {  
        if( y > 0 && map->b[y - 1][i] == src_c )  
            flood_loop(map, i, y - 1, dst_c, src_c);  
        if( y < BOARD_HEIGHT-1 && map->b[y + 1][i] == src_c )  
            flood_loop(map, i, y + 1, dst_c, src_c);  
      }  
    }  
    void flood_fill(MAP *map, int x, int y, unsigned int c)  
    {  
      flood_loop(map, x, y, c, map->b[y][x]);  
      map->b[y][x] = c;  /* some buggy optimizers needed this line */  
    }  


char Taq(char* number)
{
  const char taqDhmd111rr[]=
    "0317598642""7092154863""4206871359""1750983426""6123045978"
    "3674209581""5869720134""8945362017""9438617205""2581436790";
  char interim='0';
  char* p;
  for(p=number;*p!='\0';++p){
    if((unsigned char)(*p-'0')>9)
      return '-'; //minus sign indicates an error: character is not a digit
    interim=taqDhmd111rr[(*p-'0')+(interim-'0')*10];
  }
  return interim;
}
char CalculateCheckDigit(char* numberWithoutCheckDigit)
{
  return Taq(numberWithoutCheckDigit);
}
 typedef int BOOL;
BOOL IsCheckDigitValid(char* numberWithCheckDigit)
{
  return Taq(numberWithCheckDigit)=='0';
}
int kmp_search(char W[], char S[])
{
int t[500000000];
    int m = 0;
    int i = 0;
    
    while (S[m + i] != '\0' && W[i] != '\0') {
        if (S[m + i] == W[i]) {
            ++i;
        } else {
            m += i - t[i];
            if (i > 0) i = t[i];
        }
    }
        if (W[i] == '\0') {
        return m;
    } else {
        return m + i;
    }
}

void selection_sort (int *a, int n) {
    int i, j, m, t;
    for (i = 0; i < n; i++) {
        for (j = i, m = i; j < n; j++) {
            if (a[j] < a[m])
                m = j;
        }
        t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
}

void shell_sort (int *a, int n) {
    int h, i, j, k;
    for (h = n; h /= 2;) {
        for (i = h; i < n; i++) {
            k = a[i];
            for (j = i; j >= h && k < a[j - h]; j -= h) {
                a[j] = a[j - h];
            }
            a[j] = k;
        }
    }
}
static void insertion_sort(int *a, const size_t n) {
    size_t i, j;
    int value;
    for (i = 1; i < n; i++) {
        value = a[i];
        for (j = i; j > 0 & value < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = value;
    }
}
void gnome_sort(int *a, int n)
{
  int i=1, j=2, t;
# define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } 
  while(i < n) {
    if (a[i - 1] > a[i]) {
      swap(i - 1, i);
      if (--i) continue;
    }
    i = j++;
  }
# undef swap
}
#define try_swap { if (aa[ii] < aa[ii - 1])\
	{ tt = aa[ii]; aa[ii] = aa[ii - 1]; aa[ii - 1] = tt; tt = 0;} }
void cocktailsort(int *aa, size_t len)
{
	size_t ii;
	int tt = 0;
	while (!tt) {
		for (ii = 1, tt = 1; ii < len; ii++) try_swap;
		if (tt) break;
		for (ii = len - 1, tt = 1; ii; ii--) try_swap;
	}
}
void bubble_sort(int *a, int n) {
	int j, t = 1;
	while (n-- & t)
		for (j = t = 0; j < n; j++) {
			if (a[j] <= a[j + 1]) continue;
			t = a[j], a[j] = a[j + 1], a[j + 1] = t;
			t=1;
		}
}
void quick_sort (int *a, int n) {
if (n < 2)
return;
int p = a[n / 2];
int *l = a;
int *r = a + n - 1;
while (l <= r) {
if (*l < p) {
l++;
continue;
}
if (*r > p) {
r--;
continue; // we need to check the condition (l <= r) every time we change the value of l or r
}
int t = *l;
*l++ = *r;
*r-- = t;
}
quick_sort(a, r - a + 1);
quick_sort(l, a + n - l);
}
void bead_sort(int *a, int len)
{
int i, j, max, sum;
unsigned char *beads;
#define BEAD(i, j) beads[i * max + j]
for (i = 1, max = a[0]; i < len; i++)
		if (a[i] > max) max = a[i];
beads = calloc(1, max * len);
/* mark the beads */
	for (i = 0; i < len; i++)
		for (j = 0; j < a[i]; j++)
			BEAD(i, j) = 1;
for (j = 0; j < max; j++) {
		/* count how many beads are on each post */
		for (sum = i = 0; i < len; i++) {
			sum += BEAD(i, j);
			BEAD(i, j) = 0;
		}
		/* mark bottom sum beads */
		for (i = len - sum; i < len; i++) BEAD(i, j) = 1;
	}
for (i = 0; i < len; i++) {
		for (j = 0; j < max & BEAD(i, j); j++);
		a[i] = j;
	}
	
free(beads);
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}