---

                                                                                                                                  
//длинная арифметика Окулов Ф.М.+ отрицательные

#include <string.h>
#include <stdio.h>
#include <math.h> 

#define	MaxDig 1000 //Максимальное количество цифр — четырехзначных!
#define	Osn 0x100 //Основание нашей системы счисления, в элементах массива храним двузначные шестнадцатиричные числа
#define	mm	8	//число двоичных разрядов у Osn

//структура данных,  количество "цифр" в массиве,  сами цифры, они определяются системой счисления, знак числа
typedef struct{
	int lm[MaxDig];	//массив чисел
	int len;				//размер массива, кол-во чисел
	int sign; 			//знак числа (-1,+1);
} LDig;

//перевод строки в длинное число 
void Read16Long1(LDig *A, char *S){
	char ch;
	int i,j, len;
	
	len= strlen(S); //??????
	for (i=0;i<len;i++){

	//считываем символ
		ch=S[i];
//еслм отрицательное, то устанавливаем sign		
		if (ch=='-'){
			A->sign=-1;
			i++;
			ch=S[i];
		} 
		switch (ch){
			case 'a': ch=0xa;
						break;
			case 'A': ch=0xa;
						break;
			case 'b': ch=0xb;
						break;
			case 'B': ch=0xb;
						break;
			case 'c': ch=0xc;
						break;
			case 'C': ch=0xc;
						break;
			case 'd': ch=0xd;
						break;
			case 'D': ch=0xd;
						break;
			case 'e': ch=0xe;
						break;
			case 'E': ch=0xe;
						break;
			case 'f': ch=0xf;
						break;
			case 'F': ch=0xf;
						break;
			default:	ch=ch-0x30;
						break;
		}

	//вставляем в массив
		for (j=A->len;j>=0;j--){

			//"протаскивание" старшей цифры в числе из A[j] 
				//в младшую цифру числа из A[j+l]
				A->lm[j+1] = A->lm[j+1] + (A->lm[j]*16)/Osn;  //одна буква - 4 бита = 16, перетаскиваем на одну позицию
				A->lm[j] = (A->lm[j]*16)%Osn;
		}
		A->lm[0] = A->lm[0] + ch;//добавляем младшую цифру к числу из А[1]}

			//изменяем длину, число задействованных элементов массива А}
		if (A->lm[A->len] > 0) A->len++;		
		if (A->lm[A->len+1] > 0) A->len++;
	}
	return;
}

void Read16Long(LDig *A, char *S){
	char  chs[3], s[256];
	int i,len, b[100],ch,k=0 ;
	if (S[0]=='-'){
		A->sign = -1;
		k=1;}
//для положительных	
	strcpy(chs,"");
	len= strlen(S);
	A->len = len/2;
	for (i=k;i<len;i+=2){
		chs[0]=S[i];
		chs[1]=S[i+1];
		chs[2]='\0';
		sscanf(chs,"%02x",&ch);
		b[i/2]=ch;
	}
	
	for(i=0; i<A->len;i++)
		A->lm[A->len-1-i]=b[i];
	
	
}

//перевод короткого (целого - 2 байта) числа в строку
void Dig16Str(int k, char *s){
	int num=0, d, os,i;
	char s1[256];
	d=k;
	//формируем строку
	do{
		os=d%16;
		switch (os){
			case 10: s1[num]= 'a';
						   break;
			case 11: s1[num]= 'b';
						   break;
			case 12: s1[num]= 'c';
						   break;
			case 13: s1[num]= 'd';
						   break;
			case 14: s1[num]= 'e';
						   break;
			case 15: s1[num]= 'f';
						   break;
			default:  s1[num]=os+0x30;	   
						   break;
		}
		d=d/16;
		num++;
	} while (d!=0);

	//если отрицательное
	if (k<0)	{s1[num]='-'; num++;}

//запись числа задом наперед
	s[num]= '\0';
	for (i=num-1;i>=0;i--)	s[num-1-i]=s1[i];

	return;
}

//запись длинного числа в строку
void Write16Long(LDig *A, char *S){
	char ls[256];
	char s[10];
	int i,j,k=0,n,len1;
	
	//если отрицательное
	if (A->sign<0) strcpy(S,"-");
	else strcpy(S,"");
	strcpy(s,"");

	//рабочая строка
	for (i=A->len-1;i>=0;i--){
		sprintf(s,"%02x", A->lm[i]);
		strcat(S,s);
	}


	return;
}

