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("Ofast")
using namespace std;
namespace io {
const int L = (1 << 20) + 1;
char buf[L], *S, *T, c;
char getchar() {
  if (__builtin_expect(S == T, 0)) {
    T = (S = buf) + fread(buf, 1, L, stdin);
    return (S == T ? EOF : *S++);
  }
  return *S++;
}
int inp() {
  int x = 0, f = 1;
  char ch;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return x * f;
}
unsigned inpu() {
  unsigned x = 0;
  char ch;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    ;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return x;
}
long long inp_ll() {
  long long x = 0;
  int f = 1;
  char ch;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  return x * f;
}
char B[25], *outs = B + 20, *outr = B + 20;
template <class T>
inline void print(register T a, register char x = 0) {
  if (x) *--outs = x, x = 0;
  if (!a)
    *--outs = '0';
  else
    while (a) *--outs = (a % 10) + 48, a /= 10;
  if (x) *--outs = x;
  fwrite(outs, outr - outs, 1, stdout);
  outs = outr;
}
};  // namespace io
using io ::inp;
using io ::inp_ll;
using io ::inpu;
using io ::print;
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
long long power(long long a, long long b, long long p) {
  if (!b) return 1;
  long long t = power(a, b / 2, p);
  t = t * t % p;
  if (b & 1) t = t * a % p;
  return t;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <class T>
inline void freshmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
inline void freshmax(T &a, const T &b) {
  if (a < b) a = b;
}
const int MAXN = 100000;
const int DEG = 5;
const int BASE = 10;
const int MAXP = 10000000;
const int MOD = 1000000007;
const f80 MI = f80(1) / MOD;
const long long INF = 10000000000000000LL;
const long long inf = 5000000000000LL;
int n;
int modBASE[1111], modDEG[1111];
template <class T>
struct node {
  T v[DEG];
  node(T c = 0, int k = 0) {
    for (int i = 0; i < DEG; ++i) v[i] = 0;
    v[k] = c;
  }
  node &operator+=(const node &A) {
    for (int i = 0; i < DEG; ++i) v[i] += A.v[i];
    return *this;
  }
  friend node operator*(const node &A, const node &B) {
    node ret;
    for (int i = 0; i < DEG; ++i)
      for (int j = 0; j < DEG; ++j) ret.v[modDEG[i + j]] += A.v[i] * B.v[j];
    return ret;
  }
  node &operator*=(const node &A) { return *this = *this * A; }
  node shl(int shift) {
    node ret;
    for (int i = 0; i < DEG; ++i)
      ret.v[modDEG[i + shift]] = (shift & 1) ? -v[i] : v[i];
    return ret;
  }
};
template <class T, class V>
T power(T a, V n) {
  if (n == 0) return 1;
  T t = power(a, n / 2);
  t = t * t;
  if (n & 1) t = t * a;
  return t;
}
node<u64> a[MAXN];
void fft(bool inv = 0) {
  int shift = inv ? BASE - 1 : 1;
  for (int step = 1; step < MAXN; step *= BASE) {
    for (int offset = 0; offset < MAXN; ++offset) {
      if (offset / step % BASE != 0) continue;
      node<u64> to[BASE];
      for (int i = 0; i < BASE; ++i)
        for (int j = 0; j < BASE; ++j)
          to[i] += a[offset + j * step].shl(modBASE[i * j * shift]);
      for (int i = 0; i < BASE; ++i) a[offset + i * step] = to[i];
    }
  }
}
int main() {
  for (int i = 0; i < 1111; ++i) {
    modBASE[i] = i % BASE;
    modDEG[i] = i % DEG;
  }
  n = inp();
  for (int i = 1; i <= n; ++i) a[inp()] += 1;
  fft();
  for (int i = 0; i < MAXN; ++i) a[i] = power(a[i], n);
  fft(1);
  for (int i = 0; i < n; ++i) {
    u64 ans = a[i].v[0] - a[i].v[4];
    ans >>= 5;
    ans *= 6723469279985657373ULL;
    print(ans & ((1ULL << 58) - 1), '\n');
  }
  return 0;
}