Watson gives Sherlock an array $\mbox{A}$ of $N$ elements and two arrays $\mbox{B}$ and $\mbox{C}$, of $\mbox{M}$ elements each. Then he asks Sherlock to perform the following program:

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

This code needs to be optimized. Can you help Sherlock and tell him the resulting array $\mbox{A}$? You should print all the array elements modulo $(10^9+7)$.

Input Format 

The first line contains two integer, $N$ and $\mbox{M}$. The next line contains $N$ integers, the elements of array $\mbox{A}$. The last two lines contain $\mbox{M}$ integers each, the elements of array $\mbox{B}$ and $\mbox{C}$, respectively.

Output Format 

Print $N$ space-separated integers, the elements of array $\mbox{A}$ after performing the program modulo $(10^9+7)$.

Constraints 

$1\leq N,M\leq10^5$ 

$1\leq B[i]\leq N$ 

$1\leq A[i],C[i]\leq10^5$

Sample Input

4 3
1 2 3 4
1 2 3
13 29 71

Sample Output

13 754 2769 1508

Difficulty: HARD
Tags: Matrices

Starter code:

Solutions:
from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)


import sys
(N, M) = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = {}
A.insert(0, 0)
B.insert(0, 0)
C.insert(0, 0)
mod = 1000000007
for i in range(1, M + 1):
	if B[i] in count.keys():
		count[B[i]] = count[B[i]] * C[i] % mod
	else:
		count[B[i]] = C[i]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		a = j * i
		if a > N:
			break
		if i in count.keys():
			A[a] = A[a] * count[i] % mod
print(' '.join(map(str, A[1:])))


(N, M) = (int(i) for i in input().strip().split())
A = list((int(i) for i in input().strip().split()))
B = tuple((int(i) for i in input().strip().split()))
C = tuple((int(i) for i in input().strip().split()))
factorMap = {}
for i in range(M):
	if C[i] == 1:
		continue
	if B[i] not in factorMap:
		factorMap[B[i]] = 1
	factorMap[B[i]] = factorMap[B[i]] * C[i] % 1000000007
for (key, value) in factorMap.items():
	for j in range(key - 1, N, key):
		A[j] = A[j] * value % 1000000007
print(' '.join((str(n) for n in A)))


mod = 10 ** 9 + 7
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
mas = [1] * (n + 1)
for ind in range(m):
	mas[b[ind]] = mas[b[ind]] * c[ind] % mod
for step in range(1, n + 1):
	for a_ind in range(step - 1, n, step):
		a[a_ind] = a[a_ind] * mas[step] % mod
print(' '.join(map(str, a)))


modval = 10 ** 9 + 7
(N, M) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
collect = dict()
for i in range(M):
	collect[B[i]] = collect.get(B[i], 1) * C[i] % modval
for (skip, v) in collect.items():
	for j in range(skip - 1, N, skip):
		A[j] = A[j] * v % modval
print(' '.join([str(x) for x in A]))


modulo = 10 ** 9 + 7

def compute(A, B, C, N, M):
	tmp = [1] * M
	for i in range(M):
		num = B[i]
		if num <= M:
			tmp[num - 1] *= C[i]
			tmp[num - 1] %= modulo
	for i in range(1, M + 1):
		for j in range(i, N + 1, i):
			A[j - 1] *= tmp[i - 1]
			A[j - 1] %= modulo
	print(' '.join(list(map(str, A))))

def main():
	(N, M) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	B = list(map(int, input().split(' ')))
	C = list(map(int, input().split(' ')))
	compute(A, B, C, N, M)
main()


from collections import defaultdict
(N, M) = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
MOD = 1000000007
products = defaultdict(lambda : 1)
for (i, b) in enumerate(B):
	products[b] = products[b] * C[i] % MOD
for (b, p) in products.items():
	for i in range(b, N + 1, b):
		A[i - 1] = A[i - 1] * p % MOD
print(*A)


def sherlock(a, b, c):
	h = helper(b, c)
	for pair in h:
		b = pair[0]
		c = pair[1] % (10 ** 9 + 7)
		i = b - 1
		while i < len(a):
			a[i] = a[i] * c
			i = i + b
	for i in range(0, len(a)):
		a[i] = a[i] % (10 ** 9 + 7)
	return a

def helper(b, c):
	ans = {}
	for i in range(0, len(b)):
		if not b[i] in ans:
			ans[b[i]] = c[i]
		else:
			ans[b[i]] = ans[b[i]] * c[i]
	return ans.items()

def getar():
	s = input()
	return list(map(int, s.split(' ')))

def runner():
	mn = input()
	a = getar()
	b = getar()
	c = getar()
	ans = sherlock(a, b, c)
	print(str(ans).replace(',', '')[1:-1])
runner()


