//Takes in any size string of numbers and performs the desired math.
//By: Kurt Gosch.



/**
   This class represents arbitrarily large signed integers (at least MAXINT binary digits). 
   Basic arithmetic operations are implemented, such as sum, difference, product, quotient 
   and remainder, as well as some predicates for comparing numbers.
*/


public class Intzilla {

      public static final Intzilla	NEGATIVE_ONE = new Intzilla ( "-1" );
      public static final Intzilla	ZERO = new Intzilla ( "0" );
      public static final Intzilla	ONE = new Intzilla ( "+1" );
      
      private String intzilla;
      private String topNum;
      private String botNum;
      private int topSub = 0;
      private int botSub = 0;
      private int tempResult = 0;
      private String tempSolution = "";
      private String finalSolution = "";
      private String tempToAdd = "";
      private int carry = 0;
      private int carryFrom = 0;
      private String sign = "";


	/**
	Constructs a Intzilla from a String. The string must be "reasonably well-formed," i.e., it must have the appearance 
	of a signed integer; some examples of good strings are "-1439283467", "004245", and "+324". White space is allowed at 
	the ends of the string, but there must be no embedded spaces. '+' signs are optional. Note that this is a private
	constructor; applications have to use one of the static "factory" methods.	  
	*/
	private Intzilla ( String s ) {
	
		try {
			if ( s.charAt(0) == '+' ) {
				intzilla = s.substring(1);
			} else if ( s.charAt(0) == '-' ) {
				sign = "-";
				intzilla = s.substring(1);
			} else if ( Character.isDigit(s.charAt(0)) ) {
				intzilla = s;
			}
			if ( intzilla.length() > 1 ) {
				while ( intzilla.charAt(0) == '0' ) {
					intzilla = intzilla.substring(1);
					if ( intzilla.length() == 1 ) {
					break;
					}
				}
			}	
			intzilla = (sign + intzilla);
		} catch ( Exception e ) {
			System.out.println("Invalid Input");
		}	
	}

   /**
      Returns an Intzilla from a given string. The string must be "reasonably well-formed," i.e., it must have the appearance 
	  of a signed integer; some examples of good strings are "-1439283467", "004245", and "+324". White space is allowed at 
	  the ends of the string, but there must be no embedded spaces. '+' signs are optional.
   */
   public static Intzilla fromString ( String s ) {
      throw new UnsupportedOperationException();
   }   

   /**
      Returns an Intzilla from a given bit string, presumed to represent a non-negative number.
   */
   public static Intzilla fromBitString ( String s ) {
      throw new UnsupportedOperationException();
   }
   
   /**
      Returns the duplicate of an Intzilla.
   */
	public static Intzilla fromIntzilla ( Intzilla n ) {
	throw new UnsupportedOperationException();
	}   


   /**
	  Performs some arithmetic operation (<i>args[1]</i>) on two Intzillas (specified by <i>args[0]</i> and <i>args[2]</i>).
	  Example of use: <i>java Intzilla 245328765823458723645 times 987987987987987987987</i>. Legal operations are
	  <i>plus</i>, <i>minus</i>, <i>times</i>, <i>divide</i>, <i>remainder</i>.
   */
	public static void main ( String[] args ) {
	
	try {
		if ( args.length != 3 ) {
			throw new IllegalArgumentException("Wrong number of arguments.");
		}
		Intzilla i1 = new Intzilla( args[0] );
		Intzilla i2 = new Intzilla( args[2] );
		String useMethod = new String ( args[1] );
		if ( useMethod.equals("plus") ) {
			i1.add(i2);
		} else if ( useMethod.equals("minus") ) {
			i1.difference(i2);
		} else if ( useMethod.equals("times") ) {
			i1.product(i2);
		} else if ( useMethod.equals("divide") ) {
			i1.quotient(i2);
		} else if ( useMethod.equals("remainder") ) {
			i1.remainder(i2);
		}
		System.out.println("Result: " + i1.intzilla);
		
	} catch ( Exception e ) {
		System.out.println("Exception: " + e.getMessage());
	}
		
		
		
	
	}

