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~;

Cho 2 số nguyên dương ~a~, ~b~. Tìm ước chung lớn nhất của chúng.

Input

• Một dòng duy nhất gồm số ~a~ ~(a ≤~ ~10~^~18~~)~ và số ~b~ ~(b ≤~ ~10~^~18~~)~.

Output

• Một dòng là ước chung lớn nhất của ~a~ và ~b~.

Ví dụ

Input

12 6

Output

6

minhphan là một học sinh thông minh, cần cù chịu khó nhưng khá lười biếng. Một hôm, minhphan được thầy cho bài tập như sau: Cho trước số nguyên dương ~N~ ~(N~ ~≤~ ~50)~. Hãy đếm số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có ~2~ kí tự ~1~ nào đứng cạnh nhau. Nhưng vì tối qua minhphan mãi chơi Free Fire đến khuya nên sáng nay bạn ấy không còn đủ tỉnh táo để làm bài tập, các bạn hãy giúp minhphan giải bài tập này nhé!

Input

• Số nguyên dương ~N~ duy nhất.

Output

• Số nguyên duy nhất là số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có 2 kí tự 1 nào đứng cạnh nhau.

Ví dụ

Input

3

Output

5

• Giải thích: Với ~N~ ~=~ ~3~, ta có ~5~ dãy ~000, 001, 010, 100, 101~.

Subtask:

• Subtask ~1~ (40% số điểm): ~N~ ~≤~ ~20~.
• Subtask ~2~ (60% số điểm): ~20~ ~<~ ~N~ ~≤~ ~50~.

Cho dãy số ~A~ có ~N~ số nguyên. Hãy đếm số cặp ~(i,j)~ sao cho ~A~_~i~ ~+~ ~A~_~j~ ~=~ ~0~, với ~i~ ~<~ ~j~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1~ ~≤~ ~N~ ~≤~ ~2*10~^~5~~)~
• Dòng thứ hai chứa dãy số ~A~ gồm ~N~ số nguyên cách nhau bởi một ký tự khoảng trống. ~(|A[i]| ≤ 10^9)~

Output

In ra một số nguyên duy nhất, là số cặp phần tử trong dãy A mà có tổng là 0.

Scoring

• Subtask 1 (33,33% số điểm): ~N~ ~≤~ ~10~^~4~, ~|A~_~i~| ~≤~ ~10~^~6~.
• Subtask 2 (33,33% số điểm): ~N~ ~≤~ ~2*10~^~5~, ~|A~_~i~| ~≤~ ~10~^~6~.
• Subtask 3 (33,33% số điểm): ~N~ ~≤~ ~2*10~^~5~, ~|A~_~i~| ~≤~ ~10~^~9~.

Examples

Test 1

Input:

3
-2 0 2

Output:

1

Test 2

Input:

6
-2 -1 0 0 1 2

Output:

3

Tìm ~K~ chữ số cuối cùng của ~M~^~N~ ~(0 < K ≤ 9, 0 ≤ M, N, ≤ 10~^~6~~)~

Input

• Dòng duy nhất gồm các chữ số ~K~, ~M~, ~N~.

Output

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

Ví dụ

Input

2 2 10

Output

24

Cho N (N ≤ 100), hãy đếm số ước và tổng các ước của N!

Input

• Số nguyên dương N

Output

• Dòng thứ nhất: số ước của N!
• Dòng thứ hai: tổng các ước của N!

Ví dụ

INPUT

9

OUTPUT

160
1481040