#ifdef _MSC_VER
#pragma comment(linker, "/SUBSYSTEM:CONSOLE /ENTRY:mainCRTStartup")
#endif
#include <limits.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define SHR_BYTES( VAL, BYTES ) (VAL >> (CHAR_BIT * BYTES))

#if UINT_MAX == UCHAR_MAX
#define INT_SIZE 1
#elif UINT_MAX == USHRT_MAX
#define INT_SIZE 2
#elif SHR_BYTES(UINT_MAX,4) == 0
#define INT_SIZE 4
#else
#define INT_SIZE 8
#endif

#if SHR_BYTES(ULONG_MAX,4) == 0
#define LONG_SIZE 4
#else
#define LONG_SIZE 8
#endif

#define LLONG_SIZE 8

#define  SHRT_BIT (2 * CHAR_BIT)
#define   INT_BIT (INT_SIZE * CHAR_BIT)
#define  LONG_BIT (LONG_SIZE * CHAR_BIT)
#define LLONG_BIT (8 * CHAR_BIT)

#ifndef __nothrow
#if defined( __attribute__ )
#define __nothrow __attribute__((nothrow))
#elif defined( __declspec )
#define __nothrow __declspec(nothrow)
#elif defined(__nothrow__)
#define __nothrow __nothrow
#else
#define __nothrow
#endif
#endif

#ifndef __stdcall
#if defined( __attribute__ )
#define __stdcall __attribute__((stdcall))
#elif defined( __declspec )
#define __stdcall __declspec(stdcall)
#elif defined( __stdcall__ )
#define __stdcall __stdcall__
#else
#define __stdcall
#endif
#endif

typedef unsigned  char  uchar;
typedef   signed  char  schar;
typedef unsigned short ushort;
typedef unsigned   int   uint;
typedef unsigned  long  ulong;
#define LLONG long long int
typedef          LLONG  llong;
typedef unsigned LLONG ullong;
typedef union PTRU_
{
	void     *vptr;
	uchar    *cptr;
	uint     *iptr;
	intptr_t  sptr;
	uintptr_t uptr;
} PTRU;
typedef struct PTRS_
{
	void   *SRC;
	size_t size;
	char endian;
	char padding[3];
	PTRU    beg;
	PTRU    end;
	schar  pos1;
	schar  pos2;
	schar  neg1;
	schar  neg2;
} PTRS;

#define LIMITS(UI,SI,UMAX,SMAX,SMIN,ONE)\
  static const uchar UI##_bit = sizeof(SI) * CHAR_BIT;\
  static const uchar UI##_mov = (sizeof(SI) * CHAR_BIT) - 1;\
  static const    UI UI##_end = ONE << ((sizeof(SI) * CHAR_BIT) - 1);\
  static const    UI UI##_max = UMAX;\
  static const    SI SI##_max = SMAX;\
  static const    SI SI##_min = SMIN
LIMITS( uchar, schar,  UCHAR_MAX, SCHAR_MAX, SCHAR_MIN, 1U );
LIMITS( ushort, short,  USHRT_MAX,  SHRT_MAX,  SHRT_MIN, 1U );
LIMITS( uint,   int,   UINT_MAX,   INT_MAX,   INT_MIN, 1U );
LIMITS( ulong,  long,  ULONG_MAX,  LONG_MAX,  LONG_MIN, 1UL );
LIMITS( ullong, llong, ULLONG_MAX, LLONG_MAX, LLONG_MIN, 1ULL );

