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 = 7e5 + 10;
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;
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] = 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] = 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)
        (i + j == N - 1 ? tmp : ret.a[i + j >= N ? i + j - N : i + j]) +=
            a[i] * b.a[j];
    for (int i = 0; i < N - 1; ++i) 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)
      (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) 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;
}
void DFT(Number<5> *a) {
  Number<5> b[10];
  for (int i = 0; i < 10; ++i)
    for (int j = 0, t = 0; j < 10; ++j, (t += i) >= 10 ? t -= 10 : 0) {
      if (~t & 1)
        b[i] = b[i] + (a[j] << (t >> 1));
      else
        b[i] = b[i] - (a[j] << ((t + 5) >> 1) % 5);
    }
  for (int i = 0; i < 10; ++i) a[i] = b[i];
}
const int pwd[6] = {1, 10, 100, 1000, 10000, 100000};
const unsigned long long inv5 = 14757395258967641293ull;
void FWT(Number<5> *a, bool rev) {
  for (int i = 0; i < 5; ++i) {
    for (int cj = 0; cj < 100000; cj += pwd[i + 1])
      for (int j = cj; j < cj + pwd[i]; ++j) {
        Number<5> t[10];
        for (int k = 0; k < 10; ++k) t[k] = a[j + k * pwd[i]];
        if (rev) reverse(t + 1, t + 10);
        DFT(t);
        for (int k = 0; k < 10; ++k) a[j + k * pwd[i]] = t[k];
      }
  }
  if (rev) {
    unsigned long long c = inv5 * inv5 * inv5 * inv5 * inv5;
    for (int i = 0; i < 100000; ++i) a[i].a[0] *= c;
  }
}
const int N = 100000;
int n;
Number<5> a[N];
int main() {
  read(n);
  for (int i = 0; i < n; ++i) {
    int x;
    read(x);
    ++a[x].a[0];
  }
  FWT(a, 0);
  for (int i = 0; i < 100000; ++i) a[i] = fp(a[i], n);
  FWT(a, 1);
  for (int i = 0; i < n; ++i) cout << (a[i].a[0] >> 5) % (1ll << 58) << '\n';
}