__author__ = 'danielbaeck'
import math
import itertools
(n, m) = input().split(' ')
a = input().split(' ')
b = input().split(' ')
c = input().split(' ')
a = [int(x) for x in a]
b = [int(x) for x in b]
c = [int(x) for x in c]
ax = ['x']
ax.extend(a)
bx = ['x']
bx.extend(b)
cx = ['x']
cx.extend(c)
a = ax
b = bx
c = cx
countb = {}
for i in range(1, int(m) + 1):
	if not b[i] in countb:
		countb[b[i]] = c[i]
	else:
		countb[b[i]] = countb[b[i]] * c[i] % (10 ** 9 + 7)
for i in range(1, int(n) + 1):
	for j in range(1, int(int(n) / i) + 1):
		if i in countb:
			a[j * i] = a[j * i] * countb[i] % (10 ** 9 + 7)
print(' '.join([str(x) for x in a[1:]]))


(N, M) = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]
B = [int(x) for x in input().split(' ')]
C = [int(x) for x in input().split(' ')]
count = {}
mod = 10 ** 9 + 7
for i in range(M):
	if B[i] in count:
		count[B[i]] = count[B[i]] * C[i] % mod
	else:
		count[B[i]] = C[i]
for x in count:
	for i in range(x, N + 1, x):
		A[i - 1] = A[i - 1] * count[x] % mod
print(' '.join([str(x % mod) for x in A]))


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
(A, B, C) = [[0] + list(map(int, input().split())) for _ in range(3)]
CV = [1 for _ in range(N + 1)]
for i in range(1, M + 1):
	CV[B[i]] = CV[B[i]] * C[i] % MOD
for i in range(1, N + 1):
	for j in range(1, N // i + 1):
		A[i * j] = A[i * j] * CV[i] % MOD
for i in range(1, N + 1):
	print(str(A[i]) + ' ', end='')


from math import floor
(N, M) = (int(s) for s in input().split())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
mod = 10 ** 9 + 7
NplusOne = N + 1
MplusOne = M + 1
maxNM = max(N, M)
D = [0 for x in range(maxNM)]
for i in range(M):
	j = B[i] - 1
	D[j] = C[i] if D[j] == 0 else D[j] * C[i] % mod
for i in range(1, NplusOne):
	if D[i - 1] != 0:
		j = i
		k = 1
		while j < NplusOne:
			A[j - 1] = A[j - 1] * D[i - 1] % mod
			k += 1
			j = i * k
print(' '.join((str(i) for i in A)))


mod = 10 ** 9 + 7
(N, M) = [int(x) for x in input().split()]
A = [0] + [int(x) for x in input().split()]
B = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]
count = [-1] * (10 ** 5 + 1)
for i in range(1, M + 1):
	count[B[i]] = C[i] if count[B[i]] == -1 else count[B[i]] * C[i] % mod
