"""
class Comparator:
    def cmp(self, a, b)
You can use Compare.cmp(a, b) to compare nuts "a" and bolts "b",
if "a" is bigger than "b", it will return 1, else if they are equal,
it will return 0, else if "a" is smaller than "b", it will return -1.
When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
"""
 
from random import randint
class Solution:
    # @param nuts: a list of integers
    # @param bolts: a list of integers
    # @param compare: a instance of Comparator
    # @return: nothing
    def sortNutsAndBolts(self, fnuts, fbolts, compare):
        # write your code here
        self.nuts=fnuts
        self.bolts=fbolts
        if not self.nuts or not self.bolts or len(self.nuts)!=len(self.bolts):
            return
        self.quicksort(0,len(self.nuts)-1,compare.cmp)
   
    def quicksort(self,l,r,cmp):
        if l>=r:
            return
        pivot=self.bolts[randint(l,r)]
        i,j=l,r
        while i<=j:
            while i<=j and cmp(self.nuts[i],pivot)==-1:
                i+=1
            while i<=j and cmp(self.nuts[j],pivot)==1:
                j-=1
            if i<=j:
                self.nuts[i],self.nuts[j]=self.nuts[j],self.nuts[i]
                i+=1
                j-=1
        if i==j:
            self.quicksort_bolt(l,r,i,cmp)
        else:
            self.quicksort_bolt(l,r,i-1,cmp)
       
        self.quicksort(l,j,cmp)
        self.quicksort(i,r,cmp)
        return
       
    def quicksort_bolt(self,l,r,index,cmp):
        if l>=r:
            return
        pivot=self.nuts[index]
        i,j=l,r
        while i<=j:
            while i<=j and cmp(pivot,self.bolts[i])==1:
                i+=1
            while i<=j and cmp(pivot,self.bolts[j])==-1:
                j-=1
            if i<=j:
                self.bolts[i],self.bolts[j]=self.bolts[j],self.bolts[i]
                i+=1
                j-=1
        return