준석이는 트리를 매우 좋아하여, 트리를 가지고 노는 것이 취미이다. 어느 날 준석이는 각 정점에 번호와 정수값이 적혀있는 트리를 가지고 놀던 중, 이 트리의 루트노드를 1번 노드라고 할 때 모든 정점의 아름다움을 점수로 표현해보고 싶어졌다. 이때, x번 노드의 점수는 루트노드부터 x번 노드까지 잇는 경로 상에 존재하는 모든 정수 값의 최대공약수이다. 이는 시작점인 루트노드의 정수값과 끝점인 x번 노드의 정수값도 포함하여 계산한다. 다음 트리를 통해 자세히 살펴보자.

루트노드인 1번 노드의 점수는 6이다. 2번 노드의 점수는 6과 4의 최대공약수인 2, 3번 노드의 점수는 6과 10의 최대공약수인 2, 4번 노드의 점수는 6, 10, 9의 최대공약수인 1, 5번 노드의 점수는 6, 10, 5의 최대공약수인 1이 된다. 준석이는 이렇게 점수를 계산하던 중 각 점수가 너무 작게 나오는 것이 영 마음에 들지 않았다. 그래서 각 노드의 점수를 계산할 때 임의의 한 노드의 정수값을 0으로 취급하여 점수를 좀 더 높이려 한다. 예를 들어, 2번 노드의 점수를 계산할 때 2번 노드의 정수값을 0으로 취급하면 6과 0의 최대공약수인 6을 얻을 수 있다. 마찬가지로 3번 노드의 점수를 계산할 때 1번 노드의 정수값을 0으로 취급하면 0과 10의 최대공약수인 10을 얻을 수 있다.

각 노드의 점수를 계산할 때 임의의 한 노드를 선택하여 정수값을 0으로 취급하여 계산할 수도 있고, 또는 주어진 트리를 그대로 사용하여 계산할 수도 있다. 이와 같은 방법으로 모든 노드에서의 최대 점수를 구하면 그 값은 얼마인지 계산하여라.

입력

첫째 줄에 트리를 구성하는 노드의 개수를 나타내는 정수 N이 주어진다.
(단, )

둘째 줄에 각 노드에 적혀있는 정수값 이 공백으로 구분되어 주어진다.
(단, )

이후 N-1줄에 걸쳐 두 정수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드를 잇는 간선이 존재한다는 뜻이다.
(단, )

출력

첫째 줄에 N개의 정수 을 공백으로 구분하여 출력한다. 는 i번째 노드에서 계산될 수 있는 가장 큰 아름다움의 점수이다.