typedef unsigned int size_t;
typedef long int wchar_t;
extern double strtod (__const char *__restrict __nptr,
		      char **__restrict __endptr)  ;
extern long int strtol (__const char *__restrict __nptr,
			char **__restrict __endptr, int __base)  ;
extern unsigned long int strtoul (__const char *__restrict __nptr,
				  char **__restrict __endptr, int __base)
      ;
__extension__
extern long long int strtoq (__const char *__restrict __nptr,
			     char **__restrict __endptr, int __base)  ;
__extension__
extern unsigned long long int strtouq (__const char *__restrict __nptr,
				       char **__restrict __endptr, int __base)
      ;
__extension__
extern long long int strtoll (__const char *__restrict __nptr,
			      char **__restrict __endptr, int __base)  ;
__extension__
extern unsigned long long int strtoull (__const char *__restrict __nptr,
					char **__restrict __endptr, int __base)
      ;
extern double __strtod_internal (__const char *__restrict __nptr,
				 char **__restrict __endptr, int __group)
      ;
extern float __strtof_internal (__const char *__restrict __nptr,
				char **__restrict __endptr, int __group)
      ;
extern long double __strtold_internal (__const char *__restrict __nptr,
				       char **__restrict __endptr,
				       int __group)  ;
extern long int __strtol_internal (__const char *__restrict __nptr,
				   char **__restrict __endptr,
				   int __base, int __group)  ;
extern unsigned long int __strtoul_internal (__const char *__restrict __nptr,
					     char **__restrict __endptr,
					     int __base, int __group)  ;
__extension__
extern long long int __strtoll_internal (__const char *__restrict __nptr,
					 char **__restrict __endptr,
					 int __base, int __group)  ;
__extension__
extern unsigned long long int __strtoull_internal (__const char *
						   __restrict __nptr,
						   char **__restrict __endptr,
						   int __base, int __group)
      ;
extern char *l64a (long int __n)  ;
extern long int a64l (__const char *__s)    ;
typedef unsigned char __u_char;
typedef unsigned short __u_short;
typedef unsigned int __u_int;
typedef unsigned long __u_long;
__extension__ typedef unsigned long long int __u_quad_t;
__extension__ typedef long long int __quad_t;
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;
typedef __quad_t *__qaddr_t;
typedef __u_quad_t __dev_t;		 
typedef __u_int __uid_t;		 
typedef __u_int __gid_t;		 
typedef __u_long __ino_t;		 
typedef __u_int __mode_t;		 
typedef __u_int __nlink_t; 		 
typedef long int __off_t;		 
typedef __quad_t __loff_t;		 
typedef int __pid_t;			 
typedef int __ssize_t;			 
typedef __u_long __rlim_t;		 
typedef __u_quad_t __rlim64_t;		 
typedef __u_int __id_t;			 
typedef struct
  {
    int __val[2];
  } __fsid_t;				 
typedef int __daddr_t;			 
typedef char *__caddr_t;
typedef long int __time_t;
typedef unsigned int __useconds_t;
typedef long int __suseconds_t;
typedef long int __swblk_t;		 

typedef long int __clock_t;
typedef int __clockid_t;
typedef int __timer_t;
typedef int __key_t;
typedef unsigned short int __ipc_pid_t;
typedef long int __blksize_t;
typedef long int __blkcnt_t;
typedef __quad_t __blkcnt64_t;
typedef __u_long __fsblkcnt_t;
typedef __u_quad_t __fsblkcnt64_t;
typedef __u_long __fsfilcnt_t;
typedef __u_quad_t __fsfilcnt64_t;
typedef __u_quad_t __ino64_t;
typedef __loff_t __off64_t;
typedef long int __t_scalar_t;
typedef unsigned long int __t_uscalar_t;
typedef int __intptr_t;
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 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 * 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)  ;
typedef __blkcnt_t blkcnt_t;	  
typedef __fsblkcnt_t fsblkcnt_t;  
typedef __fsfilcnt_t fsfilcnt_t;  
extern long int random (void)  ;
extern void srandom (unsigned int __seed)  ;
extern char *initstate (unsigned int __seed, char *__statebuf,
			size_t __statelen)  ;
