Problem Description

Bajtek is learning column addition. He aligns three numbers of the same length $n$ digit by digit. He now wants to know how many pairs $(i, j)$ (where $1 \leq i \leq j \leq n$) make the fragments of these three numbers from the $i$-th digit to the $j$-th digit form a correct addition equation (that is, the corresponding fragment of the third number equals the sum of the corresponding fragments of the first and second numbers). Leading zeros are allowed in all fragments.

Input Format

The input consists of three lines, each containing an integer (possibly starting with zeros). The three numbers have the same number of digits, all being $n$ digits long ($1 \leq n \leq 10^6$).

Output Format

Output one integer, the number of pairs $(i, j)$ such that the fragments from column $i$ to column $j$ form a correct addition equation.

037523
040834
978367

4

Hint

Sample explanation: The correct addition equations correspond to the following pairs: $(2, 2)$ (because $3 + 4 = 7$), $(2, 4)$ (because $375 + 408 = 783$), $(3, 4)$ (because $75 + 8 = 83$), and $(6, 6)$ (because $3 + 4 = 7$). Note that the fragments corresponding to $(2, 2)$ and $(6, 6)$ are exactly the same, but we still count them separately, for a total of two times. For additions of misaligned fragments, such as $3 + 3 = 6$, we do not count them.

Translated by ChatGPT 5