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.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

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

class TaskE {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int k = in.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; ++i) s[i] = in.nextString();
        SuffixAutomata automaton = new SuffixAutomata(s);
        TreeNode root = automaton.root.toTree();
        int N = root.size();
        nodes = new TreeNode[N];

        tree = new Graph();
        tree.initGraphWithCost(N, N-1);
        ids = 0;
        parent = new int[N];
        dfsBuild(root, -1, 0);
        lca = new LCA(tree, 0, parent);


        root.strs.clear();
        am = new long[N];
        last = new int[n];
        Arrays.fill(last, -1);
        ids = 0;
        dfsIn(0);
        f = new long[N];

        dfsSum(0, k);
        f[0] = 0;
        ans = new long[n];
        dfsAns(0, 0);
        for (int i = 0; i < n; ++i) {
            out.print(ans[i] + " ");
        }
    }

    Graph tree;
    LCA lca;
    int[] parent;

    private void dfsBuild(TreeNode v, int par, int len) {
        int id = ids++;
        nodes[id] = v;
        if (par != -1) {
            tree.addEdgeWithCost(par, id, len);
        }
        parent[id] = par;
        for (int i = 0; i < v.subTrees.size(); ++i) {
            dfsBuild(v.subTrees.get(i), id, v.lengths.get(i));
        }
    }

    private void dfsAns(int v, long number) {
        //number += f[v];
        if (nodes[v].strs != null) {
            for (int i : nodes[v].strs) {
                ans[i] += number;
            }
        }
        for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
            if (tree.to[i] != parent[v]) {
                dfsAns(tree.to[i], number + f[tree.to[i]] * 1L * tree.cost[i]);
            }
        }
    }

    long[] f;
    long[] ans;

    private long dfsSum(int v, int k) {
        for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
            if (tree.to[i] != parent[v]) {
                am[v] += dfsSum(tree.to[i], k);
            }
        }
        if (am[v] >= k) {
            f[v] = 1;
        }
        return am[v];
    }

    private void dfsIn(int v) {
        if (nodes[v].strs != null) {
            am[v] += nodes[v].strs.size();
            for (int i : nodes[v].strs) {
                if (last[i] == -1) {
                    last[i] = v;
                } else {
                    int l = lca.LCA(last[i], v);
                    last[i] = v;
                    am[l]--;
                }
            }
        }
        for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
            if (tree.to[i] != parent[v]) {
                dfsIn(tree.to[i]);
            }
        }
    }

    int ids;
    long[] am;
    int[] last;
    TreeNode[] nodes;

    class TreeNode {
        List<TreeNode> subTrees;
        List<Integer> lengths;
        List<Integer> strs;

        int size() {
            int r = 1;
            for (TreeNode nx : subTrees) {
                r += nx.size();
            }
            return r;
        }
    }

    class SuffixAutomata {

        class Vertex {
            Vertex suffixLink;
            Vertex[] edges;
            int length = 0;

            TreeNode to;
            int toLen = -1;

            TreeNode toTree() {
                if (to != null) {
                    return to;
                }
                Vertex one = null;
                int count = 0;
                for (int i = 0; i < 26; ++i) {
                    if (edges[i] != null) {
                        one = edges[i];
                        ++count;
                    }
                }
                if (count == 1 && terminal == null) {
                    to = one.toTree();
                    toLen = one.toLen + 1;
                } else {
                    to = new TreeNode();
                    to.strs = terminal;
                    to.subTrees = new ArrayList<TreeNode>(count);
                    to.lengths = new ArrayList<Integer>(count);
                    for (int i = 0; i < 26; ++i) {
                        if (edges[i] != null) {
                            to.subTrees.add(edges[i].toTree());
                            to.lengths.add(edges[i].toLen + 1);
                        }
                    }
                    toLen = 0;
                }
                return to;
            }



            List<Integer> terminal;

            Vertex(int length) {
                this.length = length;
                edges = new Vertex[26];
                terminal = null;
            }

            Vertex(Vertex v, int length) {
                edges = v.edges.clone();
                terminal = v.terminal == null ? null : new ArrayList<Integer>(v.terminal);
                this.length = length;
            }
        }

        Vertex root, last;

        SuffixAutomata(String[] strings) {
            last = root = new Vertex(0);
            for (int it = 0; it < strings.length; ++it) {
                char[] c = strings[it].toCharArray();
                for (int i = 0; i < c.length; ++i) {
                    addChar(c[i] - 'a');
                }
                addTerm(it);
                last = root;
            }
        }

        private void addChar(int c) {
            Vertex cur = last;
            last = new Vertex(cur.length + 1);
            while (cur != null && cur.edges[c] == null) {
                cur.edges[c] = last;
                cur = cur.suffixLink;
            }
            if (cur != null) {
                Vertex q = cur.edges[c];
                if (q.length == cur.length + 1) {
                    last.suffixLink = q;
                } else {
                    Vertex r = new Vertex(q, cur.length + 1);
                    r.suffixLink = q.suffixLink;
                    q.suffixLink = r;
                    last.suffixLink = r;
                    while (cur != null) {
                        if (cur.edges[c] == q) {
                            cur.edges[c] = r;
                        } else {
                            break;
                        }
                        cur = cur.suffixLink;
                    }
                }
            } else {
                last.suffixLink = root;
            }
        }

        private void addTerm(int it) {
            Vertex cur = last;
            while (cur != null) {
                if (cur.terminal == null) {
                    cur.terminal = new ArrayList<Integer>(1);
                }
                cur.terminal.add(it);
                cur = cur.suffixLink;
            }
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int[] cost;
    public int nVertex;
    public int nEdges;
    public int curEdge;

    public Graph() {}

    public void initGraphWithCost(int n, int m) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        cost = new int[m * 2];
        Arrays.fill(first, -1);
    }

    public void addEdgeWithCost(int a, int b, int c) {
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        cost[curEdge] = c;
        ++curEdge;

        next[curEdge] = first[b];
        first[b] = curEdge;
        to[curEdge] = a;
        from[curEdge] = b;
        cost[curEdge] = c;
        ++curEdge;
    }

}

