from collections import defaultdict

class Segment_Tree:
    def __init__(self,N,f,e,lst=None,dynamic=False,bisect_search=True):
        self.f=f
        self.e=e
        self.N=N
        self.bisect_search=bisect_search
        if self.bisect_search:
            self.le=1
            while self.le<self.N:
                self.le*=2
        else:
            self.le=self.N
        if dynamic:
            self.segment_tree=defaultdict(lambda:self.e)
        else:
            if lst==None:
                self.segment_tree=[self.e]*2*self.le
            else:
                assert len(lst)<=self.N
                self.segment_tree=[self.e]*self.le+[x for x in lst]+[self.e]*(self.le-len(lst))
                for i in range(self.le-1,0,-1):
                    self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def __getitem__(self,i):
        if type(i)==int:
            if -self.le<=i<0:
                return self.segment_tree[i+self.le*2]
            elif 0<=i<self.le:
                return self.segment_tree[i+self.le]
            else:
                raise IndexError("list index out of range")
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None:
                a=self.le
            else:
                a+=self.le
            if b==None:
                b=self.le*2
            else:
                b+=self.le
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.le<=i<0:
            i+=self.le*2
        elif 0<=i<self.le:
            i+=self.le
        else:
            raise IndexError("list index out of range")
        self.segment_tree[i]=x
        while i>1:
            i>>= 1
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Build(self,lst):
        for i,x in enumerate(lst,self.le):
            self.segment_tree[i]=x
        for i in range(self.le-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.le
        else:
            assert 0<=L<=self.N
            L+=self.le
        if R==None:
            R=self.le*2
        else:
            assert 0<=R<=self.N
            R+=self.le
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.segment_tree[L])
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.segment_tree[R],vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.le
        else:
            assert 0<=L<=self.N
            L+=self.le
        if R==None:
            R=self.le*2
        else:
            assert 0<=R<=self.N
            R+=self.le
        if L==R:
            return None
        x=self.Fold(L-self.le,R-self.le)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.le:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.le
        return i

    def Bisect_Right(self,L=None,f=None):
        assert self.bisect_search
        if L==self.le:
            return self.le
        if L==None:
            L=0
        assert 0<=L<=self.N
        L+=self.le
        vl=self.e
        vr=self.e
        l,r=L,self.le*2
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.segment_tree[L])
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.le:
                    L<<=1
                    vv=self.f(v,self.segment_tree[L])
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.le

    def Bisect_Left(self,R=None,f=None):
        assert self.bisect_search
        if R==0:
            return 0
        if R==None:
            R=self.le
        assert 0<=R<=self.N
        R+=self.le
        vl=self.e
        vr=self.e
        l,r=self.le,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.segment_tree[R],v)
            if f(vv):
                v=vv
            else:
                while R<self.le:
                    R=2*R+1
                    vv=self.f(self.segment_tree[R],v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.le

    def __str__(self):
        return "["+", ".join(map(str,[self.segment_tree[i] for i in range(self.le,self.le+self.N)]))+"]"

    def __repr__(self):
        return "Segment_Tree("+str(self)+")"

class Segment_Tree_2d:
    def __init__(self,N,M,f,e,lst=None,dynamic=False):
        self.N=N
        self.M=M
        self.f=f
        self.e=e
        if dynamic:
            self.segment_tree=defaultdict(lambda:defaultdict(lambda:e))
        else:
            if lst==None:
                self.segment_tree=[[self.e]*2*self.M for i in range(2*self.N)]
            else:
                assert len(lst)<=self.N
                assert all(len(lst[i])<=self.M for i in range(self.N))
                self.segment_tree=[[self.e]*2*self.M for i in range(self.N)]+[[self.e]*self.M+lst[i]+[self.e]*(self.M-len(lst[i])) for i in range(len(lst))]+[[self.e]*2*self.M for i in range(self.N-len(lst))]
                for i in range(self.N-1,0,-1):
                    for j in range(2*self.M-1,self.M-1,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
                for i in range(2*self.N-1,-1,-1):
                    for j in range(self.M-1,0,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def __getitem__(self,tpl):
        i,j=tpl
        i+=self.N
        j+=self.M
        return self.segment_tree[i][j]

    def __setitem__(self,tpl,x):
        i,j=tpl
        i+=self.N
        j+=self.M
        self.segment_tree[i][j]=x
        idxN=[i]
        idxM=[j]
        while i>1:
            i>>=1
            idxN.append(i)
        while j>1:
            j>>=1
            idxM.append(j)
        i=idxN[0]
        for j in idxM[1:]:
            self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
        for i in idxN[1:]:
            for j in idxM:
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])

    def Build(self,lst):
        assert len(lst)<=self.N
        assert all(len(lst[i] for i in range(self.N))<=self.M)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                self.segment_tree[i+self.N][j+self.M]=lst[i][j]
        for i in range(self.N-1,0,-1):
            for j in range(2*self.M-1,self.M-1,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
        for i in range(2*self.N-1,-1,-1):
            for j in range(self.M-1,0,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def Fold(self,LN=None,RN=None,LM=None,RM=None):
        LN+=self.N
        RN+=self.N
        LM+=self.M
        RM+=self.M
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        retu=self.e
        for i in idxN:
            for j in idxM:
                retu=self.f(retu,self.segment_tree[i][j])
        return retu

    def Fold_Index(self,LN=None,RN=None,LM=None,RM=None):
        if LN==None:
            LN=self.N
        else:
            LN+=self.N
        if RN==None:
            RN=self.N*2
        else:
            RN+=self.N
        if LM==None:
            LM=self.M
        else:
            LM+=self.M
        if RM==None:
            RM=self.M*2
        else:
            RM+=self.M
        if LN==RN and LM==RM:
            return None
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        v=self.e
        for i in idxN:
            for j in idxM:
                v=self.f(v,self.segment_tree[i][j])
        for i in idxN:
            for j in idxM:
                if v==self.f(v,self.segment_tree[i][j]):
                    break
            else:
                continue
            break
        while i<self.N:
            if self.segment_tree[i<<1][j]==v:
                i<<=1
            else:
                i<<=1
                i|=1
        while j<self.M:
            if self.segment_tree[i][j<<1]==v:
                j<<=1
            else:
                j<<=1
                j|=1
        return i,j

    def __str__(self):
        m=max(len(str(self.segment_tree[i][j])) for i in range(self.N,self.N*2) for j in range(self.M,self.M*2))
        return "\n".join(["["+", ".join(map(lambda s:" "*(m-len(str(s)))+str(s),self.segment_tree[i][self.M:]))+"]" for i in range(self.N,self.N*2)])

    def __repr__(self):
        return "Segment_Tree_2d(\n"+str(self)+")"

class Dual_Segment_Tree:
    def __init__(self,N,f_act,e_act,operate,lst):
        self.N=N
        self.f_act=f_act
        self.e_act=e_act
        self.operate=operate
        self.lst=[None]*self.N
        for i,x in enumerate(lst):
            self.lst[i]=x
        self.segment_tree_act=[self.e_act]*(self.N+self.N)

    def __getitem__(self,i):
        if type(i) is int:
            if -self.N<=i<0:
                i+=self.N*2
            elif 0<=i<self.N:
                i+=self.N
            else:
                raise IndexError("list index out of range")
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.N:
                a=0
            elif self.N<=a:
                a=self.N
            elif a<0:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N
            elif b<-self.N:
                b=0
            elif b<0:
                b+=self.N
            return self.lst[slice(a,b,c)]

    def Operate_At(self,i):
        return self.operate(self.lst[i-self.N],self.segment_tree_act[i])

    def Propagate_At(self,i):
        self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
        self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
        self.segment_tree_act[i]=self.e_act

    def Propagate_Above(self,i):
        H=i.bit_length()-1
        for h in range(H,0,-1):
            self.Propagate_At(i>>h)

    def Operate_Range(self,a,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        L0=L//(L&-L)
        R0=R//(R&-R)-1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L<R:
            if L&1:
                self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
                L+=1
            if R&1:
                R-=1
                self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
            L>>=1
            R>>=1

    def Update(self):
        for i in range(1,self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i]=self.e_act

    def __str__(self):
        import copy
        segment_tree_act=copy.deepcopy(self.segment_tree_act)
        for i in range(1,self.N):
            segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
            segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
            segment_tree_act[i]=self.e_act
        return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]"

    def __repr__(self):
        return "Dual_Segment_Tree("+str(self)+")"

class Lazy_Segment_Tree:
    def __init__(self,N,f,e,f_act,e_act,operate,lst=None,bisect_search=True):
        self.N=N
        self.f=f
        self.e=e
        self.f_act=f_act
        self.e_act=e_act
        self.operate=operate
        self.bisect_search=bisect_search
        if self.bisect_search:
            self.le=1
            while self.le<self.N:
                self.le*=2
        else:
            self.le=self.N
        self.segment_tree=[self.e]*(self.le+self.le)
        self.segment_tree_act=[self.e_act]*(self.le+self.le)
        if lst!=None:
            for i,x in enumerate(lst):
                self.segment_tree[i+self.le]=x
            for i in range(self.le-1,0,-1):
                self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
            self.segment_tree_act=[self.e_act]*(self.le+self.le)

    def __getitem__(self,i):
        if type(i) is int:
            if -self.le<=i<0:
                i+=self.le*2
            elif 0<=i<self.le:
                i+=self.le
            else:
                raise IndexError("list index out of range")
            self.Propagate_Above(i)
            self.Recalculate_Above(i)
            return self.Operate_At(i)
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.le:
                a=self.le
            elif self.le<=a:
                a=self.le*2
            elif a<0:
                a+=self.le*2
            else:
                a+=self.le
            if b==None or self.le<=b:
                b=self.le*2
            elif b<-self.le:
                b=self.le
            elif b<0:
                b+=self.le*2
            else:
                b+=self.le
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.le<=i<0:
            i+=self.le*2
        elif 0<=i<self.le:
            i+=self.le
        else:
            raise IndexError("list index out of range")
        self.Propagate_Above(i)
        self.segment_tree[i]=x
        self.segment_tree_act[i]=self.e_act
        self.Recalculate_Above(i)

    def Operate_At(self,i):
        return self.operate(self.segment_tree[i],self.segment_tree_act[i])

    def Propagate_At(self,i):
        self.segment_tree[i]=self.Operate_At(i)
        self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
        self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
        self.segment_tree_act[i]=self.e_act

    def Propagate_Above(self,i):
        H=i.bit_length()-1
        for h in range(H,0,-1):
            self.Propagate_At(i>>h)

    def Recalculate_Above(self,i):
        while i>1:
            i>>=1
            self.segment_tree[i]=self.f(self.Operate_At(i<<1),self.Operate_At(i<<1|1))

    def Build(self,lst):
        for i,x in enumerate(lst):
            self.segment_tree[i+self.le]=x
        for i in range(self.le-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
        self.segment_tree_act=[self.e_act]*(self.le+self.le)

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.le
        else:
            assert 0<=L<=self.le
            L+=self.le
        if R==None:
            R=self.le*2
        else:
            assert 0<=R<=self.le
            R+=self.le
        self.Propagate_Above(L//(L&-L))
        self.Propagate_Above(R//(R&-R)-1)
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.Operate_At(L))
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.Operate_At(R),vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.le
        else:
            assert 0<=L<=self.le
            L+=self.le
        if R==None:
            R=self.le*2
        else:
            assert 0<=R<=self.le
            R+=self.le
        if L==R:
            return None
        x=self.Fold(L-self.le,R-self.le)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.le:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.le
        return i

    def Operate_Range(self,a,L=None,R=None):
        if L==None:
            L=self.le
        else:
            assert 0<=L<=self.le
            L+=self.le
        if R==None:
            R=self.le*2
        else:
            assert 0<=R<=self.le
            R+=self.le
        L0=L//(L&-L)
        R0=R//(R&-R)-1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L<R:
            if L&1:
                self.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
                L+=1
            if R&1:
                R-=1
                self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
            L>>=1
            R>>=1
        self.Recalculate_Above(L0)
        self.Recalculate_Above(R0)

    def Update(self):
        for i in range(1,self.le):
            self.Propagate_At(i)
        for i in range(self.le,self.le*2):
            self.segment_tree[i]=self.Operate_At(i)
            self.segment_tree_act[i]=self.e_act
        for i in range(self.le-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Bisect_Right(self,L=None,f=None):
        assert self.bisect_search
        if L==self.le:
            return self.le
        if L==None:
            L=0
        assert 0<=L<=self.le
        L+=self.le
        self.Propagate_Above(L//(L&-L))
        self.Propagate_Above(self.le//(self.le&-self.le)-1)
        l,r=L,self.le*2
        vl=self.e
        vr=self.e
        while l<r:
            if l&1:
                vl=self.f(vl,self.Operate_At(l))
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.Operate_At(r),vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        self.Propagate_Above(L)
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.Operate_At(L))
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.le:
                    self.Propagate_At(L)
                    L<<=1
                    vv=self.f(v,self.Operate_At(L))
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.le

    def Bisect_Left(self,R=None,f=None):
        if R==0:
            return 0
        if R==None:
            R=self.le
        assert 0<=R<=self.le
        R+=self.le
        self.Propagate_Above(self.le//(self.le&-self.le))
        self.Propagate_Above(R//(R&-R)-1)
        vl=self.e
        vr=self.e
        l,r=self.le,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.Operate_At(l))
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.Operate_At(r),vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        self.Propagate_Above(R-1)
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.Operate_At(R),v)
            if f(vv):
                v=vv
            else:
                while R<self.le:
                    self.Propagate_At(R)
                    R=(R<<1)|1
                    vv=self.f(self.Operate_At(R),v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.le

    def __str__(self):
        import copy
        segment_tree=copy.deepcopy(self.segment_tree)
        segment_tree_act=copy.deepcopy(self.segment_tree_act)
        for i in range(1,self.le):
            segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
            segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
            segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
        for i in range(self.le,self.le*2):
            segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
        for i in range(self.le-1,0,-1):
            segment_tree[i]=self.f(segment_tree[i<<1],segment_tree[i<<1|1])
        return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(segment_tree[self.le:self.le+self.N],segment_tree_act[self.le:])]))+"]"

    def __repr__(self):
        return "Lazy_Segment_Tree("+str(self)+")"

class Li_Chao_Tree:
    def __init__(self,N,X=None,inf=float("inf")):
        self.N=N
        if X==None:
            self.X=[x for x in range(self.N)]
        else:
            self.X=X
        self.idx={x:i for i,x in enumerate(self.X)}
        self.inf=inf
        self.li_chao_tree=[(0,self.inf)]*(2*self.N)
        self.left,self.right=[None]*2*N,[None]*2*N
        for i in range(self.N,2*self.N):
            self.left[i]=self.X[i-self.N]
            self.right[i]=self.X[i-self.N]
        for i in range(self.N-1,0,-1):
            self.left[i]=self.left[i<<1]
            self.right[i]=self.right[i<<1|1]

    def add_line_one_segment(self,a,b,i):
        queue=[i]
        while queue:
            i=queue.pop()
            aa,bb=self.li_chao_tree[i]
            l=a*self.X[self.left[i]]+b
            r=a*self.X[self.right[i]]+b
            ll=aa*self.X[self.left[i]]+bb
            rr=aa*self.X[self.right[i]]+bb
            if ll<=l and rr<=r:
                continue
            if l<=ll and r<=rr:
                self.li_chao_tree[i]=(a,b)
                continue
            queue.append(i<<1)
            queue.append(i<<1|1)

    def add_line(self,a,b,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=2*self.N
        else:
            R+=self.N
        while L<R:
            if L%2:
                self.add_line_one_segment(a,b,L)
                L+=1
            if R%2:
                R-=1
                self.add_line_one_segment(a,b,R)
            L>>=1
            R>>=1

    def __call__(self,x):
        i=self.idx[x]+self.N
        retu=self.inf
        while i:
            a,b=self.li_chao_tree[i]
            retu=min(retu,a*x+b)
            i>>=1
        return retu

    def __getitem__(self,i):
        x=self.X[i]
        i+=self.N
        retu=self.inf
        while i:
            a,b=self.li_chao_tree[i]
            retu=min(retu,a*x+b)
            i>>=1
        return retu

    def __str__(self):
        li_chao_tree=[(0,self.inf)]*self.N
        for i,x in enumerate(self.X):
            ii=i+self.N
            while ii:
                aa,bb=self.li_chao_tree[ii]
                a,b=li_chao_tree[i]
                if aa*x+bb<a*x+b:
                    li_chao_tree[i]=aa,bb
                ii>>=1
        return "["+", ".join(map(str,li_chao_tree))+"]"

    def __repr__(self):
        return "Li_Chao_Tree("+str(self)+")"

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
M=int(input())
Z,W=[],[]
for i in range(M):
    z,w=map(int,input().split())
    Z.append(z)
    W.append(w)
inf=1<<30
ans=inf
for t in range(4):
    if t%2==0:
        ma=max(X+Z)
        X=[ma-x for x in X]
        Z=[ma-z for z in Z]
    N,M=M,N
    X,Y,Z,W=Z,W,X,Y
    leX=max(X+Z)+1
    leY=max(Y+W)+1
    ST=Segment_Tree(leY,max,-inf)
    query0=[[] for x in range(leX)]
    query1=[[] for x in range(leX)]
    for i in range(N):
        query0[X[i]].append(Y[i])
    for i in range(M):
        query1[Z[i]].append(W[i])
    for x in range(leX):
        for y in query0[x]:
            ST[y]=max(ST[y],x+y)
        for y in query1[x]:
            ans=min(ans,x+y-ST.Fold(0,y+1))
print(ans)