Problem Statement

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.

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.

Input

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

Output

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