class LCA {
    public int[] height;
    public int[] dfsOrder;
    public int[] posInDfsOrder;
    public int countDfsOrder;
    private int block;
    private int[][] blockTable;
    int logMaxList;
    int[] blockHash;
    int[][][] blockRmq;
    int[] log2;
    int[] parent;
    int n;

    public LCA(Graph tree, int root, int[] parent) {
        n = tree.nVertex;
        log2 = new int[2 * n];
        height = new int[n];
        Arrays.fill(height, -1);
        dfsOrder = new int[n*2-1];
        posInDfsOrder = new int[n];
        countDfsOrder = 0;
        this.parent = parent;
        dfsStack(tree, root);
        logMaxList = log(countDfsOrder);
        buildLCA();
    }

    // Walk graph
    private void dfsStack(Graph tree, int v) {
        int[] stackVertex = new int[tree.nVertex*2];
        int[] stackHeight = new int[tree.nVertex*2];
        int[] stackEdge = new int[tree.nVertex*2];
        int top = 0;
        stackHeight[top] = 0;
        stackVertex[top] = v;
        stackEdge[top] = tree.first[v];
        ++top;
        int currentHeight, edge;
        while (top > 0) {
            --top;
            v = stackVertex[top];
            currentHeight = stackHeight[top];
            edge = stackEdge[top];

            if (height[v] == -1) {
                height[v] = currentHeight;
                posInDfsOrder[v] = countDfsOrder;
                dfsOrder[countDfsOrder++] = v;
            } else {
                dfsOrder[countDfsOrder++] = v;
            }

            if (edge == -1) continue;

            int nextEdge = tree.next[edge];

            if (nextEdge != -1) {
                if (tree.to[nextEdge] == parent[v]) {
                    nextEdge = tree.next[nextEdge];
                }
            }

            stackHeight[top] = currentHeight;
            stackVertex[top] = v;
            stackEdge[top] = nextEdge;
            ++top;

            int u = tree.to[edge];
            stackHeight[top] = currentHeight + 1;
            stackVertex[top] = u;
            int edgeId = tree.first[u];
            if (edgeId != -1) {
                if (tree.to[edgeId] == v) {
                    edgeId = tree.next[edgeId];
                }
            }
            stackEdge[top] = edgeId;
            ++top;
        }
    }

