typedef long unsigned int size_t;


















 




 



 


 













 
















 
























typedef struct
{
  long int alloc;		 

  long int size;		 



  unsigned long int *d;		 
} __MP_INT;






void mp_set_memory_functions (void *(*) (size_t),
			      void *(*) (void *, size_t, size_t),
			      void (*) (void *, size_t));
__MP_INT  *itom (signed short int);
__MP_INT  *xtom (const char *);
void move (const __MP_INT  *, __MP_INT  *);
void madd (const __MP_INT  *, const __MP_INT  *, __MP_INT  *);
void msub (const __MP_INT  *, const __MP_INT  *, __MP_INT  *);
void mult (const __MP_INT  *, const __MP_INT  *, __MP_INT  *);
void mdiv (const __MP_INT  *, const __MP_INT  *, __MP_INT  *, __MP_INT  *);
void sdiv (const __MP_INT  *, signed short int, __MP_INT  *, signed short int *);
void msqrt (const __MP_INT  *, __MP_INT  *, __MP_INT  *);
void pow (const __MP_INT  *, const __MP_INT  *, const __MP_INT  *, __MP_INT  *);
void rpow (const __MP_INT  *, signed short int, __MP_INT  *);
void gcd (const __MP_INT  *, const __MP_INT  *, __MP_INT  *);
int mcmp (const __MP_INT  *, const __MP_INT  *);
void min (__MP_INT  *);
void mout (const __MP_INT  *);
char *mtox (const __MP_INT  *);
void mfree (__MP_INT  *);






 

































typedef unsigned long int	mp_limb;
typedef long int		mp_limb_signed;
typedef mp_limb *		mp_ptr;

typedef const mp_limb *		mp_srcptr;



typedef long int		mp_size;

 


typedef struct
{
  __MP_INT  num;
  __MP_INT  den;

} MP_RAT;


void mp_set_memory_functions (void *(*) (size_t),
			      void *(*) (void *, size_t, size_t),
			      void (*) (void *, size_t));

 

