import random
import time
import sys
def binarys(lst,n,low,hi):
    if(low>hi):
        return -1
    mid=(low+hi)/2
    if(lst[mid]<n):
        return binarys(lst,n,mid+1,hi)
    elif(lst[mid]>n):
        return binarys(lst,n,low,mid-1)
    else:
        return 1
def partition(list, start, end):
    pivot = list[end]                          
    bottom = start-1                           
    top = end
    done = 0
    while not done:                            

        while not done:                        
            bottom = bottom+1                  

            if bottom == top:                  
                done = 1                       
                break

            if list[bottom] > pivot:           
                list[top] = list[bottom]       
                break                          

        while not done:                        
            top = top-1                        
            
            if top == bottom:                  
                done = 1                       
                break

            if list[top] < pivot:              
                list[bottom] = list[top]       
                break                          

    list[top] = pivot                          
    return top                                 


def quicksort(list, start, end):
    if start < end:                            
        split = partition(list, start, end)    
        quicksort(list, start, split-1)        
        quicksort(list, split+1, end)
    else:
        return
L1=[]
L2=[]
L3=[]
L=[]
f=open('C:\in20_16.txt','r')
f1=open('C:\out_16_20_6.txt','w')
n=int(f.readline())
l1=f.readline()
l=l1.split("-")
l[0]=int(l[0])
l[1]=int(l[1])
for i in range (0,n):
    L1.append(random.randint(l[0],l[1]))
for i in range (0,n):
    L2.append(random.randint(l[0],l[1]))
for i in range (0,n):
    L3.append(random.randint(l[0],l[1]))
f1.write("3 LISTS ARE:\n")
f1.write(str(L1))
f1.write("\n")
f1.write(str(L2))
f1.write("\n")
f1.write(str(L3))
f1.write("\n")
t1=time.clock()
quicksort(L1,0,len(L1)-1)
quicksort(L2,0,len(L2)-1)
quicksort(L3,0,len(L3)-1)
for i in range (0,len(L1)):
    s=binarys(L2,L1[i],0,len(L2)-1)
    if(s==1):
        L.append(L1[i])
        L2.remove(L1[i])
    else:
        t=binarys(L3,L1[i],0,len(L3)-1)
        if(t==1):
             L.append(L1[i])
             L3.remove(L1[i])
for i in range (0,len(L2)):
    st=binarys(L3,L2[i],0,len(L3)-1)
    if(st==1):
        L.append(L2[i])
        L3.remove(L2[i])            
t2=time.clock()
t=t2-t1
f1.write("FINAL LIST IS:\n")
f1.write(str(L))
mem=sys.getsizeof(L1)+sys.getsizeof(L2)+sys.getsizeof(L3)
f1.write("\ntime taken=%fseconds\nmemory=%dbytes"%(t,mem))

f.close()
f1.close()