Trò chơi nhị phân

Trò chơi trên truyền hình đòi hỏi những người chơi phải có khả năng quan sát, trí nhớ tốt và tính toán giỏi. Trên bàn có các quân bài, mỗi quân bài ghi một số nguyên bằng $2^k$ hoặc $-2^k$ với $k=0,1,2,\dots ,30$; số quân bài cùng giá trị là đủ nhiều. Người chơi được xem trên màn hình trong một thời gian ngắn các số nguyên $a_1,a_2,\dots ,a_n$, sau đó tự chọn cho mình các quân bài tùy ý, với số lượng tùy ý các quân bài cùng giá trị.

Trò chơi gồm $n$ bước. Ở bước thứ $i$, số $a_i$ xuất hiện trên màn hình. Người chơi phải trích từ những quân bài của mình một nhóm nào đó các quân bài có tổng bằng $a_i$ và đặt chúng lên bàn để mọi người thấy. Số lượng quân bài đặt lên bàn có thể là $0$ nếu $a_i=0$. Người nào không chọn được các quân bài có tổng bằng $a_i$ sẽ bị loại khỏi cuộc chơi. Những người còn lại thu hồi các quân bài đã đặt về tập bài của mình và trò chơi chuyển sang bước tiếp theo. Sau $n$ bước, người (hoặc những người) còn lại có tập bài với ít quân nhất sẽ chiến thắng.

Yêu cầu: Hãy xác định các quân bài cần chọn để bảo đảm bạn là người chiến thắng, tức là chọn một tập quân bài có ít quân nhất sao cho với mọi $i$, có thể lấy ra từ tập đó một nhóm quân bài (mỗi quân dùng không quá một lần trong một bước) có tổng bằng $a_i$.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $n$ $(1\le n\le {10}^6)$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(|a_i|\le {10}^6)$.

Dữ liệu ra

• Dòng đầu tiên chứa số nguyên $k$, số quân bài cần chọn.
• Dòng thứ hai chứa $k$ số nguyên, giá trị các quân bài được chọn (mỗi giá trị có dạng $2^j$ hoặc $-2^j$ với $0\le j\le 30$), theo thứ tự bất kỳ. Nếu $k=0$ thì dòng này để trống.

Nếu có nhiều tập quân bài ít quân nhất, in ra một tập bất kỳ.

Ràng buộc

• $1\le n\le {10}^6$.
• $|a_i|\le {10}^6$.

Subtasks

• Subtask 1 ($30\%$ số test, $30\%$ số điểm): $n\le {10}^2$.
• Subtask 2 ($30\%$ số test, $30\%$ số điểm): $n\le {10}^4$.
• Subtask 3 ($40\%$ số test, $40\%$ số điểm): $n\le {10}^6$.

Ví dụ