void Write16Long1(LDig *A, char *S){
	char ls[256];
	char s[256];
	int i,j,k=0,n,len1;
	//если отрицательное
	if (A->sign<0) {S[k]='-';k++;}
	
	//строка для основания системы счисления
	Dig16Str(Osn/16,ls);
	
	//рабочая строка
	for (i=A->len-1;i>=0;i--){
		Dig16Str(A->lm[i],s);
		
		//заполняем нулями перед цифрами, если надо
		while((strlen(s)<strlen(ls))&&(i!=A->len-1)){	
			len1=strlen(s);
			
			//сдвигаем число
			for (n=len1;n>0;n--)	s[n]=s[n-1];
			s[0]= '0' ; s[1]= '0';
			s[len1+1]= '\0' ;
		}

			//вставляем в основную строку
		for (j=0;j<strlen(s);j++) 	S[k+j]=s[j];
		k=k+j;
	}
	S[k]='\0';

	return;
}

//распечатка длинного числа
void ShowLong(LDig *A){
	int i;
	for (i=0; i<A->len;i++)	printf("%d ",A->lm[i]);
	printf("\n");
	return;
}

//распечатка длинного числа в строку
void ShowLongS(LDig *A){
	char S[256];
	
	Write16Long(A, S);
	printf("%s\n",S);
	return;
}

//инициализация LDig
void InitLong(LDig *A){
	int i;
	for (i=0; i<MaxDig; i++)	A->lm[i]=0;
	A->len=1;	A->sign=1; //положительное, нулевой вектор
	return;
}

//перевод целого числа в массив
void DigToArray(int k, LDig *A){
	int res, i=0, sign=1;
	if (k<0) sign=-1;
	res=fabs(k);
	while (res>0){
		A->lm[i]=res%Osn;
		res/=Osn;
		i++;
	}
	A->len=i;
	A->sign=A->sign*sign;
	return;	
}

//Сравнение двух длинных чисел: равно (1), не равно (0)
int Eq(LDig *A, LDig *B){
	int i;
	if ((A->len!=B->len)||(A->sign!=B->sign))	return 0;	//разные длины, знаки , нельзя сравнивать не равны
	else {
		i=0;
		
		//сравниваем поразрядно
		while ((i<A->len)&&(A->lm[i]==B->lm[i]))	i++;
	}
	return i==A->len;
}

//Сравнение положительных |A|>|B| больше (1), |A|<|B| меньше (0)
int More(LDig *A, LDig *B) {
	int i, sr=0;
	if (A->len<B->len)	sr=0;	//меньше
	else
		if(A->len>B->len)	sr=1;	//больше
		else{
			i=A->len-1;
			while ((i>0)&&(A->lm[i]==B->lm[i]))	i--;
			if (i==-1)	sr=0;
			else
				if (A->lm[i]>B->lm[i])	sr=1;
				else 	sr=0;
		}
	
	return sr;
}

//положительные
//сравнение со сдвигом, сдвигаем B 
//результат 0, если |A|>|B|; 1, если |A|<|B|; 2, если |A|=|B|
int More_Shift(LDig *A, LDig *B, int sp){
	int res,i;
	if (A->len>B->len+sp)	res=0;
	else{
		if (A->len<B->len+sp)	res=1;
		else{
			i=A->len-1;
			while ((i>sp-1)&&(A->lm[i]==B->lm[i-sp]))	i--;
			if (i==sp-1) {
				res=0;	
				//совпадение чисел с учетом сдвига
				for(i=0;i<sp-1;i++)	if (A->lm[i]>0) return res;
				res=2;	//числа равны, "хвост" числа А равен нулю
			}
			else 	res=(A->lm[i]<B->lm[i-sp]);
		}
	}
	return res;
}

//|A|<|B|
int Less(LDig*A, LDig *B){
	return !(More(A,B)||Eq(A,B));
}

//|A|>=|B|
int More_Eq(LDig *A, LDig *B){
	return More(A,B)||Eq(A,B);
}

