The Little Elephant loves strings very much. 

He has an array a from n strings, consisting of lowercase English letters. Let's number the elements of the array from 1 to n, then let's denote the element number i as ai. For each string ai (1 ≤ i ≤ n) the Little Elephant wants to find the number of pairs of integers l and r (1 ≤ l ≤ r ≤ |ai|) such that substring ai[l... r] is a substring to at least k strings from array a (including the i-th string).

Help the Little Elephant solve this problem.

If you are not familiar with the basic notation in string problems, you can find the corresponding definitions in the notes.

Input

The first line contains two space-separated integers — n and k (1 ≤ n, k ≤ 105). Next n lines contain array a. The i-th line contains a non-empty string ai, consisting of lowercase English letter. The total length of all strings ai does not exceed 105.

Output

On a single line print n space-separated integers — the i-th number is the answer for string ai.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 1
abc
a
ab


Output

6 1 3 


Input

7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero


Output

1 0 9 9 21 30 0 

Note

Let's assume that you are given string a = a1a2... a|a|, then let's denote the string's length as |a| and the string's i-th character as ai.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1... ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

/**
 * 204E
 * O(n*Σ(|s_i|)) time
 * O(n*Σ(|s_i|)) space
 *
 * @author artyom
 */
public class _204EFaster implements Runnable {
    private BufferedReader in;
    private StringTokenizer tok;
    private long[] ans;
    private int k;

    private Object solve() throws IOException {
        int n = nextInt();
        k = nextInt();
        ans = new long[n];
        List<byte[]> a = new ArrayList<>(n);
        GeneralizedSuffixTreeNode root = new GeneralizedSuffixTreeNode(0, 0, 0, 0, null, null);
        for (int i = 0; i < n; i++) {
            String s = nextToken();
            a.add(encode(s));
            addToTree(a, i, root);
        }
        for (GeneralizedSuffixTreeNode child : root.children) {
            if (child != null) {
                calc(child);
            }
        }
        return LongStream.of(ans).mapToObj(String::valueOf).collect(Collectors.joining(" "));
    }

    private void calc(GeneralizedSuffixTreeNode node) {
        if (!node.isLeaf) {
            boolean first = true;
            for (GeneralizedSuffixTreeNode child : node.children) {
                if (child != null) {
                    calc(child);
                    if (first) {
                        node.suffixes = child.suffixes;
                        first = false;
                    } else {
                        for (Map.Entry<Integer, Integer> entry : child.suffixes.entrySet()) {
                            int val = node.suffixes.getOrDefault(entry.getKey(), 0);
                            node.suffixes.put(entry.getKey(), val + entry.getValue());
                        }
                    }
                    child.suffixes = null; // Empty some space
                }
            }
            node.children = null; // Empty some space
        }
        if (node.suffixes.size() >= k) {
            long len = node.length();
            if (node.isLeaf) {
                len--;
            }
            for (Map.Entry<Integer, Integer> entry : node.suffixes.entrySet()) {
                ans[entry.getKey()] += len * entry.getValue();
            }
        }
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _204EFaster().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            tok = null;
            System.out.print(solve());
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private static byte[] encode(CharSequence word) {
        int n = word.length();
        byte[] r = new byte[n + 1];
        for (int j = 0; j < n; j++) {
            r[j] = (byte) (word.charAt(j) - 'a');
        }
        r[n] = 26;
        return r;
    }

    private static void addToTree(List<byte[]> a, int wordNumber, GeneralizedSuffixTreeNode root) {
        int n = a.get(wordNumber).length;
        GeneralizedSuffixTreeNode node = root;
        for (int i = 0, tail = 0; i < n; i++, tail++) {
            GeneralizedSuffixTreeNode last = null;
            while (tail >= 0) {
                GeneralizedSuffixTreeNode ch = node.children[a.get(wordNumber)[i - tail]];
                while (ch != null && tail >= ch.length()) {
                    tail -= ch.length();
                    node = ch;
                    ch = ch.children[a.get(wordNumber)[i - tail]];
                }
                if (ch == null) {
                    node.children[a.get(wordNumber)[i]] = new GeneralizedSuffixTreeNode(wordNumber, i, n, node.depth(), i, node);
                    if (last != null) {
                        last.suffixLink = node;
                    }
                    last = null;
                } else {
                    byte t = a.get(ch.wordNumber)[ch.start + tail];
                    if (t == a.get(wordNumber)[i]) {
                        if (last != null) {
                            last.suffixLink = node;
                        }
                        if (t == 26) {
                            // The suffix is already in the tree
                            ch.suffixes.put(wordNumber, 1);
                            last = null;
                        } else {
                            break;
                        }
                    } else {
                        GeneralizedSuffixTreeNode splitNode = new GeneralizedSuffixTreeNode(ch.wordNumber, ch.start, ch.start + tail, node.depth(), null, node);
                        splitNode.children[a.get(wordNumber)[i]] = new GeneralizedSuffixTreeNode(wordNumber, i, n, ch.depth + tail, i, splitNode);
                        splitNode.children[t] = ch;
                        ch.start += tail;
                        ch.depth += tail;
                        ch.parent = splitNode;
                        node.children[a.get(wordNumber)[i - tail]] = splitNode;
                        if (last != null) {
                            last.suffixLink = splitNode;
                        }
                        last = splitNode;
                    }
                }
                if (node == root) {
                    tail--;
                } else {
                    node = node.suffixLink;
                }
            }
        }
    }

    private static class GeneralizedSuffixTreeNode {
        GeneralizedSuffixTreeNode parent;
        GeneralizedSuffixTreeNode suffixLink;
        GeneralizedSuffixTreeNode[] children;
        /**
         * wordNumber -> count
         */
        Map<Integer, Integer> suffixes;
        int depth; // The number of characters from root to this node
        int start; // Inclusive
        int end; // Exclusive
        int wordNumber;
        // Additional properties
        final boolean isLeaf;

        GeneralizedSuffixTreeNode(int wordNumber, int start, int end, int depth, Integer position, GeneralizedSuffixTreeNode parent) {
            this.wordNumber = wordNumber;
            this.start = start;
            this.end = end;
            this.parent = parent;
            this.depth = depth;
            if (position != null) {
                isLeaf = true;
                children = null;
                suffixes = new HashMap<>();
                suffixes.put(wordNumber, 1);
            } else {
                isLeaf = false;
                children = new GeneralizedSuffixTreeNode[28];
            }
        }

        /**
         * @return the number of characters on the edge to the parent.
         */
        final int length() {
            return end - start;
        }

        /**
         * @return the number of characters on the path from the root to this node.
         */
        final int depth() {
            return depth + end - start;
        }
    }
}