#define UPTR_IS0( M_0, M_LAST, M_I1, M_I2 ) (!M_0 || !M_LAST || M_I1 == 0 || M_I2 == 0)
PTRS
__nothrow __stdcall
endian( void *SRC, size_t srcSize, char srcEndian )
{
	PTRS num;
	PTRU BEG, END;
	num.SRC = SRC;
	num.size = srcSize;
	num.endian = srcEndian;
	BEG.vptr = SRC;
	END.uptr = BEG.uptr + ( srcSize - 1 );
	switch( num.endian )
	{
	// 0x78563412
	case 'B':
	case 'b':
		num.pos1 = num.pos2 = -1;
		num.end = BEG;
		num.beg = END;
		return num;
	// 0x12345678
	case 'L':
	case 'l':
		num.pos1 = num.pos2 = 1;
		num.end = END;
		num.beg = BEG;
		goto done;
	// 0x56781234
	case 'R':
	case 'r':
		num.pos1 = -1;
		num.pos2 = 4;
		num.end.uptr = ++BEG.uptr;
		num.beg.uptr = --END.uptr;
		goto done;
	}
	// 0x34127856
	num.endian = 'M';
	num.pos1 = 1;
	num.pos2 = -4;
	num.end.uptr = --END.uptr;
	num.beg.uptr = ++BEG.uptr;
done:
	num.neg1 = -num.pos1;
	num.neg2 = -num.pos2;
	return num;
}
uchar
__nothrow __stdcall
eis0( PTRS src, void **S )
{
	for( uchar i = 1; src.size--; src.end.uptr += i ? src.neg1 : src.neg2, i ^= 1 )
	{
		if( *src.end.cptr )
		{
			if( S ) { *S = src.end.vptr; }
			return 0;
		}
	}
	if( S ) { *S = NULL; }
	return 1;
}
uchar
__nothrow __stdcall
eiseq( PTRS src, PTRS num, void **S, void **N )
{
	for( uchar i = 1; src.size && num.size;
	     src.end.uptr += i ? src.neg1 : src.neg2,
	     num.end.uptr += i ? num.neg1 : num.neg2,
	     --src.size, --num.size, i ^= 1 )
	{
		if( *src.end.cptr != *num.end.cptr ) { goto stop; }
	}
	if( !src.size )
	{
		if( N ) { *N = num.end.vptr; }
		if( S ) { *S = src.end.vptr; }
		if( !num.size ) { return 1; }
		return 0;
	}
	if( !num.size )
	{
stop:
		if( N ) { *N = num.end.vptr; }
		if( S ) { *S = src.end.vptr; }
		return 0;
	}
	if( N ) { *N = num.end.vptr; }
	if( S ) { *S = src.end.vptr; }
	return 1;
}
uchar
__nothrow __stdcall
emteq( PTRS src, PTRS num, void **S, void **N )
{
	void *s, *n;
	if( !S ) { S = &s; }
	if( !N ) { N = &n; }
	if( eiseq( src, num, S, N ) || **( ( uchar** )S ) > **( ( uchar** )N ) )
	{ return 1; }
	return 0;
}
uchar
__nothrow __stdcall
emt( PTRS src, PTRS num, void **S, void **N )
{
	void *s, *n;
	if( !S ) { S = &s; }
	if( !N ) { N = &n; }
	if( !eiseq( src, num, S, N ) && **( ( uchar** )S ) > **( ( uchar** )N ) )
	{ return 1; }
	return 0;
}
uchar
__nothrow __stdcall
elteq( PTRS src, PTRS num, void **S, void **N )
{
	void *s, *n;
	if( !S ) { S = &s; }
	if( !N ) { N = &n; }
	if( eiseq( src, num, S, N ) || **( ( uchar** )S ) < **( ( uchar** )N ) )
	{ return 1; }
	return 0;
}
uchar
__nothrow __stdcall
elt( PTRS src, PTRS num, void **S, void **N )
{
	void *s, *n;
	if( !S ) { S = &s; }
	if( !N ) { N = &n; }
	if( !eiseq( src, num, S, N ) && **( ( uchar** )S ) < **( ( uchar** )N ) )
	{ return 1; }
	return 0;
}
PTRS
__nothrow __stdcall
eshr( PTRS src, ullong bits )
{
	if( !bits ) { return src; }
	PTRS def = src;
	PTRS dst = src;
	uchar di = 1, ni = 1, rbits = 0, lbits = 0;
	while( bits >= uchar_bit && dst.size-- )
	{
		dst.beg.uptr += di ? dst.pos1 : dst.pos2;
		bits -= uchar_bit;
	}
	if( bits >= uchar_bit )
	{
		( void )memset( src.SRC, 0, src.size );
		return def;
	}
	if( dst.size < src.size )
	{
		while( dst.size-- )
		{
			*src.beg.cptr = *dst.beg.cptr;
			*dst.beg.cptr = 0;
			dst.beg.uptr += di ? dst.pos1 : dst.pos2;
			src.beg.uptr += ni ? src.pos1 : src.pos2;
		}
	}
	ullong move = CHAR_BIT - bits;
	while( src.size-- )
	{
		rbits = lbits;
		lbits = *src.end.cptr << move;
		*src.end.cptr >>= bits;
		*src.end.cptr |= rbits;
		src.end.uptr += ni ? src.neg1 : src.neg2;
		ni ^= 1;
	}
	return def;
}
PTRS
__nothrow __stdcall
eshl( PTRS src, ullong bits )
{
	if( !bits ) { return src; }
	PTRS def = src;
	PTRS dst = src;
	uchar di = 1, si = 1, rbits = 0, lbits = 0;
	while( bits >= uchar_bit && dst.size-- )
	{
		dst.end.uptr += di ? dst.neg1 : dst.neg2;
		bits -= uchar_bit;
	}
	if( bits >= uchar_bit )
	{
		( void )memset( src.SRC, 0, src.size );
		return def;
	}
	if( dst.size < src.size )
	{
		while( dst.size-- )
		{
			*src.end.cptr = *dst.end.cptr;
			*dst.end.cptr = 0;
			dst.end.uptr += di ? dst.neg1 : dst.neg2;
			src.end.uptr += si ? src.neg1 : src.neg2;
		}
	}
	si = 1;
	ullong move = CHAR_BIT - bits;
	while( src.size-- )
	{
		lbits = rbits;
		rbits = *src.beg.cptr >> move;
		*src.beg.cptr <<= bits;
		*src.beg.cptr |= lbits;
		src.beg.uptr += si ? src.pos1 : src.pos2;
		si ^= 1;
	}
	return def;
}
PTRS
__nothrow __stdcall
eshl1( PTRS src )
{
	PTRS def = src;
	uchar i = 1, rbits = 0, lbits = 0;
	for( ; src.size--; i ^= 1 )
	{
		lbits = rbits;
		rbits = *src.beg.cptr >> uchar_mov;
		*src.beg.cptr <<= 1;
		*src.beg.cptr |= lbits;
		src.beg.uptr += i ? src.pos1 : src.pos2;
	}
	return def;
}
PTRS
__nothrow __stdcall
eshr1( PTRS src )
{
	PTRS def = src;
	uchar i = 1, rbits = 0, lbits = 0;
	for( ; src.size--; i ^= 1 )
	{
		rbits = lbits;
		lbits = *src.beg.cptr << uchar_mov;
		*src.beg.cptr >>= 1;
		*src.beg.cptr |= rbits;
		src.beg.uptr += i ? src.pos1 : src.pos2;
	}
	return def;
}
PTRS
__nothrow __stdcall
eand( PTRS src, PTRS num )
{
	PTRS def = src;
	for( uchar i = 1; src.size-- && num.size--; i ^= 1 )
	{
		*src.beg.cptr &= *num.beg.cptr;
		src.beg.uptr += i ? src.pos1 : src.pos2;
		num.beg.uptr += i ? num.pos1 : src.pos2;
	}
	return def;
}
uchar
__nothrow __stdcall
einc( PTRS num )
{
	uchar bit, i = 1;
	for( ; num.size--; i ^= 1, num.beg.uptr += i ? num.pos1 : num.pos2 )
	{
		for( bit = 1; bit; bit <<= 1 )
		{
			if( *num.beg.cptr & bit )
			{
				*num.beg.cptr ^= bit;
			}
			else
			{
				*num.beg.cptr |= bit;
				return 1;
			}
		}
	}
	return 1;
}
PTRS
__nothrow __stdcall
eadd( PTRS src, PTRS num )
{
	PTRS def = src;
	uchar carry = 0, bit;
	for( uchar i = 1; src.size-- && num.size--; i ^= 1,
	     src.beg.uptr += i ? src.pos1 : src.pos2,
	     num.beg.uptr += i ? num.pos1 : num.pos2 )
	{
		for( bit = 1; bit; bit <<= 1 )
		{
			if( carry )
			{
				if( *src.beg.cptr & bit )
				{
					*src.beg.cptr ^= bit;
				}
				else
				{
					*src.beg.cptr |= bit;
					carry = 0;
				}
			}
			if( *src.beg.cptr & bit )
			{
				if( *num.beg.cptr & bit )
				{
					*src.beg.cptr ^= bit;
					carry = 1;
				}
			}
			else if( *num.beg.cptr & bit )
			{
				*src.beg.cptr |= bit;
			}
		}
	}
	return def;
}
PTRS
__nothrow __stdcall
esub( PTRS src, PTRS num )
{
	PTRS def = src;
	uchar carry = 0, bit = uchar_end, clr = 0, i = 1;
	for( size_t srcSize = src.size; !( *src.end.cptr ) && srcSize--; i ^= 1 )
	{
		src.end.uptr += i ? src.neg1 : src.neg2;
	}
	while( bit && !( *src.end.cptr & bit ) )
	{
		clr |= bit;
		bit >>= 1;
	}
	clr = ~clr;
	for( i = 1; src.size-- && num.size--;
	     src.beg.uptr += i ? src.pos1 : src.pos2,
	     num.beg.uptr += i ? num.pos1 : num.pos2, i ^= 1 )
	{
		for( bit = 1; bit; bit <<= 1 )
		{
			if( carry )
			{
				if( *( src.beg.cptr ) & bit )
				{
					*( src.beg.cptr ) ^= bit;
					carry = 0;
				}
				else
				{
					*( src.beg.cptr ) |= bit;
				}
			}
			if( *( src.beg.cptr ) & bit )
			{
				if( *( num.beg.cptr ) & bit )
				{
					*( src.beg.cptr ) ^= bit;
				}
			}
			else if( *( num.beg.cptr ) & bit )
			{
				*( src.beg.cptr ) |= bit;
				carry = 1;
			}
		}
	}
	*( src.beg.cptr ) &= clr;
	return def;
}
PTRS
__nothrow __stdcall
ecpy( PTRS src, PTRS num )
{
	PTRS def = src;
	for( uchar i = 1; src.size-- && num.size--; i ^= 1,
	     src.beg.uptr += i ? src.pos1 : src.pos2,
	     num.beg.uptr += i ? num.pos1 : num.pos2 )
	{
		*src.beg.cptr = *num.beg.cptr;
	}
	return def;
}

