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;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
const int maxn = 100000;
template <int p>
struct number {
  unsigned long long a[p];
  number(int x = 0) {
    memset(a, 0, sizeof(a));
    a[0] = x;
  }
  number operator+(const number &t) const {
    number ret;
    for (int i = 0; i < p; i++) ret.a[i] = a[i] + t.a[i];
    return ret;
  }
  number operator-(const number &t) const {
    number ret;
    for (int i = 0; i < p; i++) ret.a[i] = a[i] - t.a[i];
    return ret;
  }
  number operator*(const number &t) const {
    number ret;
    for (int i = 0; i < p; i++) {
      if (!a[i]) continue;
      for (int j = 0; j < p; j++) ret.a[(i + j) % p] += a[i] * t.a[j];
    }
    return ret;
  }
  unsigned long long getint() { return a[0] - a[1]; }
  void debug() {
    for (int i = 0; i < 5; i++)
      if (0) cout << a[i] << ",";
    if (0) cout << endl;
  }
};
number<5> qpown(number<5> x, int k) {
  return k == 0 ? number<5>(1)
                : (k & 1 ? qpown(x * x, k >> 1) * x : qpown(x * x, k >> 1));
}
unsigned long long qpow(unsigned long long x, unsigned long long k) {
  return k == 0 ? 1 : qpow(x * x, k >> 1) * (k & 1 ? x : 1);
}
const int n = 100000;
const int dn = 10;
const int dim[10] = {2, 5, 2, 5, 2, 5, 2, 5, 2, 5};
number<5> a[n];
number<5> root[6][6];
void DFT(number<5> a[], int coef) {
  for (int i = 0; i < dn; i++) {
    number<5> na[n];
    int d = dim[i];
    int p = 1;
    for (int j = 0; j < i; j++) p *= dim[j];
    for (int j = 0; j < n; j++) {
      int id = (j / p) % d;
      int x = j - id * p;
      na[j] = number<5>();
      for (int k = 0; k < d; k++) {
        int y = x + k * p;
        if (coef == 1)
          na[j] = na[j] + root[d][(k * id) % d] * a[y];
        else
          na[j] = na[j] + root[d][d - (k * id) % d] * a[y];
      }
    }
    for (int j = 0; j < n; j++) a[j] = na[j];
  }
}
int i_to_m(int x) {
  int ret = 0, pw = 1;
  for (int i = 0; i < dn / 2; i++) {
    ret += (x % 2) * pw;
    pw *= 2;
    ret += (x % 5) * pw;
    pw *= 5;
    x /= 10;
  }
  return ret;
}
int m_to_i(int x) {
  int ret = 0, pw = 1;
  for (int i = 0; i < dn; i += 2) {
    int c2 = x % 2;
    x /= 2;
    int c5 = x % 5;
    x /= 5;
    for (int t = 0; t < 10; t++)
      if (t % 2 == c2 && t % 5 == c5) ret = ret + t * pw;
    pw *= 10;
  }
  return ret;
}
int main() {
  root[2][0].a[0] = 1;
  root[2][1].a[0] = -1;
  root[2][2].a[0] = 1;
  for (int i = 0; i <= 5; i++) root[5][i].a[i % 5] = 1;
  int k;
  k = getnum();
  for (int i = 1; i <= k; i++) {
    int x;
    x = getnum();
    a[i_to_m(x)].a[0]++;
  }
  DFT(a, 1);
  for (int i = 0; i < n; i++) a[i] = qpown(a[i], k);
  DFT(a, -1);
  unsigned long long inv5 = qpow(5, (1ull << 63) - 1);
  unsigned long long coef = qpow(inv5, dn >> 1);
  for (int i = 0; i < k; i++) {
    int id = i_to_m(i);
    long long cur = a[id].getint();
    cur = cur >> (dn >> 1);
    cur = cur * coef;
    putnum(cur & ((1ull << 58) - 1)), putchar('\n');
  }
  return 0;
}