for i in range(1, N + 1):
	for j in range(1, N // i + 1):
		if count[i] != -1:
			A[i * j] = A[i * j] * count[i] % mod
print(' '.join(['{}'] * N).format(*A[1:]))


def get():
	return [int(i) for i in input().split(' ')]
((n, m), a, b, c) = (get() for _ in range(4))
import collections
bset = collections.defaultdict(lambda : 1)
for (bx, cx) in zip(b, c):
	bset[bx] = bset[bx] * cx % 1000000007
for (bx, cx) in bset.items():
	for j in range(bx, n + 1, bx):
		a[j - 1] = a[j - 1] * cx % 1000000007
print(*a)


(N, M) = map(int, input().split())
MOD = 10 ** 9 + 7
A = [0] + list(map(int, input().split()))
B = (0,) + tuple(map(int, input().split()))
C = (0,) + tuple(map(int, input().split()))
counts = {}
for i in range(1, M + 1):
	if B[i] not in counts:
		counts[B[i]] = C[i]
	else:
		counts[B[i]] = counts[B[i]] * C[i] % MOD
for i in range(1, N + 1):
	for j in range(1, N // i + 1):
		if i in counts:
			A[i * j] = A[i * j] * counts[i] % MOD
print(*A[1:])


def unpack():
	return [int(c) for c in input().split(' ')]
MOD = int(1000000000.0 + 7)
(N, M) = unpack()
A = [0] + unpack()
B = [0] + unpack()
C = [0] + unpack()
bs = {}
for i in range(1, M + 1):
	if B[i] in bs:
		bs[B[i]] = bs[B[i]] * C[i] % MOD
	else:
		bs[B[i]] = C[i]
for i in range(1, N + 1):
	for j in range(1, int(N / i) + 1):
		if i in bs:
			A[i * j] = A[i * j] * bs[i] % MOD
print(' '.join([str(int(i)) for i in A][1:]))


MOD = 10 ** 9 + 7
(N, M) = [int(x) for x in input().split()]
A = [0] + [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
D = {}
for (i, z) in enumerate(B):
	if z in D:
		D[z] = D[z] * C[i] % MOD
	else:
		D[z] = C[i]
for x in D:
	for y in range(x, N + 1, x):
		A[y] *= D[x]
		A[y] %= MOD
for x in A[1:]:
	print(x, end=' ')


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
mod = 1000000007
xlist = [1] * (n + 1)
for (x, y) in zip(b, c):
	xlist[x] = xlist[x] * y % mod
for (x, y) in enumerate(xlist):
	if y == 1:
		pass
	else:
		for i in range(x - 1, n, x):
			a[i] = a[i] * y % mod
a[:] = [str(i) for i in a]
print(' '.join(a))


(N, M) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.insert(0, 0)
B = [int(x) for x in input().split()]
B.insert(0, 0)
C = [int(x) for x in input().split()]
C.insert(0, 0)
values_occurred = {}
p = 10 ** 9 + 7
for i in range(1, M + 1):
	if B[i] in values_occurred:
		values_occurred[B[i]] = values_occurred[B[i]] * C[i] % p
	else:
		values_occurred[B[i]] = C[i]
for i in range(1, N + 1):
	for j in range(1, int(N / i) + 1):
		if i in values_occurred:
			A[i * j] = A[i * j] * values_occurred.get(i) % p
for i in range(1, len(A)):
	print(A[i], end=' ')


m = 10 ** 9 + 7

def func(A, B, C):
	BC = {}
	for i in range(len(B)):
		try:
			BC[B[i]] = BC[B[i]] * C[i] % m
		except:
			BC[B[i]] = C[i] % m
	(B, C) = ([], [])
	for k in BC:
		B.append(k)
		C.append(BC[k])
	for i in range(1, len(B) + 1):
		for j in range(B[i - 1], len(A) + 1, B[i - 1]):
			A[j - 1] = A[j - 1] * C[i - 1] % m
	return A
input()

def parseIntList():
	return [int(i) for i in input().split()]
print(' '.join([str(i) for i in func(parseIntList(), parseIntList(), parseIntList())]))


MOD = 10 ** 9 + 7

def readints():
	return list(map(int, input().split()))

def simplify(b, c):
	ans = []
	(filt, mult) = (-1, -1)
	for (filt1, mult1) in sorted(zip(b, c)):
		if filt1 == filt:
			mult = mult * mult1 % MOD
		else:
			ans.append((filt, mult))
			(filt, mult) = (filt1, mult1)
	return ans[1:] + [(filt, mult)]
(n, m) = readints()
a = readints()
b = readints()
c = readints()
assert len(a) == n and len(b) == m and (len(c) == m)
bc = simplify(b, c)
for (filt, mult) in bc:
	for i in range(filt - 1, n, filt):
		a[i] = a[i] * mult % MOD
print(' '.join(map(str, a)))


import collections
get_line = lambda : list(map(int, input().split()))
(n, m) = get_line()
(a, b, c) = [get_line() for _ in range(3)]
mod = 10 ** 9 + 7
factors = collections.defaultdict(lambda : 1)
for i in range(0, m):
	factors[b[i]] = factors[b[i]] * c[i] % mod
for (i, factor) in factors.items():
	for idx in range(i - 1, n, i):
		a[idx] = a[idx] * factor % mod
print(' '.join(map(str, a)))


import math
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
modulus = 10 ** 9 + 7
count = {}
for i in range(len(b)):
	if b[i] in count:
		count[b[i]] = count[b[i]] * c[i] % modulus
	else:
		count[b[i]] = c[i]
for i in range(1, n + 1):
	for j in range(1, int(n / i) + 1):
		if i in count:
			a[i * j - 1] = a[i * j - 1] * count[i] % modulus
print(' '.join([str(x) for x in a]))


import sys
__author__ = 'Vasyl'
constmod = 10 ** 9 + 7
(N, M) = [int(item) for item in next(sys.stdin).split()]
A = [int(item) for item in next(sys.stdin).split()]
B = [int(item) for item in next(sys.stdin).split()]
C = [int(item) for item in next(sys.stdin).split()]
D = [1] * (N + 1)
for i in range(M):
	if B[i] > N:
		continue
	D[B[i]] = D[B[i]] * C[i]
	D[B[i]] = D[B[i]] % constmod
M = [D[1]] * N
for i in range(2, N + 1):
	for j in range(1, N // i + 1):
		M[j * i - 1] *= D[i]
		M[j * i - 1] %= constmod
for j in range(N):
	A[j] *= M[j]
	A[j] %= constmod
	print(A[j], end=' ')


import sys

def getline(n):
	return [int(x) for x in sys.stdin.readline().split(None, n - 1)]
(N, M) = getline(2)
A = getline(N)
B = getline(M)
C = getline(M)
assert N <= 10 ** 5 and M <= 10 ** 5
assert all((1 <= b <= N for b in B))
assert all((a <= 10 ** 5 for a in A))
assert all((c <= 10 ** 5 for c in C))
modulus = 10 ** 9 + 7
products = [1 for _ in range(max(B) + 1)]
for (i, b) in enumerate(B):
	products[b] = products[b] * C[i] % modulus
for b in frozenset(B):
	for j in range(b, N + 1, b):
		A[j - 1] = A[j - 1] * products[b] % modulus
print(*A)


from collections import defaultdict

def getlist():
	return [int(i) for i in input().split()]
(n, m) = getlist()
a = [0] + getlist()
b = [0] + getlist()
c = [0] + getlist()
factors = defaultdict(lambda : 1)
for (i, bv) in enumerate(b[1:], 1):
	factors[bv] = factors[bv] * c[i] % 1000000007
for (k, v) in factors.items():
	for t in range(k, n + 1, k):
		a[t] = a[t] * v % 1000000007
print(' '.join((str(int(i)) for i in a[1:])))


modval = int(1000000000.0 + 7)

def inc_mult(d, key, val=1):
	if key in d:
		d[key] = d[key] * val % modval
	else:
		d[key] = val
(N, M) = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
B = list(map(int, input().strip().split(' ')))
C = list(map(int, input().strip().split(' ')))
mult = {}
for (k, v) in zip(B, C):
	inc_mult(mult, k, v)
mult_vec = [1] * N
for k in mult:
	mult_vec[k - 1::k] = [m * mult[k] % modval for m in mult_vec[k - 1::k]]
A = [a * m % modval for (a, m) in zip(A, mult_vec)]
print(' '.join(map(str, A)))


(n, m) = input().split()
(n, m) = (int(n), int(m))
a = input().strip().split()
b = input().strip().split()
c = input().strip().split()
pairs = []
for i in range(m):
	pairs.append((int(b[i]), int(c[i])))
b.clear()
pairs.sort()
b_value = pairs[0][0]
mult = pairs[0][1]
for i in range(1, m):
	if pairs[i][0] == b_value:
		mult = mult * pairs[i][1] % 1000000007
	else:
		b.append((b_value, mult))
		b_value = pairs[i][0]
		mult = pairs[i][1]
b.append((b_value, mult))
a.append(0)
for i in range(n - 1, -1, -1):
	a[i + 1] = int(a[i])
for i in range(len(b)):
	for j in range(b[i][0], n + 1, b[i][0]):
		a[j] = a[j] * b[i][1] % 1000000007
for i in range(1, n + 1):
	print(a[i] % 1000000007, end=' ')


MODULO = 10 ** 9 + 7
(N, M) = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [int(i) for i in input().strip().split()]
C = [int(i) for i in input().strip().split()]
A.insert(0, 0)
B.insert(0, 0)
C.insert(0, 0)
count = [1] * 100001
for i in range(1, M + 1):
	count[B[i]] = count[B[i]] * C[i] % MODULO
for i in range(1, N + 1):
	for j in range(1, int(N / i) + 1):
		A[j * i] = A[j * i] * count[i] % MODULO
A.remove(0)
print(' '.join(map(str, A)))


def run():
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	c = list(map(int, input().strip().split()))
	d = [1] * n
	for i in range(m):
		d[b[i] - 1] = d[b[i] - 1] * c[i] % 1000000007
	for i in range(n):
		if d[i] == 1:
			continue
		for ind in range(i, n, i + 1):
			a[ind] = a[ind] * d[i] % 1000000007
	for x in a:
		print(x, end=' ')
run()


modulus = int(1000000000.0 + 7)

def modular_pow(base, exponent, modulus):
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent >> 1
		base = base * base % modulus
	return result

def naive(n, m, a, b, c):
	for i in range(m):
		for j in range(n):
			if (j + 1) % b[i] == 0:
				a[j] = a[j] * c[i] % modulus
	for i in range(n):
		a[i] = int(a[i])

def faster(n, m, a, b, c):
	for i in range(m):
		for j in range(b[i], n + 1, b[i]):
			a[j - 1] = a[j - 1] * c[i] % modulus
	for i in range(n):
		a[i] = int(a[i])

def fastest(n, m, a, b, c):
	mults = {}
	for i in range(m):
		if b[i] in mults:
			(x, y, z) = mults[b[i]]
			z = z * c[i] % modulus
			mults[b[i]] = (x + 1, y, z)
		else:
			x = 1
			y = [j - 1 for j in range(b[i], n + 1, b[i])]
			z = c[i]
			mults[b[i]] = (x, y, z)
	for k in mults:
		(x, y, z) = mults[k]
		for j in y:
			a[j] = a[j] * z % modulus
(n, m) = map(int, input().split())
(a, b, c) = (list(map(int, input().split())) for i in range(3))
fastest(n, m, a, b, c)
for l in (a,):
	print(' '.join(map(str, l)))


from collections import defaultdict
(N, M) = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
B = [int(i) for i in input().split(' ')]
C = [int(i) for i in input().split(' ')]
mults = defaultdict(lambda : 1)
for i in range(0, M):
	mults[B[i]] = mults[B[i]] * C[i] % 1000000007
for (i, mult) in mults.items():
	for j in range(i - 1, N, i):
		A[j] = A[j] * mult % 1000000007
print(' '.join(map(str, A)))


import sys

def main():
	lines = [[int(x) for x in line.split()] for line in sys.stdin]
	([n, m], A, B, C) = lines
	factors = dict()
	for i in range(m):
		try:
			factors[B[i]] = factors[B[i]] * C[i] % 1000000007
		except:
			factors[B[i]] = 1 * C[i] % 1000000007
	for (stepsize, factor) in factors.items():
		for ind in range(stepsize - 1, n, stepsize):
			A[ind] = A[ind] * factor % 1000000007
	print(' '.join(map(str, A)))
main()


MN = input().split(' ')
M = int(MN[1])
N = int(MN[0])
A = input().split()
A = [int(i) for i in A]
B = input().split()
B = [int(i) for i in B]
C = input().split()
C = [int(i) for i in C]
xx = pow(10, 9) + 7
BS = set(B)
BD = list(BS)
if len(BD) < 0.5 * len(B):
	dct = {}
	Mi = [x for x in range(M)]
	for x in BD:
		m = 1
		ls = []
		for y in Mi:
			if B[y] == x:
				m = m * C[y] % xx
			else:
				ls.append(y)
		Mi = ls
		dct[str(x)] = m
	for i in BD:
		z = int(N / i)
		for it in range(1, z + 1):
			A[it * i - 1] = A[it * i - 1] * dct[str(i)] % xx
else:
	for i in range(M):
		bm = B[i]
		b = bm
		c = C[i]
		while bm <= N:
			A[bm - 1] = A[bm - 1] * c % xx
			bm = bm + b
for i in A:
	print(i, end=' ')


from collections import defaultdict

def one():
	return 1
d = defaultdict(one)
myint = int
(N, M) = list(map(myint, input().split(' ')))
(A, B, C) = (list(map(myint, input().split(' '))), map(myint, input().split(' ')), map(myint, input().split(' ')))
C_iter = C.__iter__()
next = C_iter.__next__
myrange = range
for Bi in B:
	Ci = next()
	d[Bi] = d[Bi] * Ci % 1000000007
for (i, value) in d.items():
	for k in myrange(1, int(N / i) + 1):
		A[i * k - 1] = A[i * k - 1] * value % 1000000007
mystr = str
print(' '.join(map(mystr, A)))


import re
from math import sqrt
(N, M) = list(map(int, re.split(' ', input())))
A = list(map(int, re.split(' ', input())))
B = list(map(int, re.split(' ', input())))
C = list(map(int, re.split(' ', input())))
D = [1 for _ in range(N)]
Brange = set(B)
for i in [x for x in range(M) if C[x] > 1]:
	D[B[i] - 1] = D[B[i] - 1] * C[i] % 1000000007
for i in [x for x in Brange if D[x - 1] > 1]:
	for j in range(i, N + 1, i):
		A[j - 1] = A[j - 1] * D[i - 1] % 1000000007
print(' '.join(list(map(str, A))))


(N, M) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
for i in range(M):
	Bi = B[i]
	if Bi == 0:
		continue
	Ci = C[i]
	if Bi > N / 100:
		for x in range(Bi - 1, N, Bi):
			A[x] = A[x] * Ci % (10 ** 9 + 7)
		continue
	product = 1
	prev = i
	for x in range(B[i:].count(Bi)):
		index = B.index(Bi, prev)
		product = product * C[index] % (10 ** 9 + 7)
		(B[index], prev) = (0, index + 1)
	for x in range(Bi - 1, N, Bi):
		A[x] = A[x] * product % (10 ** 9 + 7)
print(' '.join([str(x) for x in A]))


MODULUS = 10 ** 9 + 7
(N, M) = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
known_products = {b: 1 for b in B}
for (b, c) in zip(B, C):
	known_products[b] = known_products[b] * c % MODULUS
for b in known_products:
	for i in range(b, N + 1, b):
		A[i] = A[i] * known_products[b] % MODULUS
print(' '.join(map(str, A[1:])))


MODULUS = 10 ** 9 + 7
(N, M) = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
known_products = {b: 1 for b in B}
for (b, c) in zip(B, C):
	known_products[b] = known_products[b] * c % MODULUS
for b in known_products:
	for i in range(b, N + 1, b):
		A[i] = A[i] * known_products[b] % MODULUS
print(' '.join(map(str, A[1:])))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
mod = 10 ** 9 + 7
mappings = dict()
for i in range(0, m):
	mappings[b[i]] = mappings.setdefault(b[i], 1) * c[i] % mod
for (b, c) in mappings.items():
	for idx in range(b - 1, n, b):
		a[idx] = a[idx] * c % mod
print(' '.join(map(str, a)))


mod = 10 ** 9 + 7
[N, M] = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
B = [int(i) for i in input().split(' ')]
C = [int(i) for i in input().split(' ')]
D = [1] * (N + 1)
for i in range(M):
	D[B[i]] *= C[i]
	D[B[i]] %= mod
for i in range(N + 1):
	if D[i] == 1:
		continue
	for j in range(i - 1, N, i):
		A[j] *= D[i]
		A[j] %= mod
for i in A:
	print(i, end=' ')


(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
bcount = [0 for x in range(n + 1)]
for x in b:
	bcount[x] += 1
bmul = [1 for x in range(n + 1)]
for i in range(m):
	bmul[b[i]] = bmul[b[i]] * c[i] % 1000000007
for i in range(1, n + 1):
	for j in range(1, n // i + 1):
		a[i * j - 1] = a[i * j - 1] * bmul[i] % 1000000007
print(' '.join(map(str, a)))


from collections import defaultdict
input()
mod = 10 ** 9 + 7
pre = defaultdict(lambda : 1)
A = [0] + list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
for (bi, ci) in zip(B, C):
	pre[bi] = pre[bi] * ci % mod
for p in pre:
	for i in range(0, len(A), p):
		A[i] = A[i] * pre[p] % mod
print(' '.join(map(str, A[1:])))


(n, m) = [int(i) for i in input().strip().split()]
a = [int(i) for i in input().strip().split()]
b = [int(i) for i in input().strip().split()]
c = [int(i) for i in input().strip().split()]
i = 0
d = {}
while i < m:
	ind = b[i]
	if ind not in d.keys():
		d[ind] = c[i]
	else:
		d[ind] = d[ind] * c[i] % 1000000007
	i += 1
for j in d.keys():
	for i in range(j - 1, n, j):
		a[i] = a[i] * d[j] % 1000000007
for i in range(n):
	print(a[i], end=' ')


import operator
import functools
import collections

def multiples_of(divider):
	i = 1
	while True:
		yield (divider * i)
		i += 1

def main(a, b, c):
	n = len(a)
	m = len(b)
	factors = collections.defaultdict(lambda : 1)
	for i in range(m):
		factors[b[i]] = factors[b[i]] * c[i] % (10 ** 9 + 7)
	for (i, factor) in factors.items():
		for idx in range(i - 1, n, i):
			a[idx] = a[idx] * factor % (10 ** 9 + 7)
	return a
(n, m) = input().split(' ')
a = [int(n) for n in input().split(' ')]
b = [int(n) for n in input().split(' ')]
c = [int(n) for n in input().split(' ')]
print(' '.join([str(n) for n in main(a, b, c)]))


p = int(10 ** 9 + 7)
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
d = [1 for i in range(n)]
for i in range(m):
	d[b[i] - 1] = d[b[i] - 1] * c[i] % p
for j in range(n):
	for i in range(j, n, j + 1):
		a[i] = a[i] * d[j] % p
print(' '.join([str(i % p) for i in a]))


from collections import defaultdict

def one():
	return 1
(n, m) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
b = [int(i) for i in input().split(' ')]
c = [int(i) for i in input().split(' ')]
facts = defaultdict(one)
for i in range(m):
	facts[b[i]] = facts[b[i]] * c[i] % 1000000007
for (i, f) in facts.items():
	for j in range(i - 1, n, i):
		a[j] = a[j] * f % 1000000007
print(*a)


import functools
from operator import mul
(nA, nM) = [int(el) for el in input().split(' ')]
modVal = 10 ** 9 + 7
A = [int(el) for el in input().split(' ')]
B = [int(el) for el in input().split(' ')]
C = [int(el) for el in input().split(' ')]
facts = [1 for i in range(0, nM)]
for i in range(0, nM):
	facts[B[i] - 1] = facts[B[i] - 1] * C[i] % modVal
for i in range(1, nM + 1):
	for j in range(i - 1, nA, i):
		A[j] = A[j] * facts[i - 1] % modVal
for j in range(0, nA):
	print(A[j], end=' ')


import collections
MOD = 10 ** 9 + 7
(N, M) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


import collections
MOD = 1000000007
(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


import collections
import sys

def main():
	lines = [[int(x) for x in line.split()] for line in sys.stdin]
	([n, m], a, b, c) = lines

	def one():
		return 1
	factors = collections.defaultdict(one)
	for i in range(0, m):
		factors[b[i]] = factors[b[i]] * c[i] % 1000000007
	for (i, factor) in factors.items():
		for idx in range(i - 1, n, i):
			a[idx] = a[idx] * factor % 1000000007
	print(' '.join(map(str, a)))
main()


modulo = 10 ** 9 + 7
(n, m) = map(int, input().split())
multipliers = [1] * m
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
for (index, weight) in zip(b, c):
	multipliers[index - 1] = multipliers[index - 1] * weight % modulo
for (index, multiplier) in enumerate(multipliers):
	position = index
	while position < n:
		a[position] = a[position] * multiplier % modulo
		position += index + 1
print(*a)


mod = 1000000007
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = map(int, input().split())
c = map(int, input().split())
fs = {}
for (s, f) in zip(b, c):
	if f <= 1:
		continue
	try:
		fs[s] = fs[s] * f % mod
	except KeyError:
		fs[s] = f
for (s, f) in fs.items():
	a[s - 1:n:s] = (aj * f for aj in a[s - 1:n:s])
print(' '.join((str(aj % mod) for aj in a)))


mod = 10 ** 9 + 7
(N, M) = [int(num) for num in input().split(' ')]
A = [int(num) % mod for num in input().split(' ')]
B = [int(num) for num in input().split(' ')]
C = [int(num) for num in input().split(' ')]
Bdict = {}
for (ix, bTerm) in enumerate(B):
	Bdict[bTerm] = Bdict.get(bTerm, 1) * C[ix] % mod
for bTerm in Bdict:
	index = bTerm
	while index <= N:
		A[index - 1] = A[index - 1] * Bdict[bTerm] % mod
		index += bTerm
print(' '.join([str(num) for num in A]))


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
BC = [(B[i], C[i]) for i in range(M)]
BC.sort(key=lambda bc: bc[0])
Multiply = [1] * N
previous = BC[0][0]
mod = BC[0][1]
for i in range(1, M):
	if BC[i][0] == previous:
		mod = mod * BC[i][1] % 1000000007
	else:
		for j in range(previous - 1, N, previous):
			Multiply[j] = Multiply[j] * mod % 1000000007
		previous = BC[i][0]
		mod = BC[i][1]
for j in range(previous - 1, N, previous):
	Multiply[j] = Multiply[j] * mod % 1000000007
for i in range(N):
	A[i] = A[i] * Multiply[i] % 1000000007
for i in range(N):
	print(A[i], end=' ')


from collections import defaultdict
(n, m) = map(int, input().split())
(a, b, c) = [list(map(int, input().split())) for _ in range(3)]
d = defaultdict(lambda : 1)
for s in range(m):
	d[b[s]] = d[b[s]] * c[s] % (10 ** 9 + 7)
for r in d.keys():
	for rr in range(r - 1, n, r):
		a[rr] = a[rr] * d[r] % (10 ** 9 + 7)
res = ' '.join([str(k) for k in a])
print(res)


input()
a = input().split()
b = input().split()
c = input().split()
bb = [1 for i in range(len(a) + 1)]
for i in range(len(b)):
	bb[int(b[i])] = bb[int(b[i])] * int(c[i]) % 1000000007
for n in range(1, len(a) + 1):
	a[n - 1] = int(a[n - 1])
	for f in range(1, int(n ** 0.5) + 1):
		if n % f == 0:
			a[n - 1] = a[n - 1] * bb[f] % 1000000007
			if n // f != f:
				a[n - 1] = a[n - 1] * bb[n // f] % 1000000007
for e in a:
	print(e, end=' ')


Z1 = input().split()
N = int(Z1[0])
M = int(Z1[1])
A = input().split()
B = input().split()
C = input().split()
dic = {}
for i in range(0, M):
	try:
		dic[int(B[i])].append(i)
	except KeyError:
		dic[int(B[i])] = [i]
c_dic = {}
for (key, val) in dic.items():
	c_dic[key] = 1
	for (ind, ele) in enumerate(val):
		c_dic[key] = c_dic[key] * int(C[ele]) % 1000000007
for (key, val) in c_dic.items():
	j = key
	while j <= N:
		A[j - 1] = int(A[j - 1]) * val % 1000000007
		j = j + key
A = map(str, A)
print(' '.join(A))


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


modo = 10 ** 9 + 7

def dof(N, M, A, B, C):
	di = {}
	for ix in range(M):
		di[B[ix]] = C[ix] * di.get(B[ix], 1) % modo
	for k in di.keys():
		for j in range(k, N + 1, k):
			A[j - 1] = A[j - 1] * di[k] % modo
	return A
(N, M) = list((int(s) for s in input().strip().split()))
A = list((int(s) for s in input().strip().split()))
B = list((int(s) for s in input().strip().split()))
C = list((int(s) for s in input().strip().split()))
r = dof(N, M, A, B, C)
for v in r:
	print(v, end=' ')


from operator import itemgetter

def gcd(a, b):
	n = [max(a, b), min(a, b)]
	while n[-1] > 0:
		n.append(n[-2] % n[-1])
	return n[-2]
p = 1000000007
(n, m) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
d = []
for i in range(m):
	d.append([b[i], c[i]])
d.sort(key=itemgetter(0))
e = [[1, 1]]
for i in range(m):
	if e[-1][0] == d[i][0]:
		e[-1][1] = e[-1][1] * d[i][1] % p
	else:
		e.append(d[i])
final = len(e)
f = [1]
for (pos, [i, x]) in enumerate(e):
	g = gcd(len(f), i)
	if g != i:
		if len(f) * i // g >= n:
			final = pos
			break
		f = f * (i // g)
	for j in range(1, len(f) // i + 1):
		f[i * j - 1] = f[i * j - 1] * x % p
if len(f) <= n // 2:
	f = f * (n // len(f))
for i in range(n - len(f)):
	f.append(f[i])
for i in range(final, len(e)):
	(j, x) = e[i]
	for k in range(1, n // j + 1):
		f[j * k - 1] = f[j * k - 1] * x % p
for i in range(n):
	a[i] = a[i] * f[i] % p
for val in a:
	print(val, end=' ')
print()


(n, m) = (int(x) for x in input().strip().split(' '))
array_a = [int(x) for x in input().strip().split(' ')]
array_b = [int(x) for x in input().strip().split(' ')]
array_c = [int(x) for x in input().strip().split(' ')]
factors = {}
for i in range(0, m):
	factors[array_b[i]] = factors.get(array_b[i], 1) * array_c[i] % 1000000007
for (i, factor) in factors.items():
	for j in range(1, int(n / i) + 1):
		idx = j * i - 1
		array_a[idx] *= factor
		array_a[idx] = array_a[idx] % 1000000007
print(' '.join(map(str, array_a)))


mod = 10 ** 9 + 7
(n, m) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
c = [int(x) for x in input().split(' ')]
bc = [(b[i], c[i]) for i in range(m)]
bc.sort()
d = []
(b, c) = bc[0]
for i in range(1, m):
	if bc[i][0] > b:
		d.append((b, c))
		(b, c) = bc[i]
	else:
		c = c * bc[i][1] % mod
d.append((b, c))
for (b, c) in d:
	for j in range(b, n + 1, b):
		a[j - 1] = a[j - 1] * c % mod
print(' '.join((str(ai) for ai in a)))


from collections import defaultdict
MOD = 10 ** 9 + 7
(N, M) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
D = defaultdict(lambda : 1)
for i in range(M):
	D[B[i]] = D[B[i]] * C[i] % MOD
for j in D:
	k = j - 1
	while k < N:
		A[k] = A[k] * D[j] % MOD
		k += j
print(*A)


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


(N, M) = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
repeats = [1 for x in range(1, 101)]
modulus = pow(10, 9) + 7
for i in range(0, M):
	if B[i] < 100:
		repeats[B[i]] *= C[i]
		repeats[B[i]] %= modulus
	else:
		r = 1
		while r * B[i] - 1 < N:
			A[r * B[i] - 1] *= C[i]
			A[r * B[i] - 1] %= modulus
			r += 1
for i in range(0, N):
	A[i] *= repeats[1]
	for j in range(2, 100):
		if (i + 1) % j == 0:
			A[i] *= repeats[j]
	A[i] %= modulus
print(' '.join([str(s % modulus) for s in A]))


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


from heapq import *
import sys
M = 1000000007

def readints():
	return list(map(int, sys.stdin.readline().split(' ')))
(n, m) = readints()
a = readints()
b = readints()
c = readints()
mps = {}
for (x, y) in zip(b, c):
	if x not in mps:
		mps[x] = y
	else:
		mps[x] = mps[x] * y % M
q = []
for k in mps:
	heappush(q, (k, k, mps[k]))
while len(q) > 0:
	(ix, k, y) = heappop(q)
	if ix > n:
		break
	a[ix - 1] = a[ix - 1] * y % M
	heappush(q, (ix + k, k, y))
print(' '.join(map(str, a)))


from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)


import collections, sys
MOD = 1000000007
(N, M) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
count = collections.defaultdict(lambda : 1)
for i in range(M):
	count[B[i]] = count[B[i]] * C[i] % MOD
for (k, v) in count.items():
	for i in range(k - 1, N, k):
		A[i] = A[i] * v % MOD
print(*A, sep=' ')


from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)


from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)


from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)


from collections import Counter
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tmp = [-1] * (n + 1)
for i in range(m):
	if tmp[b[i]] == -1:
		tmp[b[i]] = c[i]
	else:
		tmp[b[i]] *= c[i]
		tmp[b[i]] %= mod
for i in range(1, n + 1):
	if tmp[i] >= 0:
		for j in range(1, n // i + 1):
			a[i * j - 1] *= tmp[i]
			a[i * j - 1] %= mod
print(*a)