lexgcd (IATI senior)
Time limit: 1.5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: prime, number theory, greedy, permutation

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
![](_page_0_Picture_1.jpeg)

## Task A6. LEX_GCD 1.5 sec. 512 MB

Your task is to find the lexicographically lowest \(K\)-gcd equivalent **permutation** of a given sequence of \(N\) positive integers \(a_1, a_2, …, a_N\). Two sequences (that are permutations of each other) \(a_1, a_2, ..., a_N\) and \(b_1, b_2, ..., b_N\) are considered \(K\)-gcd equivalent if for every set of \(K\) distinct indices from 1 to \(N\), the greatest common divisor (gcd) of the elements in these positions in both sequences is the same.

However, there's a twist - you are allowed to multiply at most one element of \(a\) by a given integer \(X\) before finding this lowest \(K\)-gcd equivalent sequence. You are allowed to not multiply by \(X\) at all and keep the same sequence. Additionally, it is guaranteed that **\(X\) is divisible by only** 1 **and itself**. You aim to minimize the resulting sequence lexicographically among all possible choices of preprocessing (or choosing not to) of \(a\). Note that if you decide to preprocess the sequence, then your result must be a \(K\)-gcd equivalent of the preprocessed sequence \(a\) (i.e. considering the greatest common divisors after the multiplication).

Write a program **lex_gcd** that solves this problem.

### Input

The first line of the input contains one integer \(T\), the number of test cases. Each test case consists of three positive integers \(N\), \(K\), and \(X\), followed by \(N\) positive integers \(a_1, a_2, …, a_N\).

### Constraints

*   \(2 \le \sum N \le 10^5\) (over all test cases)
*   \(2 < K < N\)
*   \(1 \le X \le 10^9\), \(X\) is either 1 or prime
*   \(1 \le a_i \le 10^9\)

### Subtasks

| Subtask | Points | Required subtasks | \(N\)               | \(X\)     | Other constraints                  |
| :------: | :----: | :---------------: | :-----------------: | :------: | :------------------------------------ |
|    1     |   6    |         -         |   \(\sum N \le 5\)    |  \(X = 1\)  |                   -                  |
|    2     |   19   |         1         | \(\sum N \le 1000\) |  \(X = 1\)  |                   -                  |
|    3     |   13   |       1 - 2       | \(\sum N \le 10^5\) |  \(X = 1\)  |                   -                  |
|    4     |   4    |         1         |  \(\sum N \le 100\)  |     -     |                   -                  |
|    5     |   4    |      1, 2, 4      | \(\sum N \le 1000\) |     -     |                   -                  |
|    6     |   31   |         -         | \(\sum N \le 10^5\) |     -     | \(a_i \ne a_j \text{ for } i \ne j\) |
|    7     |   23   |       1 - 6       | \(\sum N \le 10^5\) |     -     |                   -                  |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

### Output

For each test case, output \(N\) integers representing the lexicographically lowest \(K\)-gcd equivalent sequence to \(a\) after performing the allowed preprocessing.

![](_page_1_Picture_1.jpeg)

### Example

| Input   | Output   | Explanation                                                                                                                                                                                                                             |
| :------: | :------: | :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 2       | 2 4 6    | Two test cases. For the first one, no preprocessing is required.                                                                                                                                                                        |
| 3 2 1   | 3 6 9    | The \(K\)-gcd property is satisfied since the greatest common divisor of all pairs remains 2. For the second one, preprocessing by multiplying the first element by 3 results in the lexicographically lowest sequence 3, 6, 9, 21. |
|         | 21         |                                                                                                                                                                                                                                         |
| 2 6 4   |          |                                                                                                                                                                                                                                         |
| 4 2 3   |          |                                                                                                                                                                                                                                         |
| 7 3 6 9 |          |                                                                                                                                                                                                                                         |

Starter code:

Grader code:

Setup script:

Evaluation script: