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>
const int len = 100000;
const unsigned long long inv = (unsigned long long)6723469279985657373,
                         mod = (unsigned long long)1 << 58,
                         inf = (unsigned long long)0xffffffffffffffff;
int sum[9] = {0, 1, 2, 3, 4, 0, 1, 2, 3};
struct num {
  unsigned long long a[5];
  num() {
    for (int i(0); i < 5; ++i) a[i] = 0;
  }
  num operator+(const num& p) {
    num res;
    for (int i(0); i < 5; ++i) res.a[i] = a[i] + p.a[i];
    return res;
  }
  num operator-(const num& p) {
    num res;
    for (int i(0); i < 5; ++i) res.a[i] = a[i] - p.a[i];
    return res;
  }
  num operator*(const num& p) {
    num res;
    for (int i(0); i < 5; ++i) {
      for (int j(0); j < 5; ++j) res.a[sum[i + j]] += a[i] * p.a[j];
    }
    return res;
  }
} s[10][10], is[10][10], w10[10], c[100000], tmp[10], num0;
void fwt(num* t, num os[][10] = s) {
  for (int i(1), j(10); i < len; i *= 10, j *= 10) {
    for (int k(0); k < len; k += j) {
      for (int l0(k); l0 < k + i; ++l0) {
        for (int l1(0), l2(0); l1 < j; ++l2, l1 += i) tmp[l2] = t[l1 + l0];
        for (int l1(0), l2(0); l1 < j; ++l2, l1 += i) {
          t[l1 + l0] = num0;
          for (int l3(0); l3 < 10; ++l3)
            t[l1 + l0] = t[l1 + l0] + tmp[l3] * os[l2][l3];
        }
      }
    }
  }
  if (os == is) {
    for (int i(0); i < len; ++i) t[i].a[0] *= inv, t[i].a[1] *= inv;
  }
}
num pow(num x, int p) {
  num res;
  res.a[0] = 1;
  while (p) {
    if (p & 1) res = res * x;
    x = x * x;
    p >>= 1;
  }
  return res;
}
int main() {
  int n, ta;
  scanf("%d", &n);
  for (int i(0); i < n; ++i) {
    scanf("%d", &ta);
    ++c[ta].a[0];
  }
  for (int i(0), j(0); i < 5; ++i, j += 2)
    w10[j].a[i] = 1, w10[j + 1].a[sum[i + 3]] = inf;
  for (int i(0); i < 10; ++i) {
    for (int j(0); j < 10; ++j) {
      ta = i * j % 10;
      s[i][j] = w10[ta], is[i][j] = w10[ta ? 10 - ta : 0];
    }
  }
  fwt(c);
  for (int i(0); i < len; ++i) c[i] = pow(c[i], n);
  fwt(c, is);
  for (int i(0); i < n; ++i)
    printf("%llu\n", ((c[i].a[0] - c[i].a[1]) >> 5) % mod);
  return 0;
}