Sắp xếp Hamming

Trong một buổi nghiên cứu về khoa học máy tính, FullHouse Dev đã tìm hiểu về khoảng cách Hamming - một khái niệm quan trọng trong lý thuyết mã hóa. Để áp dụng kiến thức này vào thực tế, họ đã phát triển một thuật toán sắp xếp dựa trên khoảng cách Hamming.

Bài toán

Cho một mảng các số nguyên \(A\) và một số nguyên \(X\). Nhiệm vụ của bạn 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\) số nguyên.

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ử với \(X\) là:

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

Khi sắp xếp theo khoảng cách Hamming và theo giá trị số (trong trường hợp cùng khoảng cách), ta được kết quả là: 6 4 5.