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];



void

msqrt (const __MP_INT  *op, __MP_INT  *root, __MP_INT  *rem)







{
  mp_size op_size, root_size, rem_size;
  mp_ptr root_ptr, op_ptr;
  mp_ptr free_me = 0L ;
  mp_size free_me_size;

  op_size = op->size;
  if (op_size < 0)
    op_size = 1 / (op_size > 0);	 

  if (rem->alloc < op_size)
    _mpz_realloc (rem, op_size);

   
  root_size = (op_size + 1) / 2;

  root_ptr = root->d;
  op_ptr = op->d;

  if (root->alloc < root_size)
    {
      if (root_ptr == op_ptr)
	{
	  free_me = root_ptr;
	  free_me_size = root->alloc;
	}
      else
	(*_mp_free_func) (root_ptr, root->alloc * 4 );

      root->alloc = root_size;
      root_ptr = (mp_ptr) (*_mp_allocate_func) (root_size * 4 );
      root->d = root_ptr;
    }
  else
    {
       
      if (root_ptr == op_ptr)
	{
	   
	  op_ptr = (mp_ptr) __builtin_alloca  (op_size * 4 );
	   

	  do {	mp_size i;	for (i = 0; i < (  op_size ); i++)	( op_ptr )[i] = (  root_ptr )[i];	} while (0) ;
	}
    }

  rem_size = mpn_sqrt (root_ptr, rem->d, op_ptr, op_size);

  root->size = root_size;

   


  rem->size = rem_size;

  if (free_me != 0L )
    (*_mp_free_func) (free_me, free_me_size * 4 );

  __builtin_alloca  (0);
}