Watson gives Sherlock an array of elements and two arrays and , of 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 ? You should print all the array elements modulo .

Input Format
The first line contains two integer, and . The next line contains integers, the elements of array . The last two lines contain integers each, the elements of array and , respectively.

Output Format
Print space-separated integers, the elements of array after performing the program modulo .

Constraints

Sample Input

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

Sample Output

13 754 2769 1508