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>
#pragma GCC optimize(3)
using namespace std;
namespace io {
const int SIZE = 1.1e6;
char buff[SIZE];
char *l = buff, *r = buff;
void init() {
  l = buff;
  r = l + fread(buff, 1, SIZE, stdin);
}
char gc() {
  if (l == r) init();
  if (l == r) return EOF;
  return *(l++);
}
void read(int &x) {
  x = 0;
  char ch = gc();
  while (!isdigit(ch)) ch = gc();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
}
}  // namespace io
using io::read;
namespace {
unsigned long long ADD(unsigned long long x, unsigned long long y) {
  return x + y;
}
void ADDT(unsigned long long &x, unsigned long long y) { x += y; }
unsigned long long SUB(unsigned long long x, unsigned long long y) {
  return x - y;
}
void SUBT(unsigned long long &x, unsigned long long y) { x -= y; }
unsigned long long MUL(unsigned long long x, unsigned long long y) {
  return x * y;
}
}  // namespace
template <int N>
struct Number {
  unsigned long long a[N - 1];
  Number() { memset(a, 0, sizeof(a)); }
  friend ostream &operator<<(ostream &out, const Number<N> &b) {
    out << '{';
    for (int i = 0; i < N - 2; ++i) out << b.a[i] << ',';
    return out << b.a[N - 2] << '}';
  }
  Number operator+(const Number &b) const {
    Number ret;
    for (int i = 0; i < N - 1; ++i) ret.a[i] = ADD(a[i], b.a[i]);
    return ret;
  }
  Number operator-(const Number &b) const {
    Number ret;
    for (int i = 0; i < N - 1; ++i) ret.a[i] = SUB(a[i], b.a[i]);
    return ret;
  }
  Number operator*(const Number &b) const {
    Number ret;
    unsigned long long tmp = 0;
    for (int i = 0; i < N - 1; ++i)
      for (int j = 0; j < N - 1; ++j)
        ADDT(i + j == N - 1 ? tmp : ret.a[i + j >= N ? i + j - N : i + j],
             MUL(a[i], b.a[j]));
    for (int i = 0; i < N - 1; ++i) SUBT(ret.a[i], tmp);
    return ret;
  }
  bool operator<(const Number &b) const {
    for (int i = 0; i < N - 1; ++i)
      if (a[i] != b.a[i]) return a[i] < b.a[i];
    return 0;
  }
  Number operator<<(const int &c) const {
    Number ret;
    unsigned long long tmp = 0;
    for (int i = 0; i < N - 1; ++i)
      ADDT(i + c == N - 1 ? tmp : ret.a[i + c >= N ? i + c - N : i + c], a[i]);
    for (int i = 0; i < N - 1; ++i) SUBT(ret.a[i], tmp);
    return ret;
  }
};
template <int N>
Number<N> fp(Number<N> x, int y) {
  Number<N> ret;
  ret.a[0] = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
const unsigned long long inv5 = 14757395258967641293ull;
template <int N, int LEN>
struct FWT_helper {
  Number<N> w[N][N];
  int pwd[LEN + 1];
  FWT_helper() {
    assert(N > 1);
    for (int i = 0; i < N; ++i) w[i][0].a[0] = 1;
    w[0][1].a[0] = 1;
    w[1][1].a[1] = 1;
    for (int i = 2; i < N; ++i) w[i][1] = w[i - 1][1] * w[1][1];
    for (int i = 0; i < N; ++i)
      for (int j = 2; j < N; ++j) w[i][j] = w[i][j - 1] * w[i][1];
    pwd[0] = 1;
    for (int i = 1; i <= LEN; ++i) pwd[i] = pwd[i - 1] * N;
  }
  void DFT(Number<N> *a) {
    Number<N> b[N];
    for (int i = 0; i < N; ++i) {
      for (int j = 0, d = 0; j < N; ++j, (d += i) >= N ? d -= N : 0)
        b[i] = b[i] + (a[j] << d);
    }
    for (int i = 0; i < N; ++i) a[i] = b[i];
  }
  void IDFT(Number<N> *a) {
    reverse(a + 1, a + N);
    DFT(a);
  }
  void FWT(Number<N> *a, int m, bool rev) {
    for (int i = 0; i < m; ++i)
      for (int cj = 0; cj < pwd[m]; cj += pwd[i + 1])
        for (int j = cj; j < cj + pwd[i]; ++j) {
          Number<N> tmp[N];
          for (int k = 0; k < N; ++k) tmp[k] = a[j + pwd[i] * k];
          if (rev)
            IDFT(tmp);
          else
            DFT(tmp);
          for (int k = 0; k < N; ++k) a[j + pwd[i] * k] = tmp[k];
        }
  }
};
int n;
Number<10> a[100000];
int main() {
  FWT_helper<10, 5> ups;
  read(n);
  for (int i = 0; i < n; ++i) {
    int x;
    read(x);
    ++a[x].a[0];
  }
  ups.FWT(a, 5, 0);
  for (int i = 0; i < ups.pwd[5]; ++i) a[i] = fp(a[i], n);
  ups.FWT(a, 5, 1);
  for (int i = 0; i < n; ++i) {
    for (int j = 8; j >= 7; --j) {
      a[i].a[j - 5] -= a[i].a[j];
    }
    a[i].a[1] -= a[i].a[6];
    a[i].a[0] -= a[i].a[5];
    a[i].a[3] += a[i].a[4];
    a[i].a[2] -= a[i].a[4];
    a[i].a[1] += a[i].a[4];
    a[i].a[0] -= a[i].a[4];
  }
  unsigned long long inv = inv5 * inv5 * inv5 * inv5 * inv5;
  for (int i = 0; i < ups.pwd[5]; ++i) a[i].a[0] = MUL(a[i].a[0], inv);
  for (int i = 0; i < n; ++i) {
    cout << (a[i].a[0] >> 5) % (1ll << 58) << '\n';
  }
}