AT_arc222_d [ARC222D] Shift and Add

定义一个非负整数 $n$ 的**数位和**为将 $n$ 用十进制表示后各位数字之和。例如，$2026$ 的数位和为 $2+0+2+6=10$。 给定正整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。 利用 $A$ 和 $B$，定义整数序列 $X=(X_0,X_1,X_2,\ldots,X_N)$ 规则如下： - 设 $X_0 = 0$。 - 对于每个 $i=1,2,\ldots,N$，可以选择 $X_i=10X_{i-1}+A_i$ 或 $X_i=10X_{i-1}+B_i$ 之一来确定 $X_i$。 对于每个 $k=1,2,\ldots,N$，求 $X_k$ 能够取得的最小数位和。 每个 $k$ 都独立计算，也就是说对于不同的 $k$，可以选择不同方式确定序列 $X$ 以使 $X_k$ 的数位和最小。

输入格式如下： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

对每个 $k=1,2,\ldots,N$，输出 $X_k$ 能取得的最小数位和，数之间以空格分隔。

### 样例解释 1 可行的整数序列 $X=(X_0,X_1,X_2)$ 有如下四种： - $X = (0, 123, 1674)$ - $X = (0, 123, 1452)$ - $X = (0, 456, 5004)$ - $X = (0, 456, 4782)$ $X_1$ 能取得的最小数位和是 $6$，等于 $123$ 的数位和。 $X_2$ 能取得的最小数位和是 $9$，等于 $5004$ 的数位和。 ### 约束条件 - $1\leq N\leq 20000$ - $1\leq A_i\leq 10^9-1$ - $1\leq B_i\leq 10^9-1$ - 所有输入值均为整数。 由 ChatGPT 5 翻译