void mpz_init (__MP_INT  *);
void mpz_set (__MP_INT  *, const __MP_INT  *);
void mpz_set_ui (__MP_INT  *, unsigned long int);
void mpz_set_si (__MP_INT  *, signed long int);
int mpz_set_str (__MP_INT  *, const char *, int);
void mpz_init_set (__MP_INT  *, const __MP_INT  *);
void mpz_init_set_ui (__MP_INT  *, unsigned long int);
void mpz_init_set_si (__MP_INT  *, signed long int);
int mpz_init_set_str (__MP_INT  *, const char *, int);
unsigned long int mpz_get_ui (const __MP_INT  *);
signed long int mpz_get_si (const __MP_INT  *);
char * mpz_get_str (char *, int, const __MP_INT  *);
void mpz_clear (__MP_INT  *);
void * _mpz_realloc (__MP_INT  *, mp_size);
void mpz_add (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_add_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_sub (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_sub_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mul (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mul_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_div (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_div_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mod (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mod_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_divmod (__MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_divmod_ui (__MP_INT  *, __MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mdiv (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_mdiv_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mmod (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
unsigned long int mpz_mmod_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mdivmod (__MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
unsigned long int mpz_mdivmod_ui (__MP_INT  *, __MP_INT  *, const __MP_INT  *,
				  unsigned long int);
void mpz_sqrt (__MP_INT  *, const __MP_INT  *);
void mpz_sqrtrem (__MP_INT  *, __MP_INT  *, const __MP_INT  *);
int mpz_perfect_square_p (const __MP_INT  *);
int mpz_probab_prime_p (const __MP_INT  *, int);
void mpz_powm (__MP_INT  *, const __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_powm_ui (__MP_INT  *, const __MP_INT  *, unsigned long int, const __MP_INT  *);
void mpz_pow_ui (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_fac_ui (__MP_INT  *, unsigned long int);
void mpz_gcd (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_gcdext (__MP_INT  *, __MP_INT  *, __MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_neg (__MP_INT  *, const __MP_INT  *);
void mpz_com (__MP_INT  *, const __MP_INT  *);
void mpz_abs (__MP_INT  *, const __MP_INT  *);
int mpz_cmp (const __MP_INT  *, const __MP_INT  *);
int mpz_cmp_ui (const __MP_INT  *, unsigned long int);
int mpz_cmp_si (const __MP_INT  *, signed long int);
void mpz_mul_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_div_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_mod_2exp (__MP_INT  *, const __MP_INT  *, unsigned long int);
void mpz_and (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_ior (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);
void mpz_xor (__MP_INT  *, const __MP_INT  *, const __MP_INT  *);








void mpz_array_init (__MP_INT  [], size_t, mp_size);
void mpz_random (__MP_INT  *, mp_size);
void mpz_random2 (__MP_INT  *, mp_size);
size_t mpz_size (const __MP_INT  *);
size_t mpz_sizeinbase (const __MP_INT  *, int);

 

void mpq_init (MP_RAT *);
void mpq_clear (MP_RAT *);
void mpq_set (MP_RAT *, const MP_RAT *);
void mpq_set_ui (MP_RAT *, unsigned long int, unsigned long int);
void mpq_set_si (MP_RAT *, signed long int, unsigned long int);
void mpq_add (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_sub (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_mul (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_div (MP_RAT *, const MP_RAT *, const MP_RAT *);
void mpq_neg (MP_RAT *, const MP_RAT *);
int mpq_cmp (const MP_RAT *, const MP_RAT *);
void mpq_inv (MP_RAT *, const MP_RAT *);
void mpq_set_num (MP_RAT *, const __MP_INT  *);
void mpq_set_den (MP_RAT *, const __MP_INT  *);
void mpq_get_num (__MP_INT  *, const MP_RAT *);
void mpq_get_den (__MP_INT  *, const MP_RAT *);

 

mp_limb mpn_add (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_sub (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_mul (mp_ptr, mp_srcptr, mp_size, mp_srcptr, mp_size);
mp_size mpn_div (mp_ptr, mp_ptr, mp_size, mp_srcptr, mp_size);
mp_limb mpn_divmod_1 (mp_ptr, mp_srcptr, mp_size, mp_limb);
mp_limb mpn_mod_1 (mp_srcptr, mp_size, mp_limb);
mp_limb mpn_lshift (mp_ptr, mp_srcptr, mp_size, unsigned int);
mp_size mpn_rshift (mp_ptr, mp_srcptr, mp_size, unsigned int);
mp_size mpn_rshiftci (mp_ptr, mp_srcptr, mp_size, unsigned int, mp_limb);
mp_size mpn_sqrt (mp_ptr, mp_ptr, mp_srcptr, mp_size);
int mpn_cmp (mp_srcptr, mp_srcptr, mp_size);





 




























volatile void abort (void);







 































void *malloc (size_t);
void *realloc (void *, size_t);
void free (void *);

extern void *	(*_mp_allocate_func) (size_t);
extern void *	(*_mp_reallocate_func) (void *, size_t, size_t);
extern void	(*_mp_free_func) (void *, size_t);

void *_mp_default_allocate (size_t);
void *_mp_default_reallocate (void *, size_t, size_t);
void _mp_default_free (void *, size_t);

char *_mpz_get_str (char *, int, const __MP_INT  *);
int _mpz_set_str (__MP_INT  *, const char *, int);
void _mpz_impl_sqrt (__MP_INT  *, __MP_INT  *, const __MP_INT  *);


 






 







 








 

struct bases
{
   


  int chars_per_limb;

   



  mp_limb big_base;

   



  mp_limb big_base_inverted;

   
  float chars_per_bit_exactly;
};

extern const struct bases __mp_bases[37];



int

mcmp (const __MP_INT  *u, const __MP_INT  *v)






{
  mp_size usize = u->size;
  mp_size vsize = v->size;
  mp_size size;
  mp_size i;
  mp_limb a, b;
  mp_srcptr up, vp;

  if (usize != vsize)
    return usize - vsize;

  if (usize == 0)
    return 0;

  size = ( usize  >= 0 ?  usize  : - usize ) ;

  up = u->d;
  vp = v->d;

  i = size - 1;
  do
    {
      a = up[i];
      b = vp[i];
      i--;
      if (i < 0)
	break;
    }
  while (a == b);

  if (a == b)
    return 0;

  if ((a < b) == (usize < 0))
    return 1;
  else
    return -1;
}