시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 6 5 5 83.333%

문제

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

You have to calculate the array \(c_1, \dots , c_n\) defined as follows:

\[c_k = \max_{gcd(i,j)=k}{|a_i - b_j|}\text{.}\]

입력

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

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

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

출력

Output \(n\) integers \(c_1, \dots , c_n\).

예제 입력 1

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

예제 출력 1

7 5 3 3 1 3 5 7