P10311 "Cfz Round 2" Weighted Mean

Given a sequence $a$ of length $n$ and an integer $m$, it is guaranteed that every element in $a$ is a positive integer not greater than $m$, and all elements are pairwise distinct. You need to construct a sequence $b$ of length $n$ such that: - Every element in $b$ is a positive integer not greater than $m$. - $\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ is an integer. That is, when the weight of $a_i$ is $b_i$, the weighted mean of sequence $a$ is an integer. - There does not exist an ordered triple of integers $(i,j,k)$ such that $1\le i

**This problem contains multiple test cases.** The first line contains an integer $T$, which denotes the number of test cases. Then each test case is given as follows: - The first line contains two integers $n,m$. - The second line contains $n$ integers, representing the given sequence $a$.

For each test case, output one line: - If there exists a sequence $b$ that satisfies the conditions, output $n$ integers separated by spaces, representing the sequence $b$ you constructed. - If no such sequence $b$ exists, output $-1$. **Any output that satisfies the requirements will be accepted.**

#### "Sample Explanation #1" For the $1$st test case, the weighted mean of the sample output is $\dfrac{1 \times 1+2 \times 2 + 3 \times 1}{1+2+1}=2$, which is an integer. Output `1 5 1` is also considered correct, and its weighted mean is $2$. However, output `1 6 1` is incorrect. Although its weighted mean is $2$, it has $b_2>5$. Output `1 2 3` is also incorrect, because its weighted mean is $\dfrac{7}{3}$, which is not an integer. Output `1 1 1` is also incorrect. Although its weighted mean is $2$, there exists an ordered triple $(1,2,3)$ such that $1 \leq 1 < 2 < 3 \leq 3$ and $b_1=b_2=b_3$. For the $2$nd test case, it can be proven that no sequence $b$ satisfying the conditions exists. For the $3$rd test case, the weighted mean of the sample output is $\dfrac{1 \times 1+2 \times 1 + 5 \times 3+9 \times 4}{1+1+3+4}=6$, which is an integer. #### Constraints Let $\sum n$ denote the sum of $n$ within a single test file. For all testdata, $1 \le T \le 1000$, $1 \le n \le 10^6$, $1 \le a_i \le m \le 10^9$, $\sum n \le 10^6$. It is guaranteed that all elements in sequence $a$ are pairwise distinct. **You can get the score for this problem only if you pass all test points.** Translated by ChatGPT 5