Divisor Erasing Game 2

Time limit2sMemory limit512 MB

Summary

Given the board numbers, print for each possible first pick every reply that lets the second player force a win.

Level: Medium7 of 10
Topics: Game theory, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

A and B play the divisor erasing game.

Several distinct natural numbers are written on a blackboard. On your turn you pick one number that is still on the board, erase it, and erase every divisor of it that is still on the board as well. For example, if the board holds 2, 3, 4, 5, 6 and you pick 6, then 6 goes away together with its divisors 2 and 3. You may not skip a turn. Whoever erases the last number wins.

A moves first, but the number A picks on the very first turn is chosen at random. So the winner, and the number B has to erase in order to win, both depend on which number A took first. Apart from that first move, A and B play optimally.

For each number A can erase first, find every number B can erase on the next turn and still win.

Input

The first line contains $N$ , the count of numbers on the board. ( $1 \le N \le 29$ )

The second line contains the $N$ numbers $X_1, X_2, \dots, X_N$ on the board, separated by spaces and given in increasing order. The $X_i$ are distinct and satisfy $1 \le X_i \le 29$ .

Output

Print $N$ lines. Line $i$ starts with the $i$ -th input number $X_i$ wrapped in parentheses, so a line for $X_i = 6$ starts with (6).

If B can win after A erases $X_i$ first, print after that, separated by single spaces, every number B can erase on the second turn to win, in increasing order. If B cannot win no matter what, print A instead of the numbers.

Hint

Take the board 1, 2, 3, 4, 5, 6. If A first picks 6, then 6 and its divisors 1, 2, 3 are erased and 4, 5 remain. Whichever of the two B erases, A erases the other one and wins, so B cannot win here. If A first picks 5, then 5 and 1 are erased and 2, 3, 4, 6 remain. Now B wins by answering 2 with 3, 3 with 2, 4 with 6, and 6 with 4.

Take the board 2, 3, 4, 6. If A erases 2, B erases 3, and if A erases 3, B erases 2. Either way 4 and 6 remain and B wins. If A erases 4, B erases 6, and if A erases 6, B erases 4, clearing the board and winning at once. In each case B loses if it erases anything else.

Examples3

Example 1

Input

6
1 2 3 4 5 6

Expected output

(1) 5 6
(2) 6
(3) 4 6
(4) 3
(5) A
(6) A

Example 2

Input

6
2 3 4 5 6 7

Expected output

(2) 3
(3) 2
(4) 6
(5) 6 7
(6) 4 5 7
(7) 5 6

Example 3
Input
```
4
2 3 4 6
```
Expected output
```
(2) 3
(3) 2
(4) 6
(6) 4
```