Smith wakes up at the side of a dirty, disused bathroom, his ankle chained to pipes. Next to him is tape-player with a hand-written message "Play Me". He finds a tape in his own back pocket. After putting the tape in the tape-player, he sees a key hanging from a ceiling, chained to some kind of a machine, which is connected to the terminal next to him. After pressing a Play button a rough voice starts playing from the tape:

"Listen up Smith. As you can see, you are in pretty tough situation and in order to escape, you have to solve a puzzle. 

You are given N strings which represent words. Each word is of the maximum length L and consists of characters 'a'-'e'. You are also given M strings which represent patterns. Pattern is a string of length  ≤ L and consists of characters 'a'-'e' as well as the maximum 3 characters '?'. Character '?' is an unknown character, meaning it can be equal to any character 'a'-'e', or even an empty character. For each pattern find the number of words that matches with the given pattern. After solving it and typing the result in the terminal, the key will drop from the ceiling and you may escape. Let the game begin."

Help Smith escape.

Input

The first line of input contains two integers N and M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 5000), representing the number of words and patterns respectively.

The next N lines represent each word, and after those N lines, following M lines represent each pattern. Each word and each pattern has a maximum length L (1 ≤ L ≤ 50). Each pattern has no more that three characters '?'. All other characters in words and patters are lowercase English letters from 'a' to 'e'.

Output

Output contains M lines and each line consists of one integer, representing the number of words that match the corresponding pattern.

Example

Input

3 1
abc
aec
ac
a?c


Output

3

Note

If we switch '?' with 'b', 'e' and with empty character, we get 'abc', 'aec' and 'ac' respectively.
import java.awt.Point;
import java.io.*;
import java.util.*;

public class E{
	static HashMap<String, Integer> freq;
	
	public static void main(String[] args) {
		FastScannerE sc = new FastScannerE(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		Trie trie = new Trie();
		StringBuilder sb = new StringBuilder();
		freq = new HashMap<>();
		
		for(int i = 0 ; i < N ; i++){
			String word = sc.next();
			trie.addWord(word);
			Integer it = freq.get(word);
			if(it == null)
				it = 0;
			it++;
			freq.put(word, it);
//			System.out.println("Adding word: " + word);
//			System.out.flush();
		}
		
		for(int i = 0 ; i < M ; i++){
			String patt = sc.next();
			sb.append(trie.matchPattern(patt)).append('\n');
//			System.out.println("Found result for patt = " + patt);
		}
		
		System.out.println(sb.toString());
	}
	
}

class Trie{
	Node root;
	
	Trie(){
		root = new Node();
	}
	
	public void addWord(String word){
		Node last = root;
		
		for(char c : word.toCharArray()){
			int idx = c - 'a';
			
			if(last.children[idx] == null){
				last.children[idx] = new Node();
			}
			last = last.children[idx];
		}
		last.wordFlag = true;
		last.word = word;
	}
	
	public int matchPattern(String patt){
		HashSet<String> words = new HashSet<>();
		root.matchNode(0, patt.toCharArray(), words);

		int ctr = 0;
		
		for(String str : words){
			ctr += E.freq.get(str);
		}
		
		return ctr;
	}
	
}

class Node{
	Node[] children;
	boolean wordFlag;
	String word;
	
	Node(){
		children = new Node[5];
	}
	
	public void matchNode(int idx, char[] arr, HashSet<String> words){
		
		if(idx >= arr.length){
			if(wordFlag)
				words.add(word);
			return;
		}
		
		if(arr[idx] == '?'){
//			System.out.println("Idx = " + idx);
			matchNode(idx+1, arr, words);
//			System.out.println("Start result is " + result + " for idx = " + idx);
			
			for(Node node: children){
				if(node != null){
//					result += node.matchNode(idx + 1, arr);
					node.matchNode(idx + 1, arr, words);
				}
			}
			return;
//			return result;
		}
		
		int childIdx = arr[idx] - 'a';
		
		if(children[childIdx] == null){
			return;
		}
//		return children[childIdx].matchNode(idx + 1, arr);
		children[childIdx].matchNode(idx + 1, arr, words);
	}
}


class FastScannerE{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastScannerE(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++];
    }

    public int nextInt()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String next()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    
    public String nextLine()
    {
        int c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isLineEndChar(c));
        return res.toString();
    }    
    
    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, nextInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    
    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
    
    public boolean isLineEndChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == '\n' || c == '\r' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}