public class Env<T>{
    static <R> Env<R> empty(){ return new Env<R>(); }
    static RunErr err(String s, String w){ return new RunErr(s+"("+w+"): Empty Env");}
    Env<T> push(T s){ return new ConsEnv<T>(s,this); }
    Env<T> push(Env<T> e){ return e.append(this); }
    Env<T> append(Env<T> e){ return e; }
    int lookup(T t){ return lookup(t,0); }
    int lookup(T t, int i){ return -1; }
    Env<T> pop(int i){
        if(i == 0)return this;
        throw err("pop",""+i);
    }
    T get(int i){ throw err("get", ""+i); }
    T find(T t){ throw err("find","\""+t+"\""); }
    Env<T> replace(T t, int i){ throw err("replace","\""+t+"\""); }
    boolean isEmpty(){ return true; }
    public String toString(){ return ""; }
}

class ConsEnv<T> extends Env<T>{
    T first;
    Env<T> rest;
    ConsEnv(T f, Env<T> r){ first = f; rest = r; }
    Env<T> append(Env<T> e){ return rest.append(e).push(first); }
    int lookup(T t, int i){ return first.equals(t)?i:rest.lookup(t, i+1); }
    Env<T> pop(int i){ return (i==0)?this:rest.pop(i-1); }
    T get(int i){ return (i==0)?first:rest.get(i-1); }
    T find(T t){ return first.equals(t)?first:rest.find(t); }
    Env<T> replace(T t, int i){ 
        return (i==0)?rest.push(t):(rest.replace(t, i-1).push(first));
    }    
    boolean isEmpty(){ return false; }
    public String toString(){ return "("+first+", "+rest+")"; }
}