typedef unsigned int size_t;
typedef 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 __inline double
  __attribute__ ((__nothrow__)) atof (__const char *__nptr)
{
  return strtod (__nptr, (char **) ((void *) 0));
}

extern __inline int __attribute__ ((__nothrow__)) atoi (__const char *__nptr)
{
  return (int) strtol (__nptr, (char **) ((void *) 0), 10);
}

extern __inline long int
  __attribute__ ((__nothrow__)) atol (__const char *__nptr)
{
  return strtol (__nptr, (char **) ((void *) 0), 10);
}

__extension__ extern __inline long long int
  __attribute__ ((__nothrow__)) atoll (__const char *__nptr)
{
  return strtoll (__nptr, (char **) ((void *) 0), 10);
}

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__));
__extension__ extern __inline unsigned int
  __attribute__ ((__nothrow__)) gnu_dev_major (unsigned long long int __dev)
{
  return ((__dev >> 8) & 0xfff) | ((unsigned int) (__dev >> 32) & ~0xfff);
}

__extension__ extern __inline unsigned int
  __attribute__ ((__nothrow__)) gnu_dev_minor (unsigned long long int __dev)
{
  return (__dev & 0xff) | ((unsigned int) (__dev >> 12) & ~0xff);
}

__extension__ extern __inline unsigned long long int
  __attribute__ ((__nothrow__)) gnu_dev_makedev (unsigned int __major,
						 unsigned int __minor)
{
  return ((__minor & 0xff) | ((__major & 0xfff) << 8)
	  | (((unsigned long long int) (__minor & ~0xff)) << 12)
	  | (((unsigned long long int) (__major & ~0xfff)) << 32));
}

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];
  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];
  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)));
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned int uint32_t;
__extension__ typedef unsigned long long int uint64_t;
typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;
__extension__ typedef long long int int_least64_t;
typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;
__extension__ typedef unsigned long long int uint_least64_t;
typedef signed char int_fast8_t;
typedef int int_fast16_t;
typedef int int_fast32_t;
__extension__ typedef long long int int_fast64_t;
typedef unsigned char uint_fast8_t;
typedef unsigned int uint_fast16_t;
typedef unsigned int uint_fast32_t;
__extension__ typedef unsigned long long int uint_fast64_t;
typedef int intptr_t;
typedef unsigned int uintptr_t;
__extension__ typedef long long int intmax_t;
__extension__ typedef unsigned long long int uintmax_t;
union double_union
{
  double d;
  uint32_t i[2];
};
struct _Jv_Bigint
{
  struct _Jv_Bigint *_next;
  int _k, _maxwds, _sign, _wds;
  unsigned long _x[1];
};
struct _Jv_reent
{
  int _errno;
  struct _Jv_Bigint *_result;
  int _result_k;
  struct _Jv_Bigint *_p5s;
  struct _Jv_Bigint **_freelist;
  int _max_k;
};
typedef struct _Jv_Bigint _Jv_Bigint;
extern double _Jv_strtod_r (struct _Jv_reent *ptr, const char *s00,
			    char **se);
extern char *_Jv_dtoa_r (struct _Jv_reent *ptr, double d, int mode,
			 int ndigits, int *decpt, int *sign, char **rve,
			 int float_type);
void _Jv_dtoa (double d, int mode, int ndigits, int *decpt, int *sign,
	       char **rve, char *buf, int float_type);
double _Jv_ulp (double x);
double _Jv_b2d (_Jv_Bigint * a, int *e);
_Jv_Bigint *_Jv_Balloc (struct _Jv_reent *p, int k);
void _Jv_Bfree (struct _Jv_reent *p, _Jv_Bigint * v);
_Jv_Bigint *_Jv_multadd (struct _Jv_reent *p, _Jv_Bigint *, int, int);
_Jv_Bigint *_Jv_s2b (struct _Jv_reent *, const char *, int, int,
		     unsigned long);