extern char *setstate (char *__statebuf)  ;
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)  ;
extern int srandom_r (unsigned int __seed, struct random_data *__buf)  ;
extern int initstate_r (unsigned int __seed, char *__restrict __statebuf,
			size_t __statelen,
			struct random_data *__restrict __buf)  ;
extern int setstate_r (char *__restrict __statebuf,
		       struct random_data *__restrict __buf)  ;
extern int rand (void)  ;
extern void srand (unsigned int __seed)  ;
extern int rand_r (unsigned int *__seed)  ;
extern double drand48 (void)  ;
extern double erand48 (unsigned short int __xsubi[3])  ;
extern long int lrand48 (void)  ;
extern long int nrand48 (unsigned short int __xsubi[3])  ;
extern long int mrand48 (void)  ;
extern long int jrand48 (unsigned short int __xsubi[3])  ;
extern void srand48 (long int __seedval)  ;
extern unsigned short int *seed48 (unsigned short int __seed16v[3])  ;
extern void lcong48 (unsigned short int __param[7])  ;
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)  ;
extern int erand48_r (unsigned short int __xsubi[3],
		      struct drand48_data *__restrict __buffer,
		      double *__restrict __result)  ;
extern int lrand48_r (struct drand48_data *__restrict __buffer,
		      long int *__restrict __result)  ;
extern int nrand48_r (unsigned short int __xsubi[3],
		      struct drand48_data *__restrict __buffer,
		      long int *__restrict __result)  ;
extern int mrand48_r (struct drand48_data *__restrict __buffer,
		      long int *__restrict __result)  ;
extern int jrand48_r (unsigned short int __xsubi[3],
		      struct drand48_data *__restrict __buffer,
		      long int *__restrict __result)  ;
extern int srand48_r (long int __seedval, struct drand48_data *__buffer)
      ;
extern int seed48_r (unsigned short int __seed16v[3],
		     struct drand48_data *__buffer)  ;
extern int lcong48_r (unsigned short int __param[7],
		      struct drand48_data *__buffer)  ;
extern void *malloc (size_t __size)    ;
extern void *calloc (size_t __nmemb, size_t __size)
        ;
extern void *realloc (void *__ptr, size_t __size)    ;
extern void free (void *__ptr)  ;
extern void cfree (void *__ptr)  ;
extern void *alloca (size_t __size)  ;
extern void *valloc (size_t __size)    ;
extern void abort (void)   __attribute__ ((__noreturn__));
extern int atexit (void (*__func) (void))  ;
extern int on_exit (void (*__func) (int __status, void *__arg), void *__arg)
      ;
extern void exit (int __status)   __attribute__ ((__noreturn__));
extern char *getenv (__const char *__name)  ;
extern char *__secure_getenv (__const char *__name)  ;
extern int putenv (char *__string)  ;
extern int setenv (__const char *__name, __const char *__value, int __replace)
      ;
extern int unsetenv (__const char *__name)  ;
extern int clearenv (void)  ;
extern char *mktemp (char *__template)  ;
extern int mkstemp (char *__template)  ;
extern char *mkdtemp (char *__template)  ;
extern int system (__const char *__command)  ;
extern char *realpath (__const char *__restrict __name,
		       char *__restrict __resolved)  ;
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);
extern void qsort (void *__base, size_t __nmemb, size_t __size,
		   __compar_fn_t __compar);
extern int abs (int __x)   __attribute__ ((__const__));
extern long int labs (long int __x)   __attribute__ ((__const__));
extern char *ecvt (double __value, int __ndigit, int *__restrict __decpt,
		   int *__restrict __sign)  ;
extern char *fcvt (double __value, int __ndigit, int *__restrict __decpt,
		   int *__restrict __sign)  ;
extern char *gcvt (double __value, int __ndigit, char *__buf)  ;
extern char *qecvt (long double __value, int __ndigit,
		    int *__restrict __decpt, int *__restrict __sign)  ;
