Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 
Chef found a very useful open-source code for the current problem. Unfortunately, one fragment of code isn't optimized. Consider that problem: given an array D of size N and Q queries X to the following open-source code:

read X

for i = 1..N:

X = floor(X / D[i])

print X

Help Chef to optimize that code for all possible X, he will be very thankful :)

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.  The first line of each test case contains two integers - N and Q. The second line contains array D. The third line contains Q queries - X_{1}, X_{2}, ..., X_{Q}. 

------ Output ------ 

For every test case in single line output Q integers - for each X_{i} output result for this query.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ X_{i}, D_{i} ≤ 10^{9}$
$ Sum of N over all test cases ≤ 3*10^{5}$
$ Sum of Q over all test cases ≤ 3*10^{5}$

------ Subtasks ------ 

$Subtask #1: (25 points)  sum of N over all test cases ≤ 3*10^{3} and sum of Q over all test cases ≤ 3*10^{3} $
$Subtask #2: (75 points)  Original constraints$

----- Sample Input 1 ------ 
2
2 3
2 3
5 100 8
3 2
2 2 2
16 8
----- Sample Output 1 ------ 
0 16 1
2 1
----- explanation 1 ------ 
Example case 1. [[5 / 2] / 3] = 0, [[100 / 2] / 3] = 16, [[8 / 2] / 3] = 1

