typedef long unsigned int size_t;
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;
typedef signed long int __int64_t;
typedef unsigned long int __uint64_t;
typedef long int __quad_t;
typedef unsigned long int __u_quad_t;
typedef unsigned long int __dev_t;
typedef unsigned int __uid_t;
typedef unsigned int __gid_t;
typedef unsigned long int __ino_t;
typedef unsigned long int __ino64_t;
typedef unsigned int __mode_t;
typedef unsigned long int __nlink_t;
typedef long int __off_t;
typedef long int __off64_t;
typedef int __pid_t;
typedef struct { int __val[2]; } __fsid_t;
typedef long int __clock_t;
typedef unsigned long int __rlim_t;
typedef unsigned long int __rlim64_t;
typedef unsigned int __id_t;
typedef long int __time_t;
typedef unsigned int __useconds_t;
typedef long int __suseconds_t;
typedef int __daddr_t;
typedef long int __swblk_t;
typedef int __key_t;
typedef int __clockid_t;
typedef void * __timer_t;
typedef long int __blksize_t;
typedef long int __blkcnt_t;
typedef long int __blkcnt64_t;
typedef unsigned long int __fsblkcnt_t;
typedef unsigned long int __fsblkcnt64_t;
typedef unsigned long int __fsfilcnt_t;
typedef unsigned long int __fsfilcnt64_t;
typedef long int __ssize_t;
typedef __off64_t __loff_t;
typedef __quad_t *__qaddr_t;
typedef char *__caddr_t;
typedef long 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 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 * 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 __inline unsigned int gnu_dev_major (unsigned long long int __dev)
     __attribute__ ((__nothrow__));
__extension__
extern __inline unsigned int gnu_dev_minor (unsigned long long int __dev)
     __attribute__ ((__nothrow__));
__extension__
extern __inline 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[56];
  long int __align;
} pthread_attr_t;
typedef struct __pthread_internal_list
{
  struct __pthread_internal_list *__prev;
  struct __pthread_internal_list *__next;
} __pthread_list_t;
typedef union
{
  struct __pthread_mutex_s
  {
    int __lock;
    unsigned int __count;
    int __owner;
    unsigned int __nusers;
    int __kind;
    int __spins;
    __pthread_list_t __list;
  } __data;
  char __size[40];
  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;
    int __writer;
    int __pad1;
    unsigned long int __pad2;
    unsigned long int __pad3;
    unsigned int __flags;
  } __data;
  char __size[56];
  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[32];
  long int __align;
} pthread_barrier_t;
typedef union
{
  char __size[4];
  int __align;
} pthread_barrierattr_t;



typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned int uint32_t;
typedef unsigned long int uint64_t;
typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;
typedef long int int_least64_t;
typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;
typedef unsigned long int uint_least64_t;
typedef signed char int_fast8_t;
typedef long int int_fast16_t;
typedef long int int_fast32_t;
typedef long int int_fast64_t;
typedef unsigned char uint_fast8_t;
typedef unsigned long int uint_fast16_t;
typedef unsigned long int uint_fast32_t;
typedef unsigned long int uint_fast64_t;
typedef long int intptr_t;
typedef unsigned long int uintptr_t;
typedef long int intmax_t;
typedef unsigned long int uintmax_t;


struct iovec
  {
    void *iov_base;
    size_t iov_len;
  };
extern ssize_t readv (int __fd, __const struct iovec *__iovec, int __count);
extern ssize_t writev (int __fd, __const struct iovec *__iovec, int __count);

typedef __socklen_t socklen_t;
enum __socket_type
{
  SOCK_STREAM = 1,
  SOCK_DGRAM = 2,
  SOCK_RAW = 3,
  SOCK_RDM = 4,
  SOCK_SEQPACKET = 5,
  SOCK_PACKET = 10
};
typedef unsigned short int sa_family_t;
struct sockaddr
  {
    sa_family_t sa_family;
    char sa_data[14];
  };
struct sockaddr_storage
  {
    sa_family_t ss_family;
    __uint64_t __ss_align;
    char __ss_padding[(128 - (2 * sizeof (__uint64_t)))];
  };
