Tima trở về sau chuyến đi đến Xorland và mang theo một mảng gồm $n$ số nguyên. Xorland là một đất nước nhỏ nổi tiếng về ẩm thực, âm nhạc và những trò chơi trên mảng. Một điểm đặc biệt của các trò chơi ở Xorland là không có người thắng: tình bạn luôn chiến thắng! Một trong những trò chơi đó là “Xor-Mat”.
Luật chơi “Xor-Mat” rất đơn giản. Trước khi bắt đầu trò chơi, hai người chơi chọn một mảng $a$ và một số nguyên $k$. Sau đó, người chơi thứ nhất tô mỗi số trong mảng bằng một trong $k$ màu. Gọi $c_i$ là màu của số thứ $i$ trong mảng, với các màu được đánh số từ $1$ đến $k$. Tiếp theo, người chơi thứ hai chọn một cặp chỉ số $(i, j)$ sao cho $i \ne j$ và $c_i = c_j$.
Mục tiêu của người chơi thứ nhất là làm cho $a_i \oplus a_j$ lớn nhất, còn người chơi thứ hai cố gắng làm cho $a_i \oplus a_j$ nhỏ nhất. Ở đây, $\oplus$ là phép “XOR” theo bit.
Mansur thách Tima chơi một ván “Xor-Mat”. Họ chơi trên mảng của Tima. Mansur đi trước và Tima đi sau. Hãy in giá trị của $a_i \oplus a_j$ khi cả hai đều chơi tối ưu. Đồng thời, hãy tìm một cách tô màu tối ưu cho mảng mà Mansur có thể chọn.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 5 \cdot 10^4$) — số bộ kiểm thử.
Tiếp theo là $2 \cdot t$ dòng theo khuôn dạng sau:
Dòng đầu tiên của mỗi bộ kiểm thử chứa hai số nguyên $n$ ($2 \le n \le 5 \cdot 10^4$) và $k$ ($1 \le k \le \min(n - 1, 50)$).
Dòng thứ hai của mỗi bộ kiểm thử chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — mảng của Tima.
Đảm bảo rằng tổng $n$ trên tất cả các bộ kiểm thử không vượt quá $5 \cdot 10^4$.
Dữ liệu ra
Với mỗi bộ kiểm thử trong dữ liệu vào, in hai dòng:
- Ở dòng đầu tiên, in giá trị của $a_i \oplus a_j$ khi cả hai người chơi đều chơi tối ưu.
- Ở dòng thứ hai, in $n$ số nguyên $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le k$), trong đó $c_i$ là màu mà Mansur chọn cho số thứ $i$ của mảng. Nếu có nhiều cách tô màu tối ưu, hãy in bất kỳ cách nào.
Nhiệm vụ con
Gọi $S$ là tổng $n$ trên tất cả các bộ kiểm thử.
| Nhiệm vụ con | Giới hạn bổ sung | Điểm | Các nhiệm vụ con cần thiết |
|---|---|---|---|
| 0 | Ví dụ | 0 | — |
| 1 | $S \le 10$, $k \le 5$ | 6 | 0 |
| 2 | $S \le 50000$, $k = 1$ | 10 | |
| 3 | $S \le 1000$, $k \le 2$ | 10 | — |
| 4 | $S \le 50000$, $k \le 2$ | 20 | 2, 3 |
| 5 | $S \le 50000$, $k \le 4$ | 22 | 1, 4 |
| 6 | — | 32 | 5 |
Ví dụ
Dữ liệu vào 1
2 3 1 1 2 3 3 2 1 2 3
Dữ liệu ra 1
1 1 1 1 3 1 1 2