또 다른 컨볼루션

시간 제한4초메모리 제한512 MB

요약

길이 n인 배열 a와 b가 주어졌을 때, 각 k에 대해 gcd(i, j)가 k인 모든 쌍 (i, j)에서 |a_i - b_j|의 최댓값을 구합니다.

난이도: 어려움10점 중 9점
유형: 정수론, 수학, 분할 정복
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 정수 배열 $a_1, \dots, a_n$ 과 $b_1, \dots, b_n$ 이 주어진다. 다음과 같이 정의된 배열 $c_1, \dots, c_n$ 을 구하라.

$c_k = \max_{\gcd(i,j)=k} |a_i - b_j|$

입력

첫 줄에 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 둘째 줄에는 $n$ 개의 정수 $a_1, \dots, a_n$ ( $1 \le a_i \le 10^9$ )이 주어진다. 셋째 줄에는 $n$ 개의 정수 $b_1, \dots, b_n$ ( $1 \le b_i \le 10^9$ )이 주어진다.

출력

정수 $n$ 개 $c_1, \dots, c_n$ 을 출력한다.

예제1

예제 1

입력

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

예상 출력

7 5 3 3 1 3 5 7