Problem: Let's define radix sum of number a consisting of digits a_1, … ,a_k and number b consisting of digits b_1, … ,b_k(we add leading zeroes to the shorter number to match longer length) as number s(a,b) consisting of digits (a_1+b_1)mod 10, … ,(a_k+b_k)mod 10. The radix sum of several integers is defined as follows: s(t_1, … ,t_n)=s(t_1,s(t_2, … ,t_n))

You are given an array x_1, … ,x_n. The task is to compute for each integer i (0 ≤ i < n) number of ways to consequently choose one of the integers from the array n times, so that the radix sum of these integers is equal to i. Calculate these values modulo 2^{58}.

Input

The first line contains integer n — the length of the array(1 ≤ n ≤ 100000).

The second line contains n integers x_1, … x_n — array elements(0 ≤ x_i < 100000).

Output

Output n integers y_0, …, y_{n-1} — y_i should be equal to corresponding number of ways modulo 2^{58}.

Examples

Input


2
5 6


Output


1
2


Input


4
5 7 5 7


Output


16
0
64
0

Note

In the first example there exist sequences: sequence (5,5) with radix sum 0, sequence (5,6) with radix sum 1, sequence (6,5) with radix sum 1, sequence (6,6) with radix sum 2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
inline bool chmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool chmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
bool IN(long long x, long long l, long long r) { return l <= x and x <= r; }
void GG() {
  puts("-1");
  exit(0);
}
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int MM = 1e5 + 10;
long long fac[MM], facinv[MM], Inv[MM];
long long Comb(int n, int m) {
  return n < 0 or m < 0 or n < m
             ? 0
             : fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}
void PRE() {
  fac[0] = 1;
  for (int i = (1), I = (MM - 1); i <= I; i++) fac[i] = fac[i - 1] * i % MOD;
  facinv[MM - 1] = invm(fac[MM - 1]);
  for (int i = (MM - 1), I = (1); i >= I; i--)
    facinv[i - 1] = facinv[i] * i % MOD;
  Inv[1] = 1;
  for (int i = (2), I = (MM - 1); i <= I; i++)
    Inv[i] = (MOD - MOD / i) * Inv[MOD % i] % MOD;
}
const int N = 1e6 + 10;
unsigned long long t[10];
struct Num {
  unsigned long long a[5];
  Num() { memset(a, 0, sizeof a); }
  unsigned long long &operator[](int x) { return a[x]; }
  void operator+=(Num b) {
    for (int i = (0), I = (4); i <= I; i++) a[i] += b[i];
  }
  void operator*=(unsigned long long b) {
    for (int i = (0), I = (4); i <= I; i++) a[i] *= b;
  }
  Num operator*(Num b) {
    memset(t, 0, sizeof t);
    for (int i = (0), I = (4); i <= I; i++)
      if (a[i])
        for (int j = (0), I = (4); j <= I; j++)
          if (b[j]) t[i + j] += a[i] * b[j];
    Num c;
    for (int i = (0), I = (4); i <= I; i++) c[i] = t[i] + t[i + 5];
    return c;
  }
  friend Num operator^(Num x, unsigned long long e) {
    Num ans;
    ans[0] = 1;
    while (e) {
      if (e & 1) ans = ans * x;
      x = x * x;
      e >>= 1;
    }
    return ans;
  }
};
namespace kFWT {
const int K = 10, M = 100000;
Num B[M];
Num omega[2][K * K];
void pre() {
  omega[0][0][0] = 1;
  omega[0][1][3] = -1;
  for (int i = (2), I = (K * K - 1); i <= I; i++)
    omega[0][i] = omega[0][i - 1] * omega[0][1];
  for (int i = (0), I = (K * K - 1); i <= I; i++)
    omega[1][i] = omega[0][i], reverse(omega[1][i].a + 1, omega[1][i].a + 5);
}
void FWT(Num A[], int op = 0) {
  for (int w = 1; w < M; w *= K) {
    for (int up = 0; up < M; up += w * K)
      for (int i = 0, ii = 0; i < K; i++, ii += w)
        for (int j = 0, jj = 0; j < K; j++, jj += w)
          for (int dw = 0; dw < w; dw++)
            B[up + ii + dw] += omega[op][i * j] * A[up + jj + dw];
    for (int x = (0), I = (M - 1); x <= I; x++) A[x] = B[x], B[x] *= 0;
  }
}
};  // namespace kFWT
Num A[N];
void main() {
  int n = qread();
  for (int i = (1), I = (n); i <= I; i++) A[qread()][0]++;
  kFWT::pre();
  kFWT::FWT(A);
  for (int i = (0), I = (kFWT::M - 1); i <= I; i++) A[i] = A[i] ^ n;
  kFWT::FWT(A, 1);
  for (int x = (0), I = (n - 1); x <= I; x++) {
    unsigned long long num = A[x][0] - A[x][1];
    for (int i = (1), I = (3); i <= I; i++) assert(A[x][i] == A[x][i + 1]);
    num *= 6723469279985657373ull;
    assert(num % (1ll << (5)) == 0);
    write1(num / (1ll << (5)) % (1ll << (58)));
  }
}
};  // namespace mine
signed main() {
  mine::main();
  printf("");
}