Sắp xếp Hamming

Trong giờ học thuật toán, FullHouse Dev được thầy giáo giao cho một bài toán thú vị về khoảng cách Hamming.

Bài toán

Cho một mảng số nguyên \(A\) và một số nguyên \(X\), nhiệm vụ của bạn là cài đặt một thuật toán sắp xếp. Mục tiêu là sắp xếp các phần tử trong mảng \(A\) dựa trên Khoảng cách Hamming của chúng với số nguyên \(X\).

Khoảng cách Hamming được định nghĩa là số bit khác nhau trong biểu diễn nhị phân của hai số nguyên.

Việc sắp xếp phải được thực hiện theo thứ tự tăng dần của khoảng cách Hamming, và trong trường hợp các phần tử có cùng khoảng cách Hamming, chúng sẽ được sắp xếp theo thứ tự số học tăng dần.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa hai số nguyên \(N\) và \(X\).
  • Dòng thứ hai chứa mảng \(A\) gồm \(N\) phần tử.

OUTPUT FORMAT:

• Với mỗi test case, in ra mảng đã được sắp xếp theo quy tắc trên trên một dòng mới.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq N \leq 10^5\)
• \(1 \leq A[i], X \leq 10^9\)

Ví dụ

INPUT

1
3 2
4 5 6

OUTPUT

6 4 5

Giải thích

Trong ví dụ này, biểu diễn nhị phân của \(X = 2\) là "10". Tương tự, với mảng \(A\), biểu diễn nhị phân của các phần tử là:

• 4: "100"
• 5: "101"
• 6: "110"

Khoảng cách Hamming của mỗi phần tử trong mảng với \(X\) là:

• H(4,2) = 1
• H(5,2) = 2
• H(6,2) = 1

Do 4 và 6 có cùng khoảng cách Hamming là 1, chúng được sắp xếp theo thứ tự số học. Vì vậy, kết quả cuối cùng là: 6 4 5.