Problem: The best programmers of Embezzland compete to develop a part of the project called "e-Government" — the system of automated statistic collecting and press analysis.

We know that any of the k citizens can become a member of the Embezzland government. The citizens' surnames are a1, a2, ..., ak. All surnames are different. Initially all k citizens from this list are members of the government. The system should support the following options:

  * Include citizen ai to the government. 
  * Exclude citizen ai from the government. 
  * Given a newspaper article text, calculate how politicized it is. To do this, for every active government member the system counts the number of times his surname occurs in the text as a substring. All occurrences are taken into consideration, including the intersecting ones. The degree of politicization of a text is defined as the sum of these values for all active government members. 



Implement this system.

Input

The first line contains space-separated integers n and k (1 ≤ n, k ≤ 105) — the number of queries to the system and the number of potential government members.

Next k lines contain the surnames a1, a2, ..., ak, one per line. All surnames are pairwise different.

Next n lines contain queries to the system, one per line. Each query consists of a character that determines an operation and the operation argument, written consecutively without a space.

Operation "include in the government" corresponds to the character "+", operation "exclude" corresponds to "-". An argument of those operations is an integer between 1 and k — the index of the citizen involved in the operation. Any citizen can be included and excluded from the government an arbitrary number of times in any order. Including in the government a citizen who is already there or excluding the citizen who isn't there changes nothing.

The operation "calculate politicization" corresponds to character "?". Its argument is a text.

All strings — surnames and texts — are non-empty sequences of lowercase Latin letters. The total length of all surnames doesn't exceed 106, the total length of all texts doesn't exceed 106.

Output

For any "calculate politicization" operation print on a separate line the degree of the politicization of the given text. Print nothing for other operations.

Examples

Input

7 3
a
aa
ab
?aaab
-2
?aaab
-3
?aaab
+2
?aabbaa


Output

6
4
3
6

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.StringTokenizer;

/**
 * Created by Hedin on 20-Mar-15.
 */
public class ProblemE {

    static final int MAX = 1001000;
    static final int MAX_CHAR = 26;

//    private static class IntArrayOnShorts {
//        private short[] array;
//
//        private int bitsStart;
//        private int index;
//        private int bitsInAnother;
//
//        public IntArrayOnShorts(int size) {
//            array = new short[size * 20 / 16 + 1];
//        }
//
//        public void setValue(int position, int value) {
//            bitsStart = position * 20;
//            index = bitsStart / 16;
//            switch (bitsStart % 16) {
//                case 0:
//                    array[index] = (short) (value >> 4);
//                    array[index + 1] |= (short) (value & ~(value >> 4));
//                    break;
//                case 4:
//                    array[index] |= (short) (value >> 8);
//                    array[index + 1] |= (short) (value & ~(value >> 8));
//                    break;
//                case 8:
//                    pw.println(Integer.toBinaryString(value));
//                    pw.println(Integer.toBinaryString((short) (value >> 12)));
//                    pw.println(Integer.toBinaryString(value & ~(value >> 12)));
//                    array[index] |= (short) (value >> 12);
//                    array[index + 1] |= (short) (value & ~(value >> 12));
//                    break;
//                case 12:
//                    array[index] |= (short) (value >> 16);
//                    array[index + 1] = (short) (value & ~(value >> 16));
//                    break;
//            }
//        }
//
//        public int getValue(int position) {
//            bitsStart = position * 20;
//            index = bitsStart / 16;
//            switch (bitsStart % 16) {
//                case 0:
//                    return (array[index] << 4) + (array[index + 1] >> 12);
//                case 4:
//                    return ((array[index] & ~(array[index] >> 12)) << 8) + (array[index + 1] >> 8);
//                case 8:
//                    return ((array[index] & ~(array[index] >> 8)) << 12) + (array[index + 1] >> 12);
//                default:
//                    return ((array[index] & ~(array[index] >> 4)) << 16) + (array[index + 1] >> 16);
//            }
//        }
//    }

    static int edgeNumberBor = 0;
    static int[] edgeBorSymbol = new int[MAX];
    static int[] edgeBorVertex = new int[MAX];
    static int[] nextEdgeBor = new int[MAX];
    static int[] firstEdgeBor = new int[MAX];

    static int[] fail = new int[MAX];
    static int[] end = new int[MAX];
    static int[] wordEnd = new int[1000000];
    static boolean[] active = new boolean[100000];
    static int[] queue = new int[MAX];

    static int edgeNumberEuler = 0;
    static int[] edgeEuler = new int[MAX];
    static int[] nextEdgeEuler = new int[MAX];
    static int[] firstEdgeEuler = new int[MAX];

    static int treeSize = 1;
    static int[] directEncounter = new int[MAX];
    static int[] reverseEncounter = new int[MAX];

    static int fenwickTree[] = new int[2097152];

    static int counter = 0;
    static int fenwickRes = 0;

    static void addEdgeToEulerTree(int v, int g) {
        edgeEuler[edgeNumberEuler] = g;
        nextEdgeEuler[edgeNumberEuler] = firstEdgeEuler[v];
        firstEdgeEuler[v] = edgeNumberEuler;
        edgeNumberEuler++;
    }

    static void addEdgeToBor(int parent, int child, int symbol) {
        edgeBorVertex[edgeNumberBor] = child;
        edgeBorSymbol[edgeNumberBor] = symbol;
        nextEdgeBor[edgeNumberBor] = firstEdgeBor[parent];
        firstEdgeBor[parent] = edgeNumberBor;
        edgeNumberBor++;
    }

