406311: GYM102354 B Yet Another Convolution

Memory Limit:0 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Yet Another Convolutiontime limit per test6 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

You are given an integer array $$$a_1, \dots, a_n$$$ and an integer array $$$b_1, \dots, b_n$$$.

You have to calculate the array $$$c_1, \dots, c_{n}$$$ defined as follows:

$$$$$$c_k = \max\limits_{\gcd(i,j) = k} |a_i - b_j|\text{.}$$$$$$

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line of input contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The third line of input contains $$$n$$$ integers $$$b_1, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

Output

Output $$$n$$$ integers $$$c_1, \dots, c_n$$$.

ExampleInput
8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Output
7 5 3 3 1 3 5 7

加入题单

上一题 下一题 算法标签: