typedef unsigned int size_t; typedef long int wchar_t; typedef struct { int quot; int rem; } div_t; typedef struct { long int quot; long int rem; } ldiv_t; __extension__ typedef struct { long long int quot; long long int rem; } lldiv_t; extern size_t __ctype_get_mb_cur_max (void) __attribute__ ((__nothrow__)) ; extern double atof (__const char *__nptr) __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ; extern int atoi (__const char *__nptr) __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ; extern long int atol (__const char *__nptr) __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ; __extension__ extern long long int atoll (__const char *__nptr) __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ; extern double strtod (__const char *__restrict __nptr, char **__restrict __endptr) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern float strtof (__const char *__restrict __nptr, char **__restrict __endptr) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern long double strtold (__const char *__restrict __nptr, char **__restrict __endptr) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern long int strtol (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern unsigned long int strtoul (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; __extension__ extern long long int strtoq (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; __extension__ extern unsigned long long int strtouq (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; __extension__ extern long long int strtoll (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; __extension__ extern unsigned long long int strtoull (__const char *__restrict __nptr, char **__restrict __endptr, int __base) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern char *l64a (long int __n) __attribute__ ((__nothrow__)) ; extern long int a64l (__const char *__s) __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ; typedef unsigned char __u_char; typedef unsigned short int __u_short; typedef unsigned int __u_int; typedef unsigned long int __u_long; typedef signed char __int8_t; typedef unsigned char __uint8_t; typedef signed short int __int16_t; typedef unsigned short int __uint16_t; typedef signed int __int32_t; typedef unsigned int __uint32_t; __extension__ typedef signed long long int __int64_t; __extension__ typedef unsigned long long int __uint64_t; __extension__ typedef long long int __quad_t; __extension__ typedef unsigned long long int __u_quad_t; __extension__ typedef __u_quad_t __dev_t; __extension__ typedef unsigned int __uid_t; __extension__ typedef unsigned int __gid_t; __extension__ typedef unsigned long int __ino_t; __extension__ typedef __u_quad_t __ino64_t; __extension__ typedef unsigned int __mode_t; __extension__ typedef unsigned int __nlink_t; __extension__ typedef long int __off_t; __extension__ typedef __quad_t __off64_t; __extension__ typedef int __pid_t; __extension__ typedef struct { int __val[2]; } __fsid_t; __extension__ typedef long int __clock_t; __extension__ typedef unsigned long int __rlim_t; __extension__ typedef __u_quad_t __rlim64_t; __extension__ typedef unsigned int __id_t; __extension__ typedef long int __time_t; __extension__ typedef unsigned int __useconds_t; __extension__ typedef long int __suseconds_t; __extension__ typedef int __daddr_t; __extension__ typedef long int __swblk_t; __extension__ typedef int __key_t; __extension__ typedef int __clockid_t; __extension__ typedef void * __timer_t; __extension__ typedef long int __blksize_t; __extension__ typedef long int __blkcnt_t; __extension__ typedef __quad_t __blkcnt64_t; __extension__ typedef unsigned long int __fsblkcnt_t; __extension__ typedef __u_quad_t __fsblkcnt64_t; __extension__ typedef unsigned long int __fsfilcnt_t; __extension__ typedef __u_quad_t __fsfilcnt64_t; __extension__ typedef int __ssize_t; typedef __off64_t __loff_t; typedef __quad_t *__qaddr_t; typedef char *__caddr_t; __extension__ typedef int __intptr_t; __extension__ typedef unsigned int __socklen_t; typedef __u_char u_char; typedef __u_short u_short; typedef __u_int u_int; typedef __u_long u_long; typedef __quad_t quad_t; typedef __u_quad_t u_quad_t; typedef __fsid_t fsid_t; typedef __loff_t loff_t; typedef __ino_t ino_t; typedef __dev_t dev_t; typedef __gid_t gid_t; typedef __mode_t mode_t; typedef __nlink_t nlink_t; typedef __uid_t uid_t; typedef __off_t off_t; typedef __pid_t pid_t; typedef __id_t id_t; typedef __ssize_t ssize_t; typedef __daddr_t daddr_t; typedef __caddr_t caddr_t; typedef __key_t key_t; typedef __time_t time_t; typedef __clockid_t clockid_t; typedef __timer_t timer_t; typedef unsigned long int ulong; typedef unsigned short int ushort; typedef unsigned int uint; typedef int int8_t __attribute__ ((__mode__ (__QI__))); typedef int int16_t __attribute__ ((__mode__ (__HI__))); typedef int int32_t __attribute__ ((__mode__ (__SI__))); typedef int int64_t __attribute__ ((__mode__ (__DI__))); typedef unsigned int u_int8_t __attribute__ ((__mode__ (__QI__))); typedef unsigned int u_int16_t __attribute__ ((__mode__ (__HI__))); typedef unsigned int u_int32_t __attribute__ ((__mode__ (__SI__))); typedef unsigned int u_int64_t __attribute__ ((__mode__ (__DI__))); typedef int register_t __attribute__ ((__mode__ (__word__))); typedef int __sig_atomic_t; typedef struct { unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))]; } __sigset_t; typedef __sigset_t sigset_t; struct timespec { __time_t tv_sec; long int tv_nsec; }; struct timeval { __time_t tv_sec; __suseconds_t tv_usec; }; typedef __suseconds_t suseconds_t; typedef long int __fd_mask; typedef struct { __fd_mask __fds_bits[1024 / (8 * (int) sizeof (__fd_mask))]; } fd_set; typedef __fd_mask fd_mask; extern int select (int __nfds, fd_set *__restrict __readfds, fd_set *__restrict __writefds, fd_set *__restrict __exceptfds, struct timeval *__restrict __timeout); extern int pselect (int __nfds, fd_set *__restrict __readfds, fd_set *__restrict __writefds, fd_set *__restrict __exceptfds, const struct timespec *__restrict __timeout, const __sigset_t *__restrict __sigmask); __extension__ extern unsigned int gnu_dev_major (unsigned long long int __dev) __attribute__ ((__nothrow__)); __extension__ extern unsigned int gnu_dev_minor (unsigned long long int __dev) __attribute__ ((__nothrow__)); __extension__ extern unsigned long long int gnu_dev_makedev (unsigned int __major, unsigned int __minor) __attribute__ ((__nothrow__)); typedef __blkcnt_t blkcnt_t; typedef __fsblkcnt_t fsblkcnt_t; typedef __fsfilcnt_t fsfilcnt_t; typedef unsigned long int pthread_t; typedef union { char __size[36]; long int __align; } pthread_attr_t; typedef struct __pthread_internal_slist { struct __pthread_internal_slist *__next; } __pthread_slist_t; typedef union { struct __pthread_mutex_s { int __lock; unsigned int __count; int __owner; int __kind; unsigned int __nusers; __extension__ union { int __spins; __pthread_slist_t __list; }; } __data; char __size[24]; long int __align; } pthread_mutex_t; typedef union { char __size[4]; long int __align; } pthread_mutexattr_t; typedef union { struct { int __lock; unsigned int __futex; __extension__ unsigned long long int __total_seq; __extension__ unsigned long long int __wakeup_seq; __extension__ unsigned long long int __woken_seq; void *__mutex; unsigned int __nwaiters; unsigned int __broadcast_seq; } __data; char __size[48]; __extension__ long long int __align; } pthread_cond_t; typedef union { char __size[4]; long int __align; } pthread_condattr_t; typedef unsigned int pthread_key_t; typedef int pthread_once_t; typedef union { struct { int __lock; unsigned int __nr_readers; unsigned int __readers_wakeup; unsigned int __writer_wakeup; unsigned int __nr_readers_queued; unsigned int __nr_writers_queued; unsigned char __flags; unsigned char __shared; unsigned char __pad1; unsigned char __pad2; int __writer; } __data; char __size[32]; long int __align; } pthread_rwlock_t; typedef union { char __size[8]; long int __align; } pthread_rwlockattr_t; typedef volatile int pthread_spinlock_t; typedef union { char __size[20]; long int __align; } pthread_barrier_t; typedef union { char __size[4]; int __align; } pthread_barrierattr_t; extern long int random (void) __attribute__ ((__nothrow__)); extern void srandom (unsigned int __seed) __attribute__ ((__nothrow__)); extern char *initstate (unsigned int __seed, char *__statebuf, size_t __statelen) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2))); extern char *setstate (char *__statebuf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); struct random_data { int32_t *fptr; int32_t *rptr; int32_t *state; int rand_type; int rand_deg; int rand_sep; int32_t *end_ptr; }; extern int random_r (struct random_data *__restrict __buf, int32_t *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int srandom_r (unsigned int __seed, struct random_data *__buf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2))); extern int initstate_r (unsigned int __seed, char *__restrict __statebuf, size_t __statelen, struct random_data *__restrict __buf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 4))); extern int setstate_r (char *__restrict __statebuf, struct random_data *__restrict __buf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int rand (void) __attribute__ ((__nothrow__)); extern void srand (unsigned int __seed) __attribute__ ((__nothrow__)); extern int rand_r (unsigned int *__seed) __attribute__ ((__nothrow__)); extern double drand48 (void) __attribute__ ((__nothrow__)); extern double erand48 (unsigned short int __xsubi[3]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern long int lrand48 (void) __attribute__ ((__nothrow__)); extern long int nrand48 (unsigned short int __xsubi[3]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern long int mrand48 (void) __attribute__ ((__nothrow__)); extern long int jrand48 (unsigned short int __xsubi[3]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern void srand48 (long int __seedval) __attribute__ ((__nothrow__)); extern unsigned short int *seed48 (unsigned short int __seed16v[3]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern void lcong48 (unsigned short int __param[7]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); struct drand48_data { unsigned short int __x[3]; unsigned short int __old_x[3]; unsigned short int __c; unsigned short int __init; unsigned long long int __a; }; extern int drand48_r (struct drand48_data *__restrict __buffer, double *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int erand48_r (unsigned short int __xsubi[3], struct drand48_data *__restrict __buffer, double *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int lrand48_r (struct drand48_data *__restrict __buffer, long int *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int nrand48_r (unsigned short int __xsubi[3], struct drand48_data *__restrict __buffer, long int *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int mrand48_r (struct drand48_data *__restrict __buffer, long int *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int jrand48_r (unsigned short int __xsubi[3], struct drand48_data *__restrict __buffer, long int *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int srand48_r (long int __seedval, struct drand48_data *__buffer) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2))); extern int seed48_r (unsigned short int __seed16v[3], struct drand48_data *__buffer) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern int lcong48_r (unsigned short int __param[7], struct drand48_data *__buffer) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2))); extern void *malloc (size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) ; extern void *calloc (size_t __nmemb, size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) ; extern void *realloc (void *__ptr, size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__warn_unused_result__)); extern void free (void *__ptr) __attribute__ ((__nothrow__)); extern void cfree (void *__ptr) __attribute__ ((__nothrow__)); extern void *alloca (size_t __size) __attribute__ ((__nothrow__)); extern void *valloc (size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) ; extern int posix_memalign (void **__memptr, size_t __alignment, size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern void abort (void) __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__)); extern int atexit (void (*__func) (void)) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern int on_exit (void (*__func) (int __status, void *__arg), void *__arg) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern void exit (int __status) __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__)); extern void _Exit (int __status) __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__)); extern char *getenv (__const char *__name) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern char *__secure_getenv (__const char *__name) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern int putenv (char *__string) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); extern int setenv (__const char *__name, __const char *__value, int __replace) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2))); extern int unsetenv (__const char *__name) __attribute__ ((__nothrow__)); extern int clearenv (void) __attribute__ ((__nothrow__)); extern char *mktemp (char *__template) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern int mkstemp (char *__template) __attribute__ ((__nonnull__ (1))) ; extern int mkstemps (char *__template, int __suffixlen) __attribute__ ((__nonnull__ (1))) ; extern char *mkdtemp (char *__template) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern int system (__const char *__command) ; extern char *realpath (__const char *__restrict __name, char *__restrict __resolved) __attribute__ ((__nothrow__)) ; typedef int (*__compar_fn_t) (__const void *, __const void *); extern void *bsearch (__const void *__key, __const void *__base, size_t __nmemb, size_t __size, __compar_fn_t __compar) __attribute__ ((__nonnull__ (1, 2, 5))) ; extern void qsort (void *__base, size_t __nmemb, size_t __size, __compar_fn_t __compar) __attribute__ ((__nonnull__ (1, 4))); extern int abs (int __x) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; extern long int labs (long int __x) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; __extension__ extern long long int llabs (long long int __x) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; extern div_t div (int __numer, int __denom) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; extern ldiv_t ldiv (long int __numer, long int __denom) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; __extension__ extern lldiv_t lldiv (long long int __numer, long long int __denom) __attribute__ ((__nothrow__)) __attribute__ ((__const__)) ; extern char *ecvt (double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4))) ; extern char *fcvt (double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4))) ; extern char *gcvt (double __value, int __ndigit, char *__buf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3))) ; extern char *qecvt (long double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4))) ; extern char *qfcvt (long double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4))) ; extern char *qgcvt (long double __value, int __ndigit, char *__buf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3))) ; extern int ecvt_r (double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign, char *__restrict __buf, size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5))); extern int fcvt_r (double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign, char *__restrict __buf, size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5))); extern int qecvt_r (long double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign, char *__restrict __buf, size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5))); extern int qfcvt_r (long double __value, int __ndigit, int *__restrict __decpt, int *__restrict __sign, char *__restrict __buf, size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5))); extern int mblen (__const char *__s, size_t __n) __attribute__ ((__nothrow__)) ; extern int mbtowc (wchar_t *__restrict __pwc, __const char *__restrict __s, size_t __n) __attribute__ ((__nothrow__)) ; extern int wctomb (char *__s, wchar_t __wchar) __attribute__ ((__nothrow__)) ; extern size_t mbstowcs (wchar_t *__restrict __pwcs, __const char *__restrict __s, size_t __n) __attribute__ ((__nothrow__)); extern size_t wcstombs (char *__restrict __s, __const wchar_t *__restrict __pwcs, size_t __n) __attribute__ ((__nothrow__)); extern int rpmatch (__const char *__response) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))) ; extern int posix_openpt (int __oflag) ; extern int getloadavg (double __loadavg[], int __nelem) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1))); struct _IO_FILE; typedef struct _IO_FILE FILE; typedef struct _IO_FILE __FILE; typedef struct { int __count; union { unsigned int __wch; char __wchb[4]; } __value; } __mbstate_t; typedef struct { __off_t __pos; __mbstate_t __state; } _G_fpos_t; typedef struct { __off64_t __pos; __mbstate_t __state; } _G_fpos64_t; typedef int _G_int16_t __attribute__ ((__mode__ (__HI__))); typedef int _G_int32_t __attribute__ ((__mode__ (__SI__))); typedef unsigned int _G_uint16_t __attribute__ ((__mode__ (__HI__))); typedef unsigned int _G_uint32_t __attribute__ ((__mode__ (__SI__))); typedef __builtin_va_list __gnuc_va_list; struct _IO_jump_t; struct _IO_FILE; typedef void _IO_lock_t; struct _IO_marker { struct _IO_marker *_next; struct _IO_FILE *_sbuf; int _pos; }; enum __codecvt_result { __codecvt_ok, __codecvt_partial, __codecvt_error, __codecvt_noconv }; struct _IO_FILE { int _flags; char* _IO_read_ptr; char* _IO_read_end; char* _IO_read_base; char* _IO_write_base; char* _IO_write_ptr; char* _IO_write_end; char* _IO_buf_base; char* _IO_buf_end; char *_IO_save_base; char *_IO_backup_base; char *_IO_save_end; struct _IO_marker *_markers; struct _IO_FILE *_chain; int _fileno; int _flags2; __off_t _old_offset; unsigned short _cur_column; signed char _vtable_offset; char _shortbuf[1]; _IO_lock_t *_lock; __off64_t _offset; void *__pad1; void *__pad2; void *__pad3; void *__pad4; size_t __pad5; int _mode; char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)]; }; typedef struct _IO_FILE _IO_FILE; struct _IO_FILE_plus; extern struct _IO_FILE_plus _IO_2_1_stdin_; extern struct _IO_FILE_plus _IO_2_1_stdout_; extern struct _IO_FILE_plus _IO_2_1_stderr_; typedef __ssize_t __io_read_fn (void *__cookie, char *__buf, size_t __nbytes); typedef __ssize_t __io_write_fn (void *__cookie, __const char *__buf, size_t __n); typedef int __io_seek_fn (void *__cookie, __off64_t *__pos, int __w); typedef int __io_close_fn (void *__cookie); extern int __underflow (_IO_FILE *); extern int __uflow (_IO_FILE *); extern int __overflow (_IO_FILE *, int); extern int _IO_getc (_IO_FILE *__fp); extern int _IO_putc (int __c, _IO_FILE *__fp); extern int _IO_feof (_IO_FILE *__fp) __attribute__ ((__nothrow__)); extern int _IO_ferror (_IO_FILE *__fp) __attribute__ ((__nothrow__)); extern int _IO_peekc_locked (_IO_FILE *__fp); extern void _IO_flockfile (_IO_FILE *) __attribute__ ((__nothrow__)); extern void _IO_funlockfile (_IO_FILE *) __attribute__ ((__nothrow__)); extern int _IO_ftrylockfile (_IO_FILE *) __attribute__ ((__nothrow__)); extern int _IO_vfscanf (_IO_FILE * __restrict, const char * __restrict, __gnuc_va_list, int *__restrict); extern int _IO_vfprintf (_IO_FILE *__restrict, const char *__restrict, __gnuc_va_list); extern __ssize_t _IO_padn (_IO_FILE *, int, __ssize_t); extern size_t _IO_sgetn (_IO_FILE *, void *, size_t); extern __off64_t _IO_seekoff (_IO_FILE *, __off64_t, int, int); extern __off64_t _IO_seekpos (_IO_FILE *, __off64_t, int); extern void _IO_free_backup_area (_IO_FILE *) __attribute__ ((__nothrow__)); typedef _G_fpos_t fpos_t; extern struct _IO_FILE *stdin; extern struct _IO_FILE *stdout; extern struct _IO_FILE *stderr; extern int remove (__const char *__filename) __attribute__ ((__nothrow__)); extern int rename (__const char *__old, __const char *__new) __attribute__ ((__nothrow__)); extern int renameat (int __oldfd, __const char *__old, int __newfd, __const char *__new) __attribute__ ((__nothrow__)); extern FILE *tmpfile (void) ; extern char *tmpnam (char *__s) __attribute__ ((__nothrow__)) ; extern char *tmpnam_r (char *__s) __attribute__ ((__nothrow__)) ; extern char *tempnam (__const char *__dir, __const char *__pfx) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) ; extern int fclose (FILE *__stream); extern int fflush (FILE *__stream); extern int fflush_unlocked (FILE *__stream); extern FILE *fopen (__const char *__restrict __filename, __const char *__restrict __modes) ; extern FILE *freopen (__const char *__restrict __filename, __const char *__restrict __modes, FILE *__restrict __stream) ; extern FILE *fdopen (int __fd, __const char *__modes) __attribute__ ((__nothrow__)) ; extern FILE *fmemopen (void *__s, size_t __len, __const char *__modes) __attribute__ ((__nothrow__)) ; extern FILE *open_memstream (char **__bufloc, size_t *__sizeloc) __attribute__ ((__nothrow__)) ; extern void setbuf (FILE *__restrict __stream, char *__restrict __buf) __attribute__ ((__nothrow__)); extern int setvbuf (FILE *__restrict __stream, char *__restrict __buf, int __modes, size_t __n) __attribute__ ((__nothrow__)); extern void setbuffer (FILE *__restrict __stream, char *__restrict __buf, size_t __size) __attribute__ ((__nothrow__)); extern void setlinebuf (FILE *__stream) __attribute__ ((__nothrow__)); extern int fprintf (FILE *__restrict __stream, __const char *__restrict __format, ...); extern int printf (__const char *__restrict __format, ...); extern int sprintf (char *__restrict __s, __const char *__restrict __format, ...) __attribute__ ((__nothrow__)); extern int vfprintf (FILE *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg); extern int vprintf (__const char *__restrict __format, __gnuc_va_list __arg); extern int vsprintf (char *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg) __attribute__ ((__nothrow__)); extern int snprintf (char *__restrict __s, size_t __maxlen, __const char *__restrict __format, ...) __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__printf__, 3, 4))); extern int vsnprintf (char *__restrict __s, size_t __maxlen, __const char *__restrict __format, __gnuc_va_list __arg) __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__printf__, 3, 0))); extern int vdprintf (int __fd, __const char *__restrict __fmt, __gnuc_va_list __arg) __attribute__ ((__format__ (__printf__, 2, 0))); extern int dprintf (int __fd, __const char *__restrict __fmt, ...) __attribute__ ((__format__ (__printf__, 2, 3))); extern int fscanf (FILE *__restrict __stream, __const char *__restrict __format, ...) ; extern int scanf (__const char *__restrict __format, ...) ; extern int sscanf (__const char *__restrict __s, __const char *__restrict __format, ...) __attribute__ ((__nothrow__)); extern int fscanf (FILE *__restrict __stream, __const char *__restrict __format, ...) __asm__ ("" "__isoc99_fscanf") ; extern int scanf (__const char *__restrict __format, ...) __asm__ ("" "__isoc99_scanf") ; extern int sscanf (__const char *__restrict __s, __const char *__restrict __format, ...) __asm__ ("" "__isoc99_sscanf") __attribute__ ((__nothrow__)); extern int vfscanf (FILE *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg) __attribute__ ((__format__ (__scanf__, 2, 0))) ; extern int vscanf (__const char *__restrict __format, __gnuc_va_list __arg) __attribute__ ((__format__ (__scanf__, 1, 0))) ; extern int vsscanf (__const char *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg) __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__scanf__, 2, 0))); extern int vfscanf (FILE *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vfscanf") __attribute__ ((__format__ (__scanf__, 2, 0))) ; extern int vscanf (__const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vscanf") __attribute__ ((__format__ (__scanf__, 1, 0))) ; extern int vsscanf (__const char *__restrict __s, __const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vsscanf") __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__scanf__, 2, 0))); extern int fgetc (FILE *__stream); extern int getc (FILE *__stream); extern int getchar (void); extern int getc_unlocked (FILE *__stream); extern int getchar_unlocked (void); extern int fgetc_unlocked (FILE *__stream); extern int fputc (int __c, FILE *__stream); extern int putc (int __c, FILE *__stream); extern int putchar (int __c); extern int fputc_unlocked (int __c, FILE *__stream); extern int putc_unlocked (int __c, FILE *__stream); extern int putchar_unlocked (int __c); extern int getw (FILE *__stream); extern int putw (int __w, FILE *__stream); extern char *fgets (char *__restrict __s, int __n, FILE *__restrict __stream) ; extern char *gets (char *__s) ; extern __ssize_t __getdelim (char **__restrict __lineptr, size_t *__restrict __n, int __delimiter, FILE *__restrict __stream) ; extern __ssize_t getdelim (char **__restrict __lineptr, size_t *__restrict __n, int __delimiter, FILE *__restrict __stream) ; extern __ssize_t getline (char **__restrict __lineptr, size_t *__restrict __n, FILE *__restrict __stream) ; extern int fputs (__const char *__restrict __s, FILE *__restrict __stream); extern int puts (__const char *__s); extern int ungetc (int __c, FILE *__stream); extern size_t fread (void *__restrict __ptr, size_t __size, size_t __n, FILE *__restrict __stream) ; extern size_t fwrite (__const void *__restrict __ptr, size_t __size, size_t __n, FILE *__restrict __s) ; extern size_t fread_unlocked (void *__restrict __ptr, size_t __size, size_t __n, FILE *__restrict __stream) ; extern size_t fwrite_unlocked (__const void *__restrict __ptr, size_t __size, size_t __n, FILE *__restrict __stream) ; extern int fseek (FILE *__stream, long int __off, int __whence); extern long int ftell (FILE *__stream) ; extern void rewind (FILE *__stream); extern int fseeko (FILE *__stream, __off_t __off, int __whence); extern __off_t ftello (FILE *__stream) ; extern int fgetpos (FILE *__restrict __stream, fpos_t *__restrict __pos); extern int fsetpos (FILE *__stream, __const fpos_t *__pos); extern void clearerr (FILE *__stream) __attribute__ ((__nothrow__)); extern int feof (FILE *__stream) __attribute__ ((__nothrow__)) ; extern int ferror (FILE *__stream) __attribute__ ((__nothrow__)) ; extern void clearerr_unlocked (FILE *__stream) __attribute__ ((__nothrow__)); extern int feof_unlocked (FILE *__stream) __attribute__ ((__nothrow__)) ; extern int ferror_unlocked (FILE *__stream) __attribute__ ((__nothrow__)) ; extern void perror (__const char *__s); extern int sys_nerr; extern __const char *__const sys_errlist[]; extern int fileno (FILE *__stream) __attribute__ ((__nothrow__)) ; extern int fileno_unlocked (FILE *__stream) __attribute__ ((__nothrow__)) ; extern FILE *popen (__const char *__command, __const char *__modes) ; extern int pclose (FILE *__stream); extern char *ctermid (char *__s) __attribute__ ((__nothrow__)); extern void flockfile (FILE *__stream) __attribute__ ((__nothrow__)); extern int ftrylockfile (FILE *__stream) __attribute__ ((__nothrow__)) ; extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__)); struct ScannerState; void ScannerState_init(struct ScannerState* self, const char* input_file_name, FILE* input_file, off_t position, unsigned row_number, unsigned column_number, int input); void ScannerState_get(struct ScannerState* self, const char** input_file_name, FILE** input_file, off_t* position, unsigned* row_number, unsigned* column_number, int* input); size_t ScannerStateClass_get_size(void); struct ScannerState* ScannerStateClass_get_nth_instance(struct ScannerState* head, int n); struct ScannerState; struct Scanner { const char* input_file_name; FILE* input_file; off_t position; unsigned row_number; unsigned column_number; struct ScannerState* state_stack; int state_stack_used; int input; }; struct ScannerState; struct Scanner; struct Symbol; void Scanner_init(struct Scanner* self); void Scanner_begin(struct Scanner* self, const char* input_file_name, FILE* input_file, off_t position, unsigned row_number, unsigned column_number, int input); int Scanner_consume(struct Scanner* self, char expected_input); void Scanner_raise_error(struct Scanner* self, const char* expected_input_string, const char* got_input_string); void Scanner_push_state(struct Scanner* self); void Scanner_pop_state(struct Scanner* self); void Scanner_end(struct Scanner* self); void Scanner_skip_optional_whitespace(struct Scanner* self); struct Symbol* Scanner_parse_ID(struct Scanner* self); int Scanner_ID_P(int input); struct Symbol; struct Symbol* Symbol_intern(const char* name); const char* Symbol_get_name(struct Symbol* self); struct ScannerState; void Scanner_init(struct Scanner* self) { self->input = 0; self->state_stack = (struct ScannerState*) calloc(256, ScannerStateClass_get_size()); } void Scanner_begin(struct Scanner* self, const char* input_file_name, FILE* input_file, off_t position, unsigned row_number, unsigned column_number, int input) { Scanner_push_state(self); self->input_file_name = input_file_name; self->input_file = input_file; self->position = position; self->row_number = row_number; self->column_number = column_number; self->input = input; } void Scanner_end(struct Scanner* self) { Scanner_pop_state(self); } int Scanner_consume(struct Scanner* self, char expected_input) { if(expected_input != self->input) { char input_string[5] = {0}; if(expected_input < 32 || expected_input > 127) { input_string[0] = '<'; input_string[1] = expected_input / 100; input_string[2] = (expected_input / 10) % 10; input_string[3] = expected_input % 10; input_string[4] = '>'; } else input_string[0] = expected_input; Scanner_raise_error(self, input_string, ((void *)0)); } } void Scanner_raise_error(struct Scanner* self, const char* expected_input_string, const char* got_input_string) { char input_string[5] = {0}; if(self->input < 32 || self->input > 127) { input_string[0] = '<'; input_string[1] = self->input / 100; input_string[2] = (self->input / 10) % 10; input_string[3] = self->input % 10; input_string[4] = '>'; } else input_string[0] = self->input; fprintf(stderr, "%s(%u)(%u): error: expected %s, got %s\n", self->input_file_name, self->row_number, self->column_number, expected_input_string, got_input_string ? got_input_string : input_string); exit(1); } void Scanner_push_state(struct Scanner* self) { struct ScannerState* state; if(self->state_stack_used >= 256) abort(); state = ScannerStateClass_get_nth_instance(self->state_stack, self->state_stack_used); ScannerState_init(state, self->input_file_name, self->input_file, self->position, self->row_number, self->column_number, self->input); ++self->state_stack_used; } void Scanner_pop_state(struct Scanner* self) { struct ScannerState* state; if(self->state_stack_used == 0) abort(); --self->state_stack_used; state = ScannerStateClass_get_nth_instance(self->state_stack, self->state_stack_used); ScannerState_get(state, &self->input_file_name, &self->input_file, &self->position, &self->row_number, &self->column_number, &self->input); } void Scanner_skip_optional_whitespace(struct Scanner* self) { int input; while((input = self->input), input == ' ' || input == '\t' || input == '\n' || input == '\r') { Scanner_consume(self, self->input); } } struct Symbol* Scanner_parse_ID(struct Scanner* self) { int input; char c; char ID[100] = {0}; int i = 0; Scanner_skip_optional_whitespace(self); while((input = self->input), Scanner_ID_P(input)) { c = Scanner_consume(self, input); if(i >= 100 - 1) { fprintf(stderr, "error: ID too long.\n"); Scanner_raise_error(self, "", ((void *)0)); abort(); } ID[i++] = c; } Scanner_skip_optional_whitespace(self); return(Symbol_intern(ID)); } int Scanner_ID_P(int input) { return((input >= 'A' && input <= 'Z') || (input >= 'a' && input <= 'z')); }