Rearranging

AtCoder

IDagc010_e

Time2000ms

Memory256MB

Difficulty—

There are $N$ integers written on a blackboard. The $i$\-th integer is $A_i$. Takahashi and Aoki will arrange these integers in a row, as follows: * First, Takahashi will arrange the integers as he wishes. * Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes. We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible. Find the eventual sequence that will be produced. ## Constraints * $1 ≦ N ≦ 2000$ * $1 ≦ A_i ≦ 10^8$ ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ … $A_N$ [samples]

Samples

Input #1

5
1 2 3 4 5

Output #1

5 3 2 4 1

If Takahashi arranges the given integers in the order $(1,2,3,4,5)$, they will become $(5,3,2,4,1)$ after Aoki optimally manipulates them.

Input #2

4
2 3 4 6

Output #2

2 4 6 3

API Response (JSON)

{
  "problem": {
    "name": "Rearranging",
    "description": {
      "content": "There are $N$ integers written on a blackboard. The $i$\\-th integer is $A_i$. Takahashi and Aoki will arrange these integers in a row, as follows: *   First, Takahashi will arrange the integers as he",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc010_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ integers written on a blackboard. The $i$\\-th integer is $A_i$.\nTakahashi and Aoki will arrange these integers in a row, as follows:\n\n*   First, Takahashi will arrange the integers as he...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments