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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Mathematics

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


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]


class ProductOfNumbers:
	prod_list = []

	def __init__(self):
		pass

	def add(self, num: int) -> None:
		if num == 0:
			self.prod_list = []
		elif 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]
		elif self.prod_list[-k] == 0:
			return 0
		else:
			return self.prod_list[-1] // self.prod_list[-k - 1]


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 = {}

	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])


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]


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)
		elif 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)]


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:
		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)


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


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


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:])


class ProductOfNumbers:

	def __init__(self):
		self.array = [0]
		self.prods = [0]
		self.state = True
		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
		elif 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)]


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])


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


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


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


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


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


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


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)
		elif self.zero:
			self.product.append(num)
			self.zero = False
		else:
			self.product.append(num * self.product[-1])

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


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)


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
		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


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)


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:])


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:])


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:])


class ProductOfNumbers:

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

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

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


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
		elif self.n == 0 or self.product[-1] == 0:
			self.product.append(num)
		else:
			self.product.append(num * self.product[-1])
		self.n += 1

	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]


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 = math.prod(self.usable_array[-k:])
		return product


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)])


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:]
		return math.prod(prodList)


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:])


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:])


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]


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]


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:
			if isinstance(self.nums[idx], list):
				k -= self.nums[idx][0]
			else:
				prod *= self.nums[idx]
				k -= 1
			idx -= 1
		return prod


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]


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


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
		elif self.n == 0 or self.product[-1] == 0:
			self.product.append(num)
		else:
			self.product.append(num * self.product[-1])
		self.n += 1

	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]


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)])


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]


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]


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]


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]


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


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])


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]


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]


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:
		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])


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


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


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)
		elif 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]


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
		elif 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]


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]


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)
		elif 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:
		i = len(self.arr) - k
		x = bisect.bisect_right(self.zero_idx, i - 1, 0, len(self.zero_idx))
		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


class ProductOfNumbers:

	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


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]


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
		elif 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]


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)

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


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]


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)]


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]


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]


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)


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]


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


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


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

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


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
		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)


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


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])


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


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


from collections import deque

class ProductOfNumbers:

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

	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]


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)
		elif 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


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]


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]


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)
window.add(2)
assert window.getProduct() == 2
window.add(3)
assert window.getProduct() == 6
window.add(4)
assert window.getProduct() == 24
window.add(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


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])


class ProductOfNumbers:

	def __init__(self):
		self.ll = []
		self.dd = [1]
		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
		elif self.count[upp] - self.count[low - 1] == 0:
			return self.dd[upp] // self.dd[low - 1]
		else:
			return 0


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])


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


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
		elif 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
		return self.pre[self.n - 1] // self.pre[l - 1]


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])


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:
		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]


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


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


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]


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]


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
		if self.queue[p] != 0:
			return self.queue[-1] // self.queue[p]
		return self.queue[-1]


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)

	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
		sorted_list = SortedList(self.zero_index)
		to_be_inserted = sorted_list.bisect_left(to_look + 1)
		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
		if self.product[to_look] == 0:
			return self.product[len(self.product) - 1]
		return self.product[len(self.product) - 1] // self.product[to_look]


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
		n = len(self.arr)
		for idx in self.ZeroIdx:
			if idx >= n - k:
				return 0
		n = len(self.arr)
		if n == k:
			return self.arr[n - 1]
		else:
			return self.arr[n - 1] // self.arr[n - k - 1]


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]


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])


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