extern char *qfcvt (long double __value, int __ndigit,
		    int *__restrict __decpt, int *__restrict __sign)  ;
extern char *qgcvt (long double __value, int __ndigit, char *__buf)  ;
extern int ecvt_r (double __value, int __ndigit, int *__restrict __decpt,
		   int *__restrict __sign, char *__restrict __buf,
		   size_t __len)  ;
extern int fcvt_r (double __value, int __ndigit, int *__restrict __decpt,
		   int *__restrict __sign, char *__restrict __buf,
		   size_t __len)  ;
extern int qecvt_r (long double __value, int __ndigit,
		    int *__restrict __decpt, int *__restrict __sign,
		    char *__restrict __buf, size_t __len)  ;
extern int qfcvt_r (long double __value, int __ndigit,
		    int *__restrict __decpt, int *__restrict __sign,
		    char *__restrict __buf, size_t __len)  ;
extern int mblen (__const char *__s, size_t __n)  ;
extern int mbtowc (wchar_t *__restrict __pwc,
		   __const char *__restrict __s, size_t __n)  ;
extern int wctomb (char *__s, wchar_t __wchar)  ;
extern size_t mbstowcs (wchar_t *__restrict  __pwcs,
			__const char *__restrict __s, size_t __n)  ;
extern size_t wcstombs (char *__restrict __s,
			__const wchar_t *__restrict __pwcs, size_t __n)
      ;
extern int rpmatch (__const char *__response)  ;
extern int getloadavg (double __loadavg[], int __nelem)  ;
typedef struct _IO_FILE FILE;
typedef struct _IO_FILE __FILE;
typedef unsigned int  wint_t;
typedef struct
{
  int __count;
  union
  {
    wint_t __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;
enum
{
  __GCONV_OK = 0,
  __GCONV_NOCONV,
  __GCONV_NODB,
  __GCONV_NOMEM,
  __GCONV_EMPTY_INPUT,
  __GCONV_FULL_OUTPUT,
  __GCONV_ILLEGAL_INPUT,
  __GCONV_INCOMPLETE_INPUT,
  __GCONV_ILLEGAL_DESCRIPTOR,
  __GCONV_INTERNAL_ERROR
};
enum
{
  __GCONV_IS_LAST = 0x0001,
  __GCONV_IGNORE_ERRORS = 0x0002
};
struct __gconv_step;
struct __gconv_step_data;
struct __gconv_loaded_object;
struct __gconv_trans_data;
typedef int (*__gconv_fct) (struct __gconv_step *, struct __gconv_step_data *,
			    __const unsigned char **, __const unsigned char *,
			    unsigned char **, size_t *, int, int);
typedef int (*__gconv_init_fct) (struct __gconv_step *);
typedef void (*__gconv_end_fct) (struct __gconv_step *);
typedef int (*__gconv_trans_fct) (struct __gconv_step *,
				  struct __gconv_step_data *, void *,
				  __const unsigned char *,
				  __const unsigned char **,
				  __const unsigned char *, unsigned char **,
				  size_t *);
typedef int (*__gconv_trans_context_fct) (void *, __const unsigned char *,
					  __const unsigned char *,
					  unsigned char *, unsigned char *);
typedef int (*__gconv_trans_query_fct) (__const char *, __const char ***,
					size_t *);
typedef int (*__gconv_trans_init_fct) (void **, const char *);
typedef void (*__gconv_trans_end_fct) (void *);
struct __gconv_trans_data
{
  __gconv_trans_fct __trans_fct;
  __gconv_trans_context_fct __trans_context_fct;
  __gconv_trans_end_fct __trans_end_fct;
  void *__data;
  struct __gconv_trans_data *__next;
};
struct __gconv_step
{
  struct __gconv_loaded_object *__shlib_handle;
  __const char *__modname;
  int __counter;
  char *__from_name;
  char *__to_name;
  __gconv_fct __fct;
  __gconv_init_fct __init_fct;
  __gconv_end_fct __end_fct;
  int __min_needed_from;
  int __max_needed_from;
  int __min_needed_to;
  int __max_needed_to;
  int __stateful;
  void *__data;		 
};
struct __gconv_step_data
{
  unsigned char *__outbuf;     
  unsigned char *__outbufend;  
  int __flags;
  int __invocation_counter;
  int __internal_use;
  __mbstate_t *__statep;
  __mbstate_t __state;	 
  struct __gconv_trans_data *__trans;
};
typedef struct __gconv_info
{
  size_t __nsteps;
  struct __gconv_step *__steps;
  __extension__ struct __gconv_step_data __data [0] ;
} *__gconv_t;
typedef union
{
  struct __gconv_info __cd;
  struct
  {
    struct __gconv_info __cd;
    struct __gconv_step_data __data;
  } __combined;
} _G_iconv_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 void *__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 _blksize;
  __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;
  int _mode;
  char _unused2[15 * sizeof (int) - 2 * sizeof (void *)];
};
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 wint_t   __wunderflow (_IO_FILE *)  ;
extern wint_t   __wuflow (_IO_FILE *)  ;
extern wint_t   __woverflow (_IO_FILE *, wint_t  )  ;
extern int _IO_getc (_IO_FILE *__fp)  ;
extern int _IO_putc (int __c, _IO_FILE *__fp)  ;
extern int _IO_feof (_IO_FILE *__fp)  ;
extern int _IO_ferror (_IO_FILE *__fp)  ;
extern int _IO_peekc_locked (_IO_FILE *__fp)  ;
extern void _IO_flockfile (_IO_FILE *)  ;
extern void _IO_funlockfile (_IO_FILE *)  ;
extern int _IO_ftrylockfile (_IO_FILE *)  ;
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 *)  ;
typedef _G_fpos_t fpos_t;
extern FILE *stdin;		 
extern FILE *stdout;		 
extern FILE *stderr;		 
extern int remove (__const char *__filename)  ;
extern int rename (__const char *__old, __const char *__new)  ;
extern FILE *tmpfile (void)  ;
extern char *tmpnam (char *__s)  ;
extern char *tmpnam_r (char *__s)  ;
extern char *tempnam (__const char *__dir, __const char *__pfx)
        ;
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)  ;
extern void setbuf (FILE *__restrict __stream, char *__restrict __buf)  ;
extern int setvbuf (FILE *__restrict __stream, char *__restrict __buf,
		    int __modes, size_t __n)  ;
