BlueTube 공원

시간 제한2초메모리 제한1024 MB

요약

각 A_i마다 소수를 곱하거나 나눠서 가장 적은 연산으로 바꿀 수 있는 값을 찾고, 그 값의 가장 작은 인덱스 j를 구합니다.

난이도: 어려움10점 중 8점
유형: 정수론, 해시맵, 완전 탐색
정답자: 아직 제출이 없습니다

문제

파샤 아저씨는 BlueTube 공원에서 산책하는 것을 좋아한다. 가끔 산책 중에 사람이 외계인에게 납치되기도 한다. 안타깝게도 이번에는 우리 주인공에게 그 일이 일어났다.

외계인들은 파샤에게 어려운 문제를 풀어 달라고 부탁했다. 이 문제의 최적해가 있으면 외계인들이 세상을 정복하는 데 도움이 된다고 한다. 문제는 다음과 같다. 자연수 $A_i$ 로 이루어진 길이 $N$ 의 리스트가 주어진다. 수는 1부터 번호가 매겨진다. 각 $i$ 에 대해, 모든 $k$ ( $1 \le k \le N$ , $k \ne i$ )에 대하여 $dist(A_i, A_j) \le dist(A_i, A_k)$ 를 만족하는 가장 작은 $j$ ( $j \ne i$ )를 구하라.

$dist(x, y)$ 는 $x$ 를 $y$ 로 바꾸는 데 필요한 최소 연산 횟수이다. 외계인은 한 번의 연산으로 수에 임의의 소수를 곱하거나 나눌 수 있다. 소수는 서로 다른 약수가 정확히 두 개, 곧 1과 자기 자신뿐인 수이다. 예를 들어 $dist(10, 24) = 4$ 이다.

입력

첫째 줄에 리스트에 있는 수의 개수 $N$ ( $1 \le N \le 10^5$ )이 주어진다.

다음 $N$ 개의 줄에는 $A_1$ 부터 차례대로 각 $A_i$ ( $1 \le A_i \le 10^6$ )가 한 줄에 하나씩 주어진다.

출력

$N$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 에 대한 답인 $j$ 를 출력한다.

예제1

예제 1
입력
```
6
1
2
3
4
5
6
```
예상 출력
```
2
1
1
2
1
2
```