enum
  {
    MSG_OOB = 0x01,
    MSG_PEEK = 0x02,
    MSG_DONTROUTE = 0x04,
    MSG_CTRUNC = 0x08,
    MSG_PROXY = 0x10,
    MSG_TRUNC = 0x20,
    MSG_DONTWAIT = 0x40,
    MSG_EOR = 0x80,
    MSG_WAITALL = 0x100,
    MSG_FIN = 0x200,
    MSG_SYN = 0x400,
    MSG_CONFIRM = 0x800,
    MSG_RST = 0x1000,
    MSG_ERRQUEUE = 0x2000,
    MSG_NOSIGNAL = 0x4000,
    MSG_MORE = 0x8000
  };
struct msghdr
  {
    void *msg_name;
    socklen_t msg_namelen;
    struct iovec *msg_iov;
    size_t msg_iovlen;
    void *msg_control;
    size_t msg_controllen;
    int msg_flags;
  };
struct cmsghdr
  {
    size_t cmsg_len;
    int cmsg_level;
    int cmsg_type;
    __extension__ unsigned char __cmsg_data [];
  };
extern struct cmsghdr *__cmsg_nxthdr (struct msghdr *__mhdr,
          struct cmsghdr *__cmsg) __attribute__ ((__nothrow__));
enum
  {
    SCM_RIGHTS = 0x01
    , SCM_CREDENTIALS = 0x02
  };
struct ucred
{
  pid_t pid;
  uid_t uid;
  gid_t gid;
};
struct linger
  {
    int l_onoff;
    int l_linger;
  };
struct osockaddr
  {
    unsigned short int sa_family;
    unsigned char sa_data[14];
  };
enum
{
  SHUT_RD = 0,
  SHUT_WR,
  SHUT_RDWR
};
extern int socket (int __domain, int __type, int __protocol) __attribute__ ((__nothrow__));
extern int socketpair (int __domain, int __type, int __protocol,
         int __fds[2]) __attribute__ ((__nothrow__));
extern int bind (int __fd, __const struct sockaddr * __addr, socklen_t __len)
     __attribute__ ((__nothrow__));
extern int getsockname (int __fd, struct sockaddr *__restrict __addr,
   socklen_t *__restrict __len) __attribute__ ((__nothrow__));
extern int connect (int __fd, __const struct sockaddr * __addr, socklen_t __len);
extern int getpeername (int __fd, struct sockaddr *__restrict __addr,
   socklen_t *__restrict __len) __attribute__ ((__nothrow__));
extern ssize_t send (int __fd, __const void *__buf, size_t __n, int __flags);
extern ssize_t recv (int __fd, void *__buf, size_t __n, int __flags);
extern ssize_t sendto (int __fd, __const void *__buf, size_t __n,
         int __flags, __const struct sockaddr * __addr,
         socklen_t __addr_len);
extern ssize_t recvfrom (int __fd, void *__restrict __buf, size_t __n,
    int __flags, struct sockaddr *__restrict __addr,
    socklen_t *__restrict __addr_len);
extern ssize_t sendmsg (int __fd, __const struct msghdr *__message,
   int __flags);
extern ssize_t recvmsg (int __fd, struct msghdr *__message, int __flags);
extern int getsockopt (int __fd, int __level, int __optname,
         void *__restrict __optval,
         socklen_t *__restrict __optlen) __attribute__ ((__nothrow__));
extern int setsockopt (int __fd, int __level, int __optname,
         __const void *__optval, socklen_t __optlen) __attribute__ ((__nothrow__));
extern int listen (int __fd, int __n) __attribute__ ((__nothrow__));
extern int accept (int __fd, struct sockaddr *__restrict __addr,
     socklen_t *__restrict __addr_len);
extern int shutdown (int __fd, int __how) __attribute__ ((__nothrow__));
extern int sockatmark (int __fd) __attribute__ ((__nothrow__));
extern int isfdtype (int __fd, int __fdtype) __attribute__ ((__nothrow__));