    static void buildFenwickTree(int v) {
        int edgeIndex = firstEdgeEuler[v];
        int g;

        while (edgeIndex != -1) {
            g = edgeEuler[edgeIndex];
            edgeIndex = nextEdgeEuler[edgeIndex];
            directEncounter[g] = treeSize;
            addToFenwickTree(treeSize++, end[g]);
            buildFenwickTree(g);
            reverseEncounter[g] = treeSize;
            addToFenwickTree(treeSize++, -end[g]);
        }
    }

    public static void addToFenwickTree(int index, int value) {
//        pw.println(value);
        for (counter = index; counter < fenwickTree.length; counter |= counter + 1) {
            fenwickTree[counter] += value;
        }
    }

    public static int getSumFromFenwickTree(int index) {
        fenwickRes = 0;
        for (counter = index; counter >= 0; counter = (counter & (counter + 1)) - 1) {
            fenwickRes += fenwickTree[counter];
        }
        return fenwickRes;
    }

    private static int getBorEdgeForChar(int state, int symbol) {
        int edgeIndexBor = firstEdgeBor[state];

        while (edgeIndexBor != -1) {
            if (edgeBorSymbol[edgeIndexBor] == symbol) {
                return edgeBorVertex[edgeIndexBor];
            }
            edgeIndexBor = nextEdgeBor[edgeIndexBor];
        }
        return -1;
    }

    static void buildAhoKorasik(int wordsNumber) {
        for (int i = 0; i < MAX; i++) {
            fail[i] = -1;
            firstEdgeEuler[i] = -1;
            firstEdgeBor[i] = -1;
            edgeBorSymbol[i] = -1;
        }

        int states = 1;
        int currentState = 0;
        int nextState;

        for (int i = 0; i < wordsNumber; i++) {
            String word = sc.next();
            currentState = 0;
            for (char c : word.toCharArray()) {
                nextState = getBorEdgeForChar(currentState, c - 'a');
                if (nextState == -1) {
                    addEdgeToBor(currentState, states, c - 'a');
                    currentState = states++;
                } else {
                    currentState = nextState;
                }
            }
            end[currentState]++;
            wordEnd[i] = currentState;
            active[i] = true;
        }

        for (int c = 0; c < MAX_CHAR; c++) {
            if (getBorEdgeForChar(0, c) == -1) {
                addEdgeToBor(0, 0, c);
            }
        }

        int queuePointer = 0;
        int queueEnd = 0;
        int childState;

        for (int c = 0; c < MAX_CHAR; c++) {
            childState = getBorEdgeForChar(0, c);
            if (childState != -1 && childState != 0) {
                fail[childState] = 0;
                addEdgeToEulerTree(0, childState);
                queue[queueEnd++] = childState;
            }
        }

        while (queuePointer != queueEnd) {
            int state = queue[queuePointer++];
            for (int c = 0; c < MAX_CHAR; c++) {
                childState = getBorEdgeForChar(state, c);
                if (childState != -1) {
                    int failure = fail[state];
                    while (getBorEdgeForChar(failure, c) == -1) {
                        failure = fail[failure];
                    }
                    failure = getBorEdgeForChar(failure, c);
                    fail[childState] = failure;
                    addEdgeToEulerTree(failure, childState);
                    queue[queueEnd++] = childState;
                }
            }
        }

        queue = null;
        System.gc();
    }

    private static int getNextState(int currentState, char nextInput) {
        int answer = currentState;
        int c = nextInput - 'a';
        while (getBorEdgeForChar(answer, c) == -1) {
            answer = fail[answer];
        }

        return getBorEdgeForChar(answer, c);
    }

    private static void addMember(int index) {
        if (active[index]) {
            return;
        }
        active[index] = true;
        end[wordEnd[index]]++;
        addToFenwickTree(directEncounter[wordEnd[index]], 1);
        addToFenwickTree(reverseEncounter[wordEnd[index]], -1);
    }

    private static void removeMember(int index) {
        if (!active[index]) {
            return;
        }
        active[index] = false;
        end[wordEnd[index]]--;
        addToFenwickTree(directEncounter[wordEnd[index]], -1);
        addToFenwickTree(reverseEncounter[wordEnd[index]], 1);
    }

    private static void solve() {
        int n = sc.nextInt();
        int k = sc.nextInt();
        buildAhoKorasik(k);
        buildFenwickTree(0);
        pw.flush();
        for (int i = 0; i < n; i++) {
            String query = sc.next();
            if (query.startsWith("+")) {
                addMember(Integer.parseInt(query.substring(1)) - 1);
            } else if (query.startsWith("-")) {
                removeMember(Integer.parseInt(query.substring(1)) - 1);
            } else {
                int currentState = 0;
                int res = 0;
                for (char c : query.substring(1).toCharArray()) {
                    currentState = getNextState(currentState, c);
                    res += getSumFromFenwickTree(directEncounter[currentState]);
                }
                pw.println(res);
            }
        }
    }

    static ContestScanner sc;
    static PrintWriter pw;

    public static void main(String[] args) {
        sc = new ContestScanner(System.in);
        pw = new PrintWriter(System.out);

        solve();

        sc.close();
        pw.flush();
        pw.close();
    }

    static class ContestScanner {
        BufferedReader reader;
        StringTokenizer tokenizer;

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

        public void close() {
            try {
                reader.close();
            } catch (IOException ignored) {}
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String s = null;
                try {
                    s = reader.readLine();
                } catch (IOException ignored) {}
                if (s == null) {
                    return null;
                }
                tokenizer = new StringTokenizer(s);
            }
            return tokenizer.nextToken();
        }

        boolean hasMoreTokens() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String s = null;
                try {
                    s = reader.readLine();
                } catch (IOException ignored) {}
                if (s == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}