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;
using ll = int64_t;
auto& errStream = cerr;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
using ull = unsigned long long;
const ll S = 5;
struct Num {
  ull p[S];
  Num() { memset(p, 0, sizeof(p)); }
  Num operator+(const Num& rhs) const {
    Num res;
    for (ll i = ll(0); i < ll(S); i++) res.p[i] = p[i] + rhs.p[i];
    return res;
  }
  Num operator*(const Num& rhs) const {
    Num res;
    for (ll i = ll(0); i < ll(S); i++)
      for (ll j = ll(0); j < ll(S); j++) {
        if (i + j < S)
          res.p[i + j] += p[i] * rhs.p[j];
        else
          res.p[i + j - S] -= p[i] * rhs.p[j];
      }
    return res;
  }
};
Num pow(Num x, ll n) {
  Num res;
  res.p[0] = 1;
  while (n) {
    if (n & 1) res = res * x;
    x = x * x;
    n >>= 1;
  }
  return res;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    ll g = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
  }
}
const ll B = 10;
const ll N = 100000;
Num w[B];
Num x[N];
void trans(ll b, ll e) {
  ll len = e - b;
  if (len == 1) return;
  ll s = len / B;
  for (ll i = b; i < e; i += s) trans(i, i + s);
  for (ll i = ll(b); i < ll(b + s); i++) {
    Num tmp[B];
    for (ll j = ll(0); j < ll(B); j++) tmp[j] = x[i + j * s];
    for (ll j = ll(0); j < ll(B); j++) {
      Num z;
      for (ll k = ll(0); k < ll(B); k++) z = z + w[j * k % B] * tmp[k];
      x[i + j * s] = z;
    }
  }
}
signed main() {
  ll n = read();
  for (ll i = ll(0); i < ll(n); i++) {
    ll a = read();
    x[a].p[0]++;
  }
  {
    Num root;
    root.p[1] = 1;
    for (ll i = ll(0); i < ll(B); i++) w[i] = pow(root, i);
    trans(0, N);
  }
  for (ll i = ll(0); i < ll(N); i++) x[i] = pow(x[i], n);
  {
    Num root;
    root.p[4] = -1;
    for (ll i = ll(0); i < ll(B); i++) w[i] = pow(root, i);
    trans(0, N);
  }
  const ll mod = ll(1) << 58;
  ll inv5, tmp;
  extgcd(5, mod, inv5, tmp);
  if (inv5 < 0) inv5 += mod;
  for (ll i = ll(0); i < ll(n); i++) {
    ull ans = x[i].p[0] - x[i].p[4];
    cerrDummy << vector<ull>(x[i].p, x[i].p + 5) << endl;
    for (ll _ = ll(0); _ < ll(5); _++) ans *= inv5;
    ans >>= 5;
    ans %= mod;
    print(ans);
  }
}