Source: codechef | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = 1
	for i in range(n):
		f = f * a[i]
	c = []
	for i in range(q):
		c.append(b[i] // f)
	print(*c)


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	x = list(map(int, input().split()))
	mul = 1
	for i in a:
		mul *= i
	for i in x:
		print(i // mul, end=' ')
	print()


from functools import reduce
tc = int(input().strip())
for t in range(tc):
	(n, q) = map(int, input().split())
	d = reduce(lambda a, b: a * b, list(map(int, input().split())))
	x = list(map(int, input().split()))
	for i in x:
		print(i // d, end=' ')
	print()


T = int(input())
while T > 0:
	(N, Q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	quer = list(map(int, input().split()))
	mult = 1
	for i in range(N):
		mult = mult * arr[i]
	for i in range(Q):
		quer[i] = str(int(quer[i] / mult))
	s = ' '.join(quer)
	print(s)
	T -= 1


from bisect import bisect_left
from code import interact
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, q) = il()
	d = il()
	x = il()
	p = 1
	for ele in d:
		p = p * ele
	for val in x:
		print(val // p, end=' ')
	print()


T = int(input())
for i in range(T):
	(N, Q) = list(map(int, input().split()))
	D = list(map(int, input().split()))
	Qseries = list(map(int, input().split()))
	temp = 1
	for num in D:
		temp *= num
	ans = ''
	for Qsub in Qseries:
		if len(ans) == 0:
			ans = str(Qsub // temp)
		else:
			ans += ' ' + str(Qsub // temp)
	print(ans)


T = int(input())

def findX(N, Q, q):
	ans = ''
	for i in q:
		ans += str(i // N) + ' '
	print(ans[:-1])
for testcase in range(T):
	(N, Q) = map(int, input().split())
	n = list(map(int, input().split()))
	q = list(map(int, input().split()))
	multiplication = 1
	for number in n:
		multiplication *= number
	findX(multiplication, Q, q)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	temp = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	x = [i for i in temp if i != 1]
	i = 0
	le = len(x)
	for j in range(q):
		no = d[j]
		i = 0
		while i < le and no != 0:
			no //= x[i]
			i += 1
		print(no, end=' ')
	print()


t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	p = d[0]
	for i in range(1, n):
		p *= d[i]
	for i in range(q):
		x[i] //= p
		print(x[i], end=' ')
	print()


t = int(input())
for h in range(t):
	(N, Q) = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	re = 1
	for i in l1:
		re = re * i
	l3 = [str(i // re) for i in l2]
	print(' '.join(l3))


import math
T = int(input())
for tj in range(T):
	(N, Q) = map(int, input().split())
	D = list(map(int, input().split()))
	X = list(map(int, input().split()))
	mult = 1
	for i in range(N):
		mult *= D[i]
	for j in range(Q):
		print(math.floor(X[j] / mult), end=' ')
	print()


t = int(input())
while t:
	(n, q) = map(int, input().split(' '))
	ls = list(map(int, input().split(' ')))
	queries = list(map(int, input().split(' ')))
	mul = 1
	for i in ls:
		mul *= i
	for i in queries:
		print(i // mul, end=' ')
	print()
	t -= 1


T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	D = list(map(int, input().split()))
	Queries = list(map(int, input().split()))
	D_eff = 1
	for item in D:
		D_eff *= item
	for i in range(Q):
		ans = int(Queries[i] / D_eff)
		print(ans, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	array = list(map(int, input().split()))
	x_array = list(map(int, input().split()))
	total = 1
	for i in range(n):
		total *= array[i]
	for j in range(q):
		print(x_array[j] // total, end=' ')
	print()


import numpy as np
t = int(input())
for i in range(0, t):
	b = list(map(int, input().split()))
	a = np.array(b)
	n = a[0]
	q = a[1]
	d = list(map(int, input().split()))
	c = np.array(d)
	f = list(map(int, input().split()))
	e = np.array(f)
	y = 1
	for j in range(0, n):
		y = y * c[j]
	z = ''
	for k in range(0, q):
		m = e[k] // y
		m = str(m)
		z = z + m
		z = z + ' '
	print(z)


T = int(input())
if T >= 1 and T <= 1000:
	for k in range(0, T):
		(N, Q) = map(int, input().split())
		temp = 1
		D = list(map(int, input().split()))
		X = list(map(int, input().split()))
		for i in D:
			temp = i * temp
		for j in X:
			print(j // temp, end=' ')
		print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	k = 1
	for rt in l:
		k = k * rt
	m = list(map(int, input().split()))
	for rt in m:
		ans = rt // k
		print(ans, end=' ')
	print(' ')


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 1
	for j in l:
		s *= j
	l2 = list(map(int, input().split()))
	for z in l2:
		ans = z // s
		print(ans, end=' ')
	print()


from sys import stdin
for _ in range(int(stdin.readline())):
	stdin.readline()
	d = list(map(int, stdin.readline().split()))
	q = list(map(int, stdin.readline().split()))
	m = max(q)
	p = 1
	while d and p <= m:
		p *= d.pop()
	print(' '.join(map(lambda x: str(x // p), q)))


from sys import stdin
for _ in range(int(stdin.readline())):
	stdin.readline()
	d = list(map(int, stdin.readline().split()))
	q = list(map(int, stdin.readline().split()))
	p = 1
	m = max(q)
	for dx in d:
		p *= dx
		if p > m:
			break
	for qx in q:
		print(qx // p, end=' ')
	print()


from sys import stdin
for _ in range(int(stdin.readline())):
	stdin.readline()
	p = 1
	for dx in map(int, stdin.readline().split()):
		p *= dx
	print(' '.join(map(lambda x: str(int(x) // p), stdin.readline().split())))


from sys import stdin
from functools import reduce
for _ in range(int(stdin.readline())):
	stdin.readline()
	p = reduce(lambda x, y: x * y, map(int, stdin.readline().split()))
	print(' '.join(map(lambda x: str(int(x) // p), stdin.readline().split())))


from sys import stdin
for _ in range(int(stdin.readline())):
	stdin.readline()
	p = 1
	for dx in map(int, stdin.readline().split()):
		p *= dx
	for qx in map(int, stdin.readline().split()):
		print(qx // p, end=' ')
	print()


import numpy
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	d = [int(x) for x in input().split(' ')]
	n = [int(x) for x in input().split(' ')]
	pro = numpy.prod(d)
	for i in n:
		print(i // pro, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	k = list(map(int, input().split()))
	p = 1
	for i in d:
		p *= i
	for i in range(q):
		k[i] = k[i] // p
	print(*k)


for tc in range(int(input())):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	p = 1
	for i in d:
		p *= i
	for j in range(q):
		x[j] = x[j] // p
	print(*x)


t = int(input())
for I in range(t):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	p = 1
	for i in d:
		p *= i
	for i in range(q):
		x[i] = x[i] // p
	print(*x)


import sys
import os.path
import math
import heapq
import copy
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
from bisect import bisect
mod = int(1000000000.0 + 7)
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp().split())

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(l1):
	print(*l1)

def power(n):
	return 1 << n
for _ in range(ninp()):
	(N, Q) = mapinp()
	D = linp()
	X = linp()
	(div, result) = (1, [])
	for i in D:
		div = div * i
	for i in X:
		result.append(floor(i / div))
	prntlist(result)


from functools import reduce
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	div = reduce(lambda a, b: a * b, d)
	for i in x:
		print(i // div, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = 1
	for i in range(n):
		p *= a[i]
	for i in range(q):
		b[i] = b[i] // p
	print(*b)


from math import floor
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	c = 1
	for i in l1:
		c *= i
	for i in l2:
		print(i // c, end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	lq = list(map(int, input().split()))
	c = 1
	for i in lq:
		c = c * i
	l = list(map(int, input().split()))
	for i in l:
		print(i // c, end=' ')
	print()


for h in range(int(input())):
	(e, r) = map(int, input().split())
	(f, v) = (list(map(int, input().split())), list(map(int, input().split())))
	(r, t) = (max(v), 1)
	for g in f:
		t = t * g
		if t > r:
			break
	for _ in v:
		print(_ // t, end=' ')
	print()


for i in range(int(input())):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	m = max(x)
	prod = 1
	for num in d:
		prod *= num
		if prod > m:
			break
	for query in x:
		print(query // prod, end=' ')
	print()


for _ in range(int(input())):
	(N, Q) = [int(s) for s in input().split()]
	D = [int(s) for s in input().split()]
	Q = [int(s) for s in input().split()]
	MaximumQ = max(Q)
	Product = 1
	for i in D:
		Product = Product * i
		if Product > MaximumQ:
			break
	for q in Q:
		print(q // Product, end=' ')
	print()


t = int(input())
for loop in range(t):
	(n, q) = map(int, input().split())
	prodD = 1
	for val in input().split():
		prodD *= int(val)
	for val in input().split():
		print(int(int(val) / prodD), end='')
		q -= 1
		if q != 0:
			print(' ', end='')
	print()


t = int(input())
for loop in range(t):
	(n, q) = map(int, input().split())
	d = [int(val) for val in input().split()]
	prodD = 1
	for i in d:
		prodD *= i
	q = [int(val) for val in input().split()]
	for i in range(len(q)):
		print(int(q[i] / prodD), end='')
		if i < len(q) - 1:
			print(' ', end='')
	print()


import numpy
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	arr = numpy.array(l1)
	brr = numpy.array(l2)
	brr = brr // numpy.prod(arr)
	print(*brr)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	x_arr = list(map(int, input().split()))
	tot = 1
	for i in range(n):
		tot *= arr[i]
	for i in range(q):
		print(x_arr[i] // tot, end=' ')
	print()


T = int(input())
for i in range(T):
	(n, q) = map(int, input().split())
	lq = list(map(int, input().split()))
	p = 1
	for x in lq:
		p *= x
	l = list(map(int, input().split()))
	for x in l:
		print(x // p, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l_q = list(map(int, input().split()))
	p = 1
	for x in l_q:
		p *= x
	l = list(map(int, input().split()))
	for x in l:
		print(x // p, end=' ')
	print()


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	m = 1
	for i in range(len(d)):
		m = m * d[i]
	for i in range(len(x)):
		print(x[i] // m, end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	p = 1
	for i in range(n):
		p = p * d[i]
	for i in range(q):
		print(x[i] // p, end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	ar = list(map(int, input().split()))
	xr = list(map(int, input().split()))
	d = 1
	for i in ar:
		d *= i
	for j in xr:
		print(j // d, end=' ')
	print()


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	dlt = list(map(int, input().split()))
	xlt = list(map(int, input().split()))
	d_pr = 1
	for d in dlt:
		d_pr *= d
	for x in xlt:
		x = x // d_pr
		print(x, end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, q) = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	total = 1
	for i in d:
		total *= i
	x = [int(z) for z in input().split()]
	for i in x:
		print(i // total, end=' ')
	print()


t = int(input())
for _ in range(t):
	product = 1
	ans = list(map(int, input().split()))
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	for i in range(ans[0]):
		product *= list1[i]
	for i in range(ans[1]):
		print(list2[i] // product, end=' ')
	print()


t = int(input())
while t:
	(n, q) = map(int, input().split())
	m = 1
	for i in input().split():
		m = m * int(i)
	x = [int(i) // m for i in input().split()]
	for i in x:
		print(i, end=' ')
	print()
	t -= 1


import math
for t in range(int(input())):
	(n, q) = [int(x) for x in input().rstrip().split()]
	d = [int(x) for x in input().rstrip().split()]
	a = [int(x) for x in input().rstrip().split()]
	prd = 1
	for i in d:
		prd *= i
	for i in a:
		print(i // prd, end=' ')
	print('\r')


for i in range(int(input())):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y = 1
	for k in d:
		y *= k
	for j in x:
		print(j // y, end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	s = list(map(int, input().split()))
	p = 1
	for i in l:
		p *= i
	for j in s:
		print(j // p, end=' ')
	print()


import math
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	dl = list(map(int, input().split()))
	ql = list(map(int, input().split()))
	mul = 1
	for i in dl:
		mul *= i
	for i in ql:
		print(math.floor(i / mul), end=' ')
	print()


t = int(input())
for i in range(t):
	nq = input().split()
	n = int(nq[0])
	q = int(nq[1])
	arr = list(map(int, input().split()))
	x = list(map(int, input().split()))
	c = 1
	for j in arr:
		c *= j
	for k in x:
		print(k // c, end=' ')
	print('\r')


import math
for i in range(int(input())):
	a = input()
	z = list(map(int, input().split()))
	s = 1
	for i in z:
		s *= i
	k = list(map(int, input().split()))
	k = list(map(lambda x: str(x // s), k))
	print(' '.join(k))


for test in range(int(input())):
	_ = input()
	D = list(map(int, input().split()))
	queries = list(map(int, input().split()))
	s = 1
	for i in D:
		s *= i
	queries = list(map(lambda x: str(x // s), queries))
	print(' '.join(queries))


from math import floor
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	d = list(map(int, input().split()))
	total = d[0]
	for i in range(1, len(d)):
		total = total * d[i]
	q = list(map(int, input().split()))
	for i in range(len(q)):
		print(floor(q[i] / total), end=' ')
	print()