PTRS
__nothrow __stdcall
ediv( PTRS quo, PTRS src, PTRS num, ullong *radix, ullong radix_max )
{
	if( !quo.SRC || !quo.size ) { return ( PTRS ) { NULL }; }
	( void )memset( quo.SRC, 0, quo.size );
	if( eis0( src, NULL ) || eis0( num, NULL ) ) { return quo; }
	void *TMP = calloc( 1, src.size );
	if( !TMP ) return ( PTRS ) { NULL };
	PTRS tmp = endian( TMP, src.size, src.endian );
	uchar i = 1, bit;
	size_t size = src.size;
	//
	for( ; !( *src.end.cptr ) && size--; i ^= 1 )
	{
		src.end.uptr += i ? src.neg1 : src.neg2;
	}
	//*/
	//PTRS def = src;
	for( ; size--;//&& emteq( src, num, NULL, NULL );
	     src.end.uptr += i ? src.neg1 : src.neg2, i ^= 1 )
	{
		for( bit = uchar_end; bit; bit >>= 1 )
		{
			( void )eshl1( quo );
			( void )eshl1( tmp );
			if( *src.end.cptr & bit )
			{
				*tmp.beg.cptr |= 1;
				*src.end.cptr ^= bit;
			}
			if( emteq( tmp, num, NULL, NULL ) )
			{
				*quo.beg.cptr |= 1;
				( void )esub( tmp, num );
			}
		}
	}
	if( radix )
	{
		for( *radix = 0; *radix < radix_max && !eis0( tmp, NULL ); ++( *radix ) )
		{
			( void )eshl1( quo );
			( void )eshl1( tmp );
			if( emteq( tmp, num, NULL, NULL ) )
			{
				*quo.beg.cptr |= 1;
				( void )esub( tmp, num );
			}
		}
	}
	( void )memcpy( src.SRC, TMP, tmp.size );
	//free( tmp.SRC );
	return quo;
}