enum
  {
    IPPROTO_IP = 0,
    IPPROTO_HOPOPTS = 0,
    IPPROTO_ICMP = 1,
    IPPROTO_IGMP = 2,
    IPPROTO_IPIP = 4,
    IPPROTO_TCP = 6,
    IPPROTO_EGP = 8,
    IPPROTO_PUP = 12,
    IPPROTO_UDP = 17,
    IPPROTO_IDP = 22,
    IPPROTO_TP = 29,
    IPPROTO_IPV6 = 41,
    IPPROTO_ROUTING = 43,
    IPPROTO_FRAGMENT = 44,
    IPPROTO_RSVP = 46,
    IPPROTO_GRE = 47,
    IPPROTO_ESP = 50,
    IPPROTO_AH = 51,
    IPPROTO_ICMPV6 = 58,
    IPPROTO_NONE = 59,
    IPPROTO_DSTOPTS = 60,
    IPPROTO_MTP = 92,
    IPPROTO_ENCAP = 98,
    IPPROTO_PIM = 103,
    IPPROTO_COMP = 108,
    IPPROTO_SCTP = 132,
    IPPROTO_RAW = 255,
    IPPROTO_MAX
  };
typedef uint16_t in_port_t;
enum
  {
    IPPORT_ECHO = 7,
    IPPORT_DISCARD = 9,
    IPPORT_SYSTAT = 11,
    IPPORT_DAYTIME = 13,
    IPPORT_NETSTAT = 15,
    IPPORT_FTP = 21,
    IPPORT_TELNET = 23,
    IPPORT_SMTP = 25,
    IPPORT_TIMESERVER = 37,
    IPPORT_NAMESERVER = 42,
    IPPORT_WHOIS = 43,
    IPPORT_MTP = 57,
    IPPORT_TFTP = 69,
    IPPORT_RJE = 77,
    IPPORT_FINGER = 79,
    IPPORT_TTYLINK = 87,
    IPPORT_SUPDUP = 95,
    IPPORT_EXECSERVER = 512,
    IPPORT_LOGINSERVER = 513,
    IPPORT_CMDSERVER = 514,
    IPPORT_EFSSERVER = 520,
    IPPORT_BIFFUDP = 512,
    IPPORT_WHOSERVER = 513,
    IPPORT_ROUTESERVER = 520,
    IPPORT_RESERVED = 1024,
    IPPORT_USERRESERVED = 5000
  };
typedef uint32_t in_addr_t;
struct in_addr
  {
    in_addr_t s_addr;
  };
struct in6_addr
  {
    union
      {
 uint8_t u6_addr8[16];
 uint16_t u6_addr16[8];
 uint32_t u6_addr32[4];
      } in6_u;
  };
extern const struct in6_addr in6addr_any;
extern const struct in6_addr in6addr_loopback;
struct sockaddr_in
  {
    sa_family_t sin_family;
    in_port_t sin_port;
    struct in_addr sin_addr;
    unsigned char sin_zero[sizeof (struct sockaddr) -
      (sizeof (unsigned short int)) -
      sizeof (in_port_t) -
      sizeof (struct in_addr)];
  };
struct sockaddr_in6
  {
    sa_family_t sin6_family;
    in_port_t sin6_port;
    uint32_t sin6_flowinfo;
    struct in6_addr sin6_addr;
    uint32_t sin6_scope_id;
  };
struct ip_mreq
  {
    struct in_addr imr_multiaddr;
    struct in_addr imr_interface;
  };
struct ip_mreq_source
  {
    struct in_addr imr_multiaddr;
    struct in_addr imr_interface;
    struct in_addr imr_sourceaddr;
  };
struct ipv6_mreq
  {
    struct in6_addr ipv6mr_multiaddr;
    unsigned int ipv6mr_interface;
  };
struct group_req
  {
    uint32_t gr_interface;
    struct sockaddr_storage gr_group;
  };
struct group_source_req
  {
    uint32_t gsr_interface;
    struct sockaddr_storage gsr_group;
    struct sockaddr_storage gsr_source;
  };