    int log(int n) {
        int res = 1;
        while ((1 << res) < n)  ++res;
        return res;
    }

    // compares two indices in a
    int minHeight(int i, int j) {
        return height[dfsOrder[i]] < height[dfsOrder[j]] ? i : j;
    }

    // O(N) preprocessing
    void buildLCA() {
        block = (logMaxList + 1) / 2;
        int blocks = countDfsOrder / block + ((countDfsOrder % block > 0) ? 1 : 0);
        int maxBlocks = ((2 * n) / block) + 2;
        blockHash = new int[maxBlocks + 1];
        blockTable = new int[maxBlocks + 1][logMaxList + 1];
        blockRmq = new int[(int) (Math.sqrt(2*n) + 2)][block + 2][block + 2];
        ArrayUtils.fill(blockRmq, -1);
        ArrayUtils.fill(blockTable, -1);
        Arrays.fill(blockHash, 0);

        // precalc in each block and build sparse table
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (blockTable[blockId][0] == -1 || minHeight(i, blockTable[blockId][0]) == i) {
                blockTable[blockId][0] = i;
            }
        }

        for (int j = 1; j <= logMaxList; ++j) {
            for (int i = 0; i < blocks; ++i) {
                int ni = i + (1 << (j - 1));
                if (ni >= blocks) {
                    blockTable[i][j] = blockTable[i][j - 1];
                } else {
                    blockTable[i][j] = minHeight(blockTable[i][j - 1], blockTable[ni][j - 1]);
                }
            }
        }

        // calc hashes of blocks
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder || j < block; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (j > 0 && (i >= countDfsOrder || minHeight(i - 1, i) == i - 1)) {
                blockHash[blockId] += (1 << (j - 1));
            }
        }

        // precalc RMQ inside each unique block
        for (int i = 0; i < blocks; ++i) {
            int id = blockHash[i];
            if (blockRmq[id][0][0] != -1) continue;
            for (int l = 0; l < block; ++l) {
                blockRmq[id][l][l] = l;
                for (int r = l + 1; r < block; ++r) {
                    blockRmq[id][l][r] = blockRmq[id][l][r-1];
                    if (i * block + r < countDfsOrder) {
                        blockRmq[id][l][r] = minHeight(i * block + blockRmq[id][l][r], i * block + r) - i * block;
                    }
                }
            }
        }

        // precalc logarithms
        for (int i = 0, j = 0; i < countDfsOrder; ++i) {
            if (1 << (j + 1) <= i) ++j;
            log2[i] = j;
        }
    }

    // answers RMQ in block #bl [l;r] in O(1)
    int LCAInBlocks(int blockId, int l, int r) {
        return blockRmq[blockHash[blockId]][l][r] + blockId * block;
    }

    // answers LCA in O(1)
    public int LCA(int v, int u) {
        int l = posInDfsOrder[v], r = posInDfsOrder[u];
        if (l > r) {
            int t = l;
            l = r;
            r = t;
        }
        int leftBlock = l / block, rightBlock = r / block;
        if (leftBlock == rightBlock) {
            return dfsOrder[LCAInBlocks(leftBlock, l % block, r % block)];
        }
        int ans1 = LCAInBlocks(leftBlock, l % block, block - 1);
        int ans2 = LCAInBlocks(rightBlock, 0, r % block);
        int ans = minHeight(ans1, ans2);
        if (leftBlock < rightBlock - 1) {
            int pw2 = log2[rightBlock-leftBlock-1];
            int ans3 = blockTable[leftBlock + 1][pw2];
            int ans4 = blockTable[rightBlock - (1 << pw2)][pw2];
            ans = minHeight(ans, minHeight(ans3, ans4));
        }
        return dfsOrder[ans];
    }

    // End of LCA
}

class ArrayUtils {

    public static void fill(int[][] f, int value) {
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], value);
        }
    }

    public static void fill(int[][][] a, int value) {
        for (int i = 0; i < a.length; ++i) {
            fill(a[i], value);
        }
    }

}

