/* strcpy:copy t to s;array subscript version */
void strcpy(char *s, char *t)
{
   int i;

   i = 0;
   while ((s[i] = t[i]) != '\0')
           i++;
}
/* strcpy: copy t to s; pointer version 1 */
void strcpy((*s = *t) != '\0') {
     s++;
     t++;
}

/* strcpy: copy t to s; pointer version 2 */
void strcpy(char *s, char *t) {
     while (( *s++ = *t++)  != '\0')
            ;
}
/* strcpy: copy t to s ; pointer version 3 */
void strcpy(char *s, char *t){
     while (*s++ = *t++)
            ;
}

/* strlen: return length of string s */
int strlen(char *s){
    char *p = s; 
    while (*p != '\0')
          p++;
    return p - s;
}

#define ALLOCSIZE   1000     /*size of available space */
static char allocbuf[ALLOCSIZE];   /*storage for alloc */
static char *allocp = allocbuf;    /* next free position */

char *alloc(int n) /*return pointer to n characters */
{
   if (allocbuf + ALLOCSIZE -allocp >= n){   /* it fits */
      allocp += n;
      return allocp - n;   /*old p */
   }else   /*not enough room */
        return 0;
}
void afree(char *p)   /* free storage pointed to by p */
{
   if (p >= allocbuf && p <allocbuf + ALLOCSIZE)
       allocp = p;
}

/*strlen: return length of a string */
int strlen(char *s){
    int n;

    for (n = 0; *s != '\0'; s++)
         n++;
    return n;
}

#include <ctype.h>
int getch(void);
void ungetch(int);

/* getint: get next integer from input into *pn */
int getint(int *pn){
    int c, sign;

    while (isspace(c =getch()))   /*skip white space */
           ;
    if (!isdigit(c) && c != EOF && c != '+' && c != '-'){
        ungetch(c);
        return 0;
    }
    sign = (c == '-') ? -1 : 1;
    if (c == '+' || c == '-')
        c =getch();
    for (*pn = 0; isdigit(c); c =getch())
         *pn = 10 * *pn + (c - '0');
    *pn *= sign;
    if (c != EOF)
       ungetch(c);
    return c;
}

void swap(int v[], int i, int j){
     int temp;
     
      temp = v[i];
      v[i] = v[j];
      v[j] = temp;
}
/*swap: without temp */
void swap(int v[], int i , int j){
   v[i] ^= v[j];
   v[j] ^= v[i];
   v[i] ^= v[j];
}

/*qsort: sort v[left]....v[right] into increasing order */
void qsort(int v[], int left, int right){
     int i, last;
     void swap(int v[], int i , int j);
     
     if (left >= right)   /*do nothing if array contains */
         return;          /*fewer than two elements */
     swap(v, left, (left + right) /2);     /*move partition elem */
     last = left;                          /* to v[0] */
     for(i =left + 1; i <= right; i++)     /* partition */
         if (v[i] < v[left])
             swap(v, ++last, i);
     swap(v ,left, last);                /*restore partition elem */
     qsort(v ,left, last -1);
     qsort(v ,last + 1, right);
}

#include <stdio.h>

/*printd: print n in decimal */
void printd(int n){
     if (n < 0){
        putchar('-');
        n = -n;
     }
     if (n /10)
        printd(n /10);
     putchar(n %10 + '0');
}

#define BUFSIZE  100

char buf[BUFSIZE];    /*buffer for ungetch */
int bufp =0;          /*next free position in buf */

int getch(void) /*get a (possibly pushed back) character */
{
  return (bufp > 0) ? buf[--bufp]: getchar();
}
void ungetch(int c) /*push character back on input */
{
   if(bufp >=BUFSIZE)
      printf("ungetch:too many characters\n");
   else
     buf[bufp++] =c;
}

#include <ctype.h>

int getch(void);
void ungetch(int);

/*getop: get next operator or numeric operand */
int getop(char s[]){
    int i, c;

    while ((s[0] = c =getch()) == ' ' || c =='\t')
            ;
    s[1] ='\0';
    if (!isdigit(c) && c != '.')
         return c;            /*not a number */
    i =0;
    if (isdigit(c))    /*collect integer part */
       while(isdigit(s[++i] =c=getch()))
        ;
    if (c == '.')   /*collect fraction part */
        while (isdigit(s[i++] =c=getch()))
              ;
    s[i] ='\0';
    if (c != EOF)
        ungetch(c);
    return NUMBER;
}