AT_arc222_d.Shift and Add

Define the digit sum of a non-negative integer $n$ as the sum of the digits when $n$ is written in decimal notation. For example, the digit sum of $2026$ is $2+0+2+6=10$.

You are given positive integer sequences $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$.

Using $A$ and $B$, define an integer sequence $X=(X_0,X_1,X_2,\ldots,X_N)$ as follows:

• Set $X_0 = 0$.
• For each $i=1,2,\ldots,N$, choose one of $X_i = 10X_{i-1} + A_i$ and $X_i = 10X_{i-1} + B_i$ to determine $X_i$.

For each $k=1,2,\ldots,N$, find the minimum possible digit sum of $X_k$.

Solve independently for each $k$. That is, for different $k$, the way to determine the integer sequence $X$ that minimizes the digit sum of $X_k$ may be different.

定义一个非负整数 $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_k$ 的数位和最小的序列 $X$ 的构造方式可以不同。

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$

输入从标准输入以如下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$

For $k=1,2,\ldots,N$, output the minimum possible digit sum of $X_k$, space-separated.

对于 $k=1,2,\ldots,N$，输出 $X_k$ 的最小可能各位数字之和，以空格分隔。

Sample 1 Explanation:
The possible integer sequences $X=(X_0,X_1,X_2)$ are the following four:

• $X = (0, 123, 1674)$
• $X = (0, 123, 1452)$
• $X = (0, 456, 5004)$
• $X = (0, 456, 4782)$

The minimum possible digit sum of $X_1$ is $6$, which is the digit sum of $123$.

The minimum possible digit sum of $X_2$ is $9$, which is the digit sum of $5004$.

Constraints

• $1\leq N\leq 20000$
• $1\leq A_i \leq 10^9-1$
• $1\leq B_i \leq 10^9-1$
• All input values are integers.

样例 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$
• 所有输入值均为整数。