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.IOException;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;

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

class TaskE {
    private static final int MAXLOGN = 20;
    Suffix[] L;
    int totalLen;
    int maxLen;
    int[][] P;
    int[][] rmq;
    int len;
    int[] lg;
    int[] G;

    public void solve(int testNumber, StreamInputReader in, PrintWriter out) {
        int N = in.nextInt();
        int K = in.nextInt();
        String[] A = new String[N];

        totalLen = 0;
        maxLen = 0;
        for(int i = 0; i < N; i++) {
            A[i] = in.nextString();
            totalLen += A[i].length();
            maxLen = Math.max(maxLen, A[i].length());
        }
        totalLen += N - 1;

        if(K == 1) {
            for(int i = 0; i < N; i++)
                out.print(((long)A[i].length() * (A[i].length() + 1) / 2) + " ");
            return;
        }

        int[] totalString = new int[totalLen];
        int[] inputString = new int[totalLen];
        int uniqueSeparator = 1000;
        int idx = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < A[i].length(); j++) {
                inputString[idx] = i;
                totalString[idx++] = (int)A[i].charAt(j);
            }
            if(i < N - 1) {
                inputString[idx] = -1;
                totalString[idx++] = uniqueSeparator++;
            }
        }
        if(idx != totalLen)
            throw new RuntimeException();

        L = new Suffix[totalLen];
        for(int i = 0; i < totalLen; i++)
            L[i] = new Suffix();


        P = new int[MAXLOGN][totalLen];
        for(int i = 0; i < totalLen; i++) {
            P[0][i] = totalString[i];
            if(totalString[i] > 256)
                P[0][i] = -P[0][i];
        }


        int cnt;
        for(len = 1, cnt = 1; (cnt >> 1) <= maxLen; len++, cnt <<= 1) {
            for(int i = 0; i < totalLen; i++) {
                L[i].nr[0] = P[len - 1][i];
                L[i].nr[1] = i + cnt < totalLen ? P[len - 1][i + cnt] : -1;
                L[i].p = i;
            }

            Arrays.sort(L);

            for(int i = 0; i < totalLen; i++)
                if(i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1])
                    P[len][L[i].p] = P[len][L[i - 1].p];
                else
                    P[len][L[i].p] = i;
        }

        for(int i = 0; i < totalLen; i++)
            P[len - 1][L[i].p] = i;

        rmq = new int[MAXLOGN][totalLen];
        for(int i = 0; i < totalLen - 1; i++)
            rmq[0][i] = lcp(L[i].p, L[i + 1].p);
        for(int j = 1; (1 << j) <= totalLen; j++)
            for(int i = 0; i + (1 << j) <= totalLen; i++)
                rmq[j][i] = Math.min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);

        lg = new int[totalLen + 1];
        lg[1] = 0;
        for(int i = 2; i <= totalLen; i++)
            lg[i] = lg[i / 2] + 1;

        G = new int[totalLen];
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        int[] getKey = new int[N];
        Arrays.fill(getKey, -1);

        for(int i = 0; i < totalLen; i++) {
            G[i] = -10000000;
            if(inputString[L[i].p] == -1)
                continue;
            int iStr = inputString[L[i].p];
            if(getKey[iStr] != -1)
                map.remove(getKey[iStr]);
            map.put(i, iStr);
            getKey[iStr] = i;
            while(map.size() > K)
                map.remove(map.firstKey());
            if(map.size() == K)
                G[i] = map.firstKey();
        }

        long[] ans = new long[N];
        for(int i = 0; i < totalLen; i++)
            if(totalString[i] < 256) {
                int st = 0;
                int dr = totalLen - i;
                int m;
                int max = -1;
                while(st <= dr) {
                    m = (st + dr) / 2;
                    if(good(P[len - 1][i], m)) {
                        st = m + 1;
                        max = Math.max(max, m);
                    }
                    else dr = m - 1;
                }

                ans[inputString[i]] += max;
            }

        for(int i = 0; i < N; i++)
            out.print(ans[i] + " ");
	}

    private boolean good(int pos, int len) {
        if(len == 0)
            return true;
        if(len > maxLen)
            return false;
        int r = pos;
        int st = pos + 1;
        int dr = totalLen - 1;
        int m;
        while(st <= dr) {
            m = (st + dr) / 2;
            if(query(pos, m) >= len) {
                r = Math.max(r, m);
                st = m + 1;
            }
            else dr = m - 1;
        }

        int l = pos;
        st = 0;
        dr = pos - 1;
        while(st <= dr) {
            m = (st + dr) / 2;
            if(query(m, pos) >= len) {
                l = Math.min(l, m);
                dr = m - 1;
            }
            else st = m + 1;
        }

        if(G[r] >= l)
            return true;
        return false;
    }

    private int query(int x, int y) {
        y--;
        int k = lg[y - x + 1];
        int ret = Math.min(rmq[k][x], rmq[k][y - (1 << k) + 1]);
        return ret;
    }

    private int lcp(int x, int y) {
        int ret = 0;
        int k = len - 1;
        while(k >= 0 && x < totalLen && y < totalLen) {
            if(P[k][x] == P[k][y]) {
                ret += (1 << k);
                x += (1 << k);
                y += (1 << k);
            }
            k--;
        }
        return ret;
    }

    private class Suffix implements Comparable<Suffix> {
        public int[] nr;
        public int p;

        private Suffix() {
            nr = new int[2];
        }

        public int compareTo(Suffix s) {
            if(nr[0] == s.nr[0]) {
                return nr[1] - s.nr[1];
            }
            return nr[0] - s.nr[0];
        }
    }
}

class StreamInputReader extends InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar, numChars;

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

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

    }

abstract class InputReader {

    public abstract int read();

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

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

