Description

小七是一位強大的魔法師,她可以變身成其他人的樣子。但是,變身成其他人會需要消耗自己的靈力才可以成功。

今天,她在路上看到了 $N$ 個人在路上,第 $i$ 個人可以用一個數字 $a_i$ 表示,而我們說兩個人相似若且唯若他們的數字不互質。
小七現在的樣貌可以用數字 $S$ 表示,並且如果 $S$ 與 $a_i$ 相似,則她可以花費 $b_i$ 的靈力把自己,也就是 $S$ 變成 $a_i$。

她想知道,對於每個人,如果透過一系列的變身變得跟第 $i$ 個人相似,至少需要花費多少靈力?如果無法變得跟第 $i$ 個人相似,請輸出 -1。

Input Format

第一行輸入一個數字 $N$,表示陣列長度
第二行輸入 $N$ 個數字 $a_1,a_2,\dots,a_N$
第三行輸入 $N$ 個數字 $b_1,b_2,\dots,b_N$
第四行輸入一個數字 $S$

對於所有測試資料:

  • $1\le N \le 5 \times 10 ^ 4 $
  • $1 \le a_i,S,b_i \le 10 ^ 9 $

Output Format

輸出 $N$ 個整數,分別表示 $S$ 變成與 $a_1,a_2,\dots,a_N$ 不互質分別所需的最小花費

Sample Input 1

7
2 4 10 6 7 14 11
1 2 4 8 16 32 64
3

Sample Output 1

8 8 8 0 40 8 -1

Hints

關於範測中,如果要將 $S$ 變得跟 $a_5$ 相似,則花費最少靈力的方法為:
因為 $\gcd(S,a_4) \ne 1$($S$ 與 $a_4$ 相似),因此,可以先將 $S$ 變成 $6$,花費 $8$ 的靈力
接下來,因為 $S$ 與 $a_6$ 相似,因此將 $S$ 變成 $14$,花費 $32$ 的靈力。
現在 $S$ 與 $a_5$ 相似,總共花費 $8+32 = 40$ 的靈力。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~10 $a_i,S$ 皆為質數 5
3 0~20 $a_i,S$ 的因數至多只有四個 10
4 0, 21~30 $N \le 1000$ 15
5 0, 31~40, 63 $a_i,S \le 10 ^ 6 $ 45
6 0~64 無其他限制 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 65536 1 3 4 5 6
1 1500 65536 65536 2 3 6
2 1500 65536 65536 2 3 6
3 1500 65536 65536 2 3 6
4 1500 65536 65536 2 3 6
5 1500 65536 65536 2 3 6
6 1500 65536 65536 2 3 6
7 1500 65536 65536 2 3 6
8 1500 65536 65536 2 3 6
9 1500 65536 65536 2 3 6
10 1500 65536 65536 2 3 6
11 1500 65536 65536 3 6
12 1500 65536 65536 3 6
13 1500 65536 65536 3 6
14 1500 65536 65536 3 6
15 1500 65536 65536 3 6
16 1500 65536 65536 3 6
17 1500 65536 65536 3 6
18 1500 65536 65536 3 6
19 1500 65536 65536 3 6
20 1500 65536 65536 3 6
21 1500 65536 65536 4 6
22 1500 65536 65536 4 6
23 1500 65536 65536 4 6
24 1500 65536 65536 4 6
25 1500 65536 65536 4 6
26 1500 65536 65536 4 6
27 1500 65536 65536 4 6
28 1500 65536 65536 4 6
29 1500 65536 65536 4 6
30 1500 65536 65536 4 6
31 1500 65536 65536 5 6
32 1500 65536 65536 5 6
33 1500 65536 65536 5 6
34 1500 65536 65536 5 6
35 1500 65536 65536 5 6
36 1500 65536 65536 5 6
37 1500 65536 65536 5 6
38 1500 65536 65536 5 6
39 1500 65536 65536 5 6
40 1500 65536 65536 5 6
41 1500 65536 65536 6
42 1500 65536 65536 6
43 1500 65536 65536 6
44 1500 65536 65536 6
45 1500 65536 65536 6
46 1500 65536 65536 6
47 1500 65536 65536 6
48 1500 65536 65536 6
49 1500 65536 65536 6
50 1500 65536 65536 6
51 1500 65536 65536 6
52 1500 65536 65536 6
53 1500 65536 65536 6
54 1500 65536 65536 6
55 1500 65536 65536 6
56 1500 65536 65536 6
57 1500 65536 65536 6
58 1500 65536 65536 6
59 1500 65536 65536 6
60 1500 65536 65536 6
61 1500 65536 65536 6
62 1500 65536 65536 6
63 1500 65536 65536 5 6
64 1500 65536 65536 6