1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define V vector
using namespace std;
typedef long long ll;
int mod = 119<<23|1;
ll infll = 2e18;
int add(int a, int b) { return a+b >= mod ? a+b-mod : a+b; }
int sub(int a, int b) { return add(mod-b, a); }
int mul(int a, int b) { return int(a*ll(b)%mod); }
int fpow(int a, int b = mod-2) {
    int res = 1;
    while(b) {
        if (b & 1) res = mul(res, a);
        b >>= 1, a = mul(a, a);
    }
    return res;
}
int divd(int a, int b) {
    assert(b != 0);
    return mul(a, fpow(b));
}

template<typename... Args>
void read(Args&... args) {
    auto read_one = [&](auto &a) {
        a = 0; int c = getchar_unlocked();
        while (c < '0' || '9' < c) c = getchar_unlocked();
        while ('0' <= c && c <= '9') a = a*10+c-'0', c = getchar_unlocked();
    };
    return (read_one(args), ...);
}

void answer() {
    mod = 10; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    ios_base::sync_with_stdio(0); cin.tie(0);
    V<string> s(3);
    cin >> s[0] >> s[1] >> s[2];

    int n = ssize(s[0]);
    V<V<int>> t(3, V<int>(n+2, 0));
    for (int l = 0; l < 3; ++l)
        for (int i = 1; i <= n; ++i) t[l][i] = s[l][i-1]-'0';

    // for (int l = 0; l < 3; ++l) {
    //     for (int i = 1; i <= n; ++i) printf("%d ", t[l][i]);
    //     printf("\n");
    // }
    
    ll result = 0;
    int l = n+1, sub_cnt = 0;
    V<int> not_normal(n+2);
    for (int r = n; r >= 1; sub_cnt -= not_normal[r--]) {
        if (l <= r) {
            // printf("b: %d %d\n", l, r);
            if (add(t[0][r], t[1][r]) == t[2][r]) result += r-l+1-sub_cnt;
            continue;
        }
        l = r+1, sub_cnt = 0;
        int carry = 0;
        while (1 < l) {
            if (add(add(t[0][l-1], t[1][l-1]), carry) == t[2][l-1]) --l;
            else break;
            if ((t[0][l] + t[1][l] + carry) / 10) carry = 1, not_normal[l] = 1, ++sub_cnt;
            else carry = 0;
        }
        // printf("a: %d %d\n", l, r);
        result += r-l+1-sub_cnt;
    }
    printf("%lld\n", result);
}
int main() {
    int T = 1; //scanf("%d", &T);
    for (++T; --T; ) answer();
    return 0;
}