_Jv_Bigint *_Jv_i2b (struct _Jv_reent *, int);
_Jv_Bigint *_Jv_mult (struct _Jv_reent *, _Jv_Bigint *, _Jv_Bigint *);
_Jv_Bigint *_Jv_pow5mult (struct _Jv_reent *, _Jv_Bigint *, int k);
int _Jv_hi0bits (unsigned long);
int _Jv_lo0bits (unsigned long *);
_Jv_Bigint *_Jv_d2b (struct _Jv_reent *p, double d, int *e, int *bits);
_Jv_Bigint *_Jv_lshift (struct _Jv_reent *p, _Jv_Bigint * b, int k);
_Jv_Bigint *_Jv__mdiff (struct _Jv_reent *p, _Jv_Bigint * a, _Jv_Bigint * b);
int _Jv__mcmp (_Jv_Bigint * a, _Jv_Bigint * b);
double _Jv_ratio (_Jv_Bigint * a, _Jv_Bigint * b);
extern const double _Jv__mprec_tinytens[];
extern const double _Jv__mprec_bigtens[];
extern const double _Jv__mprec_tens[];
extern int signgam;
enum fdversion
{ fdlibm_ieee = -1, fdlibm_svid, fdlibm_xopen, fdlibm_posix };
extern enum fdversion _fdlib_version;
struct exception
{
  int type;
  char *name;
  double arg1;
  double arg2;
  double retval;
};
extern double acos (double);
extern double asin (double);
extern double atan (double);
extern double atan2 (double, double);
extern double cos (double);
extern double sin (double);
extern double tan (double);
extern double cosh (double);
extern double sinh (double);
extern double tanh (double);
extern double exp (double);
extern double frexp (double, int *);
extern double ldexp (double, int);
extern double log (double);
extern double log10 (double);
extern double modf (double, double *);
extern double pow (double, double);
extern double sqrt (double);
extern double ceil (double);
extern double fabs (double);
extern double floor (double);
extern double fmod (double, double);
extern double erf (double);
extern double erfc (double);
extern double gamma (double);
extern double hypot (double, double);
extern int finite (double);
extern double j0 (double);
extern double j1 (double);
extern double jn (int, double);
extern double lgamma (double);
extern double y0 (double);
extern double y1 (double);
extern double yn (int, double);
extern double acosh (double);
extern double asinh (double);
extern double atanh (double);
extern double cbrt (double);
extern double logb (double);
extern double nextafter (double, double);
extern double remainder (double, double);
extern double scalb (double, double);
extern int matherr (struct exception *);
extern double significand (double);
extern double copysign (double, double);
extern int ilogb (double);
extern double rint (double);
extern double scalbn (double, int);
extern double expm1 (double);
extern double log1p (double);
extern double __ieee754_sqrt (double);
extern double __ieee754_acos (double);
extern double __ieee754_acosh (double);
extern double __ieee754_log (double);
extern double __ieee754_atanh (double);
extern double __ieee754_asin (double);
extern double __ieee754_atan2 (double, double);
extern double __ieee754_exp (double);
extern double __ieee754_cosh (double);
extern double __ieee754_fmod (double, double);
extern double __ieee754_pow (double, double);
extern double __ieee754_lgamma_r (double, int *);
extern double __ieee754_gamma_r (double, int *);
extern double __ieee754_lgamma (double);
extern double __ieee754_gamma (double);
extern double __ieee754_log10 (double);
extern double __ieee754_sinh (double);
extern double __ieee754_hypot (double, double);
extern double __ieee754_j0 (double);
extern double __ieee754_j1 (double);
extern double __ieee754_y0 (double);
extern double __ieee754_y1 (double);
extern double __ieee754_jn (int, double);
extern double __ieee754_yn (int, double);
extern double __ieee754_remainder (double, double);
extern int32_t __ieee754_rem_pio2 (double, double *);
extern double __ieee754_scalb (double, double);
extern double __kernel_standard (double, double, int);
extern double __kernel_sin (double, double, int);
extern double __kernel_cos (double, double);
extern double __kernel_tan (double, double, int);
extern int __kernel_rem_pio2 (double *, double *, int, int, int, const int *);
typedef union
{
  double value;
  struct
  {
    uint32_t lsw;
    uint32_t msw;
  } parts;
} ieee_double_shape_type;
typedef union
{
  float value;
  uint32_t word;
} ieee_float_shape_type;
static const double one = 1.0, Zero[] = { 0.0, -0.0, };

double
__ieee754_fmod (double x, double y)
{
  int32_t n, hx, hy, hz, ix, iy, sx, i;
  uint32_t lx, ly, lz;
  {
    ieee_double_shape_type ew_u;
    ew_u.value = (x);
    (hx) = ew_u.parts.msw;
    (lx) = ew_u.parts.lsw;
  }
  {
    ieee_double_shape_type ew_u;
    ew_u.value = (y);
    (hy) = ew_u.parts.msw;
    (ly) = ew_u.parts.lsw;
  }
  if ((hy | ((ly | -ly) >> 31)) > 0x7ff00000)
    return (x * y) / (x * y);
  if (hx < 0x00100000)
    {
      for (ix = -1043, i = lx; i > 0; i <<= 1)
	ix -= 1;
      for (ix = -1022, i = (hx << 11); i > 0; i <<= 1)
	ix -= 1;
    }
  while (n--)
    {
      hz = hx - hy;
      lz = lx - ly;
      hx = hx + hx + (lx >> 31);
      if ((hz | lz) == 0)
	return Zero[(uint32_t) sx >> 31];
    }
}