Xâu con chia hết cho 4

Trên màn hình máy tính bỏ túi hiện lên một xâu $s$ chỉ gồm các chữ số từ 0 đến 9.

Một xâu con liên tiếp của $s$ là một dãy khác rỗng gồm các ký tự đứng liền nhau trong $s$. Mỗi xâu con liên tiếp được hiểu là một số nguyên viết ở hệ thập phân, và số này được phép có chữ số 0 ở đầu (ví dụ xâu con 04 được hiểu là số $4$).

Hãy đếm số lượng xâu con liên tiếp của $s$ mà giá trị của nó chia hết cho $4$. Hai xâu con được coi là khác nhau nếu chúng có vị trí bắt đầu hoặc vị trí kết thúc khác nhau, kể cả khi nội dung giống hệt nhau.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các chữ số từ 0 đến 9.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng xâu con liên tiếp của $s$ chia hết cho $4$.

Ràng buộc

• $1\le |s|\le 3·{10}^5$
• $s$ chỉ gồm các ký tự 0–9
• Kết quả có thể rất lớn, hãy dùng kiểu số nguyên 64-bit

Ví dụ