Bạn có ~n~ đồng xu, đồng xu thứ ~i~ mang giá trị nguyên dương ~x_i~. Mỗi đồng xu là một vật riêng và chỉ được chọn nhiều nhất một lần. Khi chọn một tập con không rỗng các đồng xu, tổng giá trị của chúng tạo thành một số tiền.

Hãy tìm tất cả các số tiền dương khác nhau có thể tạo được. Trước tiên in số lượng, sau đó in các số tiền theo thứ tự tăng dần.

Input

• Dòng đầu chứa số nguyên ~n~, là số đồng xu.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~, trong đó ~x_i~ là giá trị đồng xu thứ ~i~.

Output

• Dòng đầu in số nguyên ~k~, là số tổng dương khác nhau có thể tạo.
• Dòng thứ hai in ~k~ số nguyên theo thứ tự tăng dần, là toàn bộ các tổng có thể tạo.

Giới hạn

• ~1 ≤ n ≤ 100~.
• ~1 ≤ x_i ≤ 1000~ với mọi ~1 ≤ i ≤ n~.

Ví dụ

Input

4
4 2 5 2

Output

9
2 4 5 6 7 8 9 11 13

Giải thích ví dụ

Có thể tạo chín tổng dương khác nhau. Chẳng hạn 6 = 4 + 2, 9 = 4 + 5, 11 = 4 + 5 + 2 và 13 = 4 + 2 + 5 + 2. Không thể tạo các tổng như 1, 3, 10 hoặc 12.