Anny là một người rất đam mê khám phá, tình cờ Anny có được một tấm bản đồ kho báu. Trong hành trình tìm kiếm, Anny tìm được cửa kho báu thứ nhất, trên cửa có ghi một dãy ký tự tiếng Anh in thường liên tiếp nhau. Bản đồ kho báu cho biết mật mã để mở cửa lần này là số lượng xâu con đặc biệt của dãy ký tự trên.

Biết rằng, một xâu con đặc biệt là một dãy ký tự liên tiếp bắt đầu bằng một nguyên âm ('a', 'e', 'i', 'o', 'u') và kết thúc bằng một phụ âm hoặc ngược lại.

Yêu cầu: Hãy giúp Anny đếm số lượng xâu con đặc biệt của xâu ký tự trên cửa.

Input

Vào từ tập tin XAUCON.INP, gồm một dòng duy nhất chứa dãy ký tự theo đề bài.

Output

Ghi vào tập tin XAUCON.OUT, gồm một số nguyên duy nhất là mật mã tìm được.

Ví dụ

Input

abco

Output

4

Giải thích

Các xâu con đặc biệt là: ab, abc, bco, co.

Giới hạn

• Xâu chỉ gồm các chữ cái tiếng Anh in thường.
• Có 50% số test ứng với 50% số điểm có chiều dài xâu ~\le 10^3~;
• Có 50% số test ứng với 50% số điểm có chiều dài xâu ~\le 5 \times 10^5~.

Sau khi mở được cửa thứ nhất của kho báu, Anny cần vượt qua một chướng ngại vật để mở cửa thứ hai. Chướng ngại vật lần này là một ma trận các số nguyên dương không vượt quá ~10^9~ có chứa các cạm bẫy.

Bản đồ kho báu mô tả ma trận gồm ~N~ hàng và ~M~ cột. Cạm bẫy được đặt trên các hàng và các cột có chứa giá trị lớn nhất hoặc nhỏ nhất của ma trận.

Mật mã để mở cửa thứ hai của kho báu là số lượng ô của ma trận không chứa cạm bẫy.

Yêu cầu: Hãy giúp Anny đếm số ô của ma trận không chứa cạm bẫy.

Input

Vào từ tập tin CAMBAY.INP, có cấu trúc như sau:

• Dòng đầu gồm hai số nguyên dương ~N~ và ~M~ được viết cách nhau một ký tự khoảng trắng;
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên, các số được viết cách nhau một ký tự khoảng trắng.

Output

Ghi vào tập tin CAMBAY.OUT, gồm một số duy nhất là mật mã tìm được.

Ví dụ

Input

4 4
2 3 5 4
3 2 4 2
1 2 3 4
4 3 4 2

Output

4

Giải thích

Giá trị lớn nhất của ma trận là ~5~ (ở hàng ~1~, cột ~3~), giá trị nhỏ nhất là ~1~ (ở hàng ~3~, cột ~1~). Cạm bẫy được đặt trên các hàng ~1, 3~ và các cột ~1, 3~. Các ô không chứa cạm bẫy là ~(2, 2)~, ~(2, 4)~, ~(4, 2)~, ~(4, 4)~.

Giới hạn

• Các phần tử của ma trận là số nguyên dương không vượt quá ~10^9~.
• Có 40% số test ứng với 40% số điểm có: ~1 \le N, M \le 10~;
• Có 30% số test ứng với 30% số điểm có: ~1 \le N, M \le 100~;
• Có 30% số test ứng với 30% số điểm có: ~1 \le N \times M \le 5 \times 10^6~.

Sau khi qua cửa thứ hai, Anny gặp được cánh cửa thứ ba. Để mở cửa Anny cần có mật mã. Mật mã lần này là chữ số cuối cùng của phép toán ~a^n~ được ghi trên bản đồ kho báu.

Yêu cầu: Hãy giúp Anny tìm chữ số cuối cùng của phép toán ~a^n~.

Input

Vào từ tập tin MATMA.INP, gồm hai số nguyên dương ~a~ và ~n~ được viết cách nhau một ký tự khoảng trắng.

Output

Ghi vào tập tin MATMA.OUT, gồm một số duy nhất là mật mã tìm được.

Ví dụ

Input

2 5

Output

2

Giải thích

~2^5 = 32~, chữ số cuối cùng là ~2~.

Giới hạn

• Có 40% số test ứng với 40% số điểm có: ~1 \le a \le 9~; ~1 \le n \le 10^3~;
• Có 30% số test ứng với 30% số điểm có: ~1 \le a \le 10^6~; ~1 \le n \le 10^6~;
• Có 30% số test ứng với 30% số điểm có: ~1 \le a \le 10^9~; ~1 \le n \le 10^{18}~.

Sau khi tìm được kho báu, Anny sắp xếp một chuyến đi du lịch vòng quanh thế giới. Có ~N~ điểm du lịch Anny muốn ghé thăm, được đánh số từ ~1~ đến ~N~. Giữa các điểm du lịch có các chuyến bay đi trực tiếp; chi phí để bay từ điểm ~i~ đến điểm ~j~ là ~C_{ij}~ (có thể khác ~C_{ji}~) và ~1 \le C_{ij} \le 10^9~.

Anny muốn chọn một hành trình du lịch qua ~N~ điểm, mỗi điểm chỉ ghé thăm một lần duy nhất. Với tinh thần tiết kiệm, Anny muốn chọn một hành trình du lịch với tổng chi phí nhỏ nhất.

Yêu cầu: Hãy giúp Anny tìm được hành trình có tổng chi phí nhỏ nhất.

Input

Vào từ tập tin DULICH.INP, có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương ~N~;
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo, ghi ~N~ số nguyên không âm ~C_{ij}~ là chi phí bay từ điểm ~i~ đến điểm ~j~ ~(1 \le j \le N)~.

Output

Ghi vào tập tin DULICH.OUT, gồm một số nguyên dương duy nhất là tổng chi phí của hành trình nhỏ nhất tìm được.

Ví dụ

Input

6
0 1 2 1 3 4
5 0 3 2 3 4
4 1 0 2 1 2
4 2 5 0 4 3
2 5 3 5 0 2
5 4 3 3 1 0

Output

8

Giải thích

Một hành trình có tổng chi phí nhỏ nhất là ~6 \to 5 \to 1 \to 3 \to 2 \to 4~ với tổng chi phí ~1 + 2 + 2 + 1 + 2 = 8~ (hành trình có thể bắt đầu tại một điểm bất kỳ và không cần quay lại điểm xuất phát).

Giới hạn

• ~1 \le C_{ij} \le 10^9~ với ~i \ne j~.
• Có 50% số test ứng với 50% số điểm có: ~5 < N \le 10~;
• Có 50% số test ứng với 50% số điểm có: ~10 < N \le 15~.