[AdditionalFile5681.zip](file://AdditionalFile5681.zip?type=additional_file)

#5681. 「PA 2026」Dodawanie

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 3 Dodawanie

Bajtek 正在学习笔算加法。他将三个长度相同且为 $n$ 的数字垂直排列（上下对齐）。他现在想知道，对于多少对 $(i, j)$ （其中 $1 \leq i \leq j \leq n$），这三个数从第 $i$ 位到第 $j$ 位构成的数字满足正确的加法关系（即第三个数在考虑区间内的数字等于前两个数相应数字之和）。所有数字均允许包含前导零。

输入格式

输入包含三行，每行一个整数（可能以零开头）。这三个数字都包含相同位数的 $n$ $(1 \leq n \leq 10^{6})$ 个数字。

输出格式

输出一个整数，表示有多少对 $(i, j)$ 对应的从第 $i$ 位到第 $j$ 位的区间构成了正确的加法关系。

样例

输入

037523
040834
978367

输出

4

对于以下数对，可以得到正确的加法关系：

• $(2,2)$ （因为 $3+4=7$）；
• $(2,4)$ （因为 $375+408=783$）；
• $(3,4)$ （因为 $75+8=83$）；
• $(6,6)$ （因为 $3+4=7$）。

注意，尽管 $(2,2)$ 和 $(6,6)$ 的区间内容相同，但我们仍将它们分别计入。我们不计算未对齐的数字之和，例如 $3+3=6$（此处指不对应相同位置的区间）。