// Normal Shift & Add Algorithm
PTRS
__nothrow __stdcall
emul( PTRS src, PTRS num )
{
	if( UPTR_IS0( src.SRC, src.size, src.pos1, src.pos2 )
	    || UPTR_IS0( num.SRC, num.size, num.pos1, num.pos2 ) )
		return ( PTRS ) {NULL};
	if( eis0( src, NULL ) )
	{ return src; }
	if( eis0( num, NULL ) )
	{
		( void )memset( src.SRC, 0, src.size );
		return src;
	}
	PTRS def = src;
	uchar *TMP = calloc( src.size, 1 );
	if( !TMP ) return ( ( PTRS ) {NULL} );
	PTRS tmp = endian( TMP, src.size, src.endian );
	uchar bit;
	for( uchar i = 1; num.size--; i ^= 1, num.beg.uptr += i ? num.pos1 : num.pos2 )
	{
		for( bit = 1; bit; bit <<= 1, eshl1( src ) )
		{
			if( *num.beg.cptr & bit ) { ( void )eadd( tmp, src ); }
		}
	}
	( void )memcpy( src.SRC, TMP, src.size );
	free( TMP );
	return def;
}
char
__nothrow __stdcall
getIntEndianEx( schar *i1, schar *i2 )
{
	uint num = 0x12345678;
	uchar *buf = ( uchar* )( &num );
	switch( buf[0] )
	{
	// 0x123465678
	case 0x12:
		if( i1 ) { *i1 = -1; }
		if( i2 ) { *i2 = -1; }
		return 'B';
	// 0x78563412
	case 0x78:
		if( i1 ) { *i1 = 1; }
		if( i2 ) { *i2 = 1; }
		return 'L';
	// 0x56781234
	case 0x56:
		if( i1 ) { *i1 = 1; }
		if( i2 ) { *i2 = -4; }
		return 'R';
	}
	// 0x34127856
	if( i1 ) { *i1 = -1; }
	if( i2 ) { *i2 = 3; }
	return 'M';
}
#define getIntEndian() getIntEndianEx(NULL, NULL)
char
__nothrow __stdcall
getShortEndianEx( schar *i )
{
	ushort value = 0x1234;
	uchar *buff = ( uchar* )( &value );
	switch( *buff )
	{
	case 0x12:
		if( i ) { *i = -1; }
		return 'B';
	case 0x34:
		if( i ) { *i = 1; }
		return 'L';
	}
	if( i ) { *i = 0; }
	return 0;
}
#define getShortEndian() getShortEndianEx(NULL)
PTRS
__nothrow __stdcall
emul_karatsuba( PTRS SRC, PTRS NUM )
{
//#error "Bug causing write to BEFORE buffer"
	if( SRC.size < 2 || NUM.size < 2
	    || elteq( SRC, endian( ( void* )&ushort_max, sizeof( short ),
	                           getShortEndian() ), NULL, NULL ) )
	{
		return emul( SRC, NUM );
	}
	PTRS low1 = endian( SRC.SRC, SRC.size / 2, SRC.endian ), high1 = low1;
	PTRS low2 = endian( NUM.SRC, NUM.size / 2, NUM.endian ), high2 = low2;
	void *SCPY = malloc( low1.size );
	if( !SCPY ) return ( PTRS ) {NULL};
	void *NCPY = malloc( low2.size );
	if( !NCPY )
	{
		free( SCPY );
		return ( PTRS ) {NULL};
	}
	PTRS scpy = endian( SCPY, low1.size, SRC.endian );
	PTRS ncpy = endian( NCPY, low2.size, NUM.endian );
	uchar si = 1, ni = 1;
	( void )memcpy( SCPY, SRC.SRC, low1.size );
	( void )memcpy( NCPY, NUM.SRC, low2.size );
	while( SRC.size-- > low1.size )
	{
		low1.end.uptr += si ? low1.neg1 : low1.neg2;
		scpy.end.uptr += si ? low1.neg1 : low1.neg2;
		si ^= 1;
	}
	while( NUM.size-- > low2.size )
	{
		low2.end.uptr += ni ? low2.neg1 : low2.neg2;
		ncpy.end.uptr += ni ? low2.neg1 : low2.neg2;
		ni ^= 1;
	}
	PTRS z0 = emul_karatsuba( endian( scpy.beg.vptr, low1.size, SRC.endian ),
	                          endian( ncpy.beg.vptr, low2.size, NUM.endian ) );
	PTRS z2 = emul_karatsuba( endian( scpy.end.vptr, low1.size, SRC.endian ),
	                          endian( ncpy.end.vptr, low2.size, NUM.endian ) );
	PTRS z1 = emul_karatsuba( eadd( low1, high1 ), eadd( low2, high2 ) );
	eadd( eadd( emul( esub( esub( z1, z2 ), z0 ), endian( &low1.size,
	                  sizeof( size_t ), getIntEndian() ) ), z0 ), emul( z2, endian( &low1.size,
	                      sizeof( size_t ), getIntEndian() ) ) );
	free( SCPY );
	free( NCPY );
	return low1;
}
void
__nothrow __stdcall
putt( char *text, uchar result )
{
	fputs( text, stdout );
	puts( result ? " succeeded" : " failed" );
}
void
__nothrow __stdcall
puti( char* text, ullong i1, ullong i2, ullong q1, ullong q2 )
{
	ullong last = LLONG_BIT, i = last - 1, bit = 1;
	char b1[ LLONG_BIT + 1] = "";
	char b2[ LLONG_BIT + 1] = "";
	char b3[ LLONG_BIT + 1] = "";
	char b4[ LLONG_BIT + 1] = "";
	do
	{
		b1[i] = ( i1 & bit ) ? '1' : '0';
		b2[i] = ( i2 & bit ) ? '1' : '0';
		b3[i] = ( q1 & bit ) ? '1' : '0';
		b4[i] = ( q2 & bit ) ? '1' : '0';
		bit <<= 1;
		--i;
	}
	while( bit );
	b1[last] = b2[last] = b3[last] = b4[last] = '\0';
	puts( text );
	puts( b1 );
	puts( b2 );
	puts( b3 );
	puts( b4 );
}

