import java.util.Vector; import java.awt.*; import java.awt.event.*; import java.applet.*;

public class LeiteAb extends Applet {
    // {0,a,0} = z(a) = a
    // {1,a,0} = v(a) = "x", ...
    // {2,a,b} = +(a,b) = a+b
    // {3,a,b} = -(a,b) = a-b
    // {4,a,b} = *(a,b) = a*b
    // {5,a,b} = /(a,b) = a/b
    // {6,a,b} = p(a,b) = a^b
    // {7,a,0} = ln a
    // {8,a,b} = log(a)(b)
    // {9,a,0} = sin(a)
    //{10,a,0} = cos(a)
    //{11,a,0} = tan(a)
    //{12,a,0} = arcsin(a) = asin(a) = asn(a)
    //{13,a,0} = arccos(a) = acos(a) = acs(a)
    //{14,a,0} = arctan(a) = atan(a) = atn(a)

    public static Vector L=new Vector();
    public static String vars;
    public static TextField TF1 = new TextField(90);
    public static Label TF2 = new Label();
    public static Label TF3 = new Label();
    public static Label TF4 = new Label();

    public void init() {
        GridBagLayout gridbag = new GridBagLayout(); setSize(600,120);
        setFont(new Font("Serif",Font.BOLD, 10)); GridBagConstraints c = new GridBagConstraints();
        Label T1 = new Label("Enter Formula here:");
        Label T2 = new Label("Assuming:");
        Label T3 = new Label("Derivation:");
        Label T4 = new Label("2nd Derivation:");
        setLayout(gridbag);c.fill=GridBagConstraints.BOTH;
        c.gridwidth = 1; T1.setAlignment(java.awt.Label.RIGHT);
        gridbag.setConstraints(T1,c); add(T1);
        c.gridwidth = GridBagConstraints.REMAINDER; TF1.addActionListener(new ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		try {
		while(L.size()>0) kill(0);
		ad(0,0,0); root(anl(opt(e.getActionCommand())));
		while(rmv()||unify()||seman());
		TF2.setText(neat(read(root())));
		root(abl(root()));
		while(rmv()||unify()||seman());
		TF3.setText(neat(read(root())));
		root(abl(root()));
		while(rmv()||unify()||seman());
		TF4.setText(neat(read(root())));
		} catch(Exception f) {TF3.setText("Error: "+f.getMessage()); TF2.setText(""); TF4.setText(""); }
	    }
	});
        gridbag.setConstraints(TF1,c);add(TF1);
        c.gridwidth = 1; T2.setAlignment(java.awt.Label.RIGHT);
        gridbag.setConstraints(T2,c); add(T2);
        c.gridwidth = GridBagConstraints.REMAINDER; TF2.setAlignment(java.awt.Label.CENTER);
        gridbag.setConstraints(TF2,c);add(TF2);
        c.gridwidth = 1; T3.setAlignment(java.awt.Label.RIGHT);
        gridbag.setConstraints(T3,c); add(T3);
        c.gridwidth = GridBagConstraints.REMAINDER; TF3.setAlignment(java.awt.Label.CENTER);
        gridbag.setConstraints(TF3,c);add(TF3);
        c.gridwidth = 1; T4.setAlignment(java.awt.Label.RIGHT);
        gridbag.setConstraints(T4,c); add(T4);
        c.gridwidth = GridBagConstraints.REMAINDER; TF4.setAlignment(java.awt.Label.CENTER);
        gridbag.setConstraints(TF4,c);add(TF4);
    }

    public void start() { L = new Vector(); vars = "x"; TF2.setText(""); TF3.setText(""); TF4.setText("");}

    public void stop() { vars=""; }

    public static void main(String[] args) {
	if((args.length<1)||(args.length>2)) {
	    System.out.println("Syntax: LeiteAb function [variable]"); System.exit(0); }
	if((args.length==2)&&((args[1]).length()==1)) vars=args[1]; else vars="x";
	ad(0,0,0);
	try { root(anl(opt(args[0])));
	while(rmv()||unify()||seman());
	System.out.println("Assuming: ");pri();
	root(abl(root()));
	while(rmv()||unify()||seman());
	System.out.println("Derivation: ");pri();
	root(abl(root()));
	while(rmv()||unify()||seman());
	System.out.println("2nd derivation: ");pri();
	} catch(Exception e) { System.out.println(e.getMessage()); }
    }

    public static int abl(int pr) { // do the Ableitung
	int[] e = get(pr);
	switch(e[0]) {
	case 0: return ad(0,0,0); // (z(a))' = 0
	case 1: if(e[1]==0) return ad(0,1,0); else return ad(0,0,0); // (x)' = 1 ; (l)' = 0
	case 2: return ad(2,abl(e[1]),abl(e[2])); // (+(a,b))' = +((a)',(b)')
	case 3: return ad(3,abl(e[1]),abl(e[2])); // (-(a,b))' = -((a)',(b)')
	case 4: return ad(2,ad(4,abl(e[1]),e[2]),ad(4,e[1],abl(e[2]))); // (*(a,b))' = a'*b+a*b'
	case 5: return ad(5,ad(3,ad(4,abl(e[1]),e[2]),ad(4,e[1],abl(e[2]))),ad(6,e[2],ad(0,2,0))); // /(a,b)
	case 6: return ad(2,ad(4,abl(e[1]),ad(4,e[2],ad(6,e[1],ad(3,e[2],ad(0,1,0))))),ad(4,ad(4,ad(6,e[1],e[2]),ad(7,e[1],0)),abl(e[2])));
	case 7: return ad(5,abl(e[1]),e[1]);
	case 8: return ad(5,abl(e[1]),ad(4,e[1],ad(7,e[2],0)));
	case 9: return ad(4,abl(e[1]),ad(10,e[1],0));
	case 10:return ad(3,ad(0,0,0),ad(4,abl(e[1]),ad(9,e[1],0)));
	case 11:return abl(ad(5,ad(9,e[1],0),ad(10,e[1],0)));
	case 12:return ad(5,abl(e[1]),ad(6,ad(3,ad(0,1,0),ad(6,e[1],ad(0,2,0))),ad(5,ad(0,1,0),ad(0,2,0))));
	case 13:return ad(3,ad(0,0,0),ad(5,abl(e[1]),ad(6,ad(3,ad(0,1,0),ad(6,e[1],ad(0,2,0))),ad(5,ad(0,1,0),ad(0,2,0)))));
	case 14:return ad(5,abl(e[1]),ad(2,ad(0,1,0),ad(6,e[1],ad(0,2,0))));
	} return 0;
    }

    public static int ad(int a,int b, int c) { // create new predicate, return number
        int[] d = {a,b,c};
        L.addElement(d);
	return L.size()-1;
    }

    public static int[] get(int a) { // get predicate number
	return (int[])L.elementAt(a);
    }

    public static int get(int a,int b) { // get predicate depth 1
	return ((int[])(L.elementAt(a)))[b];
    }

    public static int get(int a, int b, int c) { // get predicate depth 2
	return get(get(a,b),c);
    }

    public static int get(int a, int b, int c, int d) { // get predicate depth 3
	return get(get(a,b,c),d);
    }

    public static int get(int a, int b, int c, int d, int e) { // get predicate depth 4
	return get(get(a,b,c,d),e);
    }

    public static void put(int i, int[] a) { // set predicate
	L.setElementAt(a,i);
    }

    public static void put(int i, int a, int b, int c) {
        int[] d = {a,b,c};
        L.setElementAt(d, i);
    }

    public static boolean prin() { // printout tree as numbers
	for(int i=0; i<L.size();i++) {
	System.out.print(i); if(i==root()) System.out.print(" *");
	System.out.print("\t");	for(int j=0;j<3;j++) { System.out.print(get(i,j)+"\t");}
	System.out.println(); } System.out.println();
	return false;
    }

    public static boolean pri() { // initialise printing
	System.out.println(neat(read(root()))); return false;
    }

    public static String neat(String l) {
        while(l.indexOf("  ")>=0) l=l.substring(0,l.indexOf("  "))+l.substring(l.indexOf("  ")+1);
        return l; }

    public static String read(int a) { // return a neat output string
	switch(get(a,0)) {
	case 0: return Integer.toString(get(a,1))+" ";
	case 1: return vars.substring(get(a,1),get(a,1)+1)+" ";
	case 2: return read(get(a,1))+"+ "+read(get(a,2))+" ";
	case 3: {
	    String r = "";
	    if((get(a,1,0)==0)&&(get(a,1,1)==0)) r="-"; else r=read(get(a,1))+"- ";
	    if((get(a,2,0)==2)||(get(a,2,0)==3)) r+="( "+read(get(a,2))+") "; else r+=read(get(a,2));
	    return r; }
	case 4: {
	    String r="";
	    if((get(a,1,0)==2)||(get(a,1,0)==3)) r="( "+read(get(a,1))+") * "; else r=read(get(a,1))+"* ";
	    if((get(a,2,0)==2)||(get(a,2,0)==3)) r+="( "+read(get(a,2))+") "; else r+= read(get(a,2));
	    return r;
	}
	case 5: {
	    String r="";
	    if((get(a,1,0)==2)||(get(a,1,0)==3)) r="( "+read(get(a,1))+") / "; else r=read(get(a,1))+"/ ";
	    if((get(a,2,0)==2)||(get(a,2,0)==3)||(get(a,2,0)==4)) r+="( "+read(get(a,2))+") "; else r+= read(get(a,2));
	    return r;
	}
	case 6: {
	    String r="";
            if((get(a,2,0)==5)&&(get(a,2,1,0)==0)&&(get(a,2,1,1)==1)&&(get(a,2,2,0)==0)&&(get(a,2,2,1)==2)) {
              if((get(a,1,0)>1)&&(get(a,1,0)<6)) return "sqr( "+read(get(a,1))+") "; else return "sqr "+read(get(a,1))+" "; }
	    if((get(a,1,0)>1)&&(get(a,1,0)<6)) r="( "+read(get(a,1))+") ^ "; else r=read(get(a,1))+"^ ";
	    if((get(a,2,0)>1)&&(get(a,2,0)<6)) r+="( "+read(get(a,2))+") "; else r+= read(get(a,2));
	    return r;
	}
	case 7: {
	    String r="";
	    if(get(a,1,0)>1) return "ln( "+read(get(a,1))+") "; else return "ln "+read(get(a,1));
	}
	case 8: return "log( "+read(get(a,1))+") ("+read(get(a,2))+") ";
	case 9: {
	    if(get(a,1,0)>1) return "sin( "+read(get(a,1))+") "; else return "sin "+read(get(a,1));
	}
	case 10: {
	    if(get(a,1,0)>1) return "cos( "+read(get(a,1))+") "; else return "cos "+read(get(a,1));
	}
	case 11: {
	    if(get(a,1,0)>1) return "tan( "+read(get(a,1))+") "; else return "tan "+read(get(a,1));
	}
	case 12: {
	    if(get(a,1,0)>1) return "arcsin( "+read(get(a,1))+") "; else return "arcsin "+read(get(a,1));
	}
	case 13: {
	    if(get(a,1,0)>1) return "arccos( "+read(get(a,1))+") "; else return "arccos "+read(get(a,1));
	}
	case 14: {
	    if(get(a,1,0)>1) return "arctan( "+read(get(a,1))+") "; else return "arctan "+read(get(a,1));
	}
	} return "buu";
    }

    public static boolean unify() { boolean x = false; // search for identic predicates
	for(int i=1;i<L.size();i++) for(int j=1;j<i;j++)
	  if((get(i,0)==get(j,0))&&(((get(i,1)==get(j,1))&&(get(i,2)==get(j,2)))||
            (((get(i,0)==2)||(get(i,0)==4))&&(get(i,1)==get(j,2))&&(get(i,2)==get(j,1)))))
	     { if(root()==i) root(j);
		rpl(i,j); kill(i); x=true; i=1; j=1;
	      };
	return x;
    }

    public static void rpl(int old, int nw) { // search for entry old, replace by nw
	for(int i=1;i<L.size();i++) { int[] now=get(i); if(now[0]>1) {
	    if(now[1]==old) now[1]=nw; if(now[2]==old) now[2]=nw;
	    put(i,now);
	}}
    }

    public static boolean rmv() {
	boolean x=false;
	for(int i=1;i<L.size();i++)
	    if((i!=root())&&(unused(i))) {kill(i); x=true;}
	return x;
    }

    public static void kill(int a) {
	if(L.size()-1==root()) root(a);
	put(a,get(L.size()-1)); rpl(L.size()-1,a); L.removeElementAt(L.size()-1);
    }

    public static boolean unused(int pred) {
	for(int i=1;i<L.size();i++)
	    if((get(i,0)>1)&&((get(i,1)==pred)||(get(i,2)==pred))) return false; return true;
    }

    public static int mine=0;

    public static int root() { return mine; }

    public static void root(int a) { mine=a; }

    public static boolean seman() throws Exception {
	boolean x=false;
	for(int i=0;i<L.size();i++) {
	    switch(get(i,0)) {
	    case 2: {
		if(get(i,1,0)==2) { // +(+(a,b),c) = +(a,+(b,c))
		    put(i,2,get(i,1,1),ad(2,get(i,1,2),get(i,2))); x=true; break; }
                if((get(i,1,0) > get(i,2,0))&&(get(i,2,0)!=2)) { // sort predicates
                    put(i,2,get(i,2),get(i,1)); x=true; break; }
                if((get(i,2,0)==2)&&(smaller(get(i,2,1),get(i,1)))) { // wow... :)
                    put(i,2,get(i,2,1),ad(2,get(i,1),get(i,2,2))); x=true; break; }
                if((ait(get(i,1),2,0)!=0)&&(ait(get(i,2),2,0)!=0)&&(get(ait(get(i,1),4,0),1)!=0)&&(get(ait(get(i,2),4,0),1)!=0)) { // +(z(a),z(b)) = z(a+b)
                    put(i,2,copyTree(get(i,1),2),copyTree(get(i,2),2));
                    int q=ait(get(i,1),2,0);int y=ait(get(i,2),2,0);
                    put(q,0,get(q,1)+get(y,1),0);put(y,0,0,0);
                    x=true;break; }
		if(get(i,1)==get(i,2)) { // +(a,a) = *(a,2)
		    put(i,4,get(i,1),ad(0,2,0)); x=true; break; }
		if((get(i,2,0)==2)&&(get(i,1)==get(i,2,1))) { // +(a,+(a,b)) = +(b,*(a,2))
		    put(i,4,get(i,2,2),ad(4,get(i,1),ad(0,2,0))); x=true; break; }
		if((get(i,2,0)==2)&&(get(i,1)==get(i,2,2))) { // +(a,+(b,a)) = +(b,*(a,2))
		    put(i,4,get(i,2,1),ad(4,get(i,1),ad(0,2,0))); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // +(0,a) = a
		    put(i,get(get(i,2))); x=true; break; }
		if((get(i,2,0)==0)&&(get(i,2,1)==0)) { // +(a,0) = a
		    put(i,get(get(i,1))); x=true; break; }
		if((get(i,1,0)==3)&&(get(i,1,1,0)==0)&&(get(i,1,1,1)==0)) { // +(-(0,a),b) = -(b,a)
		    put(i,3,get(i,2),get(i,1,2)); x=true; break; }
		if((get(i,2,0)==3)&&(get(i,2,1,0)==0)&&(get(i,2,1,1)==0)) { // +(b,-(0,a)) = -(b,a)
		    put(i,3,get(i,1),get(i,2,2)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)) {
		    if(get(i,1,1)==get(i,2,1)) { // +(*(a,b),*(a,c)) = *(a,+(b,c))
			put(i,4,get(i,1,1),ad(2,get(i,1,2),get(i,2,2))); x=true; break; }
		    if(get(i,1,1)==get(i,2,2)) { // +(*(a,b),*(c,a)) = *(a,+(b,c))
			put(i,4,get(i,1,1),ad(2,get(i,1,2),get(i,2,1))); x=true; break; }
		    if(get(i,1,2)==get(i,2,1)) { // +(*(b,a),*(a,c)) = *(a,+(b,c))
			put(i,4,get(i,1,2),ad(2,get(i,1,1),get(i,2,2))); x=true; break; }
		    if(get(i,1,2)==get(i,2,2)) { // +(*(b,a),*(c,a)) = *(a,+(b,c))
			put(i,4,get(i,1,2),ad(2,get(i,1,1),get(i,2,1))); x=true; break; }
		}
		if((get(i,1,0)==5)&&(get(i,2,0)==5)&&(get(i,1,2)==get(i,2,2))) { // +(/(b,a),/(c,a)) == /(+(b,c),a)
		    put(i,5,ad(2,get(i,1,1),get(i,2,1)),get(i,1,2)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,1,1)==get(i,2))) { // +(*(a,b),a) = *(a,+(b,1))
		    put(i,4,get(i,2),ad(2,get(i,1,2),ad(0,1,0))); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,1,2)==get(i,2))) { // +(*(b,a),a) = *(a,+(b,1))
		    put(i,4,get(i,2),ad(2,get(i,1,1),ad(0,1,0))); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,2,1)==get(i,1))) { // +(a,*(a,b)) = *(a,+(b,1))
		    put(i,4,get(i,1),ad(2,get(i,2,2),ad(0,1,0))); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,2,2)==get(i,1))) { // +(a,*(b,a)) = *(a,+(b,1))
		    put(i,4,get(i,1),ad(2,get(i,2,1),ad(0,1,0))); x=true; break; }
		if(get(i,2,0)==3) { // +(a,-(b,c)) = -(+(a,b),c)
		    put(i,3,ad(2,get(i,1),get(i,2,1)),get(i,2,2)); x=true; break; }
		if(get(i,1,0)==3) { // +(-(a,b),c)) = -(+(a,c),b)
		    put(i,3,ad(2,get(i,1,1),get(i,2)),get(i,1,2)); x=true; break; }
                if((get(i,1,0)==0)&&(get(i,2,1,0)==0)&&(get(i,2,2,0)==0)&&(get(i,2,0)==5)) { // +(z(c),/(z(a),z(b))) = /(z(a+b*c),z(b))
                    put(i,5,ad(0,get(i,2,1,1)+get(i,2,2,1)*get(i,1,1),0),get(i,2,2)); x=true; break; }
                if((get(i,1,0)==5)&&(get(i,2,0)==5)) { // +(/(a,b),/(c,d)) = /(+(*(a,d),*(b,c)),*(b,d))
                    put(i,5,ad(2,ad(4,get(i,1,1),get(i,2,2)),ad(4,get(i,1,2),get(i,2,1))),ad(4,get(i,1,2),get(i,2,2))); x=true; break; }
                break;
	    }
	    case 3: {
		if((get(i,1,0)==0)&&(get(i,2,0)==0)&&(get(i,1,1)!=0)) { // -(z(a),z(b)) = z(a-b)
		    int merk=get(i,1,1)-get(i,2,1);
		    if(merk<0) put(i,3,ad(0,0,0),ad(0,-merk,0)); else put(i,0,merk,0);
		    x=true;break; }
		if(get(i,1)==get(i,2)) { // -(a,a) = z(0)
		    put(i,0,0,0); x=true; break; }
		if((get(i,2,0)==0)&&(get(i,2,1)==0)) { // -(a,0) = a
		    put(i, get(get(i,1))); x=true; break; }
		if((get(i,2,0)==3)) { // -(a,-(b,c)) = -(+(a,c),b)
		    put(i,3,ad(2,get(i,1),get(i,2,2)),get(i,2,1)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)) {
		    if(get(i,1,1)==get(i,2,1)) { // -(*(a,b),*(a,c)) = *(a,-(b,c))
			put(i,4,get(i,1,1),ad(3,get(i,1,2),get(i,2,2))); x=true; break; }
		    if(get(i,1,1)==get(i,2,2)) { // -(*(a,b),*(c,a)) = *(a,-(b,c))
			put(i,4,get(i,1,1),ad(3,get(i,1,2),get(i,2,1))); x=true; break; }
		    if(get(i,1,2)==get(i,2,1)) { // -(*(b,a),*(a,c)) = *(a,-(b,c))
			put(i,4,get(i,1,2),ad(3,get(i,1,1),get(i,2,2))); x=true; break; }
		    if(get(i,1,2)==get(i,2,2)) { // -(*(b,a),*(c,a)) = *(a,-(b,c))
			put(i,4,get(i,1,2),ad(3,get(i,1,1),get(i,2,1))); x=true; break; }
		}
		if((get(i,1,0)==5)&&(get(i,2,0)==5)&&(get(i,1,2)==get(i,2,2))) { // -(/(b,a),/(c,a)) == /(-(b,c),a)
		    put(i,5,ad(3,get(i,1,1),get(i,2,1)),get(i,1,2)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,1,1)==get(i,2))) { // -(*(a,b),a) = *(a,-(b,1))
		    put(i,4,get(i,2),ad(3,get(i,1,2),ad(0,1,0))); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,1,2)==get(i,2))) { // -(*(b,a),a) = *(a,-(b,1))
		    put(i,4,get(i,2),ad(3,get(i,1,1),ad(0,1,0))); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,2,1)==get(i,1))) { // -(a,*(a,b)) = *(a,-(1,b))
		    put(i,4,get(i,1),ad(3,ad(0,1,0),get(i,2,2))); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,2,2)==get(i,1))) { // -(a,*(b,a)) = *(a,-(1,b))
		    put(i,4,get(i,1),ad(3,ad(0,1,0),get(i,2,1))); x=true; break; }
                if((get(i,2,0)==5)&&(get(i,1,0)==0)&&(get(i,2,1,0)==0)&&(get(i,2,2,0)==0)) { // -(z(c),/(z(a),z(b))) = /(z(b*c-a),z(b))
                    int merk=get(i,2,2,1)*get(i,1,1)-get(i,2,1,1);
                    if(merk<0) put(i,5,ad(3,ad(0,0,0),ad(0,-merk,0)),get(i,2,2)); else put(i,5,ad(0,merk,0),get(i,2,2));
                    x=true; break; }
                if((get(i,1,0)==5)&&(get(i,2,0)==0)&&(get(i,1,1,0)==0)&&(get(i,1,2,0)==0)) { // -(/(z(a),z(b)),z(c)) = /(z(a-b*c),z(b))
                    int merk=get(i,1,1,1)-get(i,1,2,1)*get(i,2,1);
                    if(merk<0) put(i,5,ad(3,ad(0,0,0),ad(0,-merk,0)),get(i,1,2)); else put(i,5,ad(0,merk,0),get(i,1,2));
                    x=true; break; }
                if((get(i,1,0)==5)&&(get(i,2,0)==5)) { // -(/(a,b),/(c,d)) = /(-(*(a,d),*(b,c)),*(b,d))
                    put(i,5,ad(3,ad(4,get(i,1,1),get(i,2,2)),ad(4,get(i,1,2),get(i,2,1))),ad(4,get(i,1,2),get(i,2,2))); x=true; break; }
		break;
	    }
	    case 4: {
		if(get(i,1,0)==4) { // *(*(a,b),c) = *(a,*(b,c))
		    put(i,4,get(i,1,1),ad(4,get(i,1,2),get(i,2))); x=true; break; }
                if((get(i,1,0) > get(i,2,0))&&(get(i,2,0)!=4)) { // sort predicates
                    put(i,4,get(i,2),get(i,1)); x=true; break; }
                if((get(i,2,0)==4)&&(smaller(get(i,2,1),get(i,1)))) { // *(a,*(b,c)) =? *(b,*(a,c))
                    put(i,4,get(i,2,1),ad(4,get(i,1),get(i,2,2))); x=true; break; }
                if((ait(get(i,1),4,0)!=0)&&(ait(get(i,2),4,0)!=0)&&(get(ait(get(i,1),4,0),1)!=1)&&(get(ait(get(i,2),4,0),1)!=1)) { // *(z(a),z(b)) = z(a*b)
                    put(i,4,copyTree(get(i,1),4),copyTree(get(i,2),4));
                    int q=ait(get(i,1),4,0);int y=ait(get(i,2),4,0);
                    put(q,0,get(q,1)*get(y,1),0);put(y,0,1,0);
                    x=true;break; }
                if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // *(0,a) = 0
		    put(i,0,0,0); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,1,1)==1)) { // *(1,a) = a
		    put(i, get(get(i,2))); x=true; break; }
		if((get(i,2,0)==0)&&(get(i,2,1)==1)) { // *(a,1) = a
		    put(i, get(get(i,1))); x=true; break; }
		if(get(i,1)==get(i,2)) { // *(a,a) = p(a,2)
		    put(i,6,get(i,1),ad(0,2,0)); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,1)==get(i,2,1))) { // *(a,*(a,b)) = *(b,p(a,2))
		    put(i,4,get(i,2,2),ad(6,get(i,1),ad(0,2,0))); x=true; break; }
		if((get(i,2,0)==4)&&(get(i,1)==get(i,2,2))) { // *(a,*(b,a)) = *(b,p(a,2))
		    put(i,4,get(i,2,1),ad(6,get(i,1),ad(0,2,0))); x=true; break; }
		if((get(i,1,0)==3)&&(get(i,1,1,0)==0)&&(get(i,1,1,1)==0)) { // *(-(0,a),b) = -(0,*(a,b))
		    put(i,3,get(i,1,1),ad(4,get(i,1,2),get(i,2))); x=true; break; }
		if((get(i,2,0)==3)&&(get(i,2,1,0)==0)&&(get(i,2,1,1)==0)) { // *(b,-(0,a)) = -(0,*(a,b))
		    put(i,3,get(i,2,1),ad(4,get(i,2,2),get(i,1))); x=true; break; }
		if((get(i,1,0)==5)&&(get(i,2,0)==5)&&(get(i,1,1)==get(i,2,2))&&(get(i,1,2)==get(i,2,1))) { // *(/(a,b),/(b,a)) = z(1)
		    put(i,0,1,0); x=true; break; }
		if((get(i,1,0)==6)&&(get(i,2,0)==6)&&(get(i,1,1)==get(i,2,1))) { // *(p(a,b),p(a,c)) = p(a,+(b,c))
		    put(i,6,get(i,1,1),ad(2,get(i,1,2),get(i,2,2))); x=true; break; }
		if((get(i,1,0)==6)&&(get(i,2,0)==6)&&(get(i,1,2)==get(i,2,2))) { // *(p(a,b),p(c,b)) = p(*(a,c),b)
		    put(i,6,ad(4,get(i,1,1),get(i,2,1)),get(i,1,2)); x=true; break; }
		if((get(i,1,0)==6)&&(get(i,1,1)==get(i,2))) { // *(p(a,b),a) = p(a,+(b,1))
		    put(i,6,get(i,2),ad(2,get(i,1,2),ad(0,1,0))); x=true; break; }
		if((get(i,2,0)==6)&&(get(i,1)==get(i,2,1))) { // *(a,p(a,b)) = p(a,+(b,1))
		    put(i,6,get(i,1),ad(2,get(i,2,2),ad(0,1,0))); x=true; break; }
		if((get(i,1,0)==6)&&(get(i,2,0)==4)&&(get(i,1,1)==get(i,2,1))) { // *(p(a,b),*(a,c)) = *(c,p(a,+(b,1)))
		    put(i,4,get(i,2,2),ad(6,get(i,1,1),ad(2,ad(0,1,0),get(i,1,2)))); x=true; break; }
		if((get(i,1,0)==6)&&(get(i,2,0)==4)&&(get(i,1,1)==get(i,2,2))) { // *(p(a,b),*(c,a)) = *(c,p(a,+(b,1)))
		    put(i,4,get(i,2,1),ad(6,get(i,1,1),ad(2,ad(0,1,0),get(i,1,2)))); x=true; break; }
		if((get(i,2,0)==6)&&(get(i,1,0)==4)&&(get(i,1,1)==get(i,2,1))) { // *(*(a,c),p(a,b)) = *(c,p(a,+(b,1)))
		    put(i,4,get(i,1,2),ad(6,get(i,1,1),ad(2,ad(0,1,0),get(i,2,2)))); x=true; break; }
		if((get(i,2,0)==6)&&(get(i,1,0)==4)&&(get(i,1,2)==get(i,2,1))) { // *(*(c,a),p(a,b)) = *(c,p(a,+(b,1)))
		    put(i,4,get(i,1,1),ad(6,get(i,1,2),ad(2,ad(0,1,0),get(i,2,2)))); x=true; break; }
                if(get(i,1,0)==5) { // *(/(a,b),c) = /(*(a,c),b)
                    put(i,5,ad(4,get(i,1,1),get(i,2)),get(i,1,2)); x=true; break; }
                if(get(i,2,0)==5) { // *(a,/(b,c)) = /(*(a,b),c)
                    put(i,5,ad(4,get(i,1),get(i,2,1)),get(i,2,2)); x=true; break; }
		if((get(i,2,0)==5)&&(get(i,1)==get(i,2,2))) { // *(a,/(b,a)) = b
		    put(i,get(get(i,2,1))); x=true; break; }
		break;
	    }
	    case 5: {
		if((get(i,2,0)==0)&&(get(i,2,1)==0)) { // /(a,0) err
		    throw new Exception("Forbidden term: n/0"); }
		if((get(i,2,0)==0)&&(get(i,2,1)==1)) { // /(a,1) = a
		    put(i,get(get(i,1))); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // /(0,a) = 0
		    put(i,0,0,0); x=true; break; }
		if(get(i,1)==get(i,2)) { // /(a,a) = 1
		    put(i,0,1,0); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)&&(get(i,1,1)==get(i,2,1))) { // /(*(a,b),*(a,c)) = /(b,c)
		    put(i,5,get(i,1,2),get(i,2,2)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)&&(get(i,1,1)==get(i,2,2))) { // /(*(a,b),*(c,a)) = /(b,c)
		    put(i,5,get(i,1,2),get(i,2,1)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)&&(get(i,1,2)==get(i,2,1))) { // /(*(b,a),*(a,c)) = /(b,c)
		    put(i,5,get(i,1,1),get(i,2,2)); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,2,0)==4)&&(get(i,1,2)==get(i,2,2))) { // /(*(b,a),*(c,a)) = /(b,c)
		    put(i,5,get(i,1,1),get(i,2,1)); x=true; break; }
		if((get(i,1,0)==5)&&(get(i,2,0)==5)&&(get(i,1,2)==get(i,2,2))) { // /(/(a,c),/(b,c)) = /(a,b)
		    put(i,5,get(i,1,1),get(i,2,1)); x=true; break; }
		if((get(i,1,0)==5)&&(get(i,2,0)==5)) { // /(/(a,b),/(c,d)) = /(*(a,d),*(b,c))
		    put(i,5,ad(4,get(i,1,1),get(i,2,2)),ad(4,get(i,1,2),get(i,2,1))); x=true; break; }
		if(get(i,2,0)==5) { // /(a,/(b,c)) = /(*(a,c),b)
		    put(i,5,ad(4,get(i,1),get(i,2,2)),get(i,2,1)); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,2,0)==0)&&(ggT(get(i,1,1),get(i,2,1))>1)) { // /(z(a),z(b)) = /(z(a/ggT(a,b)),z(b/ggT(a,b)))
		    put(i,5,ad(0,get(i,1,1)/ggT(get(i,1,1),get(i,2,1)),0),ad(0,get(i,2,1)/ggT(get(i,1,1),get(i,2,1)),0)); x=true; break; }
                if((get(i,1,0)==0)&&(get(i,2,0)==4)&&(get(i,2,1,0)==0)&&(ggT(get(i,1,1),get(i,2,1,1))>1)) { // /(z(a),*(z(b),c)) = /(z(a)/ggT(a,b),*(z(b)/ggT(a,b),c))
                    put(i,5,ad(0,get(i,1,1)/ggT(get(i,1,1),get(i,2,1,1)),0),ad(4,ad(0,get(i,2,1,1)/ggT(get(i,1,1),get(i,2,1,1)),0),get(i,2,2))); x=true; break; }
                if((get(i,1,0)==4)&&(get(i,1,1)==get(i,2))) { // /(*(a,b),a) = b
		    put(i,get(get(i,1,2))); x=true; break; }
		if((get(i,1,0)==4)&&(get(i,1,2)==get(i,2))) { // /(*(a,b),b) = a
		    put(i,get(get(i,1,1))); x=true; break; }
		if(get(i,1,0)==5) { // /(/(a,b),c) = /(a,*(b,c))
		    put(i,5,get(i,1,1),ad(4,get(i,1,2),get(i,2))); x=true; break; }
		if((get(i,1,0)==3)&&(get(i,1,1,0)==0)&&(get(i,1,1,1)==0)) { // /(-a,b) = -(/(a,b))
                    put(i,3,ad(0,0,0),ad(5,get(i,1,2),get(i,2))); x=true; break; }
		if((get(i,2,0)==3)&&(get(i,2,1,0)==0)&&(get(i,2,1,1)==0)) { // /(a,-b) = -(/(a,b))
                    put(i,3,ad(0,0,0),ad(5,get(i,2,2),get(i,1))); x=true; break; }
		break;
	    }
	    case 6: {
		if((get(i,1,0)==0)&&(get(i,1,1)==0)&&(get(i,2,0)==0)&&(get(i,2,1)==0)) { // p(0,0) err
		    throw new Exception("Forbidden Term: 0^0"); }
		if((get(i,2,0)==0)&&(get(i,2,1)==0)) { // p(a,0) = 1
		    put(i,0,1,0); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // p(0,a) = 0
		    put(i,0,0,0); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,1,1)==1)) { // p(1,a) = 1
		    put(i,0,1,0); x=true; break; }
		if((get(i,2,0)==0)&&(get(i,2,1)==1)) { // p(a,1) = a
		    put(i,get(get(i,1))); x=true; break; }
		if((get(i,2,0)==3)&&(get(i,2,1,0)==0)&&(get(i,2,1,1)==0)) { // p(a,-(z(0),b)) = /(z(1),p(a,b))
		    put(i,5,ad(0,1,0),ad(6,get(i,1),get(i,2,2))); x=true; break; }
		if((get(i,2,0)==7)&&(get(i,1,0)==1)&&(vars.charAt(get(i,1,1))=='e')) {// p(e,ln(a)) = a
		    put(i,get(get(i,2))); x=true; break; }
		if((get(i,1,0)==0)&&(get(i,2,0)==0)) { // p(z(a),z(b)) = z(p(a,b))
		    put(i,0,(int)java.lang.Math.pow(get(i,1,1),get(i,2,1)),0); x=true; break; }
                if((get(i,1,0)==4)&&(get(i,1,1,0)==0)&&(get(i,2,0)==0)) { // p(*(z(a),b),z(c)) = *(p(a,c),p(b,z(c)))
                    put(i,4,ad(0,(int)java.lang.Math.pow(get(i,1,1,1),get(i,2,1)),0),ad(6,get(i,1,2),get(i,2))); x=true; break; }
                if(get(i,1,0)==6) { // p(p(a,b),c) = p(a,*(b,c))
		    put(i,6,get(i,1,1),ad(4,get(i,1,2),get(i,2))); x=true; break; }
		break;
	    }
	    case 7: {
		if((get(i,1,0)==0)&&(get(i,1,1)==1)) { // ln(1) = 0
		    put(i,0,0,0); x=true; break; }
		if((get(i,1,0)==1)&&(vars.charAt(get(i,1,1))=='e')) { // ln(e) = 1
		    put(i,0,1,0); x=true; break; }
		break;
	    }
	    case 9: {
		if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // sin(0) = 0
		    put(i,0,0,0); x=true; break; }
		break;
	    }
	    case 10: {
		if((get(i,1,0)==0)&&(get(i,1,1)==0)) { // cos(0) = 1
		    put(i,0,1,0); x=true; break; }
		break;
	    }}} return x;
    }

    public static int ait(int i, int a, int b) {
        if(get(i,0)==a) { int x=ait(get(i,1),a,b); if(x!=0) return x;
                              x=ait(get(i,2),a,b); if(x!=0) return x;}
        if(get(i,0)==b) return i;
        return 0;
    }

    public static int copyTree(int i, int a) {
        if(get(i,0)!=a) return ad(get(i,0),get(i,1),get(i,2)); else return ad(a,copyTree(get(i,1), a),copyTree(get(i,2), a));
    }

    public static boolean smaller(int a,int b) {
	if(get(a,0)<get(b,0)) return true;
	if(get(a,0)>get(b,0)) return false;
	if(get(a,1)<get(b,1)) return true;
	if(get(a,1)>get(b,1)) return false;
	if(get(a,2)<get(b,2)) return true;
	return false; }

    public static int ggT(int a, int b) {
        if(a<b) { int c=a;a=b;b=c; }
	if(a%b!=0) return ggT(b,a%b); return b; }

    public static int anl(String l) throws Exception {
        if(l.length()==0) { throw new Exception("Null length string error"); }
        while(l.indexOf(" ")==0) l=l.substring(1); // strip leading spaces
	while(l.lastIndexOf(" ")==l.length()-1) l=l.substring(0,l.length()-1); // strip terminating spaces
	if((l.indexOf("(")==0)&&(l.lastIndexOf(")")==l.length()-1)&&(checkBrackets(l.substring(1,l.length()-1))))
	    { l=l.substring(1,l.length()-1); return anl(l); } // strip outside brackets
	if(l.length()==0) return ad(0,0,0);
	if(isZahl(l)) return ad(0,Integer.parseInt(l),0);
	if((l.length()==1)&&(l.charAt(0)>='a')&&(l.charAt(0)<='z')) return ad(1,addVar(l.charAt(0)),0);
        if(l.indexOf("--")==0) return anl(l.substring(2));
	int par=0; for(int i=0;i<l.length();i++) {
	    if(l.charAt(i)=='(') par++; if(l.charAt(i)==')') par--;
	    if((l.charAt(i)=='+')&&(par==0)) return ad(2,anl(l.substring(0,i)),anl(l.substring(i+1,l.length()))); }
	par=0; for(int i=l.length()-1;i>0;i--) {
	    if(l.charAt(i)==')') par++; if(l.charAt(i)=='(') par--;
	    if((l.charAt(i)=='-')&&(par==0)) {
              while(l.charAt(i-1)=='-') i--;
	      return ad(3,anl(l.substring(0,i)),anl(l.substring(i+1,l.length()))); }
	}
	if(l.charAt(0)=='-') return ad(3,ad(0,0,0),anl(l.substring(1)));
	par=0; for(int i=0;i<l.length();i++) {
	    if(l.charAt(i)=='(') par++; if(l.charAt(i)==')') par--;
	    if((l.charAt(i)=='*')&&(par==0)) return ad(4,anl(l.substring(0,i)),anl(l.substring(i+1,l.length()))); }
	par=0; for(int i=l.length()-1;i>=0;i--) {
	    if(l.charAt(i)==')') par++; if(l.charAt(i)=='(') par--;
	    if((l.charAt(i)=='/')&&(par==0)) return ad(5,anl(l.substring(0,i)),anl(l.substring(i+1,l.length()))); }
        if(isZahl(l.substring(0,1))) {
            int k=1; while(isZahl(l.substring(0,k))) k++;k--; if(l.charAt(k)!='^')
              return ad(4,anl(l.substring(0,k)),anl(l.substring(k)));
        }
        if((l.charAt(0)>='a')&&(l.charAt(0)<='z')&&(l.charAt(1)!='^')) return ad(4,ad(1,addVar(l.charAt(0)),0),anl(l.substring(1)));
	par=0; for(int i=0;i<l.length();i++) {
	    if(l.charAt(i)==')') par++; if(l.charAt(i)=='(') par--;
	    if((l.charAt(i)=='^')&&(par==0)) return ad(6,anl(l.substring(0,i)),anl(l.substring(i+1,l.length()))); }
        if(l.charAt(0)=='I') return ad(7,anl(l.substring(1)),0); // = ln
        if(l.charAt(0)=='H') return logExp(l.substring(1));       // = log
        if(l.charAt(0)=='E') return ad(9,anl(l.substring(1)),0); // = sin
        if(l.charAt(0)=='F') return ad(10,anl(l.substring(1)),0);// = cos
        if(l.charAt(0)=='G') return ad(11,anl(l.substring(1)),0);// = tan
        if(l.charAt(0)=='A') return ad(12,anl(l.substring(1)),0);// = asn
        if(l.charAt(0)=='B') return ad(13,anl(l.substring(1)),0);// = acs
        if(l.charAt(0)=='C') return ad(14,anl(l.substring(1)),0);// = atn
        if(l.charAt(0)=='J') return ad(5,ad(0,1,0),ad(11,anl(l.substring(1)),0));         // cot
        if(l.charAt(0)=='D') return ad(6,anl(l.substring(1)),ad(5,ad(0,1,0),ad(0,2,0))); // sqr
        par=0; for(int i=0;i<l.length()-1; i++) {
          if(l.charAt(i)=='(') par++; if(l.charAt(i)==')') { par--; if((par==0)&&(l.charAt(i+1)=='(')) return ad(4,anl(l.substring(0,i+1)),anl(l.substring(i+1))); }}
	throw new Exception("Could not parse string");
    }

    public static int logExp(String l) throws Exception {
	while(l.indexOf(" ")==0) l=l.substring(1); // strip leading spaces
	while(l.lastIndexOf(" ")==l.length()-1) l=l.substring(0,l.length()-1); // strip terminating spaces
	if(l.charAt(0)!='(') { throw new Exception("Wrong log structure!"); }
	if(l.lastIndexOf(')')!=l.length()-1) { throw new Exception("Wrong log structure!"); }
	l=l.substring(1,l.length()-1); if(l.indexOf(",")==-1) { throw new Exception("Wrong log structure!"); }
	return ad(8,anl(l.substring(0,l.indexOf(","))),anl(l.substring(l.indexOf(",")+1)));
    }

    public static boolean isZahl(String p) {
	for(int i=0;i<p.length();i++) if((p.charAt(i)<'0')||(p.charAt(i)>'9')) return false; return true;
    }

    public static int addVar(char c) {
	for(int i=0;i<vars.length();i++) if(vars.charAt(i)==c) return i;
	vars+=c; return vars.length()-1;
    }

    public static boolean checkBrackets(String l) {
	int par=0; for(int i=0;i<l.length();i++) {
	    if(l.charAt(i)=='(') par++;if (l.charAt(i)==')') par--;if(par<0) return false;
	} if(par>0) return false; return true;
    }

    public static String opt(String k) {
        k=k.toLowerCase();
        while(k.indexOf("arcsin")>=0) k=k.substring(0,k.indexOf("arcsin"))+"A"+k.substring(k.indexOf("arcsin")+6);
        while(k.indexOf("arccos")>=0) k=k.substring(0,k.indexOf("arccos"))+"B"+k.substring(k.indexOf("arccos")+6);
        while(k.indexOf("arctan")>=0) k=k.substring(0,k.indexOf("arctan"))+"C"+k.substring(k.indexOf("arctan")+6);
        while(k.indexOf("asin")>=0) k=k.substring(0,k.indexOf("asin"))+"A"+k.substring(k.indexOf("asin")+4);
        while(k.indexOf("acos")>=0) k=k.substring(0,k.indexOf("acos"))+"B"+k.substring(k.indexOf("acos")+4);
        while(k.indexOf("atan")>=0) k=k.substring(0,k.indexOf("atan"))+"C"+k.substring(k.indexOf("atan")+4);
        while(k.indexOf("sqrt")>=0) k=k.substring(0,k.indexOf("sqrt"))+"D"+k.substring(k.indexOf("sqrt")+4);
        while(k.indexOf("asn")>=0) k=k.substring(0,k.indexOf("asn"))+"A"+k.substring(k.indexOf("asn")+3);
        while(k.indexOf("acs")>=0) k=k.substring(0,k.indexOf("acs"))+"B"+k.substring(k.indexOf("acs")+3);
        while(k.indexOf("atn")>=0) k=k.substring(0,k.indexOf("atn"))+"C"+k.substring(k.indexOf("atn")+3);
        while(k.indexOf("sqr")>=0) k=k.substring(0,k.indexOf("sqr"))+"D"+k.substring(k.indexOf("sqr")+3);
        while(k.indexOf("sin")>=0) k=k.substring(0,k.indexOf("sin"))+"E"+k.substring(k.indexOf("sin")+3);
        while(k.indexOf("cos")>=0) k=k.substring(0,k.indexOf("cos"))+"F"+k.substring(k.indexOf("cos")+3);
        while(k.indexOf("tan")>=0) k=k.substring(0,k.indexOf("tan"))+"G"+k.substring(k.indexOf("tan")+3);
        while(k.indexOf("log")>=0) k=k.substring(0,k.indexOf("log"))+"H"+k.substring(k.indexOf("log")+3);
        while(k.indexOf("cot")>=0) k=k.substring(0,k.indexOf("cot"))+"J"+k.substring(k.indexOf("cot")+3);
        while(k.indexOf("ln")>=0) k=k.substring(0,k.indexOf("ln"))+"I"+k.substring(k.indexOf("ln")+2);
        return k;
    }

}