Gần đây, những chú bò ở trang trại của Farmer John mê mẩn bộ phim Apothecowry Dairies. Bộ phim xoay quanh CowCow, một thám tử bò thông minh chuyên giải quyết đủ loại vấn đề. Bessie tìm thấy một bài toán mới trong phim, nhưng phải đến tập tiếp theo sau một tuần lời giải mới được tiết lộ! Hãy giải bài toán giúp cô.

Bạn được cho hai số nguyên \(M\) và \(K\) (\(1 \leq M \leq 10^9\), \(1 \leq K \leq 31\)). Hãy chọn một số nguyên dương \(N\) và xây dựng một dãy \(a\) gồm \(N\) số nguyên không âm sao cho các điều kiện sau được thỏa mãn:

• \(1 \le N \le 100\).
• \(a_1+a_2+\dots+a_N=M\).
• \(\operatorname{popcount}(a_1)\oplus\operatorname{popcount}(a_2)\oplus\dots\oplus\operatorname{popcount}(a_N)=K\).

Nếu không tồn tại dãy như vậy, in ra \(-1\).

\(\dagger\ \operatorname{popcount}(x)\) là số bit bằng \(1\) trong biểu diễn nhị phân của số nguyên \(x\). Chẳng hạn, popcount của \(11\) là \(3\) và popcount của \(16\) là \(1\).

\(\dagger\ \oplus\) là phép XOR theo bit.

Dữ liệu vào gồm \(T\) (\(1 \le T \le 5\cdot 10^3\)) bộ dữ liệu độc lập.

Dữ liệu vào

Dòng đầu tiên chứa \(T\).

Dòng đầu tiên và duy nhất của mỗi bộ dữ liệu chứa \(M\) và \(K\).

Đảm bảo mọi bộ dữ liệu đều khác nhau.

Dữ liệu ra

In lời giải cho \(T\) bộ dữ liệu như sau:

Nếu không tồn tại đáp án, dòng duy nhất cho bộ dữ liệu đó phải là \(-1\).

Ngược lại, dòng đầu tiên cho bộ dữ liệu đó chứa một số nguyên \(N\), là độ dài của dãy (\(1 \le N \le 100\)).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách thỏa mãn các điều kiện (\(0 \le a_i \le M\)).

Ví dụ

3
2 1
33 5
10 5

2
2 0
3
3 23 7
-1

Phân nhóm

• Dữ liệu 2: \(M\le 8, K\le 8\).
• Dữ liệu 3–5: \(M>2^K\).
• Dữ liệu 6–18: Không có ràng buộc bổ sung.

Đề bài: Aakash Gokhale.

Nguồn

USACO 2025 US Open Contest, Silver — Sequence Construction: https://usaco.org/index.php?page=viewproblem2&cpid=1518