codeforces#P1910H. Sum of Digits of Sums

    ID: 34278 远端评测题 6000ms 512MiB 尝试: 0 已通过: 0 难度: 9 上传者: 标签>*special problembinary searchdata structures*2400

Sum of Digits of Sums

Description

You are given an array $[a_1, a_2, \dots, a_n]$, consisting of positive integers.

For every $i$ from $1$ to $n$, calculate $\sum \limits_{j=1}^{n} F(a_i + a_j)$, where $F(x)$ is the sum of digits of $x$.

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^9$).

Print $n$ integers. The $i$-th of them should be equal to $\sum \limits_{j=1}^{n} F(a_i + a_j)$.

Input

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^9$).

Output

Print $n$ integers. The $i$-th of them should be equal to $\sum \limits_{j=1}^{n} F(a_i + a_j)$.

4
1 3 3 7
3
42 1337 999
18 17 17 15
38 53 47