310929: CF1910H. Sum of Digits of Sums

H. Sum of Digits of Sumstime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$.

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)$.

ExamplesInput

4
1 3 3 7

Output

18 17 17 15 

Input

3
42 1337 999

Output

38 53 47 

题目大意：给定一个由正整数组成的数组 $[a_1, a_2, \dots, a_n]$，对于每个 $i$ 从 $1$ 到 $n$，计算 $\sum \limits_{j=1}^{n} F(a_i + a_j)$，其中 $F(x)$ 是 $x$ 的各位数字之和。

输入数据格式：
- 第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^9$)。

输出数据格式：
- 输出 $n$ 个整数，第 $i$ 个数应为 $\sum \limits_{j=1}^{n} F(a_i + a_j)$。题目大意：给定一个由正整数组成的数组 $[a_1, a_2, \dots, a_n]$，对于每个 $i$ 从 $1$ 到 $n$，计算 $\sum \limits_{j=1}^{n} F(a_i + a_j)$，其中 $F(x)$ 是 $x$ 的各位数字之和。 输入数据格式： - 第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i < 10^9$)。 输出数据格式： - 输出 $n$ 个整数，第 $i$ 个数应为 $\sum \limits_{j=1}^{n} F(a_i + a_j)$。