AT_arc222_d [ARC222D] 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.

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 $

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

### Sample Explanation 1 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.