atoi(s)
char *s;
{
 int c, n;
 while (isspace(*s)) s++;
 c = *s == '+' || *s == '-' ? '+' - *s++ + 1 : 1;
 for (n = 0; isdigit(*s); n = 10 * n + *s++ - '0');
 return c * n;
}

char _seed[4] = { 1, 0, 0, 0 };

rand()
{
 static char a[4];
 static char b[4];
 static char c[4] = { 0x6D, 0x4E, 0xC6, 0x41 };
 static char d[4] = { 0x39, 0x30, 0, 0 };
 inline(221, 229, 33, _seed, 17, a, 1, 4, 0, 237, 176, 33, c);
 inline(17, b, 1, 4, 0, 237, 176, 33, _seed, 17, _seed + 1, 1);
 inline(3, 0, 54, 0, 237, 176, 221, 33, a, 33, b, 17, _seed);
 inline(14, 4, 6, 8, 197, 229, 221, 203, 0, 14, 48, 14, 213);
 inline(65, 175, 26, 142, 18, 19, 35, 16, 249, 209, 225, 229);
 inline(175, 65, 203, 22, 35, 16, 251, 225, 193, 16, 224, 221);
 inline(35, 35, 19, 13, 32, 215, 17, _seed, 33, d, 6, 4, 175);
 inline(26, 142, 18, 19, 35, 16, 249, 221, 225);
 return (_seed[2] + 256 * _seed[3]) & 32767;
}

srand(n)
{
 _seed[0] = n;
 _seed[1] = n >> 8;
 _seed[2] = 0;
 _seed[3] = 0;
}

#define HSZ    5000
#define NALLOC 128

typedef struct _hdr
{
 struct _hdr *ptr;
 unsigned size;
} HDR, *HDR_PTR;

HDR _BAS, *_BLK;

char *sbrk(n)
{
 static char HEAP[HSZ], *HPT = HEAP;
 char *p;
 if (HPT > HEAP + HSZ - n) return ERROR;
 p = HPT;
 HPT += n;
 return p;
}

free(p)
char *p;
{
 HDR *q, *r;
 q = cast (HDR_PTR) p - 1;
 for (r = _BLK; !(q > r && q < r -> ptr); r = r -> ptr)
  if (r >= r -> ptr && (q > r || q < r -> ptr)) break;
 if (q + q -> size == r -> ptr)
 {
  q -> size += r -> ptr -> size;
  q -> ptr = r -> ptr -> ptr;
 }
 else q -> ptr = r -> ptr;
 if (r + r -> size == q)
 {
  r -> size += q -> size;
  r -> ptr = q -> ptr;
 }
 else r -> ptr = q;
 _BLK = r;
}

HDR *morecore(n)
{
 char *p;
 HDR *q;
 n = NALLOC * ((n + NALLOC - 1) / NALLOC);
 p = sbrk(n * sizeof(HDR));
 if (cast (int) p == ERROR) return NULL;
 q = cast (HDR_PTR) p;
 q -> size = n;
 free(cast (char_ptr) (q + 1));
 return _BLK;
}

char *malloc(n)
{
 HDR *p, *q;
 if (n == 0) return NULL;
 n = 1 + (n + sizeof(HDR) - 1) / sizeof(HDR);
 if ((q = _BLK) == NULL)
 {
  _BAS.ptr = _BLK = q = &_BAS;
  _BAS.size = 0;
 }
 p = q -> ptr;
 while (TRUE)
 {
  if (p -> size >= n)
  {
   if (p -> size == n) q -> ptr = p -> ptr;
   else
   {
    p -> size -= n;
    p += p -> size;
    p -> size = n;
   }
   _BLK = q;
   return cast (char_ptr) (p + 1);
  }
  if (p == _BLK) if ((p = morecore(n)) == NULL) return NULL;
  q = p;
  p = p -> ptr;
 }
}

char *calloc(n, size)
{
 char *p;
 if ((p = malloc(n * size)) == NULL) return NULL;
 *p = 0;
 move(p + 1, p, n * size - 1);
 return p;
}

char *realloc(p, n)
char *p;
{
 char *q;
 if ((q = malloc(n)) == NULL) return NULL;
 if (p = NULL) return q;
 move(q, p, n);
 free(p);
 return q;
}

char *bsearch(key, base, n, size, cmp)
char *key, *base;
int (*cmp)();
{
 char *a, *b, *c;
 int i;
 a = base;
 b = base + n * size;
 while (a != b)
 {
  c = (b - a) / (size * 2) * size + a;
  i = (*cmp)(key, c);
  if (i == 0) return c;
  if (i > 0) a = c + size;
  if (i < 0) b = c;
 }
 return NULL;
}

qsort(base, n, size, cmp)
char *base;
int (*cmp)();
{
 int g, b, i;
 char *p;
 for (g = n >> 1; g > 0; g >>= 1)
 {
  b = g * size;
  for (i = g; i < n; i++)
   for (p = base + i * size - b; p >= base; p -= b)
   {
    if ((*cmp)(p, p + b) <= 0) break;
    swap(p, p + b, size);
   }
 }
}

abs(n)
{
 return n >= 0 ? n : -n;
}