Một số nguyên dương ~A~ được gọi là số "gần hoàn hảo" nếu thỏa mãn điều kiện: ~2 \times A \le K~, với ~K~ là tổng các ước số của ~A~.

Ví dụ: ~12~ là một số "gần hoàn hảo" vì ~2 \times 12 \lt 1 + 2 + 3 + 4 + 6 + 12~.

Yêu cầu: Cho một dãy số nguyên dương, hãy in ra các số "gần hoàn hảo".

Input

Vào từ file GHH.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~N~ (~0 \lt N \le 10^4~).

• ~N~ dòng tiếp theo, mỗi dòng là một số nguyên dương có giá trị không vượt quá ~10^6~.

Output

Ghi ra file GHH.OUT gồm:

• Dòng đầu tiên ghi số lượng số "gần hoàn hảo".

• Các dòng tiếp theo, mỗi dòng ghi một số "gần hoàn hảo", số gặp trước thì viết trước.

Sample Input 1

5
8
16
12
6
7

Sample Output 1

2
12
6

Cho một dãy gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~. Hãy đếm và đưa ra số lượng số đặc biệt trong dãy ~A~.

(Số đặc biệt là số chỉ xuất hiện đúng một lần trong dãy số)

Input

Dữ liệu vào từ tệp SDB.INP có cấu trúc:

• Dòng đầu là số nguyên ~N~ (~0 < N \leq 10^6~).

• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~A_i~ (~0 < i \leq N~, ~|A_i| \leq 10^9~).

Output

Ghi ra tệp SDB.OUT có cấu trúc:

• Dòng đầu tiên ghi số lượng số đặc biệt.

• Các dòng tiếp theo, mỗi dòng ghi một số đặc biệt (theo thứ tự tính từ đầu dãy ~A~).

Sample Input 1

8
9
9
7
7
6
11
9
5

Sample Output 1

3
6
11
5

Một công ty có tổ chức trò chơi, tặng ~N~ gói quà đã được chuẩn bị theo giá trị phần quà từ thấp đến cao, để tri ân cho ~N~ khách hàng. Công ty đó đã chuẩn bị 1 chiếc hộp đựng ~N~ mảnh giấy, mỗi mảnh giấy được bí mật ghi một mã hóa gồm nhiều kí tự số và chữ. Mỗi khách hàng được chọn ~1~ mảnh giấy trong chiếc hộp đó. Em hãy viết chương trình tặng quà từ thấp đến cao theo số lượng các kí tự số của mã hóa trong tờ giấy, nếu số lượng kí tự số trong mã hóa bằng nhau thì khách hàng chọn trước được quà trước.

Input

Vào từ file TROCHOI.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~N~ với (~0 < N \le 10^4~)

• ~N~ dòng tiếp theo, mỗi dòng chứa một mã hóa không dài quá ~255~ kí tự tương ứng cho từng khách hàng.

Output

Ghi ra file TROCHOI.OUT gồm:

• Thứ tự tặng quà của trò chơi này cho ~N~ khách hàng trên.

Sample Input 1

5
N123456Cao
A89Dat
G2Chuc
L512Ket
E3689Qua

Sample Output 1

G2Chuc
A89Dat
L512Ket
E3689Qua
N123456Cao

Trong ~1~ dây chuyền làm việc của công ty có ~N~ công nhân làm ~N~ việc. Người ta đánh số cho công nhân từ ~1~ đến ~N~ theo thứ tự đứng trong dây chuyền. Thời gian hoàn thành ~1~ công việc của người thứ ~i~ là ~t_i~ phút. Mỗi người cần làm xong công việc của mình nhưng được quyền làm tối đa ~2~ việc. Vì thế họ có thể phối hợp với người đứng ngay trước mình cùng làm, nếu người thứ ~i~ và người thứ ~i+1~ phối hợp thì thời gian làm xong cho ~2~ người là ~p_i~. Tìm phương án sao cho ~N~ công việc đều hoàn thành với thời gian ít nhất.

Input

Vào từ file văn bản WORK.INP:

• Dòng thứ nhất ghi số ~N~ (~1 \le N \le 10^6~)

• Dòng thứ hai ghi thời gian làm xong việc của từng công nhân tương ứng trong dây truyền ~t_1, t_2, ..., t_N~ (~1 \le t_i \le 60~)

• Dòng thứ ba ghi ~N-1~ số thời gian cùng làm tương ứng cho số cặp công nhân nếu phối hợp ~p_1, p_2, ..., p_{N-1}~ (~1 \le p_i \le 100~)

Output

Ghi ra file WORK.OUT là ~1~ số duy nhất ghi tổng thời gian hoàn thành công việc ít nhất của ~N~ công nhân.

Sample Input 1

5
2 5 7 8 4
3 9 10 10

Sample Output 1

17