class intOrderedListNode:
    def __init__(self):
        self.zero_next=None
        self.zero_size=0
        self.one_next=None
        self.one_size=0
class intOrderedList(intOrderedListNode):
    def __init__(self):
        self.node=intOrderedListNode()
        self.max_depth=1
        self.size=0
    def insert(self, value: int) -> None:
        while self.max_depth<value:
            temp=self.node
            self.node=intOrderedListNode()
            self.node.zero_next=temp
            self.node.zero_size=temp.zero_size+temp.one_size
            self.max_depth<<=1
        temp=self.max_depth
        itr=self.node
        while temp>0:
            if value&temp:
                itr.one_size+=1
                if itr.one_next is None:
                    itr.one_next=intOrderedListNode()
                itr=itr.one_next
            else:
                itr.zero_size+=1
                if itr.zero_next is None:
                    itr.zero_next=intOrderedListNode()
                itr=itr.zero_next
            temp>>=1
        self.size+=1
    def __iter__(self):
        self.idx=0
        return self
    def __next__(self):
        if self.idx>=self.size:
            raise StopIteration
        result=self.index(self.idx)
        self.idx+=1
        return result
    def index(self, idx: int) -> int:
        if idx<0 or idx>=self.size:
            raise IndexError
        result=0
        temp=self.max_depth
        itr=self.node
        while temp>0:
            if itr.zero_size>idx:
                itr=itr.zero_next
            else:
                result|=temp
                idx-=itr.zero_size
                itr=itr.one_next
            temp>>=1
        return result
    def __len__(self):
        return self.size
    def __contains__(self, value: int) -> bool:
        temp=self.max_depth
        itr=self.node
        while temp>0:
            if value&temp:
                if itr.one_size==0:
                    return False
                itr=itr.one_next
            else:
                if itr.zero_size==0:
                    return False
                itr=itr.zero_next
            temp>>=1
        return True
    def lower_bound(self, value: int) -> int:
        temp=self.max_depth
        itr=self.node
        result=0
        last=None
        last_temp=temp
        chk=1
        while temp>0:
            if value&temp:
                if chk:
                    result+=itr.zero_size
                if itr.one_next :
                    itr=itr.one_next
                else:
                    if last:
                        itr=last
                        itr=itr.zero_next
                        temp=last_temp
                        chk=0
                        value=0
                    else:
                        return self.size
                    
            else:
                if itr.zero_next:
                    if itr.one_next:
                        last=itr
                        last_temp=temp
                    itr=itr.zero_next
                else:
                    itr=itr.one_next
                    chk=0
                    value=0
            temp>>=1
        return result
    def upper_bound(self, value: int) -> int:   
        temp=self.max_depth
        itr=self.node
        result=0
        last=None
        last_temp=temp
        chk=1
        while temp>0:
            if value&temp:
                result+=itr.zero_size
                if itr.one_next :
                    if temp==1 and chk:
                        result+=itr.one_size
                    itr=itr.one_next
                else:
                    if last:
                        itr=last
                        itr=itr.zero_next
                        temp=last_temp
                        value=0
                    else:
                        return self.size
                    
            else:
                if itr.zero_next:
                    if itr.one_next:
                        last=itr
                        last_temp=temp
                    if temp==1 and chk:
                        result+=itr.zero_size
                    itr=itr.zero_next
                else:
                    itr=itr.one_next
                    chk=0
                    value=0
            temp>>=1
        return result
    def pop(self, idx: int) -> int:
        if idx<0 or idx>=self.size:
            raise IndexError
        temp=self.max_depth
        itr=self.node
        result=0
        while temp>0:
            if itr.zero_size>idx:
                itr.zero_size-=1
                if itr.zero_size==0:
                    itr.zero_next=None
                itr=itr.zero_next
            else:
                result|=temp
                itr.one_size-=1
                if itr.one_size==0:
                    itr.one_next=None
                idx-=itr.zero_size
                itr=itr.one_next
            temp>>=1
        self.size-=1
        while self.node.one_size==0:
            self.node=self.node.zero_next
            self.max_depth>>=1
        return result