    /**
	   This static method returns the binary representation Intzilla as a string of zeros 
	   and ones. This Intzilla must be non-negative.
	*/
   public static String toBitString ( Intzilla n ) {
      throw new UnsupportedOperationException();
   }


   /**
		Returns a stringy representation of this Intzilla. The initial character is the sign.
   */
	public String toString () {
	
		return ( this.intzilla + "" );
	}

   /**
	   Returns true if this Intzilla is equivalent to the argument.
   */
	public boolean equals ( Object obj ) {
	
		Intzilla compare1 = new Intzilla(this.toString());
		Intzilla compare2 = new Intzilla(obj.toString());
		if ( compare1.getSign() == compare2.getSign() ) {
			compare1.absoluteValue();
			compare2.absoluteValue();
		}else{
			return false;
		}	
		return (compare1.intzilla.equals(compare2.intzilla));
	}

	/**
	   Returns <i>-1</i> if this Intzilla is smaller than the argument, <i>0</i> if they are identical, or
	   <i>+1</i> if the Intzilla is greater than the arguments.
	*/
	public int compareTo ( Intzilla n ) {
		
		if ( this.isLessThan(n) ) {
			return -1;
		}else if ( this.isGreaterThan(n) ) {
			return 1;
		}
		return 0;
	}
   /**
	   Returns true if and only if this Intzilla is greater than the argument.
   */
	public boolean isGreaterThan ( Intzilla n ) {
	
		Intzilla compare1 = new Intzilla(this.toString());
		Intzilla compare2 = new Intzilla(n.toString());
		compare1.absoluteValue();
		compare2.absoluteValue();
		String newN = compare2.toString();	
		if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
			return true;
		}else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			return false;	
		}else if ( (this.getSign() == '+') && (n.getSign() == '+') ) {
			if ( (compare1.intzilla.length()) > (compare2.intzilla.length()) ) {
				return true;
			}else if ( (compare1.intzilla.length()) == (compare2.intzilla.length()) ) {
				for ( int i = 0; i<newN.length(); i++ ) {
					int x = Integer.parseInt(compare1.intzilla.substring(i,i+1));
					int y = Integer.parseInt(newN.substring(i,i+1));
					if ( x < y ) {
						return false;
					}else if ( x > y ) {
						return true;
					}
				}
			}else if ( (compare1.intzilla.length()) < (compare2.intzilla.length()) ) {
				return false;
			}
		}else if ( (this.getSign() == '-') && (n.getSign() == '-') ) {
			if ( (compare1.intzilla.length()) > (compare2.intzilla.length()) ) {
				return false;
			}else if ( (compare1.intzilla.length()) == (compare2.intzilla.length()) ) {
				for ( int i = 0; i<newN.length(); i++ ) {
					int x = Integer.parseInt(compare1.intzilla.substring(i,i+1));
					int y = Integer.parseInt(newN.substring(i,i+1));
					if ( x > y ) {
						return false;
					}else if ( x < y ) {
						return true;
					}
				}
			}else if ( (compare1.intzilla.length()) < (compare2.intzilla.length()) ) {
				return true;
			}	
		}
		return false;	
	}

   /**
	   Returns true if this Intzilla is less than the argument.
   */

	public boolean isLessThan ( Intzilla n ) {
	
		Intzilla compare1 = new Intzilla(this.toString());
		Intzilla compare2 = new Intzilla(n.toString());
		compare1.absoluteValue();
		compare2.absoluteValue();
		String newN = compare2.toString();	
		if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
			return false;
		}else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			return true;	
		}else if ( (this.getSign() == '+') && (n.getSign() == '+') ) {
			if ( (compare1.intzilla.length()) > (compare2.intzilla.length()) ) {
				return false;
			}else if ( (compare1.intzilla.length()) == (compare2.intzilla.length()) ) {
				for ( int i = 0; i<newN.length(); i++ ) {
					int x = Integer.parseInt(compare1.intzilla.substring(i,i+1));
					int y = Integer.parseInt(newN.substring(i,i+1));
					if ( x < y ) {
						return true;
					}else if ( x > y ) {
						return false;
					}
				}
			}else if ( (compare1.intzilla.length()) < (compare2.intzilla.length()) ) {
				return true;
			}
		}else if ( (this.getSign() == '-') && (n.getSign() == '-') ) {
			if ( (compare1.intzilla.length()) > (compare2.intzilla.length()) ) {
				return true;
			}else if ( (compare1.intzilla.length()) == (compare2.intzilla.length()) ) {
				for ( int i = 0; i<newN.length(); i++ ) {
					int x = Integer.parseInt(compare1.intzilla.substring(i,i+1));
					int y = Integer.parseInt(newN.substring(i,i+1));
					if ( x > y ) {
						return true;
					}else if ( x < y ) {
						return false;
					}
				}
			}else if ( (compare1.intzilla.length()) < (compare2.intzilla.length()) ) {
				return false;
			}	
		}
		return false;	
	}
   
   /**
	   Adds the argument to this Intzilla.
   */
	public void add ( Intzilla n ) {
		
		tempSolution = "";
		finalSolution = "";
		carry = 0;
		sign = "";
		if ( this.compareTo(n) == 1 || this.compareTo(n) == 0 ) {
			topNum = this.toString();
			botNum = n.toString();
		}else if ( this.compareTo(n) == -1 ) {
			topNum = n.toString();
			botNum = this.toString();
		}
		if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			Intzilla tempZilly = new Intzilla ( this.intzilla );
			this.intzilla = n.intzilla;
			n.intzilla = tempZilly.intzilla;
			n.absoluteValue();
			this.difference(n);
			return;
		} else if ( (this.getSign() == '+') && (n.getSign() == '-')	) {
			n.absoluteValue();
			this.difference(n);
			return;
		}else if ( (topNum.charAt(0) == '-') && (botNum.charAt(0) == '-') ) {
			topNum = topNum.substring(1);
			botNum = botNum.substring(1);
			if ( topNum.length() < botNum.length() ) {
				String temp = topNum;
				topNum = botNum;
				botNum = temp;
			}	
			sign = "-";
		}else if ( (topNum.charAt(0) != '-'/*+*/) && (botNum.charAt(0) != '-'/*+*/) ) {
			if ( topNum.charAt(0) == '+' ) {
				topNum = topNum.substring(1);
			}
			if ( botNum.charAt(0) == '+' ) {
				botNum = botNum.substring(1);
			}	
		}
		for ( int i = 0; botNum.length() < topNum.length(); i++ ) {
			botNum = ("0" + botNum);
		}
		int loopTimes = botNum.length();
		for ( int i = 0; i < loopTimes; i++ ) {
			topSub = Integer.parseInt( topNum.substring( (topNum.length()) - 1 ) );
			topNum = topNum.substring( 0, ((topNum.length()) - 1) );
			botSub = Integer.parseInt( botNum.substring( (botNum.length()) - 1 ) );
			botNum = botNum.substring( 0, ((botNum.length()) - 1) );
			tempResult = (topSub + botSub + carry);
			tempSolution = (tempResult + "");
			finalSolution = ( (tempSolution.substring( (tempSolution.length()) - 1 )) + finalSolution );
			if ( tempSolution.length() > 1 ) {
				carry = 1;
			}else{
				carry = 0;
			}	
		}
		if ( carry == 1 ) {
			finalSolution = ("1" + finalSolution);
		}
		if ( finalSolution.length() > 1 ) {
			while ( finalSolution.charAt(0) == '0' ) {
				finalSolution = finalSolution.substring( 1 );
			}
		}	
		this.intzilla = (sign + finalSolution);
		
	}

   /**
	   Subtracts the argument from this Intzilla.
   */
	public void difference ( Intzilla n ) {
	
		finalSolution = "";
		sign = "";
		if ( this.equals(n) ) {
			this.intzilla = "0";
			return;
		} else if ( (this.getSign() == '+') && (n.getSign() == '+') && (this.isGreaterThan(n)) ) {
			topNum = this.toString();
			botNum = n.toString();
		} else if ( (this.getSign() == '+') && (n.getSign() == '+') && (this.isLessThan(n)) ) {
			topNum = n.toString();
			botNum = this.toString();
			sign = "-";
		} else if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
			this.absoluteValue();
			n.absoluteValue();
			this.add(n);
			return;
		} else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			n.intzilla = ("-" + n.intzilla);
			this.add(n);
			return;
		} else if ( (this.getSign() == '-') && (n.getSign() == '-') && (this.isLessThan(n)) ) {
			this.absoluteValue();
			n.absoluteValue();
			sign = "-";
			topNum = this.toString();
			botNum = n.toString();
		} else if ( (this.getSign() == '-') && (n.getSign() == '-') && (this.isGreaterThan(n)) ) {
			this.absoluteValue();
			n.absoluteValue();
			topNum = n.toString();
			botNum = this.toString();
		}
		int loopTimes = botNum.length();
		for ( int i = 0; i < loopTimes; i++ ) {
			topSub = Integer.parseInt( topNum.substring( (topNum.length()) - 1 ) );
			topNum = topNum.substring( 0, ((topNum.length()) - 1) );
			botSub = Integer.parseInt( botNum.substring( (botNum.length()) - 1 ) );
			botNum = botNum.substring( 0, ((botNum.length()) - 1) );
			if ( topSub >= botSub ) {
				tempResult = topSub - botSub;
			}else{
				int [] topNumArray = new int [topNum.length()];
				for ( int p = 0; p < topNum.length(); p++ ) {
					topNumArray[p] = Integer.parseInt( topNum.substring( p, p+1 ) );
				}
				for ( int a = (topNumArray.length - 1); a >= 0; a-- ) {
					if ( topNumArray[a] == 0 ) {
						topNumArray[a] = 9;
					} else {
						topNumArray[a] = (topNumArray[a] - 1);
						break;
					}				
				}
				topNum = "";
				for ( int b = 0; b < topNumArray.length; b++ ) {
					topNum = ( topNum + (topNumArray[b] + "") );
				}
				topSub = 10 + topSub;
				tempResult = topSub - botSub;
			}		
			tempSolution = (tempResult + "");
			finalSolution = ( tempSolution + finalSolution );
		}
		finalSolution = (topNum + finalSolution);
		tempSolution = finalSolution;
		for ( int j = 0; j < tempSolution.length(); j++ ) {
			if ( Integer.parseInt( tempSolution.substring( j, j+1 ) ) == 0 ) {
				finalSolution = tempSolution.substring(j+1);
			}else{
				finalSolution = tempSolution.substring(j);
				break;
			}	
		}
		this.intzilla = (sign + finalSolution);
	}

   /**
	   Multiplies this Intzilla by the argument.
   */
	public void product ( Intzilla n ) {
	
		tempSolution = "";
		finalSolution = "0";
		carry = 0;
		if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
			n.absoluteValue();
			sign = "-";
		} else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			this.absoluteValue();
			sign = "-";
		} else if ( (this.getSign() == '-') && (n.getSign() == '-') ) {
			this.absoluteValue();
			n.absoluteValue();
			sign = "";
		}	
		if ( this.compareTo(n) == 1 || this.compareTo(n) == 0 ) {
			topNum = this.toString();
			botNum = n.toString();
		}else if ( this.compareTo(n) == -1 ) {
			topNum = n.toString();
			botNum = this.toString();
		}
		int topLoopTimes = topNum.length();
		int botLoopTimes = botNum.length();
		for ( int j = 0; j < botLoopTimes; j++ ) {
			botSub = Integer.parseInt( botNum.substring( (botNum.length()) - 1 ) );
			botNum = botNum.substring( 0, ((botNum.length()) - 1) );
			for ( int i = 1; i <= topLoopTimes; i++ ) {
				topSub = Integer.parseInt( topNum.substring( ((topNum.length()) - i), (((topNum.length()) - i) + 1)  ) );
				tempResult = ((topSub * botSub) + carry);
				tempSolution = ((tempResult + "") + tempSolution);
				if ( tempResult >= 10 ) {
					carry = Integer.parseInt( (tempSolution.substring( 0, 1 )) );
					tempSolution = tempSolution.substring( 1 );
				}else{
					carry = 0;
				}
			}
			tempToAdd = ((carry + "") + tempSolution);
			tempSolution = "";
			carry = 0;
			for ( int k = 0; k < j; k++ ) {
				tempToAdd = (tempToAdd + "0");
			}
			Intzilla zilly1 = new Intzilla(tempToAdd);
			Intzilla zilly2 = new Intzilla(finalSolution);
			zilly1.add(zilly2);
			finalSolution = zilly1.toString();
		}
		if ( finalSolution.length() > 1 ) {
			while ( finalSolution.charAt(0) == '0' ) {
				finalSolution = finalSolution.substring(1);
				if ( finalSolution.length() == 1 ) {
				break;
				}
			}
		}
		if ( finalSolution.charAt(0) == '0' ) {
			this.intzilla = finalSolution;
		} else {
			this.intzilla = (sign + finalSolution);
		}	
	}

   /**
	   Divides this Intzilla by the argument.
   */
	public void quotient ( Intzilla n ) {
	
	try {
			if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
				n.absoluteValue();
				sign = "-";
			} else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
				this.absoluteValue();
				sign = "-";
			} else if ( (this.getSign() == '-') && (n.getSign() == '-') ) {
				this.absoluteValue();
				n.absoluteValue();
				sign = "";
			} else if ( (this.getSign() == '+') && (n.getSign() == '+') ) {
				sign = "";
			}
			if ( n.intzilla.charAt(0) == '0' ) {
				throw new IllegalArgumentException ("Can't divide by zero!");
			} else if ( this.isLessThan(n) && this.intzilla.charAt(0) != '0' ) {
				throw new IllegalArgumentException ("Can't result in fraction!");
			}
		final Intzilla TWO = new Intzilla("2");
		Intzilla tempN = new Intzilla(n.intzilla);
		Intzilla tempPowers = new Intzilla("1");
		Intzilla tempSolution = new Intzilla("0");
		int loopTimes = 0;
		for ( int i = 0; n.isLessThan(this) || n.intzilla.equals(this.intzilla); i++ ) {
			n.add(n);
			loopTimes = i;
		}
		if ( loopTimes == 0 ) {
			loopTimes = 1;
		}
		Intzilla [] doublesToAdd = new Intzilla [loopTimes+1];
		Intzilla [] powersOfTwo = new Intzilla [loopTimes+1];
		Intzilla [] powersToAdd = new Intzilla [loopTimes+1];
		for ( int i = 0; i < powersToAdd.length; i++ ) {
			doublesToAdd[i] = new Intzilla("0");
			powersOfTwo[i] = new Intzilla("0");
			powersToAdd[i] = new Intzilla("0");
		}
		n.intzilla = tempN.intzilla;
		doublesToAdd[0] = tempN; 
		powersOfTwo[0].intzilla = "1";
		for ( int i = 0; i < loopTimes; i++ ) {
			n.product(TWO);
			doublesToAdd[i+1].intzilla = n.intzilla;
			tempPowers.product(TWO);
			powersOfTwo[i+1].intzilla = tempPowers.intzilla; 
		}
		for ( int i = 0; i < doublesToAdd.length; i++ ) {
			powersToAdd[(powersToAdd.length - 1)] = powersOfTwo[(powersOfTwo.length - 1)];
			tempSolution = doublesToAdd[(doublesToAdd.length - 1)];
		}
		for ( int i = (doublesToAdd.length - 1); tempSolution.isLessThan(this) && i > 0; i-- ) {
			tempSolution.add(doublesToAdd[i-1]);	
			if ( tempSolution.isGreaterThan(this) ) {
				tempSolution.difference(doublesToAdd[i-1]);		
			} else if ( tempSolution.isLessThan(this) || tempSolution.equals(this) ) {
				powersToAdd[i-1] = powersOfTwo[i-1];
			}	
		}
		tempSolution = powersToAdd[0];
		for ( int i = 1; i < powersToAdd.length; i++ ) {
			tempSolution.add(powersToAdd[i]);
		}
		n.intzilla = tempN.intzilla;
		n.product(TWO);
		if ( n.isGreaterThan(this) && this.intzilla.charAt(0) != '0' ) {
			this.intzilla = (sign + "1");
		}else
		if ( this.intzilla.charAt(0) == '0' ) {
			this.intzilla = "0";
		} else {
			this.intzilla = (sign + tempSolution.intzilla);
		}
	} catch ( Exception e ) {
		System.out.println("Exception: " + e.getMessage());
	}
			
	}


   /**
	   Remainders this Intzilla by the argument. It is 
	   similar to Java's infix modulo (%) operator.
   */
	public void remainder ( Intzilla n ) {
	
		if ( this.intzilla.charAt(0) == '0' ) {
			this.intzilla = "0";
		} else if ( (this.getSign() == '+') && (n.getSign() == '+') ) {
			Intzilla tempThis = new Intzilla(this.intzilla);
			Intzilla tempN = new Intzilla(n.intzilla);
			this.quotient(n);
			n = tempN;
			this.product(n);
			tempThis.difference(this);
			this.intzilla = tempThis.intzilla;
		} else if ( (this.getSign() == '+') && (n.getSign() == '-') ) {
			n.absoluteValue();
			Intzilla tempThis = new Intzilla(this.intzilla);
			Intzilla tempN = new Intzilla(n.intzilla);
			this.quotient(n);
			n = tempN;
			this.product(n);
			n = tempN;
			this.add(n);
			this.difference(tempThis);
			this.intzilla = ("-" + this.intzilla);
		} else if ( (this.getSign() == '-') && (n.getSign() == '+') ) {
			this.absoluteValue();
			Intzilla tempThis = new Intzilla(this.intzilla);
			Intzilla tempN = new Intzilla(n.intzilla);
			this.quotient(n);
			n = tempN;
			this.product(n);
			n = tempN;
			this.add(n);
			this.difference(tempThis);
			this.intzilla = ("-" + this.intzilla);
		} else if ( (this.getSign() == '-') && (n.getSign() == '-') ) {
			this.absoluteValue();
			n.absoluteValue();
			Intzilla tempThis = new Intzilla(this.intzilla);
			Intzilla tempN = new Intzilla(n.intzilla);
			this.quotient(n);
			n = tempN;
			this.product(n);
			tempThis.difference(this);
			this.intzilla = tempThis.intzilla;	
		}
		
	
	}


   /** Replaces this Intzilla with its absolute value. */
	public void absoluteValue () {
	
		while ( (this.intzilla.charAt(0) == '+') || (this.intzilla.charAt(0) == '-') ) {
			this.intzilla = this.intzilla.substring(1);
		}
	}
	
	
	/** Returns the sign of the Intzilla. */
	public char getSign () {
	
		char sign = this.intzilla.charAt(0);
		if ( sign == '+' || Character.isDigit(sign) ) {
			sign = '+';
		}else{
			sign = '-';
		}
		return sign;
	}
   
   

   /** Overrides Object.hashCode(). */
   public int hashCode () {
      throw new UnsupportedOperationException();
   }   

}