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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Deque;
import java.util.function.Supplier;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.function.Consumer;
import java.io.Closeable;
import java.io.Writer;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            ERadixSum solver = new ERadixSum();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class ERadixSum {
        GenericFastWalshHadamardTransform fwt = new GenericFastWalshHadamardTransform(10);
        int L = (int) 1e5;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            long[][] cnts = new long[10][L];
            for (int i = 0; i < n; i++) {
                cnts[0][in.ri()]++;
            }

            fwt.addFWT(cnts, 0, L - 1);
            long[][] res = new long[10][L];
            fwt.pow(cnts, res, 0, L - 1, n);
            fwt.addIFWT(res, 0, L - 1, false);

            long mod = 1L << 58;
            int fiveExpFive = 1;
            for (int i = 0; i < 5; i++) {
                fiveExpFive *= 5;
            }
            long inv = DigitUtils.modInverse(fiveExpFive, mod);
            for (int i = 0; i < n; i++) {
                long ans = ((res[0][i] * inv) >>> 5) & (mod - 1);
                out.println(ans);
            }
        }

    }

    static class DigitUtils {
        private static LongExtGCDObject longExtGCDObject = new LongExtGCDObject();

        private DigitUtils() {
        }

        public static long mod(long x, long mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

        public static long modInverse(long x, long mod) {
            long g = longExtGCDObject.extgcd(x, mod);
            assert g == 1;
            long a = longExtGCDObject.getX();
            return DigitUtils.mod(a, mod);
        }

    }

    static class PrimitiveBuffers {
        public static Buffer<int[]>[] intPow2Bufs = new Buffer[30];
        public static Buffer<double[]>[] doublePow2Bufs = new Buffer[30];

        static {
            for (int i = 0; i < 30; i++) {
                int finalI = i;
                intPow2Bufs[i] = new Buffer<>(() -> new int[1 << finalI], x -> Arrays.fill(x, 0));
                doublePow2Bufs[i] = new Buffer<>(() -> new double[1 << finalI], x -> Arrays.fill(x, 0));
            }
        }

        public static int[] allocIntPow2(int n) {
            return intPow2Bufs[Log2.ceilLog(n)].alloc();
        }

        public static int[] allocIntPow2(int[] data) {
            int[] ans = allocIntPow2(data.length);
            System.arraycopy(data, 0, ans, 0, data.length);
            return ans;
        }

        public static int[] resize(int[] data, int want) {
            int log = Log2.ceilLog(want);
            if (data.length == 1 << log) {
                return data;
            }
            return replace(allocIntPow2(data, want), data);
        }

        public static int[] allocIntPow2(int[] data, int newLen) {
            int[] ans = allocIntPow2(newLen);
            System.arraycopy(data, 0, ans, 0, Math.min(data.length, newLen));
            return ans;
        }

        public static void release(int[] data) {
            intPow2Bufs[Log2.ceilLog(data.length)].release(data);
        }

        public static int[] replace(int[] a, int[] b) {
            release(b);
            return a;
        }

        public static void release(int[]... data) {
            for (int[] x : data) {
                release(x);
            }
        }

    }

    static class ExtGCD {
        public static long extGCD(long a, long b, long[] xy) {
            if (a >= b) {
                return extGCD0(a, b, xy);
            }
            long ans = extGCD0(b, a, xy);
            SequenceUtils.swap(xy, 0, 1);
            return ans;
        }

        private static long extGCD0(long a, long b, long[] xy) {
            if (b == 0) {
                xy[0] = 1;
                xy[1] = 0;
                return a;
            }
            long ans = extGCD0(b, a % b, xy);
            long x = xy[0];
            long y = xy[1];
            xy[0] = y;
            xy[1] = x - a / b * y;
            return ans;
        }

    }

    static class Log2 {
        public static int ceilLog(int x) {
            if (x <= 0) {
                return 0;
            }
            return 32 - Integer.numberOfLeadingZeros(x - 1);
        }

    }

    static class CyclotomicPolynomialBF {
        private static Map<Integer, int[]> cache = new HashMap<>();

        static {
            cache.put(1, new int[]{-1, 1});
        }

        public static int[] get(int n) {
            int[] ans = cache.get(n);
            if (ans == null) {
                int[] a = PrimitiveBuffers.allocIntPow2(cache.get(1));
                for (int i = 2; i * i <= n; i++) {
                    if (n % i != 0) {
                        continue;
                    }
                    a = PrimitiveBuffers.replace(Polynomials.mul(a, get(i)), a);
                    if (i * i != n) {
                        a = PrimitiveBuffers.replace(Polynomials.mul(a, get(n / i)), a);
                    }
                }
                int[] top = PrimitiveBuffers.allocIntPow2(n + 1);
                top[n] = 1;
                top[0] = -1;
                int[][] res = Polynomials.divAndRemainder(top, a);
                ans = Arrays.copyOf(res[0], Polynomials.rankOf(res[0]) + 1);
                assert ans.length <= n + 1;
                PrimitiveBuffers.release(a, top, res[0], res[1]);
                cache.put(n, ans);
            }

            return ans;
        }

    }

    static class GenericFastWalshHadamardTransform {
        int[][] addC;
        int[][] iaddC;
        int k;
        long[] accum;
        long[][] buf;
        int[] phi;

        public GenericFastWalshHadamardTransform(int k) {
            this.k = k;
            accum = new long[k * 2];
            addC = new int[k][k];
            iaddC = new int[k][k];
            buf = new long[k][k];
            phi = CyclotomicPolynomialBF.get(k).clone();
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    addC[i][j] = i * j % k;
                    iaddC[i][j] = (k - addC[i][j]) % k;
                }
            }
        }

        public void dotMul(long[][] a, long[][] b, long[][] c, int l, int r) {
            for (int i = l; i <= r; i++) {
                mulAddTo(a, i, b, i);
                for (int j = 0; j < k; j++) {
                    c[j][i] = accum[j];
                }
            }
        }

        public void pow(long[][] x, long[][] res, int l, int r, long n) {
            if (n == 0) {
                for (int i = 0; i < k; i++) {
                    if (i == 0) {
                        Arrays.fill(res[i], 1);
                    } else {
                        Arrays.fill(res[i], 0);
                    }
                }
                return;
            }
            pow(x, res, l, r, n / 2);
            dotMul(res, res, res, l, r);
            if (n % 2 == 1) {
                dotMul(res, x, res, l, r);
            }
        }

        private void mulAddTo(long[][] a, int offset, int t, long[] dest) {
            for (int i = 0, to = t; i < k; i++, to = to + 1 == k ? 0 : to + 1) {
                dest[to] += a[i][offset];
            }
        }

        private void mulAddTo(long[][] a, int ai, long[][] b, int bi) {
            for (int i = 0; i < k; i++) {
                accum[i] = 0;
            }
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    int ij = i + j;
                    accum[ij] += a[i][ai] * b[j][bi];
                }
            }
            for (int i = 0; i < k; i++) {
                accum[i] += accum[i + k];
                accum[i + k] = 0;
            }
        }

        public void addFWT(long[][] a, int l, int r) {
            if (l == r) {
                return;
            }
            int len = r - l + 1;
            assert len % k == 0;
            int step = len / k;
            for (int i = 0; i < len; i += step) {
                addFWT(a, l + i, l + i + step - 1);
            }
            for (int i = 0; i < step; i++) {
                int first = l + i;
                for (int j = 0; j < k; j++) {
                    for (int t = 0; t < k; t++) {
                        mulAddTo(a, t * step + first, addC[j][t], buf[j]);
                    }
                }
                //copy back
                for (int j = 0; j < k; j++) {
                    int index = j * step + first;
                    for (int t = 0; t < k; t++) {
                        a[t][index] = buf[j][t];
                        buf[j][t] = 0;
                    }
                }
            }
        }

        public void normalize(long[][] a, int l, int r) {
            for (int i = l; i <= r; i++) {
                moduleInPlace(a, i, phi);
            }
        }

        private void moduleInPlace(long[][] a, int offset, int[] b) {
            int ra = k - 1;
            int rb = Polynomials.rankOf(b);
            if (ra < rb) {
                return;
            }
            for (int i = ra; i >= rb; i--) {
                assert a[i][offset] % b[rb] == 0;
                long d = a[i][offset] / b[rb];
                if (d == 0) {
                    continue;
                }
                for (int j = rb; j >= 0; j--) {
                    int ij = i + j - rb;
                    a[ij][offset] -= d * b[j];
                }
            }
        }

        public void addIFWT(long[][] a, int l, int r, boolean divAuto) {
            int n = r - l + 1;
            addIFWT0(a, l, r);
            normalize(a, l, r);

            if (divAuto) {
                for (int i = l; i <= r; i++) {
//            assert a[0][i] % n == 0;
                    a[0][i] = a[0][i] / n;
                }
            }
        }

        private void addIFWT0(long[][] a, int l, int r) {
            if (l == r) {
                return;
            }
            int len = r - l + 1;
            assert len % k == 0;
            int step = len / k;

            for (int i = 0; i < step; i++) {
                int first = l + i;
                for (int j = 0; j < k; j++) {
                    for (int t = 0; t < k; t++) {
                        mulAddTo(a, t * step + first, iaddC[j][t], buf[j]);
                    }
                }
                //copy back
                for (int j = 0; j < k; j++) {
                    int index = j * step + first;
                    for (int t = 0; t < k; t++) {
                        a[t][index] = buf[j][t];
                        buf[j][t] = 0;
                    }
                }
            }

            for (int i = 0; i < len; i += step) {
                addIFWT0(a, l + i, l + i + step - 1);
            }
        }

    }

    static class SequenceUtils {
        public static void swap(long[] data, int i, int j) {
            long tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class Buffer<T> {
        private Deque<T> deque;
        private Supplier<T> supplier;
        private Consumer<T> cleaner;
        private int allocTime;
        private int releaseTime;

        public Buffer(Supplier<T> supplier) {
            this(supplier, (x) -> {
            });
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner) {
            this(supplier, cleaner, 0);
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner, int exp) {
            this.supplier = supplier;
            this.cleaner = cleaner;
            deque = new ArrayDeque<>(exp);
        }

        public T alloc() {
            allocTime++;
            return deque.isEmpty() ? supplier.get() : deque.removeFirst();
        }

        public void release(T e) {
            releaseTime++;
            cleaner.accept(e);
            deque.addLast(e);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            boolean rev = false;

            skipBlank();
            if (next == '+' || next == '-') {
                rev = next == '-';
                next = read();
            }

            int val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 - next + '0';
                next = read();
            }

            return rev ? val : -val;
        }

    }

    static class Polynomials {
        public static int rankOf(int[] p) {
            int r = p.length - 1;
            while (r >= 0 && p[r] == 0) {
                r--;
            }
            return Math.max(0, r);
        }

        public static int[] normalizeAndReplace(int[] p) {
            int r = rankOf(p);
            return PrimitiveBuffers.resize(p, r + 1);
        }

        public static int[][] divAndRemainder(int[] a, int[] b) {
            int ra = Polynomials.rankOf(a);
            int rb = Polynomials.rankOf(b);
            if (ra < rb) {
                return new int[][]{PrimitiveBuffers.allocIntPow2(1), PrimitiveBuffers.allocIntPow2(a)};
            }
            int[] div = PrimitiveBuffers.allocIntPow2(ra - rb + 1);
            int[] op = PrimitiveBuffers.allocIntPow2(a);

            for (int i = ra; i >= rb; i--) {
                assert op[i] % b[rb] == 0;
                int d = op[i] / b[rb];
                div[i - rb] = d;
                if (d == 0) {
                    continue;
                }
                for (int j = rb; j >= 0; j--) {
                    op[i + j - rb] -= d * b[j];
                }
            }

            op = Polynomials.normalizeAndReplace(op);
            return new int[][]{div, op};
        }

        public static int[] mul(int[] a, int[] b) {
            int ra = Polynomials.rankOf(a);
            int rb = Polynomials.rankOf(b);
            int[] ans = PrimitiveBuffers.allocIntPow2(ra + rb + 1);
            for (int i = 0; i <= ra; i++) {
                for (int j = 0; j <= rb; j++) {
                    ans[i + j] += a[i] * b[j];
                }
            }
            return ans;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class LongExtGCDObject {
        private long[] xy = new long[2];

        public long extgcd(long a, long b) {
            return ExtGCD.extGCD(a, b, xy);
        }

        public long getX() {
            return xy[0];
        }

    }
}