from time import clock
import sys

class CreateNode(object):

  def __init__(this,Num): 

    this.Num = Num     
    this.Left  = None
    this.Right  = None
  

class NodeOperation: 

 
  def __init__(this): 

    this.Head=this.Last= None
    this.TotalComparision=0 


  def InsertNode(this,Num):
    
    if this.Head is not None:

          this.Last=CreateNode(Num)
          this.Previous=this.Head
          this.SearchPosition_in_Tree_To_Insert()
          
    else:
          this.Head=this.Last=CreateNode(Num)


  def Find_Predecessor(this,Rroot):
     
     if (this.Previous.Left is not None):
        
        this.Previous=this.Previous.Left
        
        while(this.Previous.Right is not None):
          this.Previous=this.Previous.Right         
     
        return this.Previous.Num

     else:

       if (Rroot != None): 
         return Rroot.Num
       return -1 
       




  def Find_Successor(this,Lroot):
     
     if (this.Previous.Right is not None):

        this.Previous=this.Previous.Right
        while(this.Previous.Left is not None):
          this.Previous=this.Previous.Left              

        return this.Previous.Num
     else:
          
       if (Lroot != None):
         return Lroot.Num
       return -1
         

  def Traverse_Tree(this,Num):
    
    this.Previous=this.Head
    Lroot=Rroot=None    
    
    while( this.Previous is not None):
      
      if (Num == this.Previous.Num):

          this.TotalComparision+=1          
          this.Last=this.Previous         
          
          Predecessor=this.Find_Predecessor(Rroot)
          
          this.Previous=this.Last

          Successor=this.Find_Successor(Lroot)                  

          return Predecessor,Successor,this.TotalComparision
        
      elif (Num < this.Previous.Num):

        this.TotalComparision+=1
        Lroot=this.Previous
        this.Previous=this.Previous.Left        

      else:
        
        this.TotalComparision+=1
        Rroot=this.Previous
        this.Previous=this.Previous.Right
        
      
    print "::::::::::::::::::::::::NUMBER ",Num,"IS NOT PRESENT IN THE TREE::::::::::::::::::::::::::::::"





  def SearchPosition_in_Tree_To_Insert(this):    
    
    
    if (this.Last.Num == this.Previous.Num):

          this.TotalComparision+=1          
          this.Previous.Left=this.Last          
          return      
      
    if (this.Last.Num < this.Previous.Num):

        this.TotalComparision+=1
        
        if (this.Previous.Left is None) :
          
          this.Previous.Left=this.Last
          return
    
        else:
          this.Previous=this.Previous.Left
          this.SearchPosition_in_Tree_To_Insert()
        
    else:

      this.TotalComparision+=1
      
      if (this.Previous.Right is None) :
        
        this.Previous.Right=this.Last
        return
    
      else:
        this.Previous=this.Previous.Right
        this.SearchPosition_in_Tree_To_Insert()         
       




def Binary_Search_Tree():

     try:
          
          InFile=open('in14_1.txt','r')
          OutFile=open('out_11_14_1.txt','w')
          
          start=clock()        
          
          Anum=InFile.readline().split(",")

          del Anum[0]
          
          Aprec=InFile.readline().split(",")          
          
## START
          
          OprationObj=NodeOperation()
          
          for Num in Anum:                           
               OprationObj.InsertNode(int(Num))

          
          for Num in Aprec:                           
            Predecessor,Successor,TotalComparision=OprationObj.Traverse_Tree(int(Num))
            OutFile.write(str(Predecessor)+","+str(Successor)+",")

          OutFile.write("\nTotal Comparisiona are : "+str(TotalComparision))

## END
           
          
          OutFile.write("\nTotal Excution Time : "+str(clock()-start))
          
          
          memUsed = sys.getsizeof(InFile) + sys.getsizeof(OutFile)+ sys.getsizeof(start)+ sys.getsizeof(Anum)+ sys.getsizeof(Aprec)+sys.getsizeof(OprationObj)+sys.getsizeof(Predecessor)+sys.getsizeof(Successor)+sys.getsizeof(TotalComparision)
          OutFile.write("\nMemory used : "+str(memUsed)+" Bytes")
          
                           


          InFile.close()
          OutFile.close()
          
          print "Check Your Output File : out_11_sec14_1.txt is Generated"

     except ValueError:

          print "Check Your Output File Cant Not Generated",ValueError
          InFile.close()
          OutFile.close()



Binary_Search_Tree()