extern void setbuffer (FILE *__restrict __stream, char *__restrict __buf,
		       size_t __size)  ;
extern void setlinebuf (FILE *__stream)  ;
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, ...)  ;
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)  ;
extern int snprintf (char *__restrict __s, size_t __maxlen,
		     __const char *__restrict __format, ...)
       __attribute__ ((__format__ (__printf__, 3, 4)));
extern int vsnprintf (char *__restrict __s, size_t __maxlen,
		      __const char *__restrict __format, __gnuc_va_list  __arg)
       __attribute__ ((__format__ (__printf__, 3, 0)));
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, ...)  ;
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 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 fgetpos (FILE *__restrict __stream, fpos_t *__restrict __pos)
      ;
extern int fsetpos (FILE *__stream, __const fpos_t *__pos)  ;
extern void clearerr (FILE *__stream)  ;
extern int feof (FILE *__stream)  ;
extern int ferror (FILE *__stream)  ;
extern void clearerr_unlocked (FILE *__stream)  ;
extern int feof_unlocked (FILE *__stream)  ;
extern int ferror_unlocked (FILE *__stream)  ;
extern void perror (__const char *__s)  ;
extern int sys_nerr;
extern __const char *__const sys_errlist[];
extern int fileno (FILE *__stream)  ;
extern int fileno_unlocked (FILE *__stream)  ;
extern FILE *popen (__const char *__command, __const char *__modes)  ;
extern int pclose (FILE *__stream)  ;
extern char *ctermid (char *__s)  ;
extern void flockfile (FILE *__stream)  ;
extern int ftrylockfile (FILE *__stream)  ;
extern void funlockfile (FILE *__stream)  ;
#define  i    int
#define  n    struct n
#define  x ){ return (
#define  A ->
#define  N n*
n { i c ; N L ; N R ; N U ; N ( * F ) ( N ) ; } ;
#define  F A F
#define  U A U
#define  R A R
#define  L A L
#define  m q = malloc(sizeof * q ) Z F =
#define  e z F ( p ) ) ; }
#define  f e N
#define  g z L Q s f
#define  h ( N p x
#define  H h p L U Q
#define  s R z R = q
#define  t ) ? p : (
#define  z , p
#define  Z , q
#define  Q = p
#define  w ! p U t p U L Q z Q U ,
#define  D W p R U = 0 z R Q R F ( p R ) z R F != E t
#define  W h w
#define  X z = q , 0
#define  V w p F = v z L Q
#define  O m o Z L Q
#define  M m E Z A c =
#define  r Z R Q
#define  u Z U Q
#define  a ) ) ) ? 0 : j ( !
#define  k ( i c x
#define  y 0 ) ; } i
N q ; N
o H z Q L f
v H U z Q L f
K W V L R f
J W V R f
I h V R f
S W w w O L L R r s , O L R r R R g
E D p F Q L A c - p R A c ? J : K f
P D w putchar ( p L R A c ) , m I g
G W M getchar ( ) g
p ;
i j k c ? O U r u U U X : y b k y d k y
#define  d(d) ( ( d a b
#define  b(b) ( ( b a d
#define  E(E) b ( M E u X )
main k i ) ! (
#define   I  b ( m  I  u X ) 
#define   J  b ( m  J  u X ) 
#define   K  b ( m  K  u X ) 
#define   P  b ( m  P  u X ) 
#define   G  b ( m  G  u X ) 
#define   S  b ( m  S  u X ) 
#define   B   b (S (K S) K)
#define   SS  b (B (B S) B)
#define   C   b (SS B S (K K))
#define   CC  b (B (B C) B)
#define   BB  b (CC B (B B B) B)
#define   Y   b (S (C B (S I I)) (C B (S I I)))
#define   CI  b (C I)
#define  ef E((-1) )
#define  sp E(' ')
#define  ob E('(')
#define  cb E(')')
#define  lm E('\\')
#define  nl E('\n')
#define  ht E('\t')
#define  qs E('S')
#define  qk E('K')
#define  qi E('I')
#define  pair b (BB (B (B K)) C CI)
#define  atom b (B K CI)
#define  bind b (CC B B C)
#define  ore b (SS (CI K))
#define  gns b (Y (B (bind G) (CC S (C (ore sp (ore nl ht))) CI)))
#define  pr b (Y (CC C (BB CI (B (BB (bind (P ob)) K)) (SS C (CC C (BB BB bind) K) (C (CC bind) (K (P cb))))) P))
#define  trans b (Y (B (bind gns) (S (BB S (C lm) lam) (C (BB S (C ob) brac) (S (C cb (CI (atom sp))) (S (C ef (CI (atom sp))) (B CI atom)))))))
#define  brac b (S bind (B Y (C (BB B B bind) (S (BB S (BB S (S I)) (CC (BB (B K)) (BB K) pair)) (CC S (CC BB (BB C (C (CI sp)) CI)) pair)))))
#define  lam b (B (bind gns) (C (CC BB bind (B CI)) abs))
#define  abs b (Y (C (BB S (BB C CI) (SS S (BB C (BB B opt)) I)) (CC S (C C (atom qi)) (B (pair (atom qk)) atom))))
#define  make b (B pair (pair (atom qs)))
#define  opt b (S (S I (S (BB (CC B) CI (BB K K make)) (S (BB C (BB C (C (CI qk))) (SS (SS S) (S (BB (BB (S I)) S (BB (BB (CC B) CI) (BB K K) make)) (B (CC B (BB (CC C) (BB (C (CI qk)) (pair (atom qk))) pair)) make)) (B (C (BB B C (C (CI qi)))) make))) make))) (B K make))
(bind (bind trans pr) (P nl) I)
e