typedef long unsigned int size_t;


















 




 



 


 













 
















 
























typedef struct
{
  long int alloc;		 

  long int size;		 



  unsigned long int *d;		 
} __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];

 





























 











































 






 































 








































 







 


 






extern

const

unsigned char __clz_tab[];









void

gcd (const __MP_INT  *u, const __MP_INT  *v, __MP_INT  *w)







{
  mp_size usize, vsize, wsize;
  mp_ptr up_in, vp_in;
  mp_ptr up, vp;
  mp_ptr wp;
  mp_size i;
  mp_limb d;
  int bcnt;
  mp_size w_bcnt;
  mp_limb cy_digit;

  usize = ( u->size  >= 0 ?  u->size  : - u->size ) ;
  vsize = ( v->size  >= 0 ?  v->size  : - v->size ) ;

   
  if (usize == 0)
    {
      if (w->alloc < vsize)
	_mpz_realloc (w, vsize);

      w->size = vsize;
      do {	mp_size i;	for (i = 0; i < (  vsize ); i++)	( w->d )[i] = (  v->d )[i];	} while (0) ;
      return;
    }

   
  if (vsize == 0)
    {
      if (w->alloc < usize)
	_mpz_realloc (w, usize);

      w->size = usize;
      do {	mp_size i;	for (i = 0; i < (  usize ); i++)	( w->d )[i] = (  u->d )[i];	} while (0) ;
      return;
    }

   

  up = (mp_ptr) __builtin_alloca  (usize * 4 );
  up_in = u->d;
  for (i = 0; (d = up_in[i]) == 0; i++)
    ;
  do {	unsigned long int __xr = (  d & -d );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( bcnt ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
  bcnt = 32  - 1 - bcnt;
  usize = mpn_rshift (up, up_in + i, usize - i, bcnt);

  bcnt += i * 32 ;
  w_bcnt = bcnt;

   

  vp = (mp_ptr) __builtin_alloca  (vsize * 4 );
  vp_in = v->d;
  for (i = 0; (d = vp_in[i]) == 0; i++)
    ;
  do {	unsigned long int __xr = (  d & -d );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( bcnt ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
  bcnt = 32  - 1 - bcnt;
  vsize = mpn_rshift (vp, vp_in + i, vsize - i, bcnt);

   

  bcnt += i * 32 ;
  if (bcnt < w_bcnt)
    w_bcnt = bcnt;

  for (;;)
    {
      int cmp;

      cmp = usize - vsize != 0 ? usize - vsize : mpn_cmp (up, vp, usize);

       
      if (cmp == 0)
	break;

      if (cmp > 0)
	{
	   


	  usize += mpn_sub (up, up, usize, vp, vsize);
	  for (i = 0; (d = up[i]) == 0; i++)
	    ;
	  do {	unsigned long int __xr = (  d & -d );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( bcnt ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
	  bcnt = 32  - 1 - bcnt;
	  usize = mpn_rshift (up, up + i, usize - i, bcnt);
	}
      else
	{
	   


	  vsize += mpn_sub (vp, vp, vsize, up, usize);
	  for (i = 0; (d = vp[i]) == 0; i++)
	    ;
	  do {	unsigned long int __xr = (  d & -d );	unsigned int __a;	if (32   <= 32)	{	__a = __xr < (1<<2* (32   / 4) )	? (__xr < (1<< (32   / 4) ) ? 0 : (32   / 4) )	: (__xr < (1<<3* (32   / 4) ) ?  2* (32   / 4)  : 3* (32   / 4) );	}	else	{	for (__a = 32   - 8; __a > 0; __a -= 8)	if (((__xr >> __a) & 0xff) != 0)	break;	}	( bcnt ) = 32   - (__clz_tab[__xr >> __a] + __a);	} while (0) ;
	  bcnt = 32  - 1 - bcnt;
	  vsize = mpn_rshift (vp, vp + i, vsize - i, bcnt);
	}
    }

   

  wsize = usize + w_bcnt / 32  + 1;
  if (w->alloc < wsize)
    _mpz_realloc (w, wsize);

  wp = w->d;

  do {	mp_size i;	for (i = 0; i < (  w_bcnt / 32  ); i++)	( wp )[i] = 0;	} while (0) ;

  cy_digit = mpn_lshift (wp + w_bcnt / 32 , up, usize,
			  w_bcnt % 32 );
  wsize = usize + w_bcnt / 32 ;
  if (cy_digit != 0)
    {
      wp[wsize] = cy_digit;
      wsize++;
    }

  w->size = wsize;

  __builtin_alloca  (0);
}