Cycles#12412
You are given an array consisting of positive integers and an integer .
In one operation you can choose two distinct indices and and replace either a_i or a_j by (a_i + a_j)\mod m.
Your task is to determine the lexicographically smallest array that can be obtained by performing the given operation any number of times (including zero).
An array is lexicographically smaller than array if and only if one of the following holds:
is a prefix of but a \neq b.
in the first position where and differ, the array has a smaller element than the corresponding element in .
You have to answer independent test cases.
The first line contains one integer (1 \le t \le 10^{5}) — the number of test cases. Then test cases follow.
The first line of the test case contains two integers and (1 \le n \le 2 \cdot 10^{5}, 2\le m \le 10^{9}).
The second line of the test case contains integers a_1, a_2, \dots, a_n (1 \le a_i < m) — the elements of array .
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case print one line containing the lexicographically smallest array that can be obtained.
Example 1
In the first test case of the sample we can choose indices and and set a_1 to (2 + 1) \mod 3 = 0 to obtain a = [0, 1]. This is the lexicographically smallest array we can obtain.
In the second test case of the sample we cannot do any operations so the lexicographically smallest array is a = [5].
1. Subtask ( points): (\sum n \le 8, m \le 8)
2. Subtask ( points): (m \le 2000)
3. Subtask ( points): No additional constraints