//|A|<=|B|
int Less_Eq(LDig *A,LDig *B){
	return !More(A,B);
}

//проверка на равенство нулю A=0 (1, иначе 0)
int	IsNulLong(LDig *A){
	if ((A->len==1)&&(A->lm[0]==0)) return 1;
	else  return 0;
}

//Умножение длинного числа на короткое (Osn), результат в C
void Mul(LDig *A, int K, LDig*C){
	int i;
	InitLong(C);
    if (K!=0){
		for (i=0;i<A->len;i++){
			C->lm[i+1]=(C->lm[i]+A->lm[i]*fabs(K))/Osn;
			C->lm[i]=(C->lm[i]+A->lm[i]*(int)fabs(K))%Osn;
		}
		//определяем длину результата
		if (C->lm[A->len]>0)	C->len=A->len+1;
		else 	C->len=A->len;
	}
	C->sign=A->sign*(K/fabs(K));
	return;
}

//Умножение длинного числа на короткое (<Osn), результат в A
void MulA(LDig *A, int K){
	LDig C;
	InitLong(&C);
	Mul(A, K, &C);
	*A=C;
 
	return;
}

//положительные
//вычитание двух длинных чисел с учетом сдвига |A|>|B|, результат в A (вычитание модулей, без учета знака)
//sp- число разрядов для сдвига, сдвигаем B
void Sub_Shift(LDig *A, LDig *B, int sp){
	int i,j;
	
	//из А вычитаем В с учетом сдвига sp, результат вычитания в А
	for (i=0; i<B->len;i++){
		A->lm[i+sp]-=B->lm[i];
		j=i;
		
		//реализация сложного заимствования
		while ((A->lm[j+sp]<0)&&(j<A->len-1)){
			A->lm[j+sp]+=Osn;
			A->lm[j+sp+1]--;
			j++;
		}
	}
	//корректировка длины результата операции
	i = A->len-1;
	while( (i > 0)&&(A->lm[i] == 0)) 	i--;
	A->len = i+1;
	
	return;
}

//положительные
//Сложение двух длинных чисел |A| и |B| с учетом сдвига, результат в A (сложение модулей без учета знака)
//sp- число разрядов для сдвига, сдвигаем B !!!нет у Окулова
void Sum_Shift(LDig *A, LDig*B, int sp){
	int i,k;
	if (A->len>B->len+sp)	k=A->len;
	else 	k=B->len+sp;
	for (i=0;i<k;i++){
		A->lm[i+sp+1]+=(A->lm[i+sp]+B->lm[i])/Osn;
		A->lm[i+sp]=(A->lm[i+sp]+B->lm[i])%Osn;
	}
	if (A->lm[k]==0)	A->len=k;
	else 	A->len=k+1;

	return;
}

//положительные
//сложение двух положительных чисел (столбиком), результат в C без учета знака
void SumTwo(LDig *A, LDig *B, LDig *C){
	*C=*A;
	Sum_Shift(C,B,0);

	return;
}

//положительные
	//вычитание |A|>|B|, результат в C
void SubTwo(LDig *A, LDig *B, LDig *C){
	//из А вычитаем В с учетом сдвига sp, результат вычитания в А
	*C=*A;
	Sub_Shift(C,B,0);
	
	return;
}


//сложение двух длинных со знаком, результат в C
void SumLong(LDig *A, LDig *B, LDig *C){
	//Если оба одного знака - сумма
	if (A->sign==B->sign){
		 SumTwo(A, B, C);
		 C->sign=A->sign;
	 }
	 //Знаки разные - разность
	 else{
		 if (A->len>B->len){
			 SubTwo(A, B, C);
			 C->sign=A->sign;
		 }
		 else{
			 SubTwo(B, A, C);
			 C->sign=B->sign;
		 }
	 }
	return;
}

//сложение двух длинных со знаком, результат в A
void SumLongA(LDig *A, LDig *B){
	LDig C;
	InitLong(&C);
	SumLong(A, B, &C);
	*A=C;
	return;
}

