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.*;
import java.util.*;

public class Main2{
	static class suffixArrayIterative {
		int[][]arrs;
		int[]in;
		int n;
		public suffixArrayIterative(int[]in) {
			this.n=in.length;//O(n*log(n))
			this.in=in;
			arrs=solve();
		}
		int[] saArr() {
			return arrs[0];
		}
		int[] cArr() {
			return arrs[1];
		}
		int[][] solve(){
			int n=in.length;//O(n*log(n))
			int[][]a=new int[n][2];
			for(int i=0;i<in.length;i++) {
				a[i]=new int[] {in[i],i};
			}
			Arrays.sort(a,(x,y)->x[0]-y[0]);
			int[]sa=new int[n],c=new int[n];
			for(int i=0;i<n;i++) {
				sa[i]=a[i][1];
			}
			c[a[0][1]]=0;
			for(int i=1;i<n;i++) {
				c[a[i][1]]=(a[i][0]==a[i-1][0])?c[a[i-1][1]]:c[a[i-1][1]]+1;
			}
			int k=0;
			while((1<<k)<n) {
				for(int i=0;i<n;i++) {
					sa[i]=(sa[i]+n-(1<<k))%n;
				}
				sa=countingSort(sa, c);
				
				int[]newc=new int[n];
				newc[sa[0]]=0;
				for(int i=1;i<n;i++) {
					int[]curPair=new int[] {c[sa[i]],c[(sa[i]+(1<<k))%n]};
					int[]prevPair=new int[] {c[sa[i-1]],c[(sa[i-1]+(1<<k))%n]};
					newc[sa[i]]=(compare(prevPair, curPair)==0)?newc[sa[i-1]]:(newc[sa[i-1]]+1);
				}
				c=newc;
				k++;
			}
			return new int[][] {sa,c};
		}
		
		int compare(int[]x,int[]y) {
			return x[0]!=y[0]?x[0]-y[0]:x[1]-y[1];
		}
		int[] countingSort(int[]sa,int[]c) {
			int n=sa.length;
			int[]cnt=new int[n];
			for(int i:sa) {
				cnt[c[i]]++;
			}
			int[]pointers=new int[n];
			pointers[0]=0;
			for(int i=1;i<n;i++) {
				pointers[i]=pointers[i-1]+cnt[i-1];
			}
			int[]newSa=new int[n];
			for(int i:sa) {
				newSa[pointers[c[i]]++]=i;
			}
			return newSa;
		}
		int[] lcpArr() {
			int[]sa=saArr();
			int[]c=cArr();
			int[]lcp=new int[n];
			int k=0;
			for(int i=0;i<n-1;i++) {
				int cur=i,prev=sa[c[i]-1];
				while(in[cur+k]==in[prev+k])k++;
				lcp[c[i]]=k;
				k=Math.max(k-1, 0);
			}
			return lcp;
		}
	}
	static public class SparseTable {
		int[]log,min[],arr;
		int inf=(int)1e9;
		SparseTable(int[]in,int n) {
			arr=in;
			log = new int[n+1];
			for (int i = 2; i <= n; i++)
				log[i] = log[i / 2] + 1;
			
			min=new int[n][22];
			for(int i=0;i<n;i++) {
				min[i][0]=i;
			}
			for(int i=1,len=2;len<=n;i++,len<<=1) {
				for(int j=0;j<n;j++) {
					int u=min[j][i-1],v=j+(len>>1)>=n?inf:min[j+(len>>1)][i-1];
					if(v==inf) {
						min[j][i]=u;
					}
					else
						min[j][i]=(arr[u]<arr[v]?u:v);
				}
			}
		}
		int query(int l,int r) {
			int len = r - l + 1;
			int lg = log[len];
			int u = min[l][lg];
			int v = min[r - (1 << lg) + 1][lg];
			int bestIdx = arr[u] < arr[v] ? u : v;
			return arr[bestIdx];//or return bestIdx if we want the best index
		}
		
	}
	static void main() throws Exception{
		int n=sc.nextInt(),k=sc.nextInt();
		String[]in=new String[n];
		int tot=0;
		for(int i=0;i<n;i++) {
			in[i]=sc.nextLine();
			tot+=in[i].length()+1;
		}
		int[]s=new int[tot];
		int[]index=new int[tot];
		int[]lenSuff=new int[tot];
		int idx=0;
		int block=-1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<in[i].length();j++) {
				index[idx]=i;
				lenSuff[idx]=in[i].length()-j;
				s[idx++]=(in[i].charAt(j)-'a');
			}
			lenSuff[idx]=0;
			index[idx]=i;
			s[idx++]=block--;
		}
		suffixArrayIterative sai=new suffixArrayIterative(s);
		int[]sa=sai.saArr();
		SparseTable st=new SparseTable(sai.lcpArr(), tot);
		HashMap<Integer, Integer>cur=new HashMap<Integer, Integer>();
		int[]left=new int[tot];
		Arrays.fill(left, -1);
		int l=0,r=0;
		while(r<tot) {
			if(cur.size()<k) {
				put(cur, index[sa[r++]]);
				continue;
			}
			while(cur.size()>=k) {
				left[r-1]=l;
				remove(cur, index[sa[l++]]);
			}
		}
		while(cur.size()>=k) {
			left[r-1]=l;
			remove(cur, index[sa[l++]]);
		}
		for(int i=1;i<tot;i++) {
			left[i]=Math.max(left[i], left[i-1]);
		}
		long[]ans=new long[n];
		for(int i=0;i<tot;i++) {
			int curSuff=sa[i];
			if(s[curSuff]<0)continue;
			int lo=1,hi=lenSuff[curSuff];
			int biggest=0;
			while(lo<=hi) {
				int len=(lo+hi)>>1;
				int lor=i+1,hir=tot-1,lol=0,hil=i-1;
				int right=i,le=i;
				while(lor<=hir) {
					int mid=(lor+hir)>>1;
					if(st.query(i+1, mid)>=len) {
						right=mid;
						lor=mid+1;
					}
					else {
						hir=mid-1;
					}
				}
				while(lol<=hil) {
					int mid=(lol+hil)>>1;
					if(st.query(mid+1, i)>=len) {
						le=mid;
						hil=mid-1;
					}
					else {
						lol=mid+1;
					}
				}
				if(le<=left[right]) {
					biggest=len;
					lo=len+1;
				}
				else {
					hi=len-1;
				}
			}
			ans[index[curSuff]]+=biggest;
		}
		for(int i=0;i<n;i++)pw.print(ans[i]+" ");
	}
	static void put(HashMap<Integer, Integer>hm,int x) {
		hm.put(x, hm.getOrDefault(x, 0)+1);
	}
	static void remove(HashMap<Integer, Integer>hm,int x) {
		int occ=hm.get(x);
		if(occ==1) {
			hm.remove(x);
		}
		else {
			hm.put(x, occ-1);
		}
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc=1;
//		tc=sc.nextInt();
		while(tc-->0)
			main();
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner  sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}