class Arbol:
    clave=None
    izq=None
    der=None

class ArbolBidimensional(Arbol):
    def __init__(self,x,y,niv=0):
        self.clave=[x,y]
        self.niv=niv
    def __tab__(self,n):
        a=""
        for i in range(n):
            a=a+"\t"
        return a
    def __repr__(self):
        a=""
        a=a+str(self.clave)+"\n"
        if self.izq!=None:
            a=a+self.__tab__(self.izq.niv)+"Izq:"
            a=a+str(self.izq)+"\n"
        if self.der!=None:
            a=a+self.__tab__(self.der.niv)+"Der:"
            a=a+str(self.der)
        return a
    
    def insertar(self, x,y,hor=True):    
        if hor==True:
            if self.clave[0]<x:                
                if self.der==None:                    
                    self.der=ArbolBidimensional(x,y,self.niv+1)                    
                else:
                    self.der.insertar(x,y,False)
            elif self.clave[0]>x:
                if self.izq==None:
                    self.izq=ArbolBidimensional(x,y,self.niv+1)
                else:
                    self.izq.insertar(x,y,False)
            else:
                if self.clave[0]==x and self.clave[1]==y:
                    print "El dato "+str(x)+" "+str(y)+"ya existe"
                else:
                    self.insertar(x,y,False)
        elif hor==False:
            if self.clave[1]<y:                
                if self.der==None:
                    self.der=ArbolBidimensional(x,y,self.niv+1)                    
                else:
                    self.der.insertar(x,y,True)
            elif self.clave[1]>y:
                if self.izq==None:
                    self.izq=ArbolBidimensional(x,y,self.niv+1)
                else:
                    self.izq.insertar(x,y,True)
            else:
                if self.clave[0]==x and self.clave[1]==y:
                    print "El dato "+str(x)+" "+str(y)+" ya existe"
                else:
                    self.insertar(x,y,True)
    def buscar(self,x,y,hor=True):
        if self.clave==[x,y]:
            return True
        else:
            if hor==True:
                if self.clave[0]<x:
                    if self.der!=None:
                        return self.der.buscar(x,y,False)
			print clave [x,y]
                elif self.clave[0]>x:
                    if self.izq!=None:
                        return self.izq.buscar(x,y,False)
                else:
                    if self.clave[0]==x :
                        return self.insertar(x,y,False)
            elif hor==False:
                if self.clave[1]<y:
                    if self.der!=None:
                        return self.der.buscar(x,y,True)
                elif self.clave[1]>y:
                    if self.izq!=None:
                        return self.izq.buscar(x,y,True)
                else:
                    if self.clave[0]==x :
                        return self.insertar(x,y,True)
   #def imprimir(self,)

def recdatox():
   datox=int(raw_input("Digite x: "))
   return datox

def recdatoy():
   datoy=int(raw_input("Digite y: "))
   return datoy

def menu(): 
   tmp=0
   tmp2=0
   opc=""
   arbol=None   
   a=ArbolBidimensional(tmp, tmp2)
   while(opc!="0"):
	print "1). Insertar"
	print "2). Buscar"
	print "3). Imprimir listado"
	opc=raw_input("Escoja una opcion\n")
	if opc=="1":
		tmp=recdatox()
		tmp2=recdatoy()
		if arbol==None:
			arbol=ArbolBidimensional(tmp,tmp2)
		else:
			a.insertar(tmp,tmp2)
	elif opc=="2":
		tmp=recdatox()
		tmp2=recdatoy()
		if arbol==None:
			print "el arbol esta vacio"
		else:
			a.buscar(tmp, tmp2)			
	elif opc=="3":
		if arbol==None:
			print "el arbol esta vacio"
		else:
			a.imprimir()
	else:
		pass
menu()