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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int WBASE = 5;
struct W {
  unsigned long long a[WBASE];
  W() { memset(a, 0, sizeof(a)); }
  W(unsigned long long x) {
    memset(a, 0, sizeof(a));
    a[0] = x;
  }
};
void operator+=(W &p, const W &q) {
  for (int i = (0); i < (WBASE); ++i) p.a[i] += q.a[i];
}
W operator*(const W &p, const W &q) {
  W ret;
  for (int i = (0); i < (WBASE); ++i)
    for (int j = (0); j < (WBASE); ++j)
      ret.a[(i + j) % WBASE] += p.a[i] * q.a[j];
  return ret;
}
bool operator==(const W &p, const W &q) {
  for (int i = (0); i < (WBASE); ++i)
    if (p.a[i] != q.a[i]) return false;
  return true;
}
void print(const W &p) {
  int cnt = 0;
  for (int i = (0); i < (WBASE); ++i)
    if (p.a[i] != 0) ++cnt;
  if (cnt >= 2) printf("(");
  bool any = false;
  for (int i = (0); i < (WBASE); ++i) {
    if (p.a[i] == 0) continue;
    if (!any)
      any = true;
    else
      printf("+");
    printf("%llu", p.a[i]);
    if (i >= 1) printf("w");
    if (i >= 2) printf("^%d", i);
  }
  if (cnt >= 2) printf(")");
  if (cnt == 0) printf("0");
}
struct Pol {
  vector<W> a;
};
Pol operator*(const Pol &p, const Pol &q) {
  Pol ret;
  for (int i = (0); i < (((int)(p.a).size())); ++i)
    for (int j = (0); j < (((int)(p.a).size())); ++j) {
      while (i + j >= ((int)(ret.a).size())) ret.a.push_back(W());
      ret.a[i + j] += p.a[i] * q.a[j];
    }
  return ret;
}
void print(const Pol &p) {
  bool any = false;
  for (int i = (0); i < (((int)(p.a).size())); ++i) {
    if (p.a[i] == W(0)) continue;
    if (!any)
      any = true;
    else
      printf("+");
    print(p.a[i]);
    if (i >= 1) printf("x");
    if (i >= 2) printf("^%d", i);
  }
  if (!any) printf("0");
}
W eval(const Pol &p, const W &w) {
  W cur(1), ret(0);
  for (int i = (0); i < (((int)(p.a).size())); ++i) {
    ret += p.a[i] * cur;
    cur = cur * w;
  }
  return ret;
}
const int MAXDIM = 5;
const int XBASE = 10;
const unsigned long long MOD = 1ULL << 58;
unsigned long long pw(unsigned long long x, unsigned long long n) {
  unsigned long long ret = 1;
  while (true) {
    if (n & 1) ret *= x;
    if ((n >>= 1) == 0) return ret;
    x *= x;
  }
}
const int MAXN = 100000;
const unsigned long long INV5 = 57646075230342349;
W pw(W x, unsigned long long n) {
  W ret(1);
  while (true) {
    if (n & 1) ret = ret * x;
    if ((n >>= 1) == 0) return ret;
    x = x * x;
  }
}
int nitem, n = MAXN, ndim = MAXDIM;
int cnt[MAXN];
unsigned long long ans[MAXN];
int step[MAXDIM + 1];
W val[MAXN];
W tmp[XBASE];
void solve() {
  step[0] = 1;
  for (int i = (0); i < (ndim); ++i) step[i + 1] = step[i] * XBASE;
  for (int i = (0); i < (n); ++i) val[i] = W(cnt[i]);
  for (int dim = (0); dim < (ndim); ++dim)
    for (int i = 0; i < n; i += step[dim + 1])
      for (int j = (0); j < (step[dim]); ++j) {
        memset(tmp, 0, sizeof(tmp));
        W a(1), proot(0);
        proot.a[1] = -1;
        for (int x = (0); x < (XBASE); ++x) {
          W b(1);
          for (int y = (0); y < (XBASE); ++y) {
            tmp[x] += val[i + j + y * step[dim]] * b;
            b = b * a;
          }
          a = a * proot;
        }
        for (int x = (0); x < (XBASE); ++x) {
          val[i + j + x * step[dim]] = tmp[x];
        }
      }
  for (int i = (0); i < (n); ++i) val[i] = pw(val[i], nitem);
  for (int dim = (0); dim < (ndim); ++dim)
    for (int i = 0; i < n; i += step[dim + 1])
      for (int j = (0); j < (step[dim]); ++j) {
        memset(tmp, 0, sizeof(tmp));
        W a(1), iproot(0);
        iproot.a[WBASE - 1] = -1;
        for (int x = (0); x < (XBASE); ++x) {
          W b(1);
          for (int y = (0); y < (XBASE); ++y) {
            tmp[x] += val[i + j + y * step[dim]] * b;
            b = b * a;
          }
          a = a * iproot;
        }
        for (int x = (0); x < (XBASE); ++x) {
          val[i + j + x * step[dim]] = tmp[x];
        }
      }
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (WBASE); ++j) val[i].a[j] -= val[i].a[WBASE - 1];
  unsigned long long mlt = pw(INV5, ndim);
  for (int i = (0); i < (nitem); ++i)
    ans[i] = ((val[i].a[0] * mlt) >> ndim) % MOD;
}
void run() {
  scanf("%d", &nitem);
  memset(cnt, 0, sizeof(cnt));
  for (int i = (0); i < (nitem); ++i) {
    int x;
    scanf("%d", &x);
    ++cnt[x];
  }
  solve();
  for (int i = (0); i < (nitem); ++i) printf("%llu\n", ans[i]);
}
int main() {
  run();
  return 0;
}