약수 지우기 게임 2

A와 B가 약수 지우기 게임을 한다.

칠판에 서로 다른 자연수가 여러 개 적혀 있다. 각자 자기 차례에 칠판에 남아 있는 수 하나를 골라 지우고, 그 수의 약수 중 칠판에 남아 있는 수도 모두 함께 지운다. 예를 들어 칠판에 2, 3, 4, 5, 6이 적혀 있을 때 6을 고르면 6과 함께 약수인 2와 3도 지운다. 자기 차례에 아무 수도 지우지 않을 수는 없다. 마지막 수를 지운 사람이 이긴다.

게임은 A가 먼저 시작한다. 그런데 A가 맨 처음에 고르는 수는 무작위로 정해진다. 그래서 A가 처음에 어떤 수를 골랐는지에 따라 이기는 사람도, B가 이기려면 어떤 수를 지워야 하는지도 달라진다. 첫 수를 제외하면 A와 B 모두 최적으로 둔다.

A가 처음에 지울 수 있는 각 수마다, 그다음 차례에 B가 지워서 이길 수 있는 수를 모두 구하라.

첫째 줄에 칠판에 적힌 수의 개수 $N$이 주어진다. ($1 \le N \le 29$)

둘째 줄에 칠판에 적힌 $N$개의 자연수 $X_1, X_2, \dots, X_N$이 공백으로 구분되어 오름차순으로 주어진다. 모든 $X_i$는 서로 다르고, $1 \le X_i \le 29$이다.

$N$개의 줄을 출력한다. $i$번째 줄은 입력에 주어진 $i$번째 수 $X_i$를 괄호로 감싼 형태, 예를 들어 $X_i$가 6이면 (6)으로 시작한다.

A가 처음에 $X_i$를 지웠을 때 B가 이길 수 있으면, 그 뒤에 공백을 하나씩 두고 B가 두 번째 차례에 지워서 이길 수 있는 수를 모두 오름차순으로 출력한다. B가 무엇을 지워도 이길 수 없으면 수 대신 A를 출력한다.

칠판에 1, 2, 3, 4, 5, 6이 적힌 경우를 보자. A가 처음에 6을 고르면 6과 그 약수인 1, 2, 3이 함께 지워지고 4와 5가 남는다. B가 둘 중 무엇을 지워도 A가 나머지 하나를 지워 이기므로 B는 이길 수 없다. 반면 A가 처음에 5를 골라 5와 1이 지워지면 2, 3, 4, 6이 남는다. 이때는 B가 2에는 3을, 3에는 2를, 4에는 6을, 6에는 4를 맞받아 지우면 이긴다.

칠판에 2, 3, 4, 6이 적힌 경우, A가 2를 지우면 B는 3을, A가 3을 지우면 B는 2를 지운다. 그러면 4와 6이 남아 B가 이긴다. A가 4를 지우면 B는 6을, A가 6을 지우면 B는 4를 지워 칠판을 모두 비우고 이긴다. 각 경우에 B가 다른 수를 지우면 이기지 못한다.