public class intNumber
{
	byte		num[];
	int			numSize;
	int			numUsed;
	
	// init
	public intNumber(int size)
	{
		num = new byte[size];
		numSize = size;
		numUsed = 1;
		num[0] = 0;
	}
	
	// set
	public void set(int newNum)
	{
		int		i;
		byte	modulus;
		
		i = 0;
		while(newNum > 0 && i < numSize)
		{
			modulus = (byte) (newNum % 10);
			newNum /= 10;
			
			num[i] = modulus;
			i++;
		}
		
		numUsed = i;
	}
	
	public void set(intNumber newNum)
	{
		int		i, max;
		
		i = 0;
		if(newNum.numUsed < numSize)
			max = newNum.numUsed;
		else
			max = numSize;
		
		while(i < max)
		{
			num[i] = newNum.num[i];
			i++;
		}
		
		numUsed = max;
	}
	
	
	// print
	public void print()
	{
		int		i;
		
		if(numUsed == 0)
			System.out.print("0");
		else
		{
			i = numUsed;
			while(i > 0)
			{
				i--;
				System.out.print(num[i]);
			}
		}
		if(numUsed >= numSize-1)
			System.out.print(" (possible overflow)");
	}
	
	// checkUsed
	public void checkUsed()
	{
		byte	number;
		int		i;
		
		i = numUsed - 1;
		number = num[i];
		while(number == 0 && i >= 0)
		{
			i--;
			number = num[i];
		}
		
		numUsed = i + 1;
	}
	
	// exp
	public static void exp(intNumber x, int e, intNumber num)
	{
		intNumber	exp = new intNumber(num.numSize);
		intNumber	temp = new intNumber(num.numSize);
		int			i;
		
		i = e/2;
		if(i*2 != e)
			num.set(x);
		else
			num.set(1);
		
		e = i;
		exp.set(x);
		
		while(e > 0)
		{
			exp.mul(exp, temp);
			
			i = e/2;
			if(i*2 != e)
				num.mul(exp, temp);
			
			e = i;
		}
	}
	
	// mul
	public void mul(intNumber b)
	{
		intNumber	temp = new intNumber(numUsed + b.numUsed);
		
		mul(b, temp);
	}
	
	// mul
	public void mul(intNumber b, intNumber temp)
	{
		intNumber.mul(this, b, temp);
		set(temp);
	}
	
	// mul
	public static void mul(intNumber a, intNumber b, intNumber c)
	{
		// calculates: a * b = c
		
		int		over;
		int		res;
		int		i;
		int		sizeA, sizeB, sizeC, minUsed;
		intNumber temp;
		int		ia,ib, steps;
		int		na, nb;
		
		if(a == c)
		{
			a.mul(b);
			return;
		}
		if(b == c)
		{
			b.mul(a);
			return;
		}
		
		sizeA = a.numUsed;
		sizeB = b.numUsed;
		sizeC = c.numSize;
		
		if(sizeA < sizeB)
		{
			// swap numbers
			temp = a;
			a = b;
			b = temp;
			
			i = sizeA;
			sizeA = sizeB;
			sizeB = i;
		}
		
		// now we know that a is bigger than b
		
		over = 0;
		i = 0;
		steps = sizeA + sizeB;
		while(i < steps)
		{
			ia = i;
			ib = 0;
			res = over;
			
			while(ib <= i)
			{
				na = 0;
				nb = 0;
				if(ia >= 0 && ia < sizeA)
					na = a.num[ia];
				
				if(ib >= 0 && ib < sizeB)
					nb = b.num[ib];
				
				res += na * nb;
				
				ia--;
				ib++;
			}
			
			
			over = res / 10;
			res -= over*10;
			
			if(i < sizeC)
				c.num[i] = (byte)res;
			
			i++;
		}
		
		
		// store size
		if(i > sizeC)
			i = sizeC;
		
		c.numUsed = i;
		
		c.checkUsed();
	}
	
	
	// add
	public static void add(intNumber a, intNumber b, intNumber c)
	{
		// calculates: a + b = c
		
		int		over;
		byte	res;
		int		i;
		int		sizeA, sizeB, sizeC, minUsed;
		intNumber temp;
		
		sizeA = a.numUsed;
		sizeB = b.numUsed;
		sizeC = c.numSize;
		
		if(sizeA < sizeB)
		{
			// swap numbers
			temp = a;
			a = b;
			b = temp;
			
			i = sizeA;
			sizeA = sizeB;
			sizeB = i;
		}
		
		// now we know that a is bigger than b
		
		i = 0;
		over = 0;
		while(i < sizeB)
		{
			res = (byte)(a.num[i] + b.num[i] + over);
			over = 0;
			if(res > 9)
			{
				over = 1;
				res -= 10;
			}
			
			if(i < sizeC)
				c.num[i] = res;
			
			i++;
		}
		
		while(i < sizeA)
		{
			res = (byte)(a.num[i] + over);
			over = 0;
			if(res > 9)
			{
				over = 1;
				res -= 10;
			}
			
			if(i < sizeC)
				c.num[i] = res;
			
			i++;
		}
		
		if(over > 0)
		{
			if(i < sizeC)
				c.num[i] = (byte)over;
			i++;
		}
		
		// store size
		if(i > sizeC)
			i = sizeC;
		
		c.numUsed = i;
	}
}