Một số nguyên dương được gọi là số đẹp nếu tổng các chữ số của nó (trong hệ thập phân) chia hết cho ~5~. Các số được xét không chứa số ~0~ không có nghĩa. Ví dụ ~14~ là số đẹp vì ~1+4~ chia hết cho ~5~, số ~150~ không phải là số đẹp.

Yêu cầu: Cho dãy ~N~ số nguyên dương ~a~_~1~,~a~_~2~, ...,~a~_~N~ ~(1~ ~≤~ ~N~ ~≤~ ~10~^~4~~)~ in ra các số đẹp (nếu có) theo thứ tự của dãy đã cho, các số trên một dòng cách một dấu cách.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~N~ ~(1≤N≤10~^~4~~)~
• Dòng thứ hai ghi ~N~ số nguyên dương ~a~_~1~,~a~_~2~, ...,~a~_~N~ cách nhau ít nhất một dấu cách. Giá trị các số không vượt quá ~10~^~100~.

Output

• Gồm một dòng ghi lần lượt các số đẹp tương ứng.

Ví dụ

Input

5
140 15 46 4 95

Output

140 46

Giải thích: Chọn ~140~ vì ~1 + 4 = 5~, chọn ~46~ vì ~4 + 6 = 10~.

Subtask:

• Subtask 1 (60% số điểm): ~a~_~i~ ~≤~ ~10~^~9~ ;
• Subtask 2 (40% số điểm): ~a~_~i~ ~≤~ ~10~^~100~ ;

Trong cuộc thi Hái hoa dâng chủ, mỗi thí sinh phải trả lời ~n~ câu hỏi. Để tăng tính hấp dẫn của cuộc thi, ban tổ chức quyết định đưa ra ~n~ số điểm thưởng ~a~_~1~,~a~_~2~, ...,~a~_~n~. Theo thể lệ của cuộc thi, thí sinh trả lời đúng ~k~ câu hỏi ~(1 ≤ k ≤ n)~ sẽ nhận được số điểm thưởng bằng số lớn nhất trong các số ~a~_~1~,~a~_~2~, ...,~a~_~k~.

Yêu cầu: Xác định số điểm thưởng của thí sinh tương ứng với mỗi giá trị ~k~ từ ~1~ đến ~n~.

Input

• Dòng đầu chứa số nguyên dương ~n~ không vượt quá ~300000~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a~_~1~,~a~_~2~, ...,~a~_~n~, mỗi số không vượt quá ~10~^~9~.

Output

• Một dòng gồm ~n~ số là điểm thưởng cho thí sinh trả lời đúng lần lượt ~1, 2, ..., n~ câu hỏi.

Ví dụ

Input

3
6 1 7

Output

6 6 7

Giải thích: Thí sinh trả lời đúng ~1~ câu sẽ nhận điểm thưởng là ~6~, trả lời đúng ~2~ câu sẽ nhận điểm thưởng là ~6~, trả lời đúng ~3~ câu sẽ nhận điểm thưởng là ~7~.

Subtask:

• Subtask 1 (60% số điểm): ~N~ ~≤~ ~100000~ ;
• Subtask 2 (40% số điểm): ~N~ ~≤~ ~300000~;

Trong tiết học Toán về ước chung lớn nhất (UCLN) và bội chung nhỏ nhất (BCNN) của hai số nguyên dương ~A~ và ~B~, An Bình nhanh chóng tìm được ~UCLN(A, B)~ là ~m~ và ~BCNN(A, B)~ là ~n~. Hôm nay, cô giáo đưa ra một bài toán mới như sau:

"Cho trước hai số nguyên dương ~m~ và ~n~. Nếu có thể tìm được một hoặc nhiều cặp số ~(A, B)~ thỏa mãn ~UCLN(A, B) = m~ và ~BCNN(A, B) = n~, hãy đưa ra giá trị nhỏ nhất của tổng ~A + B~. Ngược lại, đưa ra ~-1~."

An Bình đang gặp khó khăn với bài toán này. Bạn hãy giúp An Bình giải bài toán nhé!

Yêu cầu: Tìm giá trị nhỏ nhất của tổng ~A + B~. Nếu không tìm được cặp số ~(A, B)~ nào thỏa mãn điều kiện, đưa ra ~-1~.

Dữ liệu vào: Đọc từ file văn bản TONGNN.INP, gồm một dòng chứa hai số nguyên dương ~m~, ~n~ ~(1 ≤ m ≤ n ≤~ ~10~^~12~~),~ các số cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản TONGNN.OUT một số nguyên là kết quả tìm được.

Input

• Dòng duy nhất gồm hai số nguyên ~m~, ~n~ ~(1 ≤ m ≤ n ≤~ ~10~^~12~~).~

Output

• Kết quả của bài toán.

Ví dụ

Input

2 10

Output

12

• Giải thích: Có cặp ~(2, 10)~ thoả mãn ~UCLN(2, 10) = 2~, ~BCNN(2, 10) = 10~, tổng nhỏ nhất ~A + B = 12~.

Input

2 20

Output

14

• Giải thích: Có hai cặp ~(2, 20)~ và ~(4, 10)~ thoả mãn, tổng nhỏ nhất ~A + B = 14~.

Input

3 5

Output

-1

• Giải thích: Không tìm được cặp số ~(A, B)~ nào thoả mãn