struct ip_msfilter
  {
    struct in_addr imsf_multiaddr;
    struct in_addr imsf_interface;
    uint32_t imsf_fmode;
    uint32_t imsf_numsrc;
    struct in_addr imsf_slist[1];
  };
struct group_filter
  {
    uint32_t gf_interface;
    struct sockaddr_storage gf_group;
    uint32_t gf_fmode;
    uint32_t gf_numsrc;
    struct sockaddr_storage gf_slist[1];
};
struct ip_opts
  {
    struct in_addr ip_dst;
    char ip_opts[40];
  };
struct ip_mreqn
  {
    struct in_addr imr_multiaddr;
    struct in_addr imr_address;
    int imr_ifindex;
  };
struct in_pktinfo
  {
    int ipi_ifindex;
    struct in_addr ipi_spec_dst;
    struct in_addr ipi_addr;
  };
extern uint32_t ntohl (uint32_t __netlong) __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern uint16_t ntohs (uint16_t __netshort)
     __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern uint32_t htonl (uint32_t __hostlong)
     __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern uint16_t htons (uint16_t __hostshort)
     __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern int bindresvport (int __sockfd, struct sockaddr_in *__sock_in) __attribute__ ((__nothrow__));
extern int bindresvport6 (int __sockfd, struct sockaddr_in6 *__sock_in)
     __attribute__ ((__nothrow__));
struct in6_pktinfo
  {
    struct in6_addr ipi6_addr;
    unsigned int ipi6_ifindex;
  };
struct ip6_mtuinfo
  {
    struct sockaddr_in6 ip6m_addr;
    uint32_t ip6m_mtu;
  };


struct passwd
{
  char *pw_name;
  char *pw_passwd;
  __uid_t pw_uid;
  __gid_t pw_gid;
  char *pw_gecos;
  char *pw_dir;
  char *pw_shell;
};

typedef struct _IO_FILE FILE;


extern void setpwent (void);
extern void endpwent (void);
extern struct passwd *getpwent (void);
extern struct passwd *fgetpwent (FILE *__stream);
extern int putpwent (__const struct passwd *__restrict __p,
       FILE *__restrict __f);
extern struct passwd *getpwuid (__uid_t __uid);
extern struct passwd *getpwnam (__const char *__name);
extern int getpwent_r (struct passwd *__restrict __resultbuf,
         char *__restrict __buffer, size_t __buflen,
         struct passwd **__restrict __result);
extern int getpwuid_r (__uid_t __uid,
         struct passwd *__restrict __resultbuf,
         char *__restrict __buffer, size_t __buflen,
         struct passwd **__restrict __result);
extern int getpwnam_r (__const char *__restrict __name,
         struct passwd *__restrict __resultbuf,
         char *__restrict __buffer, size_t __buflen,
         struct passwd **__restrict __result);
extern int fgetpwent_r (FILE *__restrict __stream,
   struct passwd *__restrict __resultbuf,
   char *__restrict __buffer, size_t __buflen,
   struct passwd **__restrict __result);



extern void *memcpy (void *__restrict __dest,
       __const void *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern void *memmove (void *__dest, __const void *__src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern void *memccpy (void *__restrict __dest, __const void *__restrict __src,
        int __c, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern void *memset (void *__s, int __c, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern int memcmp (__const void *__s1, __const void *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern void *memchr (__const void *__s, int __c, size_t __n)
      __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));


extern char *strcpy (char *__restrict __dest, __const char *__restrict __src)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strncpy (char *__restrict __dest,
        __const char *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strcat (char *__restrict __dest, __const char *__restrict __src)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strncat (char *__restrict __dest, __const char *__restrict __src,
        size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strcmp (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strncmp (__const char *__s1, __const char *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strcoll (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern size_t strxfrm (char *__restrict __dest,
         __const char *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));

extern char *strdup (__const char *__s)
     __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) __attribute__ ((__nonnull__ (1)));

extern char *strchr (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *strrchr (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));


extern size_t strcspn (__const char *__s, __const char *__reject)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern size_t strspn (__const char *__s, __const char *__accept)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strpbrk (__const char *__s, __const char *__accept)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strstr (__const char *__haystack, __const char *__needle)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strtok (char *__restrict __s, __const char *__restrict __delim)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));

extern char *__strtok_r (char *__restrict __s,
    __const char *__restrict __delim,
    char **__restrict __save_ptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 3)));
extern char *strtok_r (char *__restrict __s, __const char *__restrict __delim,
         char **__restrict __save_ptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 3)));

