(password_qn.*)

Do ảnh hưởng của đại dịch Covid-19, ban tổ chức hội thi Tin học trẻ dự kiến sẽ cho các thí sinh thi theo hình thức trực tuyến. Để tham gia thi, thí sinh sẽ được cung cấp một tài khoản và mật khẩu để đăng nhập. Để đảm bảo yếu tố bảo mật, ban tổ chức yêu cầu các thí sinh phải thay đổi mật khẩu ngay sau khi nhận được. Mật khẩu được coi là “an toàn” nếu thỏa mãn đồng thời các điều kiện sau:

• Có độ dài tối thiểu là \(6\);

• Chứa ít nhất \(1\) chữ cái in hoa (‘A’, ‘B’, …, ‘Z’);

• Chứa ít nhất \(1\) chữ cái in thường (‘a’, ‘b’, …, ‘z’);

• Chứa ít nhất \(1\) chữ số (‘0’, ‘1’, …, ‘9’).

Ví dụ các xâu kí tự: “a1B2C3”, “Tinhoc12” là các mật khẩu an toàn, còn các xâu kí tự: “a1B2C”, “a1b2c3”, “A1B2C3”, “TinHoc” không phải là mật khẩu an toàn.

Cho một xâu kí tự \(S\ \)chỉ gồm các loại kí tự: chữ cái in hoa, chữ cái in thường và chữ số. Hãy cho biết có bao nhiêu cặp chỉ số \((i,j)\) thỏa mãn đồng thời hai điều kiện:

• \(1 \leq i < j \leq |S|\), \(\text{trong đó}\ |S|\text{ là độ dài xâu }S\), \(0 \leq |S| \leq 10^{5};\)

• Xâu con \(S_{ij}\) gồm các kí tự liên tiếp từ chỉ số \(i\ \)đến \(j\) của xâu\(\ S\) là mật khẩu an toàn.

Yêu cầu: Cho xâu kí tự \(S\), tính số lượng cặp \((i,j)\) thỏa mãn hai điều kiện trên.

Dữ liệu vào:

+ Gồm một dòng chứa xâu kí tự \(S\).

Dữ liệu ra:

+ Ghi một số nguyên dương là số lượng cặp chỉ số \((i,j)\ \)thỏa mãn điều kiện xâu con \(S_{ij}\) là mật khẩu an toàn.

Ví dụ:

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: \(0\ \leq |S| \leq 10^{3};\)

• 60% số test còn lại ứng với 60% số điểm của bài không có thêm ràng buộc nào.