Bạn có \(n\) khối gỗ thuộc \(k\) màu khác nhau, được xếp thành một hàng. Màu của các khối là \(c_1,c_2,\ldots,c_n\), mỗi giá trị nằm trong đoạn từ \(1\) đến \(k\).

Một màu được gọi là cân bằng nếu vị trí trung bình của các khối mang màu đó bằng \((n+1)/2\). Giá trị này không nhất thiết là số nguyên.

Ví dụ, xét cách xếp \(7\) khối có màu lần lượt là \(1,2,2,1,3,1,2\). Vị trí trung bình của màu \(1\) là \((1+4+6)/3=11/3\), của màu \(2\) là \((2+3+7)/3=4\), và của màu \(3\) là \(5\). Vì \((7+1)/2=4\), màu \(2\) cân bằng còn màu \(1\) và \(3\) không cân bằng.

Hình 1: Cách xếp bảy khối trong ví dụ; màu \(2\) là màu cân bằng.

Hãy xác định có thể sắp xếp lại các khối sao cho mọi màu đều cân bằng hay không.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\), là số lượng bộ test.

Mỗi bộ test gồm hai dòng:

• Dòng đầu chứa hai số nguyên \(n,k\), lần lượt là số khối và số màu khác nhau.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1,c_2,\ldots,c_n\). Mỗi màu đều xuất hiện ít nhất một lần.

Dữ liệu ra

Với mỗi bộ test, in YES nếu tồn tại cách sắp xếp và in NO nếu không tồn tại. Nếu tồn tại, ở dòng tiếp theo in \(n\) số nguyên mô tả màu của các khối theo một thứ tự hợp lệ.

Ràng buộc

• \(1\le t\le100\).
• \(1\le k\le n\le2\cdot10^5\).
• \(1\le c_i\le k\).
• Tổng \(n\) qua mọi bộ test không vượt quá \(2\cdot10^5\).

Phân nhóm

1. \(4\) điểm: \(n\le3\).
2. \(13\) điểm: \(n\le15\).
3. \(18\) điểm: có nhiều nhất một màu xuất hiện số lần lẻ.
4. \(23\) điểm: mọi màu xuất hiện số lần bằng nhau.
5. \(15\) điểm: \(k\le15\).
6. \(27\) điểm: không có ràng buộc thêm.

3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1

YES
1 2 2 1 1 1 2
NO
YES
1 1

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.