You are given three strings (s1, s2, s3). For each integer l (1 ≤ l ≤ min(|s1|, |s2|, |s3|) you need to find how many triples (i1, i2, i3) exist such that three strings sk[ik... ik + l - 1] (k = 1, 2, 3) are pairwise equal. Print all found numbers modulo 1000000007 (109 + 7).

See notes if you are not sure about some of the denotions used in the statement.

Input

First three lines contain three non-empty input strings. The sum of lengths of all strings is no more than 3·105. All strings consist only of lowercase English letters.

Output

You need to output min(|s1|, |s2|, |s3|) numbers separated by spaces — answers for the problem modulo 1000000007 (109 + 7).

Examples

Input

abc
bc
cbc


Output

3 1 


Input

abacaba
abac
abcd


Output

11 2 0 0 

Note

Consider a string t = t1t2... t|t|, where ti denotes the i-th character of the string, and |t| denotes the length of the string.

Then t[i... j] (1 ≤ i ≤ j ≤ |t|) represents the string titi + 1... tj (substring of t from position i to position j inclusive).
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ilyakor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskE {
    static final int mod = 1000000007;

    //SegmentTreeFastIntervalAddSumMod tree;
    long[] sums;
    int[][] cnts;

    int i1, i2, i3;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s1 = in.nextToken();
        String s2 = in.nextToken();
        String s3 = in.nextToken();
//        Random random = new Random(0xdead);
//        String s1 = build(random);
//        String s2 = build(random);
//        String s3 = build(random);
        String s = s1 + "\1" + s2 + "\2" + s3 + "\3";
        SuffixTree.Node root = SuffixTree.buildSuffixTree(s);
        System.err.println("Built");
        //tree = new SegmentTreeFastIntervalAddSumMod((1 << 19), mod);
        sums = new long[1 << 19];
        i1 = s1.length();
        i2 = s1.length() + s2.length() + 1;
        i3 = s1.length() + s2.length() + s3.length() + 2;
        cnts = new int[1 << 20][3];
        dfs(root, 0);
        long sum = 0;
        for (int i = 1; i <= s1.length() && i <= s2.length() && i <= s3.length(); ++i) {
            sum += sums[i];
            sum %= mod;
            //out.print(tree.get(i) + " ");
            out.print(sum + " ");
        }
        //Assert.assertTrue(sum == 0);
        out.printLine();
    }



    public void dfs(SuffixTree.Node node, int depth) {
        cnts[depth][0] = 0;
        cnts[depth][1] = 0;
        cnts[depth][2] = 0;
        if (node.begin <= i1 && i1 < node.end) {
            cnts[depth][0] = 1;
            return;
        }
        if (node.begin <= i2 && i2 < node.end) {
            cnts[depth][1] = 1;
            return;
        }
        if (node.begin <= i3 && i3 < node.end) {
            cnts[depth][2] = 1;
            return;
        }
        for (char f = 0; f < SuffixTree.alphabetSize; f++) {
            if (node.children[f] != null) {
                dfs(node.children[f], depth + 1);
                for (int i = 0; i < 3; ++i)
                    cnts[depth][i] += cnts[depth + 1][i];
            }
        }
        long val = 1;
        for (int i = 0; i < 3; ++i) {
            if (cnts[depth][i] == 0) {
                val = 0;
                break;
            }
            val *= cnts[depth][i];
            val %= mod;
        }
        if (val != 0) {
            //Assert.assertTrue(node.end <= i1);
            sums[1 + node.depth] += val; if (sums[1 + node.depth] > 1E17) sums[1 + node.depth] %= mod;
            sums[1 + node.depth + node.end  - node.begin] += mod - val; if (sums[1 + node.depth + node.end  - node.begin] > 1E17) sums[1 + node.depth + node.end  - node.begin] %= mod;
            //tree.modifyAdd(1 + node.depth, 1 + node.depth + node.end  - node.begin - 1, (int) val);
        }
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buffer = new byte[10000];
    private int cur;
    private int count;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public static boolean isSpace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public int read() {
        if (count == -1) {
            throw new InputMismatchException();
        }
        try {
            if (cur >= count) {
                cur = 0;
                count = stream.read(buffer);
                if (count <= 0)
                    return -1;
            }
        } catch (IOException e) {
            throw new InputMismatchException();
        }
        return buffer[cur++];
    }

    public int readSkipSpace() {
        int c;
        do {
            c = read();
        } while (isSpace(c));
        return c;
    }

    public String nextToken() {
        int c = readSkipSpace();
        StringBuilder sb = new StringBuilder();
        while (!isSpace(c)) {
            sb.append((char) c);
            c = read();
        }
        return sb.toString();
    }

}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void printLine(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}

class SuffixTree {
    public static String alphabet = "abcdefghijklmnopqrstuvwxyz\1\2\3";
    public static int alphabetSize = alphabet.length();

    public static class Node {
        public int depth; // from start of suffix
        public int begin;
        public int end;
        public Node[] children;
        public Node parent;
        public Node suffixLink;

        Node(int begin, int end, int depth, Node parent) {
            //children = new Node[alphabetSize];
            this.begin = begin;
            this.end = end;
            this.parent = parent;
            this.depth = depth;
        }

        boolean contains(int d) {
            return depth <= d && d < depth + (end - begin);
        }
    }

    public static Node buildSuffixTree(String s) {
        int n = s.length();
        byte[] a = new byte[n];
        for (int i = 0; i < n; i++) {
            a[i] = (byte) alphabet.indexOf(s.charAt(i));
        }
        Node root = new Node(0, 0, 0, null);
        Node cn = root;
        // root.suffixLink must be null, but that way it gets more convenient
        // processing
        root.suffixLink = root;
        Node needsSuffixLink = null;
        int lastRule = 0;
        int j = 0;
        for (int i = -1; i < n - 1; i++) {// strings s[j..i] already in tree,
            // delta s[i+l] to it.
            int cur = a[i + 1]; // last char of current string
            for (; j <= i + 1; j++) {
                int curDepth = i + 1 - j;
                if (lastRule != 3) {
                    cn = cn.suffixLink != null ? cn.suffixLink : cn.parent.suffixLink;
                    int k = j + cn.depth;
                    while (curDepth > 0 && !cn.contains(curDepth - 1)) {
                        k += cn.end - cn.begin;
                        cn = cn.children == null ? null : cn.children[a[k]];
                    }
                }
                if (!cn.contains(curDepth)) { // explicit node
                    if (needsSuffixLink != null) {
                        needsSuffixLink.suffixLink = cn;
                        needsSuffixLink = null;
                    }
                    if (cn.children == null || cn.children[cur] == null) {
                        // no extension - delta leaf
                        if (cn.children == null) {
                            cn.children = new Node[alphabetSize];
                        }
                        cn.children[cur] = new Node(i + 1, n, curDepth, cn);
                        lastRule = 2;
                    } else {
                        cn = cn.children[cur];
                        lastRule = 3; // already exists
                        break;
                    }
                } else { // implicit node
                    int end = cn.begin + curDepth - cn.depth;
                    if (a[end] != cur) { // split implicit node here
                        Node newn = new Node(cn.begin, end, cn.depth, cn.parent);
                        newn.children = new Node[alphabetSize];
                        newn.children[cur] = new Node(i + 1, n, curDepth, newn);
                        newn.children[a[end]] = cn;
                        cn.parent.children[a[cn.begin]] = newn;
                        if (needsSuffixLink != null) {
                            needsSuffixLink.suffixLink = newn;
                        }
                        cn.begin = end;
                        cn.depth = curDepth;
                        cn.parent = newn;
                        cn = needsSuffixLink = newn;
                        lastRule = 2;
                    } else if (cn.end != n || cn.begin - cn.depth < j) {
                        lastRule = 3;
                        break;
                    } else {
                        lastRule = 1;
                    }
                }
            }
        }
        root.suffixLink = null;
        return root;
    }

}

