Trong một kỳ thi, số báo danh của thí sinh có định dạng như sau: CC-NNN.NN. Trong đó:

• Hai ký tự đầu tiên là chữ cái tiếng Anh in hoa từ A đến Z.
• Ký tự thứ ba là ký tự -.
• Tiếp theo là ba ký tự chữ số (từ 0 đến 9).
• Ký tự thứ bảy là ký tự ..
• Cuối cùng là hai ký tự chữ số (từ 0 đến 9).

Do quá trình nhập liệu thủ công, số báo danh có thể bị sai định dạng. Cho một xâu mô tả một
số báo danh cần kiểm tra. Các ký tự trong xâu được đánh số bắt đầu từ \(1\).

Yêu cầu: Hãy xác định số báo danh đó đúng định dạng hay không. Nếu số báo danh đúng định
dạng thì in ra \(0\), ngược lại nếu số báo danh không đúng định dạng thì in ra vị trí ký tự đầu tiên bị sai định dạng.

Input

• Một dòng duy nhất gồm xâu ký tự có độ dài không quá \(50\) là số báo danh cần kiểm tra.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

AB.123-45

3

AB-123 

7

AB-123.45 

0

AB-123.45.678 

10

Cho một chuỗi ký tự mô tả công thức hóa học của một chất hữu cơ chỉ gồm \(3\) loại ký tự C, H, O (tương ứng với các nguyên tố Carbon, Hydrogen, Oxygen) và các chữ số.

Liền sau mỗi nguyên tố có thể là một số nguyên có giá trị không vượt quá \(10^{12}\) mô tả số lượng nguyên tử tương ứng với nguyên tố đó (nếu không có số nguyên liền sau mỗi nguyên tố thì có thể hiểu là số lượng nguyên tử tương ứng với nguyên tố đó bằng \(1\)).

Ví dụ: Một chuỗi ký tự mô tả công thức hóa học như sau: C6H12O6, CH3OH, C2H5OH, \(\ldots\)

Yêu cầu: Cho các giá trị nguyên tử khối của các nguyên tố như sau: \(C = 12, H = 1, O = 16\). Hãy tính phân tử khối của chất hữu cơ được mô tả bởi chuỗi ký tự đã cho.

Input

• Một dòng duy nhất gồm chuỗi ký tự có độ dài không vượt quá \(10^{5}\) mô tả công thức hóa học của một chất hữu cơ, chỉ gồm \(3\) loại ký tự C, H, O và các chữ số.

Output

• Một số nguyên dương duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): số lượng nguyên tử tương ứng với nguyên tố có giá trị trong đoạn \([1, 9]\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc thêm.

Example

CH3OH

32

C6H12O6

180

C2H5OH

46

Cho dãy số gồm \(N\) số nguyên \(A_{1}, A_{2}, \ldots, A_{N}\) có giá trị thuộc tập hợp \(\{0, 1, 2, 3\}\).
Yêu cầu: Đếm số lượng các đoạn con gồm các số nguyên liên tiếp của dãy số sao cho:

• Gồm đúng ba loại giá trị;
• Số lần xuất hiện của các loại giá trị bằng nhau.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((N \leq 10^6)\) là số lượng số trong dãy;
• Dòng thứ hai gồm \(N\) số nguyên \(A_{1}, A_{2}, \ldots, A_{N}\) \((0 \leq A_{i} \leq 3)\) mô tả dãy số.

Output

• Một dòng duy nhất gồm một số nguyên là số đoạn con thoả mãn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 1000\)
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc thêm

Example

11
0 1 2 1 2 0 3 1 0 3 1

9

Trong bảng chữ cái tiếng Anh, các ký tự nguyên âm là: a, e, o, u, i, các ký tự còn lại là phụ âm. Mỗi ký tự đều có một mã ASCII là một số nguyên dương: mã ASCII của ký tự a là \(97\), mã ASCII của ký tự b là \(98\), \(\ldots\), mã ASCII của ký tự z là \(122\).

Cho một xâu ký tự \(S\) chỉ gồm các chữ cái in thường trong bảng chữ cái tiếng Anh và một số nguyên \(K\). Xét một xâu con liên tiếp của \(S\): gọi \(X\) là tổng mã ASCII của các ký tự nguyên âm trong xâu con, gọi \(Y\) là tổng mã ASCII của các ký tự phụ âm trong xâu con. Xâu con được coi là xâu đặc biệt nếu thỏa mãn:

• \(X > 0\).
• \(Y > 0\).
• \(0 \leq X - Y \leq K\).
• Tất cả các nguyên âm đều nằm ở một phía của xâu con. Ví dụ: aexyz, you, aeiout.

Yêu cầu: Hãy đếm số lượng xâu con liên tiếp của xâu \(S\) là xâu đặc biệt.

Input

• Dòng đầu tiên gồm xâu \(S\) có độ dài không vượt quá \(10^6\);
• Dòng thứ hai gồm số nguyên \(K\) \((0 \leq K \leq 10^6)\).

Output

• Một số nguyên duy nhất là số lượng xâu con đặc biệt.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): độ dài của xâu \(S\) không vượt quá \(100\).
• Subtask \(2\) (\(30\%\) số điểm): độ dài của xâu \(S\) không vượt quá \(5000\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc thêm.

Example

erhdeu
4

1

Trong một trò chơi tìm kho báu, bản đồ được mã hóa thành một bảng hình chữ nhật có \(M\) hàng và \(N\) cột. Các hàng được đánh số từ \(1\) đến \(M\), các cột được đánh số từ \(1\) đến \(N\), ô ở hàng \(i\), cột \(j\) trên bảng gọi là ô \((i,j)\) có giá trị là một trong bốn loại ký tự:

• 0: mô tả ô đất liền;
• 1: mô tả ô biển;
• @: mô tả ô vị trí xuất phát của nhân vật (luôn ở trên đất liền);
• #: mô tả ô chứa kho báu (luôn ở trên đất liền).

Nhân vật không biết bơi nên sẽ không thể đi vào ô biển và luôn luôn đứng ở ô đất liền. Nhân vật có thể di chuyển trên bản đồ theo các cách sau:

• Đi bộ tự do sang các ô đất liền chung cạnh;
• Nhảy qua biển theo một trong \(4\) hướng Đông, Tây, Nam, Bắc đến ô đất liền đầu tiên trên hướng nhảy đó.

Yêu cầu: Nhân vật xuất phát ở ô có ký tự @ và muốn di chuyển đến ô có ký tự # chứa kho báu. Vì mỗi lần nhảy qua biển tiêu hao nhiều năng lượng, hãy giúp nhân vật tìm số lần nhảy nhỏ nhất để có thể di chuyển đến ô có kho báu.

Input

• Dòng đầu tiên gồm hai số nguyên \(M\), \(N\) (\(1 \leq M, N \leq 10^3\));
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) ký tự mô tả bản đồ.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): tối đa một cột chứa toàn ô số 1 và một hàng chứa toàn ô số 1;
• Subtask \(2\) (\(30\%\) số điểm): \(M \leq 2\);
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc thêm.

Example

4 8
@0011011
11111011
1001101#
11111011

2

1 9
@1011101#

3