An là một học sinh giỏi ở trường THCS X, nổi tiếng trong trường với khả năng lập trình xuất sắc của mình. Nhờ sự cố gắng không ngừng nghỉ và niềm đam mê mãnh liệt với Tin học, An đã được chọn tham gia vào đội tuyển thi học sinh giỏi cấp tỉnh. Để chuẩn bị cho kỳ thi quan trọng này, An không ngừng rèn luyện và giải các bài toán lập trình phức tạp. Trong quá trình tìm kiếm bài tập trên mạng Internet, An gặp bài toán sau:

Cho số nguyên dương ~A~ ~(0 < A \le 10^{18})~. Gọi ~B~ là số lớn nhất của ~A~ nếu ~B~ được tạo thành từ các chữ số của ~A~. Ví dụ, nếu ~A = 8347~, số lớn nhất ~B~ sẽ là ~8743~.

Yêu cầu

Cho trước số nguyên dương ~A~, hãy giúp An tìm số lớn nhất ~B~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa một số nguyên dương ~A~.

Dữ liệu đầu ra

Gồm duy nhất số nguyên ~B~ tìm được.

Ràng buộc dữ liệu

• Có 80% số test ứng với 80% số điểm: ~0 < A \le 10^3~.
• Có 20% số test còn lại ứng với 20% số điểm: Không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8347

OUTPUT

8743

Hôm nay nhóm ôn thi học sinh giỏi của An được thầy giáo giảng dạy về kiểu dữ liệu chuỗi (xâu), một trong những nội dung quan trọng và thú vị trong lập trình. Sau khi hiểu rõ các khái niệm cơ bản, thầy giáo giao cho cả nhóm một bài tập thử thách.

Cho một xâu kí tự ~S~ (độ dài xâu ~S \le 10^5~) gồm các chữ cái tiếng Anh in thường từ a đến z và các kí tự chữ số từ 0 đến 9. Người ta mã hóa xâu ~S~ thành xâu ~S'~ theo quy tắc sau:

• Ban đầu xâu ~S'~ rỗng.
• Ghép một kí tự trong xâu ~S~ vào cuối của xâu ~S'~ và lập tức đảo ngược xâu ~S'~. Các kí tự của xâu ~S~ cứ đưa lần lượt như thế vào xâu ~S'~.

Yêu cầu

Hãy tìm xâu ~S'~ khi đã ghép hết các kí tự của xâu ~S~ vào xâu ~S'~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa xâu ~S~.

Dữ liệu đầu ra

Gồm một dòng duy nhất kết quả tìm được là xâu ~S'~.

Ràng buộc dữ liệu

• Có 80% số test ứng với 80% số điểm: Độ dài xâu ~S \le 10^3~.
• Có 20% số test còn lại ứng với 20% số điểm: Không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

abc

OUTPUT

cab

Một buổi chiều sau giờ học, An đi dạo qua công viên và bắt gặp hai bạn nhỏ đang chơi trò ghép số bằng những con bài hình vuông có ghi số trên đó. Một bạn giơ lên con bài có số ~12~, bạn còn lại giơ con bài có số ~45~. Cả hai tranh luận với nhau rằng nếu ghép hai số này lại thì số mới có đặc biệt gì không?

Lúc này, An liền nhớ đến bài học sáng nay. Cậu mỉm cười và ngồi xuống cùng các bạn, giải thích một các đầy hào hứng: "Nếu số ~12~ chia hết cho ~3~ và số ~45~ cũng chia hết cho ~3~, thì khi mình ghép hai số này lại, số mới cũng sẽ chia hết cho ~3~ đấy!"...

Cho dãy ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~. Có bao nhiêu cặp chỉ số ~(i, j)~ ~(1 \le i \le j \le N)~ sao cho khi ta thực hiện thao tác ghép hai số ~A_i, A_j~ (ghép số ~A_i~ sau ~A_j~), ta được một số mới chia hết cho ~3~?

Yêu cầu

Đếm số lượng cặp chỉ số ~(i, j)~ ~(1 \le i \le j \le N)~ thỏa mãn yêu cầu trên.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(A_i \le 10^{50},\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một dòng duy nhất là số lượng cặp ~(i, j)~ thỏa mãn yêu cầu.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~2 \le N \le 10^3;\ A_{i} \le 10^5;\ 1 \le i \le N~.
• Có 20% số test ứng với 20% số điểm: ~10^3 < N \le 10^5;\ A_{i} \le 10^9;\ 1 \le i \le N~.
• Có 20% số test ứng với 20% số điểm: Không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

7
123 4 5 7 10 3 2

OUTPUT

7

Giải thích: Có tổng cộng ~7~ cặp ~(i, j)~ thỏa mãn gồm: ~(1, 6)~, ~(2, 3)~, ~(2, 7)~, ~(3, 4)~, ~(3, 5)~, ~(4, 7)~, ~(5, 7)~.