Implement the class ProductOfNumbers that supports two methods:
1. add(int num)

Adds the number num to the back of the current list of numbers.

2. getProduct(int k)

Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
 
Example:
Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output
[null,null,null,null,null,null,20,40,0,null,32]

Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32 

 
Constraints:

There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Difficulty: interview

Starter code:

class ProductOfNumbers:
    def __init__(self):
    def add(self, num: int) -> None:
    def getProduct(self, k: int) -> int:
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

Solutions:
import math
class ProductOfNumbers:

    def __init__(self):
        self.numbers = [1]
        self.lastZero = 0

    def add(self, num: int) -> None:
        if num != 0:
            self.numbers.append(self.numbers[-1] * num)
        else:
            self.numbers = [1]
            

    def getProduct(self, k: int) -> int:
        if k < len(self.numbers):
            return self.numbers[-1] // self.numbers[-k - 1]
        else:
            return 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.preprod = [1]

    def add(self, num: int) -> None:
        if not num:
            self.preprod = [1]
        else:
            self.preprod.append(self.preprod[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.preprod):
            return 0
        return self.preprod[-1] // self.preprod[-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

# 20

#[2, 10, 40]

# 

# 
# 3 0  2 , 5 ,4

# 3, 0, 2 ,5 ,4, 0



# []



# [1]
# return 0
# 0  0  40  20  4 0 1


class ProductOfNumbers:
    
    prod_list = []
    
    def __init__(self):
        pass

    def add(self, num: int) -> None:
        if num == 0:
            self.prod_list = []
        else:
            if len(self.prod_list) == 0:
                self.prod_list.append(num)
            else:
                new_prod = self.prod_list[-1]*num
                self.prod_list.append(new_prod)

    def getProduct(self, k: int) -> int:
        if len(self.prod_list) == 0:
            return 0
        
        if k > len(self.prod_list):
            return 0
        elif k == len(self.prod_list):
            return self.prod_list[-1]
        else:
            if self.prod_list[-k] == 0:
                return 0
            else:
                return self.prod_list[-1]//self.prod_list[-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import numpy as np


class ProductOfNumbers:
    def __init__(self):
        self.current_list_of_numbers: list = []
        self.prefix = []

    def add(self, num: int) -> None:
        if len(self.current_list_of_numbers) == 0:
            self.prefix = [num]
            self.current_list_of_numbers.append(num)
        else:

            self.prefix = np.array(self.prefix) * num
            self.prefix = np.append(self.prefix, [int(num)], 0)
            self.current_list_of_numbers.append(num)

    def getProduct(self, k: int) -> int:
        return self.prefix[len(self.prefix) - k]

class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.zeros =[]
        self.product = 1
        self.allProducts = {} #index -> product at that index

    def add(self, num: int) -> None:
        if num == 0:
            self.zeros.append(len(self.nums))
        else:
            self.product *= num
    
        self.nums.append(num)
        self.allProducts[len(self.nums) - 1] = self.product

    def getProduct(self, k: int) -> int:
        for i in self.zeros:
            if len(self.nums) - k <= i <= len(self.nums) - 1:
                return 0
        if k == len(self.nums):
            return self.product
        return int(self.product / self.allProducts[len(self.nums) - 1 - k])
    

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import numpy as np

class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.prods = np.array([])
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        self.prods = (self.prods * num).astype(int)
        self.prods = np.append(self.prods, num)

    def getProduct(self, k: int) -> int:
        return self.prods[-k]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prefixproducts = [1]

    def add(self, num: int) -> None:
        if num==0:
            for i in range(len(self.prefixproducts)):
                self.prefixproducts[i] = 0
            self.prefixproducts.append(0)
        else:
            if self.prefixproducts[-1]!=0:
                self.prefixproducts.append(self.prefixproducts[-1]*num)
            else:
                self.prefixproducts.append(num)

    def getProduct(self, k: int) -> int:
        if self.prefixproducts[-(k+1)] == 0:
            if self.prefixproducts[-k] == 0:
                return 0
            else:
                return self.prefixproducts[-1]
        else:
            return self.prefixproducts[-1]//self.prefixproducts[-(k+1)]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = [1]
        self.run = 1
        

    def add(self, num: int) -> None:
        if num != 0:
            self.run *= num
        else:
            n = len(self.arr)
            for i in range(n):
                self.arr[i] = 0
        self.arr.append(self.run)
        

    def getProduct(self, k: int) -> int:
        # print('for k ', k)
        # print('arr is ', self.arr)
        pre = 1
        n = len(self.arr)
        before = n - k - 1
        if before >= 0:
            pre = self.arr[before]
        
        if pre == 0:
            return 0
        return int(self.arr[-1] / pre)
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.a = []

    def add(self, num: int) -> None:
        x = [0]*101
        x[num] += 1
        if len(self.a) > 0:
            for i in range(101):
                x[i] += self.a[-1][i] 
        
        self.a.append(x)

    def getProduct(self, k: int) -> int:
        res = 1
        
        for i in range(101):
            cnt = self.a[-1][i] 
            if len(self.a) > k:
                cnt -= self.a[-(k+1)][i] 
            res *= pow(i,cnt)
        return res


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import bisect 
class ProductOfNumbers:

    def __init__(self):
        self.time = 0
        self.d = collections.defaultdict(list)

    def add(self, num: int) -> None:
        self.time += 1
        self.d[num].append((self.time, len(self.d[num])))

    def getProduct(self, k: int) -> int:
        res = 1
        for num in range(101):
            i = bisect.bisect_right(self.d[num], (self.time-k+1,-1), )
            res *= num**(len(self.d[num]) - i)
        return res

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from functools import lru_cache, reduce
from operator import mul
class ProductOfNumbers:

    def __init__(self):
        self.arr = []
        self.size = 0

    def add(self, num: int) -> None:
        self.arr.append(num)
        self.size += 1
        self.getProduct.cache_clear()
    
    @lru_cache
    def getProduct(self, k: int) -> int:
        return reduce(mul,self.arr[self.size-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.array = [0] 
        self.prods = [0]
        self.state = True # border 
        self.recent_zero = 0

    def add(self, num: int) -> None: 
        self.array.append(num)
        
        if self.state == True:
            self.prods.append(num)
            if num != 0:
                self.state = False
            else:
                self.recent_zero = len(self.array)-1 
            
        else:
            if num == 0:
                self.state = True
                self.prods.append(num)
                self.recent_zero = len(self.array)-1
            else:
                self.prods.append(num*self.prods[-1])

    def getProduct(self, k: int) -> int:
        n = len(self.prods)
        if n-(k+1) < self.recent_zero:
            return 0
        else:
            if self.prods[n-(k+1)] ==0:
                return self.prods[-1]
            return self.prods[-1]//self.prods[n-(k+1)]

    
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = [1]

    def add(self, num: int) -> None:
        self.arr = [1] if num == 0 else self.arr + [num * self.arr[-1]]

    def getProduct(self, k: int) -> int:
        return 0 if len(self.arr) <= k else int(self.arr[-1] / self.arr[-k - 1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.n = 0
        self.d = {}

    def add(self, num: int) -> None:
        n = self.n
        self.d[(n, n)] = num
        self.n+=1

    def getProduct(self, k: int) -> int:
        return self.h(self.n-k, self.n-1)
        
    def h(self, i, j):
        d = self.d
        h = self.h
        if (i,j) in d:
            return d[(i,j)]
        m = (i+j)//2
        x = h(i,m)*h(m+1,j)
        d[(i,j)] = x
        return x

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.data = []
        self.product_cache = {}

    def add(self, num: int) -> None:
        self.data.append(num)

    def getProduct(self, k: int) -> int:
        product = self.product_cache.get((len(self.data) - k, len(self.data) - 1))
        if product is not None:
            return product
        product = 1
        for i in self.data[-k:]:
            product = product * i
        self.product_cache[(len(self.data) - k, len(self.data) - 1)] = product
        return product


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.cache = {}
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        self.cache = {}
        

    def getProduct(self, k: int) -> int:
        if k in self.cache:
            return self.cache[k]
        n = self.nums[-k:]
        ret = 1
        for e in n:
            ret *= e
        self.cache[k] = ret
        return ret
        
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)



class ProductOfNumbers:

    def __init__(self):
        self.l = []
        self.cache = {}

    def add(self, num: int) -> None:
        self.l.append(num)
        self.cache = {}

    def getProduct(self, k: int) -> int:
        if k in self.cache:
            return self.cache[k]
        
        elif k - 1 in self.cache:
            return self.cache[k - 1] * self.l[-k]
        
        else:

            prod = 1
            for num in self.l[-k:]:
                prod *= num
            
            self.cache[k] = prod
            
        return prod
        
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.listOfProds = []
        self.results = {}
        
    def add(self, num: int) -> None:
        self.listOfProds.append(num)
        self.results = {}
        return None

    def getProduct(self, k: int) -> int:
        if k in self.results:
            return self.results[k]
        outProd = 1
        for i in self.listOfProds[-1*k:]:
            outProd = outProd * i
        self.results[k] = outProd
        return outProd


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.data = []
        self.product = []

    def add(self, num: int) -> None:
        self.data.append(num)
        if len(self.data) % 10 == 0:
            self.product.append(self.getLastTenProduct())
    
    def getLastTenProduct(self) -> int:
        res = 1
        for i in range(len(self.data) - 1, len(self.data) - 11, -1):
            res *= self.data[i]
        return res

    def getProduct(self, k: int) -> int:
        remain = k % 10
        tenth = k // 10
        res = 1
        for i in range(len(self.product) - 1, len(self.product) - tenth - 1, -1):
            res *= self.product[i]

        for i in range(
            len(self.data) - tenth * 10 - 1,
            len(self.data) - tenth * 10 - remain - 1,
            -1
        ):
            res *= self.data[i]
        return res


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.product = [1]
        self.list = []
        self.zero = False
    def add(self, num: int):
        self.list.append(num)
        if not num:
            self.zero = True
            self.product.append(0)
        else:
            if self.zero:  
                self.product.append(num)
                self.zero = False
            else:
                self.product.append(num * self.product[-1])
            
    def getProduct(self, k: int) -> int:
        # print(\"product\", self.product)
        # print(\"list\", self.list)
        # print(\"k =\", k)
        if not all(self.product[-k:-1]):
            return 0
        else:
            if not self.product[-k-1]:
                return int(self.product[-1])
            else:
                return int(self.product[-1] / self.product[-k-1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.data = []

    def add(self, num: int) -> None:
        if num == 0:
            self.data = []
        self.data.append(num)

    def getProduct(self, k: int) -> int:
        count = 0
        if k > len(self.data):
            return 0
        res = self.data[-k:]
        return math.prod(res)
            
            
            
            
            


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.list = []
        self.mul_list = []
        self.n = -1
        
    def add(self, num: int) -> None:
        self.list.append(num)
        self.n += 1 # len(s) - 1
        if self.mul_list:
            self.mul_list.append(self.mul_list[-1] * num)
        else:
            self.mul_list.append(num)
        
        if num == 0:
            self.mul_list = []
           
    def getProduct(self, k: int) -> int:
        if len(self.mul_list) == k:
            return self.mul_list[-1]
        elif len(self.mul_list) >= k+1:
            return (self.mul_list[-1] // self.mul_list[-(k+1)])
        else :
            return 0
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from functools import reduce
from math import prod
class ProductOfNumbers:

    def __init__(self):
        self.nums=list()

    def add(self, num: int) -> None:
        self.nums.append(num)
        return
        if not self.nums:
            self.nums.append(num)
            return
        last_number = self.nums[-1]*num
        self.nums.append(last_number)
        
    def getProduct(self, k: int) -> int:
        last_k_nums = self.nums[-1*k:]
        return prod(last_k_nums)
        #return reduce((lambda x, y: x* y), last_k_nums)
        #return self.nums[k`]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:
    def __init__(self):
        self.arr = []

    def add(self, num: int) -> None:
        self.arr.append(num)

    def getProduct(self, k: int) -> int:
        
        return math.prod(self.arr[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.list = []

    def add(self, num: int) -> None:
        self.list.append(num)
        
        

    def getProduct(self, k: int) -> int:
        return math.prod(self.list[len(self.list) - k:])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:
    

    def __init__(self):
        self.nums=[]
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        

    def getProduct(self, k: int) -> int:
        stop=len(self.nums)-k
        return(math.prod(self.nums[stop:]))
       
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)



class ProductOfNumbers:
    

    def __init__(self):
        self.nums=[]
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        

    def getProduct(self, k: int) -> int:
        stop=len(self.nums)-k
        return(math.prod(self.nums[stop:]))
        #return (reduce((lambda x,y : x*y),self.nums[stop:]))
       
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)



import math
class ProductOfNumbers:

    def __init__(self):
        self.arr = []

    def add(self, num: int) -> None:
        self.arr.append(num)

    def getProduct(self, k: int) -> int:
        return math.prod(self.arr[len(self.arr)-k:])
        
       


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.mylist=[]
        

    def add(self, num: int) -> None:
        self.mylist.append(num)
        # print(self.mylist)

    def getProduct(self, k: int) -> int:
        this_list=self.mylist[-k:]
        # print(k,this_list,math.prod(this_list) )
        return math.prod(this_list) 


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = []

    def add(self, num: int) -> None:
        self.arr.append(num)

    def getProduct(self, k: int) -> int:
        # prod = 1
        # for num in self.arr[-k:]:
        #     if num == 0:
        #         return 0
        #     prod *= num
        # return prod
        return prod(self.arr[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)



import math
class ProductOfNumbers:

    def __init__(self):
        self.a = []

    def add(self, num: int) -> None:
        self.a.append(num)
        

    def getProduct(self, k: int) -> int:
        return math.prod(self.a[-k:])
        
            


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.nums = []  

    def add(self, num: int) -> None:
        self.nums.append(num)

    def getProduct(self, k: int) -> int:
        # prod = 1
        # for num in self.nums[-k:]:
        #     prod *= num
        # return prod
        return math.prod(self.nums[-k:])

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.product = []
        self.n = 0

    def add(self, num: int) -> None:
        if num == 0:
            i = self.n-1
            self.product.append(0)
            while(i >= 0 and self.product[i] != 0):
                self.product[i] = 0
                i -= 1
        else:
            if self.n == 0 or self.product[-1] == 0:
                self.product.append(num)
            else:
                self.product.append(num*self.product[-1])
        self.n += 1
        # print(self.product)

    def getProduct(self, k: int) -> int:
        if k == self.n:
            if self.product[0] == 0: return 0
            else: return self.product[-1]

        if self.product[self.n-k] == 0:
            return 0
        elif self.product[self.n-k-1] == 0:
            return self.product[-1]
        else:
            return self.product[-1]//self.product[self.n-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.usable_array = []

    def add(self, num: int) -> None:
        self.usable_array.append(num)

    def getProduct(self, k: int) -> int:
        if type(k) != int:
            self.usable_array = ProductOfNumbers()
        #product = 1
        product = math.prod(self.usable_array[-k:])
        return product


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:
    from numpy import prod
    def __init__(self):
        self.numbers= []
        
    def add(self, num: int) -> None:
        self.numbers.append(num)

    def getProduct(self, k: int) -> int:
        return prod(self.numbers[len(self.numbers)- k : len(self.numbers)])
        # for i in self.numbers[]:
        #     prod =prod*i
        # return prod

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.numList=[]

    def add(self, num: int) -> None:
        self.numList.append(num)

    def getProduct(self, k: int) -> int:
        prodList=self.numList[(-1*k):]
        
        #prod=1
        #length=len(self.numList)
        #for i in range(length-k, length):
        #    prod = prod * self.numList[i]
            
        return math.prod(prodList)


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math

class ProductOfNumbers:

    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        self.nums.append(num)

    def getProduct(self, k: int) -> int:
        return math.prod(self.nums[len(self.nums) - k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        self.nums.append(num)

    def getProduct(self, k: int) -> int:
        return prod(self.nums[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math

class ProductOfNumbers:

    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        self.nums.append(num)
        

    def getProduct(self, k: int) -> int:
        return prod(self.nums[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.numbers = []

    def add(self, num: int) -> None:
        self.numbers.append(num)

    def getProduct(self, k: int) -> int:
        return math.prod(self.numbers[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.store=[]

    def add(self, num: int) -> None:
        self.store.append(num)

    def getProduct(self, k: int) -> int:
        return prod(self.store[-k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:    
    def __init__(self):
        self.lisst = []

    def add(self, num: int) -> None:
        self.lisst += [num]

    def getProduct(self, k: int) -> int:
        return prod(self.lisst[len(self.lisst) - k:])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.product_list = []

    def add(self, num: int) -> None:
        self.product_list.append(num)

    def getProduct(self, k: int) -> int:
        return prod(self.product_list[-k:])
            


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = [1]
        self.prod = [1]
        self.pz_list = [-1]
        self.prev_zero = -1

    def add(self, num: int) -> None:
        self.nums.append(num)
        if num > 0:
            self.pz_list.append(self.prev_zero)
            if self.prod[-1] != 0:
                self.prod.append(self.prod[-1] * num)
            else:
                self.prod.append(num)
        else:
            self.prev_zero = len(self.nums) - 1
            self.pz_list.append(self.prev_zero)
            self.prod.append(1)
            
    def getProduct(self, k: int) -> int:
        if len(self.nums) - 1 - self.pz_list[-1] < k:
            return 0
        else:
            return self.prod[-1] // self.prod[-1 * k -1] 
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.l = []

    def add(self, num: int) -> None:
        self.l.append(num)
        

    def getProduct(self, k: int) -> int:
        return math.prod(self.l[len(self.l)-k:len(self.l)])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = [1]
        self.latest_zero_position = None

    def add(self, num: int) -> None:
        if num == 0:
            self.latest_zero_position = len(self.products)
            num = 1
        self.products.append(self.products[-1] * num)
        
    def getProduct(self, k: int) -> int:
        if self.latest_zero_position != None:
            if self.latest_zero_position >= len(self.products) - k:
                return 0
        
        return self.products[-1] // self.products[-k - 1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.len = 0

    def add(self, num: int) -> None:
        if num == 0:
            self.nums = []
            self.len = 0
        elif num == 1:
            self.len += 1
            if len(self.nums) and isinstance(self.nums[-1], list):
                self.nums[-1][0] += 1
            else:
                self.nums.append([1])
        else:
            self.len += 1
            self.nums.append(num)

    def getProduct(self, k: int) -> int:
        if k > self.len:
            return 0
        prod, idx = 1, len(self.nums)-1
        while k > 0:
            #print(k, idx)
            if isinstance(self.nums[idx], list):
                k -= self.nums[idx][0]
            else:
                prod *= self.nums[idx]
                k -= 1
            idx -= 1
        return prod


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)




class ProductOfNumbers:

    def __init__(self):
        self.arr = [1]
        self.zero = -1

    def add(self, num: int) -> None:
        
        if num == 0:
            self.arr.append(self.arr[-1])
            self.zero = len(self.arr)-1
        else:
            self.arr.append(self.arr[-1]*num)

    def getProduct(self, k: int) -> int:
        
        if self.zero != -1 and self.zero >= len(self.arr) - k:
            return 0
        
        return self.arr[-1] // self.arr[-k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.stack = []
        self.acc = []
        

    def add(self, num: int) -> None:
        if num == 0:
            self.stack = []
            return
        if self.stack:
            self.stack.append(self.stack[-1] * num)
        else:
            self.stack.append(num)
            
        

    def getProduct(self, k: int) -> int:
        if k > len(self.stack):
            return 0
        if k == len(self.stack):
            return self.stack[-1]
        return self.stack[-1]//self.stack[-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = [1]
        self.last_zero = -40001
        
    def add(self, num: int) -> None:
        if num == 0:
            self.last_zero = len(self.products) - 1
        if not self.products:
            self.products.append(num)
        else:
            self.products.append(self.products[-1] * max(1,num))
        

    def getProduct(self, k: int) -> int:
        if self.last_zero >= len(self.products) - k - 1:
            return 0
        result = int(self.products[-1]/self.products[len(self.products) - k - 1])
        return result

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.product = []
        self.n = 0
        self.zero = -1

    def add(self, num: int) -> None:
        if num == 0:
            self.product.append(0)
            self.zero = self.n
        else:
            if self.n == 0 or self.product[-1] == 0:
                self.product.append(num)
            else:
                self.product.append(num*self.product[-1])
        self.n += 1
        # print(self.product)

    def getProduct(self, k: int) -> int:
        if self.zero >= self.n-k: return 0
        if k == self.n or self.n-k-1 == self.zero:
            return self.product[-1]
        return self.product[-1]//self.product[self.n-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = [1, ]
        self.max_k = 0
        self.step = 0

    def add(self, num: int) -> None:
        if num == 0:
            self.max_k = self.step
        else:
            self.products.append(self.products[-1] * num)
            self.step += 1

    def getProduct(self, k: int) -> int:
        if k > self.step - self.max_k:
            return 0
        return int(self.products[-1] / self.products[self.step - k])

class ProductOfNumbers:

    def __init__(self):
        self.products = [1]
        self.zeroes = []
        self.index = 1

    def add(self, num: int) -> None:
        if num == 0:
            self.zeroes.append(self.index)
            self.index += 1
            self.products.append(self.products[-1])
        else:
            self.products.append(self.products[-1] * num)
            self.index += 1
        

    def getProduct(self, k: int) -> int:
        if self.zeroes and self.zeroes[-1] >= self.index - k:
            return 0
        else:
            return int(self.products[-1] / self.products[-(k + 1)])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.dp = [1]
        self.lastZero = -1
    def add(self, num: int) -> None:
        if num == 0:
            self.lastZero = len(self.dp)
            num = 1
        self.dp.append(num*self.dp[-1])
        

    def getProduct(self, k: int) -> int:
        if len(self.dp)-k<=self.lastZero:
            return 0
        if len(self.dp)-k-1 < 0: return self.dp[-1]
        return self.dp[-1]//self.dp[-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.d = {}
        self.nulls = []
        self.index = 0

    def add(self, num: int) -> None:
        if num == 0:
            self.nulls.append(self.index)
            num = 1
            
        if self.index == 0:
            self.d[self.index] = num
        else:
            self.d[self.index] = self.d[self.index - 1] * num        
                    
        self.index += 1     
            

    def getProduct(self, k: int) -> int:

        
        if self.nulls and self.nulls[-1] > self.index - k - 1:
            return 0
        if self.index - k == 0:
            return self.d[self.index - 1]
        
        return self.d[self.index-1] // self.d[self.index - k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import numpy as np

class ProductOfNumbers:

    def __init__(self):
        self.data = [1]
 
    def add(self, num: int) -> None:
        if num == 0:
            self.data = [1]
        else:
            self.data.append(num * self.data[-1])
 
    def getProduct(self, k: int) -> int:
        if k >= len(self.data):
            return 0
        return self.data[-1] // self.data[ - k - 1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.hash={}

    def add(self, num: int) -> None:
        curr=len(self.hash)
        if num==0:self.hash[curr]=(curr,1)
        else:
            product=1 if curr==0 or self.hash[curr-1][1]==0 else self.hash[curr-1][1]
            prev=self.hash[curr-1][0] if len(self.hash) else -1
            self.hash[curr]=(prev,product*num)
        

    def getProduct(self, k: int) -> int:
        prev=self.hash[len(self.hash)-1][0]
        low,up=(len(self.hash)-1)-k+1,len(self.hash)-1
        if low<=prev<=up:return 0
        top=len(self.hash)-1-k
        end=len(self.hash)-1
        return int(self.hash[end][1]/self.hash[top][1]) if k!=len(self.hash) else self.hash[k-1][1]
        
        
        
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class Node:
    def __init__(self, previous, value):
        self.previous = previous
        self.value = value

class ProductOfNumbers:

    def __init__(self):
        self.endNode = None
        self.lastZero = None
        self.size = 0
        self.products = None

    def add(self, num: int) -> int:
        if (num == 0):
            self.lastZero = self.size
            
        self.size += 1
        
        self.products = dict()
        
        self.endNode = Node(self.endNode, num)

    def getProduct(self, k: int) -> None:
        if self.lastZero and self.size - k < self.lastZero:
            return 0
        
        if k in self.products:
            return self.products[k]
        
        product = 1
        currentNode = self.endNode
        for i in range(0, k):
            product *= currentNode.value
            currentNode = currentNode.previous
            
        self.products[k] = product
        return product
            


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.runningProduct = []
        self.zeroStack = []
        self.addedZero = False
        

    def add(self, num: int) -> None:
        if num == 0:
            self.runningProduct.append(num)
            self.addedZero = True
            self.zeroStack.append(len(self.runningProduct)-1)
        else:
            if self.addedZero or len(self.runningProduct) == 0:
                self.runningProduct.append(num)
            else:
                currentProduct = num * self.runningProduct[-1]
                self.runningProduct.append(currentProduct)
            self.addedZero = False

    def getProduct(self, k: int) -> int:
        totalIndex = len(self.runningProduct) - 1
        if self.zeroStack and self.zeroStack[-1] > (totalIndex - k):
            return 0
        elif (totalIndex - k) == -1 or self.runningProduct[totalIndex-k] == 0:
            return int(self.runningProduct[-1])
        else:
            return int(self.runningProduct[-1] / self.runningProduct[totalIndex-k])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prods = []
        self.zeros = []
        
    def add(self, num: int) -> None:
        zero = 1 if num == 0 else 0
        if not self.zeros: self.zeros.append(zero)
        else: self.zeros.append(self.zeros[-1] + zero)
        
        prod = max(1, num)
        if self.prods: self.prods.append(self.prods[-1] * prod)
        else: self.prods.append(prod)

    def getProduct(self, k: int) -> int:
        has_zero = False
        if len(self.zeros) == k: has_zero = self.zeros[-1] > 0
        else: has_zero = (self.zeros[-1] - self.zeros[-k-1]) > 0
        if has_zero: return 0
        
        if len(self.prods) == k: return self.prods[-1]
        return self.prods[-1] // self.prods[-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class ProductOfNumbers:

    def __init__(self):
        self.p = [1]
        self.last0i = -1

    def add(self, num: int) -> None:
        p = self.p
        N = len(p)
        if num == 0:
            self.last0i = N
            num = 1
        p.append(p[-1] * num)

    def getProduct(self, k: int) -> int:
        p = self.p
        si = len(p) - k
        if si <= self.last0i:
            return 0
        else:
            return p[-1] // p[si - 1]

\"\"\"
s = ProductOfNumbers()
s.add(3)
s.add(0)
s.add(2)
s.add(5)
s.add(4)
print(s.getProduct(2))
print(s.getProduct(3))
print(s.getProduct(4))
s.add(8)
print(s.getProduct(2))
\"\"\"

from functools import reduce
class ProductOfNumbers:

    def __init__(self):
        self.list = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.list = [1]
        else:
            result = self.list[-1]*num
            self.list.append(result)

    def getProduct2(self, k: int) -> int:
        return reduce(lambda x,y:  x*y, self.list[-k:])
    
    def getProduct(self, k: int) -> int:
        if len(self.list) <= k:
            return 0
        
        ind = -1 - k 
        if self.list[ind] == 0:
            return 0
        else:
            return self.list[-1]//self.list[ind]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


#[3,0,2,2,5,4]
#[3, 0, 1, 2,  4, 20, 80]
#last 2 list[-1]/list[(-2-1)] => 80/4 = 20  
#last 3  => 80/2 = 40
#last 4 => 80/ 1 = 80
# last 5 => list[-6] == 0 => 0
# last 6 => 0 

# [2,3,4,5,6]
# l = 5 
# [2, 6, 24, 120, 720]
# last 2 => 30
# last 3 => 720/6 = 120 
# last 4 => 720/2 = 360 
# last 5 => list[-1]


class ProductOfNumbers:

    def __init__(self):
        self.lst = []
        self.running = []
        self.last0index = -1
        self.size = 0

    def add(self, num: int) -> None:
        self.size += 1
        if not self.lst and num != 0:
            self.running.append(num)
        elif num == 0: 
            self.running.append(1)
        elif self.lst[-1] == 0:
            self.running.append(num)
        else:
            self.running.append(num*self.running[-1])
        self.lst.append(num)

        if num == 0: self.last0index = self.size

    def getProduct(self, k: int) -> int:
        # print(self.running)
        if self.size == 1: return self.lst[0]
        if k > self.size: return -1
        if self.size - k < self.last0index: return 0
        if self.size == k: return self.running[-1]

        return int(self.running[-1] / self.running[self.size-k-1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.res = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.res = [1]
        else:
            self.res.append(self.res[-1]*num)
        

    def getProduct(self, k: int) -> int:
        if len(self.res) <= k:
            return 0
        else:
            return self.res[-1]//self.res[-1-k]
        
        
            
        
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.data = []
        self.prod = [1]

    def add(self, num: int) -> None:
        self.data.append(num)
        if num != 0 and self.prod[-1] != 0:
            self.prod.append(self.prod[-1]*num)
        elif num == 0:
            self.prod = (len(self.prod))*[0]
            self.prod.append(1)

    def getProduct(self, k: int) -> int:
        return self.prod[-1]//self.prod[-1-k] if self.prod[-1-k] else 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prods = []
        self.stamp = []
        

    def add(self, num: int) -> None:
        self.prods.append(num)
        self.stamp.append(1)
        
        [3, 0, 2, 5, 4]
        [1, 1, 1, 1, 1]
        

    def getProduct(self, k: int) -> int:
        if k <= 0:
            return 1
        
        index = len(self.prods) - k
        if self.stamp[index] == k:
            return self.prods[index]
        
        value = self.prods[index] * self.getProduct(k - self.stamp[index])
        
        self.stamp[index] = k
        self.prods[index] = value
        
        return value
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.last_zero = -1
        self.product_agg = []

    def add(self, num: int) -> None:
        if num == 0:
            self.last_zero = len(self.product_agg)
            self.product_agg.append(num)
        else:
            if self.last_zero == len(self.product_agg) - 1:
                self.product_agg.append(num)
            else:
                self.product_agg.append(num * self.product_agg[len(self.product_agg) - 1])

    def getProduct(self, k: int) -> int:
        diff_num = len(self.product_agg) - k -1
        
        if self.last_zero != -1 and self.last_zero > diff_num:
            return 0
        if diff_num >= 0 and self.product_agg[diff_num] > 0:
            return self.product_agg[len(self.product_agg)-1] // self.product_agg[diff_num]
        
        return self.product_agg[len(self.product_agg) - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.data = []
        self.prod = [1]

    def add(self, num: int) -> None:
        self.data.append(num)
        if num != 0 and self.prod[-1] != 0:
            self.prod.append(self.prod[-1]*num)
        elif num == 0:
            self.prod = (len(self.prod))*[0]
            self.prod.append(1)
            # elif self.prod[-1] == 0:
            #     self.prod.append(num)
        # elif num:
        #     self.prod.append(num)
        # else:
        #     self.prod.append(1)

    def getProduct(self, k: int) -> int:
        # print(self.prod)
        return self.prod[-1]//self.prod[-1-k] if self.prod[-1-k] else 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.product = []
        self.last_zero = -1

    def add(self, num: int) -> None:
        self.nums.append(num)
        if num == 0:
            self.product = [0]*len(self.product)
            self.last_zero = len(self.nums)-1
        else:
            if num != 1:
                for i in range(len(self.product)-1, self.last_zero, -1):
                    self.product[i] *= num
        self.product.append(num)

    def getProduct(self, k: int) -> int:
        if len(self.product) < k:
            return None
        return self.product[-k]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.numbers = []
        self.history = {}

    def add(self, num: int) -> None:
        self.numbers.append(num)
        self.history = {}
        
    def getProduct(self, k: int) -> int:     
        if k not in self.history:
            self.history[k] = (self.numbers[len(self.numbers)-k] * self.getProduct(k-1) if self.numbers[len(self.numbers)-k] else 0 ) if k else 1
        
        return self.history[k]  

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import bisect

class ProductOfNumbers:

    def __init__(self):
        self.arr = []
        self.zero_idx = []
        

    def add(self, num: int) -> None:
        n = len(self.arr)
        if num == 0:
            self.arr = [0] * (n + 1)
            self.zero_idx.append(n)
        
        else:
            if n == 0 or self.arr[-1] == 0:
                self.arr.append(num)
            else:
                self.arr.append(num * self.arr[-1])
        

    def getProduct(self, k: int) -> int:
        # check if there is any zeros in the range
        i = len(self.arr) - k
        x = bisect.bisect_right(self.zero_idx, i - 1, 0, len(self.zero_idx))
        
        # no zero found
        if x == len(self.zero_idx):
            if k == len(self.arr):
                return self.arr[-1]
            else:
                if self.arr[len(self.arr) - k - 1]:
                    return self.arr[-1] // self.arr[len(self.arr) - k - 1]
                
                return self.arr[-1]
        else:
            return 0
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    
    # [3, 0, 0, 2, 5, 4]
    # [(3, 1, -1), (0, 3, 1), (0, 1, 2), (2,1,2), (5,2,2), (4,10,2)]
    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        if not self.nums:
            last_zero = -1 if num else 0
            self.nums.append([num, 1, last_zero])
            return
            
        (last_val, last_product, last_zero) = self.nums[-1]
        
        last_zero = last_zero if num else len(self.nums)
        last_product = last_product * last_val or 1
        
        self.nums.append([num, last_product, last_zero])
        
    def getProduct(self, k: int) -> int:
        right_ind = len(self.nums) - 1
        left_ind = right_ind - k + 1
        
        if left_ind < 0:
            left_ind = 0
            
        (right_val, right_product, right_last_zero) = self.nums[right_ind]            
        (left_val, left_product, left_last_zero) = self.nums[left_ind]     
        
        if right_last_zero < left_ind:
            return right_val * right_product // left_product
        return 0
        
        
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr =  [1]
        
    def add(self, num: int) -> None:
        if not num :
            self.arr =[1]
        else:
            self.arr.append(self.arr[-1]*num)
        
        
    def getProduct(self, k: int) -> int: 
        if k>=len(self.arr):
            return 0
        return self.arr[-1]//self.arr[-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []

    def add(self, num: int) -> None:
        i = len(self.nums)
        self.nums.append( (num, i+1) )
        

    def getProduct(self, k: int) -> int:
        def update(i):
            cur, done = self.nums[i]
            if done < len(self.nums):
                update(done)
                cur *= self.nums[done][0]
                self.nums[i] = cur, len(self.nums)
            
        count = len(self.nums)
        i = count -k
        cur, done = self.nums[i]
        if done < count:
            update(i)
        return self.nums[i][0]
         


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.numlist = []
        self.cumprod = []
        self.zeros = []

    def add(self, num: int) -> None:
        self.numlist.append(num)
        if self.cumprod == [] or self.cumprod[-1] == 0: 
            self.cumprod.append(num)
        else: 
            new = self.cumprod[-1] * num
            self.cumprod.append(new)
        if num == 0: 
            self.zeros.append(len(self.cumprod)-1) 

    def getProduct(self, k: int) -> int:
        if self.zeros != [] and len(self.cumprod) - k <= self.zeros[-1]: 
            return 0
        else:
            if k == len(self.cumprod):
                return self.cumprod[k-1]
            else:
                ii = len(self.cumprod) - k
                return self.numlist[ii] * self.cumprod[-1] // self.cumprod[ii]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.product = [1]
        

    def add(self, num: int) -> None:
        if num == 0:
            self.product = [1]
        else:
            
            self.product.append(self.product[-1] * num)
      # [1 , 3, 4, .... k, 3 , 2, 1] 
    def getProduct(self, k: int) -> int:
        n = len(self.product) - 1
        
        return self.product[n] // self.product[n - k] if k <= n else 0
    


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.A = [1]

    def add(self, a):
        if a == 0:
            self.A = [1]
        else:
            self.A.append(self.A[-1] * a)

    def getProduct(self, k):
        if k >= len(self.A): return 0
        return self.A[-1] // self.A[-k - 1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.a=[]
        

    def add(self, num: int) -> None:
        if num == 0:
            self.a = []
        elif self.a :
            self.a.append(self.a[-1]*num)
        else:
            self.a.append(num)
        

    def getProduct(self, k: int) -> int:
        if k > len(self.a):
            return 0
        if k == len(self.a):
            return self.a[-1]
        return self.a[-1]//self.a[-(k+1)]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


'''

3,0,2,5,4,    8

k=1, 4
k=2, 20
k=3,40
k=4,0
k=5,0

d:

'''
class ProductOfNumbers:

    def __init__(self):
        self.size = 0
        self.d = {}
        self.lastZero = -1
        

    def add(self, num: int) -> None:
        self.size += 1
        if self.size <= 1 or self.d[self.size - 1] == 0:
            self.d[self.size] = num
        else:
            self.d[self.size] = num * self.d[self.size - 1]
        
        if num == 0:
            self.lastZero = self.size

        

    def getProduct(self, k: int) -> int:

        if self.size - k < self.lastZero: 
            return 0
        if self.size - k <= 0 or self.d[self.size - k] == 0: 
            return self.d[self.size]
        return self.d[self.size] // self.d[self.size - k]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math

class ProductOfNumbers:

    def __init__(self):
        self.prefixes_products = []
        
    def add(self, num: int) -> None:        
        if num == 0:
            self.prefixes_products.clear()
            return
        
        if not self.prefixes_products:
            self.prefixes_products.append(num)
        else:
            self.prefixes_products.append(num*self.prev)

        self.prev = self.prefixes_products[-1]
                
    def getProduct(self, k: int) -> int:
        if len(self.prefixes_products) == k:
            return self.prev
        elif len(self.prefixes_products) < k:
            return 0
        else:
            return self.prev//self.prefixes_products[len(self.prefixes_products)-k-1]
        
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.idx = 0
        self.pos2Prod = {}
        self.zeroPos = []
        self.currProd = 1
        
    def add(self, num: int) -> None:
        
        if num == 0:
            self.zeroPos.append(self.idx)
            num = 1
            
        self.pos2Prod[self.idx] = self.currProd * num
        self.currProd = self.currProd * num      
        self.idx += 1
        
        
    def getProduct(self, k: int) -> int:
        tailIdx = self.idx - 1
        headIdx = tailIdx - k 
        if self.zeroPos and self.zeroPos[-1] > headIdx:
            return 0
        else:
            return self.pos2Prod[tailIdx] // (self.pos2Prod[headIdx] if headIdx >=0 else 1)
        
        
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prods = []
        self.currentProd = 1
        

    def add(self, num: int) -> None:
        if num == 0:
            self.prods = []
            self.currentProd = 0
        else:
            if self.currentProd:
                self.currentProd *= num
            else:
                self.currentProd = num
                
            self.prods.append(self.currentProd)
        

    def getProduct(self, k: int) -> int:
        if len(self.prods) < k:
            return 0
        elif len(self.prods) == k:
            return int(self.currentProd)
        else:
            return int(self.currentProd / self.prods[-k-1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = []

    def add(self, num: int) -> None:
        if not num:
            self.arr = []
        else:
            prev_prod = self.arr[-1] if self.arr else 1
            self.arr.append(num*prev_prod)
        return

    def getProduct(self, k: int) -> int:
        if len(self.arr) < k:
            return 0
        elif len(self.arr) == k:
            return self.arr[-1]
        else:
            return self.arr[-1]//self.arr[-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = [1]
        

    def add(self, num: int) -> None:
        if num == 0:
            self.nums =  [1]
        else:
            self.nums.append(self.nums[-1]*num)
        

    def getProduct(self, k: int) -> int:
        if len(self.nums) <= k:
            return 0
        return self.nums[-1]//self.nums[-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.cur = 0
        self.prod = [1]
        self.last_zero = -1
        

    def add(self, num: int) -> None:
        if num != 0:
            self.prod.append(self.prod[-1] * num)
        else:
            self.prod.append(self.prod[-1])
            self.last_zero = self.cur
        self.cur += 1

    def getProduct(self, k: int) -> int:
        if self.cur - k > self.last_zero:
            return int(self.prod[-1] / self.prod[-k-1])
        else:
            return 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prefix = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix = [1]
        else:
            self.prefix.append(self.prefix[-1]*num)

    def getProduct(self, k: int) -> int:
        if k > len(self.prefix) - 1:
            return 0
        return int(self.prefix[-1]/self.prefix[-k - 1])
    # k = 1, self.prefix[-1]/self.prefix[-2]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import queue as Q
class Node:
    def __init__(self):
        self.prev = None
        self.value = None
class ProductOfNumbers:
    
    
    
    def __init__(self):
        self.tail = None
        self.maxVal = float('-inf')

    def add(self, num: int) -> None:
        
        if num > self.maxVal:
            self.maxVal = num
        
        if self.tail == None:
            self.tail = Node()
            self.tail.value = num
            return
        
        temp = self.tail
        newNode = Node()
        newNode.value = num
        newNode.prev = temp
        self.tail = newNode
        

    def getProduct(self, k: int) -> int:
        if self.maxVal == 1:
            return 1
        
        result = 1
        count = 0
        temp = self.tail
        while count < k:
            result*=temp.value
            if result == 0:
                return 0
            temp = temp.prev
            count += 1
        return result

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.z = []
        self.s = 1
        self.l = []
        self.m = [1]
        self.ind = -1

    def add(self, num: int) -> None:
        self.ind += 1
        self.l.append(num)
        self.s *= num
        self.m.append(self.s)
        if num == 0:
            self.z.append(self.ind)
            self.s = 1
            self.m[-1] = 1
        # print(num, self.l,self.m,self.s)

    def getProduct(self, k: int) -> int:
        if len(self.z) and self.z[-1] > self.ind - k:
            return 0
        else:
            # print(k,self.z[-1],self.ind)
            # print(self.m)
            return int(self.m[-1] // self.m[-k-1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.A=[1]

    def add(self, num: int) -> None:
        if not num:
            self.A = [1]
        else:
            self.A.append(self.A[-1]*num)

    def getProduct(self, k: int) -> int:
        
        if k>=len(self.A):
            return 0
        return self.A[-1]//self.A[-1-k]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums=[]
        self.suffixProduct=[]
        self.zeros=set()

    def add(self, num: int) -> None:
        self.nums.append(num)
        if num==0:
            self.zeros.add(len(self.nums)-1)
            num=1
        if len(self.suffixProduct)>0:
            self.suffixProduct.append(self.suffixProduct[-1]*num)
        else:
            self.suffixProduct.append(num)

    def getProduct(self, k: int) -> int:
        if k==1:
            return self.nums[-1]
        l = len(self.suffixProduct)-1
        # print(l,k,self.zeros)
        # for j in range(l, l-k, -1):
        #     if j in self.zeros:
        #         return 0
        for zi in self.zeros:
            if zi >l-k and zi <=l:
                return 0
        if len(self.suffixProduct) == -1*(-k):
            dd = 1
        else:
            dd = self.suffixProduct[-1-k]
        return int(self.suffixProduct[-1] / dd)


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = []
        self.zero_point = -1

    def add(self, num: int) -> None:
        if num == 0:
            self.products.append(0)
            self.zero_point = len(self.products)
        elif not self.products or self.products[-1] == 0:
            self.products.append(num)
        else:
            self.products.append(self.products[-1]*num)

    def getProduct(self, k: int) -> int:
        if len(self.products) - self.zero_point < k:
            ret = 0
        elif len(self.products) - self.zero_point == k or len(self.products) == k:
            ret = self.products[-1]
        else:
            ret = self.products[-1] // self.products[-k-1]
        return ret

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.curr_prod = None
        self.product_array = []
        self.zero_idx = set()

    def add(self, num: int) -> None:  
        self.nums.append(num)
        if self.curr_prod == None or self.curr_prod == 0:
            self.product_array.append(num)
        else:
            self.product_array.append(self.curr_prod * num)
        self.curr_prod = self.product_array[-1]
        if num == 0:
            self.zero_idx.add(len(self.nums) - 1)

    def getProduct(self, k: int) -> int:    
        if k == 1:
            return self.nums[-1]
        n = len(self.nums)
        for idx in self.zero_idx:
            if idx > n - k - 1 and idx < n:
                return 0
        if self.product_array[n - k - 1] == 0 or k == n:
            return self.product_array[n - 1]
        else:
            return int(self.product_array[n - 1] / self.product_array[n - k - 1])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.A = [1]
        

    def add(self, num: int) -> None:
        if num == 0:
            self.A = [1]
        else:
            self.A.append(self.A[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.A): return 0
        return self.A[-1] // self.A[-k - 1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = []
        

    def add(self, num: int) -> None:
        
        if num == 0:
            self.products = []    
        else:
            self.products.append(num if not len(self.products) else self.products[-1] * num)
           
    def getProduct(self, k: int) -> int:
        if k > len(self.products):
            return 0
        elif k == len(self.products):
            return self.products[-1]
        else:
            return self.products[-1] // self.products[-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)



class ProductOfNumbers:

    def __init__(self):
        self.total_list = []
        self.cumul_list = [1]
    def add(self, num: int) -> None:
        self.total_list.append(num)
        if num == 0:
            self.cumul_list= [1]
        else:
            self.cumul_list.append(self.cumul_list[len(self.cumul_list)-1]*num)

    def getProduct(self, k: int) -> int:
        if k < len(self.cumul_list):
            return int(self.cumul_list[len(self.cumul_list)-1] / self.cumul_list[len(self.cumul_list) - k - 1])
        else:
            return 0

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.max_zero_idx = -1

    def add(self, num: int) -> None:
        if num == 0:
            self.max_zero_idx = max(self.max_zero_idx, len(self.nums))
        
        if not self.nums:
            self.nums.append(num)
        else:
            prev_prod = self.nums[-1] if self.nums[-1] != 0 else 1
            self.nums.append(num * prev_prod)

    def getProduct(self, k: int) -> int:
        left, right = len(self.nums) - 1 - k, len(self.nums) - 1
        if left == self.max_zero_idx:
            return self.nums[right]
        elif left > self.max_zero_idx:
            return self.nums[right] // self.nums[left]
        else:
            return 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.a=[] 

    def add(self, num: int) -> None:
        if num==0:
            self.a=[]
            return
        if not self.a:
            self.a.append(num)
            return
        self.a.append(self.a[-1]*num)

    def getProduct(self, k: int) -> int:
        if k > len(self.a):
            return 0
        if k == len(self.a):
            return self.a[-1]
        return self.a[-1]//self.a[-1-k]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math

class ProductOfNumbers:

    def __init__(self):
        self.prefixes_products = []
        
    def add(self, num: int) -> None:        
        if num == 0:
            self.prefixes_products = []
            self.prev = 0
            return
        
        if not self.prefixes_products:
            self.prefixes_products.append(num)
        else:
            self.prefixes_products.append(num*self.prev)

        self.prev = self.prefixes_products[-1]
                
    def getProduct(self, k: int) -> int:
        if len(self.prefixes_products) == k:
            return self.prev
        if len(self.prefixes_products) < k:
            return 0
    
        return self.prev//self.prefixes_products[len(self.prefixes_products)-k-1]
        
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from collections import deque

class ProductOfNumbers:

    def __init__(self):
        self._stack = []
        # self._prod = 1
        

    def add(self, num: int) -> None:
        if num == 0:
            self._stack = []
        elif not self._stack:
            self._stack = [num]
        else:
            self._stack.append(self._stack[-1]*num)
        

    def getProduct(self, k: int) -> int:
        if k > (n:=len(self._stack)):
            return 0
        elif k == n:
            return self._stack[-1]
        else:
            return (self._stack[-1]) // self._stack[n-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.products = []
        self.lastZero = -1

    def add(self, num: int) -> None:
        self.nums.append(num)
        if(num == 0):
            self.lastZero = len(self.nums)
            self.products.append(0)
        elif len(self.products) == 0:
            self.products.append(num)
        else:
            if self.products[-1] == 0:
                self.products.append(num)
            else:
                self.products.append(self.products[-1] * num)

    def getProduct(self, k: int) -> int:
        if self.lastZero != -1 and k == len(self.nums):
            return 0
        if len(self.nums) - k >= self.lastZero:
            divisor = 1
            if k + 1 <= len(self.nums) and self.products[-k - 1] != 0:
                divisor = self.products[-k - 1]
            return int(self.products[-1]/divisor)
        else:
            return 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.nums = [1]
        else:
            self.nums.append(num * self.nums[-1])

    def getProduct(self, k: int) -> int:
        if k >= len(self.nums):
            return 0
        return self.nums[-1] // self.nums[-k - 1]
    

class SlidingWindow:
    def __init__(self, k: int):
        self.k = k
        self.q = deque()
        self.zero_cnt = 0
    
    def add(self, val: int) -> None:
        if val == 0:
            self.zero_cnt = self.k
            self.q.append(1)
        else:
            self.zero_cnt -= 1
            prev = self.q[-1] if self.q else 1
            self.q.append(prev * val)
            if len(self.q) > self.k:
                if self.zero_cnt <= 0:
                    self.q[-1] /= self.q[0]
                self.q.popleft()

    def getProduct(self) -> int:
        if self.zero_cnt > 0:
            return 0
        return self.q[-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from functools import reduce

class ProductOfNumbers:

    def __init__(self):
        self.running_product = []

    def add(self, num: int) -> None:
        if num == 0:
            self.running_product = []
        elif len(self.running_product) == 0:
            self.running_product.append(num)
        else:
            self.running_product.append(num * self.running_product[-1])
        return None

    def getProduct(self, k: int) -> int:
        if k > len(self.running_product):
            return 0
        elif k == len(self.running_product):
            return self.running_product[-1]
        else:
            return self.running_product[-1] // self.running_product[-k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.vec = []
        # self.runningProd = []
        

    def add(self, num: int) -> None:
        
        if num==0:
            self.vec=[]
        
        else:
            if self.vec:
                curr = self.vec[-1]
            else:
                curr = 1
        
            self.vec.append(num*curr)
        

    def getProduct(self, k: int) -> int:
        
        if len(self.vec)<k:
            return 0
        elif len(self.vec)==k:
            return self.vec[-1]
        else:
            return self.vec[-1]//self.vec[-k-1]
        
        # outval = self.vec[-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.preprod = [1]

    def add(self, num: int) -> None:
        if not num:
            self.preprod = [1]
        else:
            self.preprod.append(self.preprod[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.preprod):
            return 0
        return self.preprod[-1] // self.preprod[-k-1]    


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.k1=[1]

    def add(self, num: int) -> None:
        if num!=0:
            self.k1.append(self.k1[-1]*num)
        else:
            self.k1=[1]

    def getProduct(self, k: int) -> int:
        if k>=len(self.k1):
            return 0
        return (self.k1[-1]//self.k1[-1-k])

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = []
    
    def add(self, num: int) -> None:
        if num == 0:
            self.arr = []
            return
        if not self.arr :
            self.arr.append(num)
            return
        self.arr.append(self.arr[-1] * num)
        
    def getProduct(self, k: int) -> int:
        if k > len(self.arr):
            return 0
        if k == len(self.arr):
            return self.arr[-1]
        return self.arr[-1] //self.arr[-k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.nums = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.nums = [1]
        else:
            self.nums.append(num * self.nums[-1])

    def getProduct(self, k: int) -> int:
        if k >= len(self.nums):
            return 0
        return self.nums[-1] // self.nums[-k - 1]
    

class SlidingWindow:
    def __init__(self, k: int):
        self.k = k
        self.q = deque()
        self.zero_cnt = 0
    
    def add(self, val: int) -> None:
        if val == 0:
            self.zero_cnt = self.k
            self.q.append(1)
        else:
            self.zero_cnt -= 1
            prev = self.q[-1] if self.q else 1
            self.q.append(prev * val)
            if len(self.q) > self.k:
                if self.zero_cnt <= 0:
                    self.q[-1] /= self.q[0]
                self.q.popleft()

    def getProduct(self) -> int:
        if self.zero_cnt > 0:
            return 0
        return self.q[-1]
    
window = SlidingWindow(3)
window.add(1) # [1]
window.add(2) # [1, 2]
assert window.getProduct() == 2
window.add(3) # [1, 2, 3]
assert window.getProduct() == 6
window.add(4) # [2, 3, 4]
assert window.getProduct() == 24
window.add(5) # [3, 4, 5]
assert window.getProduct() == 60


window = SlidingWindow(3)
window.add(3)
window.add(0)
window.add(2)
window.add(5)
assert window.getProduct() == 0
window.add(4)
assert window.getProduct() == 40

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from collections import deque

class ProductOfNumbers:

    def __init__(self):
        self.running_products = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.running_products = [1]
        else:
            self.running_products.append(self.running_products[-1] * num)

    def getProduct(self, k: int) -> int:
        if len(self.running_products) < k + 1:
            return 0
        return int(self.running_products[-1] / self.running_products[-k - 1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.ll=[]
        self.dd=[1]#indexing form 1 not from 0
        self.count=[0]
        
    def add(self, num: int) -> None:
        self.ll.append(num)
        val=self.dd[-1]*num
        if (val==0):
            temp=self.count[-1]
            self.count.append(temp+1)
            val=self.dd[-1]
            self.dd.append(val)
        else:
            self.dd.append(val)
            temp=self.count[-1]
            self.count.append(temp)

    def getProduct(self, k: int) -> int:
        upp=len(self.count)-1
        low=upp-k+1
        
        if (low==1):
            if (self.count[upp]==0):
                return self.dd[upp]
            else:
                return (0)
        else:
            if (self.count[upp]-self.count[low-1] == 0):
                return (self.dd[upp]//self.dd[low-1])
            else:
                return(0)
            
            

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prefix_prod = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix_prod = [0] * len(self.prefix_prod) + [1]
        else:
            self.prefix_prod.append(self.prefix_prod[-1] * num)

    def getProduct(self, k: int) -> int:
        n = len(self.prefix_prod)
        if self.prefix_prod[n - k - 1] == 0:
            return 0
        else:
            return self.prefix_prod[n - 1] // self.prefix_prod[n - k - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.prefix_prod = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix_prod = [0] * len(self.prefix_prod) + [1]
        else:
            if self.prefix_prod[-1] == 0:
                self.prefix_prod.append(num)
            else:
                self.prefix_prod.append(self.prefix_prod[-1] * num)

    def getProduct(self, k: int) -> int:
        n = len(self.prefix_prod)
        if self.prefix_prod[n - k - 1] == 0:
            return 0
        else:
            return self.prefix_prod[n - 1] // self.prefix_prod[n - k - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.k1=[]
        self.mul=1

    def add(self, num: int) -> None:
        if num!=0:
            self.mul*=num
            self.k1.append(self.mul)
        else:
            self.mul=1
            self.k1=[]

    def getProduct(self, k: int) -> int:
        if k>len(self.k1):
            return 0
        elif k==len(self.k1):
            return self.k1[-1]
        else:
            return (self.k1[-1]//self.k1[-1-k])

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.array = []
        

    def add(self, num: int) -> None:
        if num == 0:
            self.array = []
        else:
            self.array.append(self.array[-1] * num if self.array else num)
            
            

    def getProduct(self, k: int) -> int:
        if len(self.array) < k:
            return 0
        
        if len(self.array) == k:
            return self.array[-1]
        
        return self.array[-1]//self.array[-k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from collections import deque

class ProductOfNumbers:

    def __init__(self):
        self.q = deque()
        self.running_products = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.q = deque()
            self.running_products = [1]
        else:
            self.running_products.append(self.running_products[-1] * num)
            self.q.append(num)        

    def getProduct(self, k: int) -> int:
        if len(self.q) < k:
            return 0
        return int(self.running_products[-1] / self.running_products[-k - 1])


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:
    
    def __init__(self):
        self.lis=[1]
    
        

    def add(self, num: int) -> None:
        if num==0:
            self.lis=[1]
        else:
            self.lis.append(self.lis[len(self.lis)-1]*num)
        

    def getProduct(self, k: int) -> int:
        
        s=len(self.lis)
        
        if s-k-1<0:
            return 0;
        
        return int(self.lis[s-1]/self.lis[s-k-1])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.products = []
        self.tmp = 1

    def add(self, num: int) -> None:
        if num == 0:
            self.products = []
            self.tmp = 1
        else:
            self.tmp *= num
            self.products.append(self.tmp)

    def getProduct(self, k: int) -> int:
        if len(self.products) < k:
            return 0
        elif len(self.products) == k:
            return self.products[-1]
        else:
            return self.products[-1] // self.products[-k-1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.__list = []
        self.__product = []
    def add(self, num: int) -> None:
        self.__list.append(num)
        if num == 0:
            self.__product = []
        else:
            if not self.__product:
                self.__product = [1]

            self.__product.insert(0, self.__product[0] * num)

    def getProduct(self, k: int) -> int:
        p = self.__product
        try:
            return p[0] // p[k]
        except IndexError:
            return 0


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.last = -1
        self.pre = [1] * 500000
        self.n = 0
        
    def add(self, num: int) -> None:
        if num == 0:
            self.pre[self.n] = 1
            self.last = self.n
        else:
            if self.n == 0:
                self.pre[self.n] = num
            else:
                self.pre[self.n] = self.pre[self.n - 1] * num
        self.n += 1
        
    def getProduct(self, k: int) -> int:
        l = self.n - k
        if self.last >= l:
            return 0
        # print(self.n - 1, l, self.last)
        return self.pre[self.n - 1] // self.pre[l - 1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from sortedcontainers import SortedList

class ProductOfNumbers:

    def __init__(self):
        self.arr = list()
        self.prod = list()
        self.zeros = SortedList()
        

    def add(self, n:int) -> None:
        num = 0
        if n == 0:
            num = 1
            self.zeros.add(len(self.prod))
        else:
            num = n
        
        
        self.arr.append(num)
        if len(self.prod) == 0:
            self.prod.append(num)
        else:
            self.prod.append(num * self.prod[-1])

    def getProduct(self, k: int) -> int:
        
        idx = len(self.prod)-k
        
        if self.zeros.bisect_left(idx) != len(self.zeros):
            return 0
        
        if k == len(self.prod):
            return self.prod[-1]
        else:
            return int(self.prod[-1]/self.prod[len(self.prod)-k-1])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:
    def __init__(self):
        self.index = 0
        self.prefix = []
        self.zeroes = []
        
    def add(self, num: int) -> None:
        if num == 0:
            self.zeroes.append(self.index)
            num = 1
            
        if not self.prefix:
            self.prefix.append(num)
        else:
            self.prefix.append(self.prefix[-1] * num)
        self.index += 1
        
    def getProduct(self, k: int) -> int:
        #print(self.index, k)
        if self.zeroes and self.index - k <= self.zeroes[-1]:
            return 0
        elif k == len(self.prefix):
            return self.prefix[-1]
        else:
            return self.prefix[-1] // self.prefix[self.index - k - 1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.l = list()
        self.last_zero = 0
        self.start_ones = 0
        
    def add(self, num: int) -> None:
        
        if num == 1:
            self.start_ones +=1
        else:
            self.start_ones = 0
        self.l.insert(0,num)
        
        if num == 0:
            self.last_zero = 0
        else:
            self.last_zero += 1

    def getProduct(self, k: int) -> int:
        
        
        if self.last_zero and self.last_zero < k:
            return 0
        
        if self.start_ones > k:
            return 1
        
        r = k
        if self.start_ones > 0:
            r -= self.start_ones - 1
        
        prod = 1
        idx = 0
        #print(self.start_ones,k)
        for idx in range(r):
            #print('->',self.l[idx])
            prod *= self.l[idx] if idx < len(self.l) else 1
        return prod

\"\"\"
[\"ProductOfNumbers\",\"add\",\"getProduct\",\"getProduct\",\"add\",\"getProduct\",\"add\",\"add\",\"add\",\"getProduct\",\"getProduct\",\"getProduct\",\"add\",\"add\",\"add\"]
[[],[1],[1],[1],[59],[2],[59],[34],[95],[1],[1],[1],[64],[0],[11]]
[null,null,1,1,null,59,null,null,null,95,95,95,null,null,null]
\"\"\"    
    
# [\"ProductOfNumbers\",\"add\",\"add\",\"add\",\"add\",\"add\",\"add\",\"add\",\"add\",\"getProduct\",\"getProduct\",\"getProduct\",\"getProduct\",\"add\"]
# [[],[2],[4],[1],[7],[4],[1],[4],[2],[3],[5],[6],[8],[4]]
# [null,null,null,null,null,null,null,null,null,8,224,224,1792,null]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.cache = {}
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        

    def getProduct(self, k: int) -> int:
        tkey = (len(self.nums),k)
        prod = self.cache.get(tkey, None)
        if not prod:
            prod = 1 
            for n in self.nums[-k:]:
                if n == 0:
                    self.cache[tkey] = 0
                    return 0
                if n == 1:
                    continue
                prod *= n
            self.cache[tkey] = prod
        return prod
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.cum_prod = []
        self.arr = []
        self.n = 0
        self.zero_flags = []

    def add(self, num: int) -> None:
        if num == 0:
            self.zero_flags.append(self.n)
        if len(self.arr) > 0:
            if self.arr[-1] == 0:
                self.cum_prod.append(num)
            else:
                self.cum_prod.append(num * self.cum_prod[-1])
        else:
            self.cum_prod.append(num)
        self.arr.append(num)
        self.n += 1

    def getProduct(self, k: int) -> int:
        if len(self.zero_flags) > 0 and max(self.zero_flags) > self.n-k-1:
            return 0
        if len(self.cum_prod) == k:
            return self.cum_prod[-1]
        den = self.cum_prod[self.n-k-1]
        if den == 0:
            return self.cum_prod[-1]
        return self.cum_prod[-1]//den


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.c=[1 for i in range(40000)]
        self.size=0
        self.z=-1
        
    def add(self, num: int) -> None:
        if(num==0):
            num=1
            self.z=self.size
        if(self.size==0):
            self.c[0]=num
            self.size+=1
            return
        self.c[self.size]*=self.c[self.size-1]*num
        self.size+=1

    def getProduct(self, k: int) -> int:
        if(self.size-self.z<=k):
            return 0
        return self.c[self.size-1]//self.c[self.size-k-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.arr = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.arr = [1]
        else:
            self.arr.append(self.arr[-1]*num)

    def getProduct(self, k: int) -> int:
        if k > len(self.arr)-1: 
            return 0
        else:
            return int(self.arr[-1]/self.arr[-k-1])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.array = []
        self.product = []

    def add(self, num: int) -> None:
        self.array.append(num)
        if len(self.product) > 0:
            i = 0
            if num == 0:
                self.product = [0] * len(self.product)
            else:
                while num != 1 and i < len(self.product) and self.product[i] != 0:
                    self.product[i] *= num
                    i += 1
            self.product.insert(0, num)
        elif len(self.product) == 0:
            self.product.append(num)

        
    def getProduct(self, k: int) -> int:
        return self.product[k - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.queue = [1]
        self.zeroes = []

    def add(self, num: int) -> None:
        prev = 1 if not self.queue or self.queue[-1]==0 else self.queue[-1]
        self.queue.append(prev*num)
        if num == 0: self.zeroes.append(len(self.queue)-1)

    def getProduct(self, k: int) -> int:
        p = max (0, len(self.queue)-k-1)
        for idx in self.zeroes:
            if p < idx < len(self.queue): 
                return 0
        #print(self.queue,self.queue[p])
        if self.queue[p] != 0:
            return self.queue[-1] // self.queue[p]
        return self.queue[-1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


from sortedcontainers import SortedList
class ProductOfNumbers:

    def __init__(self):
        self.product = []
        self.zero_index = []

    def add(self, num: int) -> None:
        if num == 0:
            self.zero_index.append(len(self.product))

        if len(self.product) == 0:
            self.product.append(num)
            return
        tail = self.product[len(self.product) - 1]
        if tail == 0:
            self.product.append(num)
        else:
            self.product.append(num * tail)

    # TODO: essentially need to get the closest 0 that's greater than len(self.product) - k - 1
    def getProduct(self, k: int) -> int:
        to_look = len(self.product) - k - 1

        if to_look < 0:
            if not self.zero_index:
                return self.product[len(self.product)-1]
            else:
                return 0
        
        # now check whether or not there is a zero after the to_look index
        sorted_list = SortedList(self.zero_index)
        to_be_inserted = sorted_list.bisect_left(to_look+1)
        # TODO: i think this logic here is kind of wrong
        if to_be_inserted != 0 and to_be_inserted < len(self.zero_index):
            return 0
        elif to_be_inserted == 0:
            if self.zero_index:
                return 0

        # check whether or not to_look_index is 0 or not
        if self.product[to_look] == 0:
            return self.product[len(self.product)-1]

        return self.product[len(self.product)-1] // self.product[to_look]




# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.cum_prod = []
        self.arr = []
        self.n = 0
        self.zero_flags = []

    def add(self, num: int) -> None:
        #print(\"self.arr\", self.arr)
        if num == 0:
            self.zero_flags.append(self.n)
        if len(self.arr) > 0:
            if self.arr[-1] == 0:
                self.cum_prod.append(num)
            else:
                self.cum_prod.append(num * self.cum_prod[-1])
        else:
            self.cum_prod.append(num)
        self.arr.append(num)
        self.n += 1

    def getProduct(self, k: int) -> int:
        #print(\"self.cum_prod\", self.cum_prod)
        #print(\"0 flags \", self.zero_flags)
        if len(self.zero_flags) > 0 and max(self.zero_flags) > self.n-k-1:
            return 0
        if len(self.cum_prod) == k:
            return self.cum_prod[-1]
        den = self.cum_prod[self.n-k-1]
        if den == 0:
            return self.cum_prod[-1]
        return self.cum_prod[-1]//den


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        
        self.arr = []
        self.ZeroIdx = []

    def add(self, num: int) -> None:
        
        n = len(self.arr)
        
        if num == 0:
            self.ZeroIdx.append(n)
            num = 1
            
        if n == 0:
            self.arr.append(num)
        else:
            self.arr.append(self.arr[-1]*num)

    def getProduct(self, k: int) -> int:
        
        if k == 0:
            return 0
        
        #0 1 2 3 4
        
        n = len(self.arr)
        
        for idx in self.ZeroIdx:
            if idx >= n-k:
                return 0
        
        #print(self.arr)
        
        n = len(self.arr) 
        #print(n, k, self.arr[n-1], self.arr[n-k-1])
        if n == k:
            return self.arr[n-1]
        else:
            return self.arr[n-1]//self.arr[n-k-1]
            
        
        
        
        
        
    

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import math
class ProductOfNumbers:

    def __init__(self):
        self.numbers = []
        self.cache = {}

    def add(self, num: int) -> None:
        self.numbers.append(num)
        self.cache = {}

    def getProduct(self, k: int) -> int:
        if k not in self.cache:
            self.cache[k] = math.prod(self.numbers[-k:])
        return self.cache[k]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.length = 0
        self.prefix = [1]
        self.zeroPosition = []

    def add(self, num: int) -> None:
        if num == 0:
            self.zeroPosition.append(self.length)
            self.prefix.append(self.prefix[-1])
        else:
            self.prefix.append(self.prefix[-1] * num)
        self.length += 1

    def getProduct(self, k: int) -> int:
        for p in self.zeroPosition:
            if self.length - k <= p <= self.length - 1:
                return 0
        return int(self.prefix[-1] / self.prefix[len(self.prefix) - k - 1])
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


import numpy as np

class ProductOfNumbers:

    def __init__(self):
        self.nums = []
        self.prods = np.array([])
        

    def add(self, num: int) -> None:
        self.nums.append(num)
        self.prods = self.prods * num
        self.prods = np.append(self.prods, num)

    def getProduct(self, k: int) -> int:
        return int(self.prods[-k])

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)


class ProductOfNumbers:

    def __init__(self):
        self.hundreds = list()  
        self.nums = []
        self.hund_prods = 1
        self.hund_res = 0
        
        
    def add(self, num: int) -> None:
        self.nums.append(num)
        self.hund_prods *= num
        self.hund_res += 1
        if self.hund_res % 100 == 0:
            self.hundreds.append(self.hund_prods)
            self.hund_res = 0
            self.hund_prods = 1

    def prod(self, f, t):
        ret = 1
        for x in self.nums[f:t]:
            ret *= x
        return ret
    
    def getProduct(self, k: int) -> int:
        prod_tail = 1
        if k < 100 + self.hund_res:
            return self.prod(len(self.nums) - k, len(self.nums))
        else:
            account = self.hund_res
            p1 = self.prod(len(self.nums) - self.hund_res, len(self.nums))
            idx = -1
            while k - account > 100:
                account += 100
                p1 = p1 * self.hundreds[idx]
                idx = idx -1
            while account <= k:
                p1 = p1 * self.nums[-account]
                account += 1
            return p1
                
            
            
            
            
            


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)