// Arup Guha
// 12/11/2025
// Solution to 2025 UCF HS Online D2 Problem A: Alien Anatomy

import java.util.*;

public class anatomy {

	public static HashMap<Long, HashSet<Long> > map;
	public static int n;
	public static int[] orig;
	public static int[] base;
	public static int[] letMap;
	
	public static void main(String[] args) {
	
		// For our pre-comp
		map = new HashMap<Long, HashSet<Long>>();
	
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		int numP = stdin.nextInt();
		int numQ = stdin.nextInt();
		int len = stdin.nextInt();
		
		orig = new int[n];
		base = new int[n];
		letMap = new int[63];
		for (int i=0; i<63; i++)
			letMap[i] = i;
		
		// Store original sequence as integers.
		String tmp = stdin.next();
		for (int i=0; i<n; i++)
			orig[i] = convert(tmp.charAt(i));
		
		// Use smaller value as base value.
		for (int i=0; i<numP; i++) {
			int a = convert(stdin.next().charAt(0));
			int b = convert(stdin.next().charAt(0));
			letMap[a] = Math.min(a, b);
			letMap[b] = Math.min(a, b);
		}
		
		// Now we can store base.
		for (int i=0; i<n; i++)
			base[i] = letMap[orig[i]];
		
		/*** Pre-comp here ***/

		/** Storing each string in base 64...convert shows char values I am using. ***/
		long hash = 0;
		long baseH = 0;
		for (int i=0; i<len; i++) {
			hash = (hash<<6) + orig[i];
			baseH = (baseH<<6) + base[i];
		}
			
		// Start this entry in the table.
		HashSet<Long> ans = new HashSet<Long>();
		ans.add(hash);
		map.put(baseH, ans);
			
		// e is the start index of this substring.
		for (int e=len; e<n; e++) {
				
			// Roll both hashes.
			hash = hash - ( ((long)orig[e-len])<<(6*len-6));
			hash = (hash<<6) + orig[e];
			baseH = baseH - ( ((long)base[e-len])<<(6*len-6));
			baseH = (baseH<<6) + base[e];
				
			if (!map.containsKey(baseH))
				map.put(baseH, new HashSet<Long>());
				
			// Get the list this is mapped to and add hash to it.
			map.get(baseH).add(hash);
		}
		
		// Process queries.
		for (int i=0; i<numQ; i++) {
			
			// Get string's hash.
			String s = stdin.next();
			hash = 0;
			for (int j=0; j<s.length(); j++) 
				hash = (hash<<6) + letMap[convert(s.charAt(j))];
			
			// Just want the size of the mapped set.
			if (map.containsKey(hash))
				System.out.println(map.get(hash).size());
			else
				System.out.println(0);
		}
	}
	
	// Converts c to 1 to 62 value. (I could have done 0 to 61 but I was initially 
	// going to store hashes of strings of different length.)
	public static int convert(char c) {
		if (c>='A' && c<='Z') return c - 'A' + 1;
		if (c>='a' && c<='z') return c - 'a' + 27;
		return c - '0' + 53;
	}
}