# problem 4
class Wavelet_Tree:
    def __init__(self , A, depth =0):
        self.A = A
        self.B = []
        self.left = None
        self.right = None
        self.depth = depth
        self.p = 0
        self.construct()
#         print(self.A, self.B)

    def construct(self):
        if len(self.A)<=1:
            return None

        small = self.A[0]
        large = self.A[0]
        for i in self.A:
            if i < small:
                small = i
            if i > large:
                large = i

        p = (large-small)//2
        p += small
        self.p = p

        left = []
        right = []
        self.B = [0 for i in self.A]
        for i in range(len(self.A)):
            if self.A[i]<=p:
                left.append(self.A[i])
                if i-1>=0:
                    self.B[i] = self.B[i-1]+1
                else:
                    self.B[0] = 1
            else:
                right.append(self.A[i])
                self.B[i] = self.B[i-1]
        self.left = Wavelet_Tree(left, self.depth+1)
        self.right = Wavelet_Tree(right, self.depth+1)


    def print(self):
        q = []
        q.append(self)
        count = 0
        while q:
            print("Level "+str(count)+":", end = " ")
            size = len(q)
            for _ in range(size):
                x = q.pop(0)
                r = ''
                for i in x.A:
                    if i<=x.p:
                        r+='0'
                    else:
                        r+='1'
                if len(r)==1:
                    print("x", end = " ")
                else:
                    print(r, end = " ")
                if x.left:
                    q.append(x.left)

                if x.right:
                    q.append(x.right)

            print()
            count+=1

    def RQQ(self, k:int , left:int , right:int):
        print("Level "+ str(self.depth)+":",k, left, right)
        if left == right:
            return self.A[0]

        x1 = self.B[right-1]
        x2 = 0
        if left-2>=0:
            x2 = self.B[left-2]
        left_c = x1-x2
#         print(k, left, right, self.A, self.B,x1,x2, left_c)
        if k <= left_c:
            return self.left.RQQ(k, x2+1, x1)

        return self.right.RQQ(k-left_c, left-x2, right-x1)


wv_tree = Wavelet_Tree([6, 2, 0, 7, 9, 3, 1, 8, 5, 4])
wv_tree.print()
print()
print()
wv_tree.RQQ(5, 3, 9)