//вычитание двух длинных со знаком, результат в C
void SubLong(LDig *A, LDig *B, LDig *C){
	//знаки разные - сумма
	if (A->sign!=B->sign){
		SumTwo(A, B, C);
		C->sign=A->sign;
	}
	//знаки одинаковые
	else{
		if (More(A, B)){
			SubTwo(A,B,C);
			C->sign=A->sign;
		}
		else{
			SubTwo(B, A, C);
			C->sign=-B->sign;
		}
	}
	return;
}

//вычитание двух длинных со знаком, результат в A
void SubLongA(LDig *A, LDig *B){
	LDig C;
	InitLong(&C);
	SubLong(A, B, &C);
	*A=C;
	return;
}

//Умножение двух длинных чисел со знаком !!!нет у Окулова, результат в C
void MulTwoLong(LDig *A, LDig *B, LDig*C){
	int i;
	LDig  C1;
	InitLong(&C1);
	for (i=0;i<B->len;i++){
		Mul(A, B->lm[i], &C1);
		Sum_Shift(C, &C1 , i);
	}
	C->sign=A->sign*B->sign;
	
	return;
}

//Умножение двух длинных чисел со знаком !!!нет у Окулова, результат в A
void MulTwoLongA(LDig *A, LDig *B){
	LDig  C;
	InitLong(&C);	
	MulTwoLong(A, B, &C);
	*A=C;
	return;
}
/*
//Сложение модальное, результат в A (аргументы - остатки по модулю)
void SumLongmA(LDig *A, LDig *B, LDig p){
	LDig C;
	InitLong(&C);
	//Если оба одного знака - сумма
	if (A->sign==B->sign)	Sum_Shift(A, B, 0);
	 //Знаки разные - разность
	 else{
		 if (A->len>B->len)	 Sub_Shift(A, B,0);
		 else{
			 C=*B;
			 Sub_Shift(&C, A, 0);
			 *A=C;
			 A->sign=B->sign;
		 }
	 }
	 if???
	return;
}*/

//деление двух длинных чисел (частное и остаток)
//=================================================

//двоичный поиск - подбираем результат деления
int FindBin(LDig *Ost, LDig *B, int sp){

	int Down=0, Up=Osn,k;
	LDig C;
	InitLong(&C);
	while(Up-1>Down){
		Mul(B, (Up + Down)/2, &C);
		k=More_Shift(Ost, &C, sp);
		switch (k) {
			case 0: Down = (Down + Up)/2;
						break;
			case 1: Up = (Up + Down)/2;
						break;
			case 2: Up = (Up + Down)/2; 
						Down = Up;
						break;
		}
	}
	Mul(B, (Up + Down)/2, &C);
	
			//находим остаток от деления
	if (More_Shift (Ost, &C, 0) == 0) Sub_Shift(Ost, &C, sp);
	else {
		Sub_Shift (&C, Ost, sp); 
		*Ost = C;
	}
	
	return (Up + Down)/2;	//целая часть частного
}

void MakeDel(LDig *A, LDig *B, LDig *Res, LDig *Ost){
	int sp;

//первоначальное значение остатка Ost=A
	*Ost = *A;
	sp=A->len-B->len;
	if (More_Shift(A,B,sp)==1)	sp--;
	//B * Osn > A, в результате одна цифра
	Res->len=sp+1;
	while (sp>=0){
		
		//находим очередную цифру результата
		Res->lm[sp]=FindBin(Ost,B,sp);
		sp--;
	}

	return;
}

//остаток может быть отрицательным
void LongDivLong(LDig *A, LDig *B, LDig *Res, LDig *Ost){

	switch (More_Shift(A,B,0)){
		case 0:	MakeDel(A,B,Res,Ost);
				break;
		case 1:	*Ost=*A;	//А меньше В
				break;
		case 2: Res->lm[1]=1;	//А равно В
				break;
	}
	Res->sign=A->sign*B->sign;
	Ost->sign=A->sign*B->sign;
	//если остаток - отрицательный
/*	if ((Ost->sign<0)&&!IsNulLong(Ost)){
		SumLongA(Ost, B);
	}*/
	return;
}

/*
int main(){
	LDig A;
	int i;
	char S[]="34FF";
	InitLong(&A);
	Read16Long1(&A, S);
	ShowLongS(&A);

	for (i=A.len-1;i>=0;i--)
		printf("%x", A.lm[i]);
	printf("\n");
	
	return 0;
}*/