/* HP Template is SJTU's 
 * Square root is using manually square root
 * reference on baike.baidu.com
 */
 
#define MaxStrLen 1005
#define MaxAnsLen 505
HP  ans[MaxAnsLen];
int ansLen;
 
void ManualSqrt(char* s)
{	
	int strLen=strlen(s),num,l,i;	
	ansLen = 0;
 
	HP  sq,rem,di,tmp,tmp2;
	HP  hundred,twenty,ten,one;
	Int2HP(100, hundred);
	Int2HP(20, twenty);
	Int2HP(10, ten);
	Int2HP(1, one);
 
 
	bool first=true;
 
	if(strLen&1) {
		num=s[0]-48;
		l=1;
	} else {
		num=(s[0]-48)*10+(s[1]-48);
		l=2;
	}
 
	// sq = (int)sqrt(num)
	Int2HP((int)sqrt((double)num), sq);
	ans[ansLen++]=sq;
 
	while(l<strLen)
	{
		Int2HP((s[l]-48)*10+s[l+1]-48, tmp);		
		if(first) { 
			// rem = (num-sq*sq)*100 + (s[l]-48)*10 + (s[l+1]-48)
			first=false; 			
			Int2HP(num, tmp2);			
			Multi(sq,sq,rem);
			Subtract(tmp2, rem, rem);
			Multi(rem, hundred, rem);
			Plus(rem, tmp, rem); 
		}
		else {
			// rem = (rem - (sq*20+di)*di)*100 + (s[l]-48)*10 + (s[l+1]-48)
			Multi(twenty, sq, tmp2);
			Plus(tmp2, di, tmp2);
			Multi(tmp2, di, tmp2);
			Subtract(rem, tmp2, rem);
			Multi(rem, hundred, rem);
			Plus(rem, tmp, rem);
 
			//sq=sq*10+di;
			Multi(sq, ten, sq);
			Plus(sq, di, sq);
		}
 
		//di=(rem/(20*sq));
		Multi(twenty, sq, tmp2);
		Divide(rem, tmp2, di, tmp);
 
		while(1)
		{
			//while((sq*20+di)*di>rem) 		
			Multi(sq, twenty, tmp2);
			Plus(tmp2, di, tmp2);
			Multi(tmp2, di, tmp2);
			if(HPCompare(tmp2, rem) <=0) break;
			Subtract(di, one, di);
		}
 
		ans[ansLen++] = di;
		l+=2;
	}
 
	//output ans
	for(int i=0;i<ansLen;i++) PrintHP(ans[i]); printf("\n");
}