int
main( void )
{
	ullong i1 = 9999, i2 = 9999 << 1, q1 = 0, q2 = 0, i = 0;
	PTRS Q1 = endian( &q1, sizeof( llong ), getIntEndian() );
	//PTRS Q2 = endian( &q2, sizeof( int ), getIntEndian());
	PTRS  I = endian( &i, sizeof( llong ), getIntEndian() );
	PTRS I1 = endian( &i1, sizeof( llong ), getIntEndian() );
	//*
	PTRS I2 = endian( &i2, sizeof( llong ), getIntEndian() );
	putt( "eiseq", !eiseq( I1, I2, NULL, NULL ) );
	putt( "  emt",   !emt( I1, I2, NULL, NULL ) );
	putt( "emteq", !emteq( I1, I2, NULL, NULL ) );
	putt( "  elt",    elt( I1, I2, NULL, NULL ) );
	putt( "elteq",  elteq( I1, I2, NULL, NULL ) );
	putt( " eis0",  !eis0( I1, NULL ) );
	//*/
	eshl( I1, 1 );
	puti( "<< 1:", i1, i2, q1, q2 );
	i2 >>= 7;
	eshr( I1, 7 );
	puti( ">> 7:", i1, i2, q1, q2 );
	i = 177777;
	i2 += i;
	eadd( I1, I );
	puti( "+ 177777:", i1, i2, q1, q2 );
	i = 3;
	for( i1 = 0; i1 < 3; ++i1 ) { putt( "emteq", !emteq( I1, I, NULL, NULL ) ); }
	for(       ; i1 < 8; ++i1 ) { putt( "emteq",  emteq( I1, I, NULL, NULL ) ); }
	i1 = i2 = 3;
	i2 -= i;
	esub( I1, I );
	puti( "3 - 3:", i1, i2, q1, q2 );
	i = 55;
	i1 = i2 = 55;
	i2 *= i;
	emul( I1, I );
	puti( "55 * 55:", i1, i2, q1, q2 );
	i = 88963;
	i2 *= i;
	emul_karatsuba( I1, I );
	puti( "* 88963:", i1, i2, q1, q2 );
	i = 3;
	q2 = i2 % i;
	i2 /= i;
	ediv( Q1, I1, I, NULL, 0 );
	puti( "/ 3:", i1, i2, q1, q2 );
	i1 = q1;
	q1 = 0;
	q2 = 0;
	puts( "Press any key to continue..." );
	fgetc( stdin );
	return 0;
}