extern size_t strlen (__const char *__s)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));


extern char *strerror (int __errnum) __attribute__ ((__nothrow__));

extern int strerror_r (int __errnum, char *__buf, size_t __buflen) __asm__ ("" "__xpg_strerror_r") __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));
extern void __bzero (void *__s, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern void bcopy (__const void *__src, void *__dest, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern void bzero (void *__s, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern int bcmp (__const void *__s1, __const void *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *index (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *rindex (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern int ffs (int __i) __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern int strcasecmp (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strncasecmp (__const char *__s1, __const char *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strsep (char **__restrict __stringp,
       __const char *__restrict __delim)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern char *crypt (__const char *__key, __const char *__salt)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern void setkey (__const char *__key) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern void encrypt (char *__block, int __edflag) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

extern char *__md5_crypt(const unsigned char *pw, const unsigned char *salt);
extern char *__des_crypt(const unsigned char *pw, const unsigned char *salt);
static u_char inv_key_perm[64];
static u_char inv_comp_perm[56];
static u_char u_sbox[8][64];
static u_char un_pbox[32];
static u_int32_t en_keysl[16], en_keysr[16];
static u_int32_t de_keysl[16], de_keysr[16];
static u_int32_t ip_maskl[8][256], ip_maskr[8][256];
static u_int32_t fp_maskl[8][256], fp_maskr[8][256];
static u_int32_t key_perm_maskl[8][128], key_perm_maskr[8][128];
static u_int32_t comp_maskl[8][128], comp_maskr[8][128];
static u_int32_t saltbits;
static u_int32_t old_salt;
static u_int32_t old_rawkey0, old_rawkey1;
static u_char init_perm[64], final_perm[64];
static u_char m_sbox[4][4096];
static u_int32_t psbox[4][256];
static const u_char ascii64[] =
    "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const u_char IP[64] = {
 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
};
static const u_char key_perm[56] = {
 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
};
static const u_char key_shifts[16] = {
 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
static const u_char comp_perm[48] = {
 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
};
static const u_char sbox[8][64] = {
 {
  14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
  0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
  4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
  15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13},
 {
  15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
  3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
  0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
  13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9},
 {
  10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
  13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
  13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
  1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12},
 {
  7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
  13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
  10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
  3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14},
 {
  2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
  14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
  4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
  11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3},
 {
  12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
  10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
  9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
  4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13},
 {
  4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
  13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
  1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
  6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12},
 {
  13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
  1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
  7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
  2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}
};
static const u_char pbox[32] = {
 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
};
static const u_int32_t bits32[32] = {
 0x80000000, 0x40000000, 0x20000000, 0x10000000,
 0x08000000, 0x04000000, 0x02000000, 0x01000000,
 0x00800000, 0x00400000, 0x00200000, 0x00100000,
 0x00080000, 0x00040000, 0x00020000, 0x00010000,
 0x00008000, 0x00004000, 0x00002000, 0x00001000,
 0x00000800, 0x00000400, 0x00000200, 0x00000100,
 0x00000080, 0x00000040, 0x00000020, 0x00000010,
 0x00000008, 0x00000004, 0x00000002, 0x00000001
};
static const u_char bits8[8] =
    { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
static const u_int32_t *bits28, *bits24;
static int ascii_to_bin(char ch)
{
 if (ch > 'z')
  return (0);
 if (ch >= 'a')
  return (ch - 'a' + 38);
 if (ch > 'Z')
  return (0);
 if (ch >= 'A')
  return (ch - 'A' + 12);
 if (ch > '9')
  return (0);
 if (ch >= '.')
  return (ch - '.');
 return (0);
}
static void des_init(void)
{
 int i, j, b, k, inbit, obit;
 u_int32_t *p, *il, *ir, *fl, *fr;
 static int des_initialised = 0;
 if (des_initialised == 1)
  return;
 old_rawkey0 = old_rawkey1 = 0L;
 saltbits = 0L;
 old_salt = 0L;
 bits24 = (bits28 = bits32 + 4) + 4;
 for (i = 0; i < 8; i++)
  for (j = 0; j < 64; j++) {
   b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
   u_sbox[i][j] = sbox[i][b];
  }
 for (b = 0; b < 4; b++)
  for (i = 0; i < 64; i++)
   for (j = 0; j < 64; j++)
    m_sbox[b][(i << 6) | j] =
        (u_char) ((u_sbox[(b << 1)][i] << 4) |
           u_sbox[(b << 1) + 1][j]);
 for (i = 0; i < 64; i++) {
  init_perm[final_perm[i] = IP[i] - 1] = (u_char) i;
  inv_key_perm[i] = 255;
 }
 for (i = 0; i < 56; i++) {
  inv_key_perm[key_perm[i] - 1] = (u_char) i;
  inv_comp_perm[i] = 255;
 }
 for (i = 0; i < 48; i++) {
  inv_comp_perm[comp_perm[i] - 1] = (u_char) i;
 }
 for (k = 0; k < 8; k++) {
  for (i = 0; i < 256; i++) {
   *(il = &ip_maskl[k][i]) = 0L;
   *(ir = &ip_maskr[k][i]) = 0L;
   *(fl = &fp_maskl[k][i]) = 0L;
   *(fr = &fp_maskr[k][i]) = 0L;
   for (j = 0; j < 8; j++) {
    inbit = 8 * k + j;
    if (i & bits8[j]) {
     if ((obit = init_perm[inbit]) < 32)
      *il |= bits32[obit];
     else
      *ir |= bits32[obit - 32];
     if ((obit = final_perm[inbit]) < 32)
      *fl |= bits32[obit];
     else
      *fr |= bits32[obit - 32];
    }
   }
  }
  for (i = 0; i < 128; i++) {
   *(il = &key_perm_maskl[k][i]) = 0L;
   *(ir = &key_perm_maskr[k][i]) = 0L;
   for (j = 0; j < 7; j++) {
    inbit = 8 * k + j;
    if (i & bits8[j + 1]) {
     if ((obit = inv_key_perm[inbit]) == 255)
      continue;
     if (obit < 28)
      *il |= bits28[obit];
     else
      *ir |= bits28[obit - 28];
    }
   }
   *(il = &comp_maskl[k][i]) = 0L;
   *(ir = &comp_maskr[k][i]) = 0L;
   for (j = 0; j < 7; j++) {
    inbit = 7 * k + j;
    if (i & bits8[j + 1]) {
     if ((obit =
          inv_comp_perm[inbit]) == 255)
      continue;
     if (obit < 24)
      *il |= bits24[obit];
     else
      *ir |= bits24[obit - 24];
    }
   }
  }
 }
 for (i = 0; i < 32; i++)
  un_pbox[pbox[i] - 1] = (u_char) i;
 for (b = 0; b < 4; b++)
  for (i = 0; i < 256; i++) {
   *(p = &psbox[b][i]) = 0L;
   for (j = 0; j < 8; j++) {
    if (i & bits8[j])
     *p |= bits32[un_pbox[8 * b + j]];
   }
  }
 des_initialised = 1;
}
static void setup_salt(u_int32_t salt)
{
 u_int32_t obit, saltbit;
 int i;
 if (salt == old_salt)
  return;
 old_salt = salt;
 saltbits = 0L;
 saltbit = 1;
 obit = 0x800000;
 for (i = 0; i < 24; i++) {
  if (salt & saltbit)
   saltbits |= obit;
  saltbit <<= 1;
  obit >>= 1;
 }
}
static int des_setkey(const char *key)
{
 u_int32_t k0, k1, rawkey0, rawkey1;
 int shifts, round;
 des_init();
 rawkey0 = ntohl(*(const u_int32_t *)key);
 rawkey1 = ntohl(*(const u_int32_t *)(key + 4));
 if ((rawkey0 | rawkey1)
     && rawkey0 == old_rawkey0 && rawkey1 == old_rawkey1) {
  return (0);
 }
 old_rawkey0 = rawkey0;
 old_rawkey1 = rawkey1;
 k0 = key_perm_maskl[0][rawkey0 >> 25]
     | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
     | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
     | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
     | key_perm_maskl[4][rawkey1 >> 25]
     | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
     | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
     | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
 k1 = key_perm_maskr[0][rawkey0 >> 25]
     | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
     | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
     | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
     | key_perm_maskr[4][rawkey1 >> 25]
     | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
     | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
     | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
 shifts = 0;
 for (round = 0; round < 16; round++) {
  u_int32_t t0, t1;
  shifts += key_shifts[round];
  t0 = (k0 << shifts) | (k0 >> (28 - shifts));
  t1 = (k1 << shifts) | (k1 >> (28 - shifts));
  de_keysl[15 - round] =
      en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
      | comp_maskl[1][(t0 >> 14) & 0x7f]
      | comp_maskl[2][(t0 >> 7) & 0x7f]
      | comp_maskl[3][t0 & 0x7f]
      | comp_maskl[4][(t1 >> 21) & 0x7f]
      | comp_maskl[5][(t1 >> 14) & 0x7f]
      | comp_maskl[6][(t1 >> 7) & 0x7f]
      | comp_maskl[7][t1 & 0x7f];
  de_keysr[15 - round] =
      en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
      | comp_maskr[1][(t0 >> 14) & 0x7f]
      | comp_maskr[2][(t0 >> 7) & 0x7f]
      | comp_maskr[3][t0 & 0x7f]
      | comp_maskr[4][(t1 >> 21) & 0x7f]
      | comp_maskr[5][(t1 >> 14) & 0x7f]
      | comp_maskr[6][(t1 >> 7) & 0x7f]
      | comp_maskr[7][t1 & 0x7f];
 }
 return (0);
}
static int
do_des(u_int32_t l_in, u_int32_t r_in, u_int32_t * l_out, u_int32_t * r_out,
       int count)
{
 u_int32_t l, r, *kl, *kr, *kl1, *kr1;
 u_int32_t f, r48l, r48r;
 int round;
 if (count == 0) {
  return (1);
 } else if (count > 0) {
  kl1 = en_keysl;
  kr1 = en_keysr;
 } else {
  count = -count;
  kl1 = de_keysl;
  kr1 = de_keysr;
 }
 l = ip_maskl[0][l_in >> 24]
     | ip_maskl[1][(l_in >> 16) & 0xff]
     | ip_maskl[2][(l_in >> 8) & 0xff]
     | ip_maskl[3][l_in & 0xff]
     | ip_maskl[4][r_in >> 24]
     | ip_maskl[5][(r_in >> 16) & 0xff]
     | ip_maskl[6][(r_in >> 8) & 0xff]
     | ip_maskl[7][r_in & 0xff];
 r = ip_maskr[0][l_in >> 24]
     | ip_maskr[1][(l_in >> 16) & 0xff]
     | ip_maskr[2][(l_in >> 8) & 0xff]
     | ip_maskr[3][l_in & 0xff]
     | ip_maskr[4][r_in >> 24]
     | ip_maskr[5][(r_in >> 16) & 0xff]
     | ip_maskr[6][(r_in >> 8) & 0xff]
     | ip_maskr[7][r_in & 0xff];
 while (count--) {
  kl = kl1;
  kr = kr1;
  round = 16;
  while (round--) {
   r48l = ((r & 0x00000001) << 23)
       | ((r & 0xf8000000) >> 9)
       | ((r & 0x1f800000) >> 11)
       | ((r & 0x01f80000) >> 13)
       | ((r & 0x001f8000) >> 15);
   r48r = ((r & 0x0001f800) << 7)
       | ((r & 0x00001f80) << 5)
       | ((r & 0x000001f8) << 3)
       | ((r & 0x0000001f) << 1)
       | ((r & 0x80000000) >> 31);
   f = (r48l ^ r48r) & saltbits;
   r48l ^= f ^ *kl++;
   r48r ^= f ^ *kr++;
   f = psbox[0][m_sbox[0][r48l >> 12]]
       | psbox[1][m_sbox[1][r48l & 0xfff]]
       | psbox[2][m_sbox[2][r48r >> 12]]
       | psbox[3][m_sbox[3][r48r & 0xfff]];
   f ^= l;
   l = r;
   r = f;
  }
  r = l;
  l = f;
 }
 *l_out = fp_maskl[0][l >> 24]
     | fp_maskl[1][(l >> 16) & 0xff]
     | fp_maskl[2][(l >> 8) & 0xff]
     | fp_maskl[3][l & 0xff]
     | fp_maskl[4][r >> 24]
     | fp_maskl[5][(r >> 16) & 0xff]
     | fp_maskl[6][(r >> 8) & 0xff]
     | fp_maskl[7][r & 0xff];
 *r_out = fp_maskr[0][l >> 24]
     | fp_maskr[1][(l >> 16) & 0xff]
     | fp_maskr[2][(l >> 8) & 0xff]
     | fp_maskr[3][l & 0xff]
     | fp_maskr[4][r >> 24]
     | fp_maskr[5][(r >> 16) & 0xff]
     | fp_maskr[6][(r >> 8) & 0xff]
     | fp_maskr[7][r & 0xff];
 return (0);
}
void setkey(const char *key)
{
 int i, j;
 u_int32_t packed_keys[2];
 u_char *p;
 p = (u_char *) packed_keys;
 for (i = 0; i < 8; i++) {
  p[i] = 0;
  for (j = 0; j < 8; j++)
   if (*key++ & 1)
    p[i] |= bits8[j];
 }
 des_setkey((char *)p);
}
void encrypt(char *block, int flag)
{
 u_int32_t io[2];
 u_char *p;
 int i, j;
 des_init();
 setup_salt(0L);
 p = (u_char *) block;
 for (i = 0; i < 2; i++) {
  io[i] = 0L;
  for (j = 0; j < 32; j++)
   if (*p++ & 1)
    io[i] |= bits32[j];
 }
 do_des(io[0], io[1], io, io + 1, flag ? -1 : 1);
 for (i = 0; i < 2; i++)
  for (j = 0; j < 32; j++)
   block[(i << 5) | j] = (io[i] & bits32[j]) ? 1 : 0;
}
char *__des_crypt(const unsigned char *key, const unsigned char *setting)
{
 u_int32_t count, salt, l, r0, r1, keybuf[2];
 u_char *p, *q;
 static char output[21];
 des_init();
 q = (u_char *) keybuf;
 while (q - (u_char *) keybuf - 8) {
  *q++ = *key << 1;
  if (*(q - 1))
   key++;
 }
 if (des_setkey((char *)keybuf))
  return (((void *)0));
 {
  count = 25;
  salt = (ascii_to_bin(setting[1]) << 6)
      | ascii_to_bin(setting[0]);
  output[0] = setting[0];
  output[1] = setting[1] ? setting[1] : output[0];
  p = (u_char *) output + 2;
 }
 setup_salt(salt);
 if (do_des(0L, 0L, &r0, &r1, (int)count))
  return (((void *)0));
 l = (r0 >> 8);
 *p++ = ascii64[(l >> 18) & 0x3f];
 *p++ = ascii64[(l >> 12) & 0x3f];
 *p++ = ascii64[(l >> 6) & 0x3f];
 *p++ = ascii64[l & 0x3f];
 l = (r0 << 16) | ((r1 >> 16) & 0xffff);
 *p++ = ascii64[(l >> 18) & 0x3f];
 *p++ = ascii64[(l >> 12) & 0x3f];
 *p++ = ascii64[(l >> 6) & 0x3f];
 *p++ = ascii64[l & 0x3f];
 l = r1 << 2;
 *p++ = ascii64[(l >> 12) & 0x3f];
 *p++ = ascii64[(l >> 6) & 0x3f];
 *p++ = ascii64[l & 0x3f];
 *p = 0;
 return (output);
}