class Solution:

    def __init__(self, w: List[int]):
        self.w = w
        self.prefix_sum = 0
        self.prefix = []
        for num in self.w:
            self.prefix_sum += num
            self.prefix.append(self.prefix_sum)

    def pickIndex(self) -> int:

        target = self.prefix_sum * random.random()
        low = 0; high = len(self.w) - 1

        while (low <= high):
            mid = (low + high)//2
            if target < self.prefix[mid]:
                high = mid - 1
                result = mid
            else:
                low = mid + 1

        return result