Problem: You want to perform the combo on your opponent in one popular fighting game. The combo is the string s consisting of n lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in s. I.e. if s="abca" then you have to press 'a', then 'b', 'c' and 'a' again.

You know that you will spend m wrong tries to perform the combo and during the i-th try you will make a mistake right after p_i-th button (1 ≤ p_i < n) (i.e. you will press first p_i buttons right and start performing the combo from the beginning). It is guaranteed that during the m+1-th try you press all buttons right and finally perform the combo.

I.e. if s="abca", m=2 and p = [1, 3] then the sequence of pressed buttons will be 'a' (here you're making a mistake and start performing the combo from the beginning), 'a', 'b', 'c', (here you're making a mistake and start performing the combo from the beginning), 'a' (note that at this point you will not perform the combo because of the mistake), 'b', 'c', 'a'.

Your task is to calculate for each button (letter) the number of times you'll press it.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Then t test cases follow.

The first line of each test case contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 2 ⋅ 10^5) — the length of s and the number of tries correspondingly.

The second line of each test case contains the string s consisting of n lowercase Latin letters.

The third line of each test case contains m integers p_1, p_2, ..., p_m (1 ≤ p_i < n) — the number of characters pressed right during the i-th try.

It is guaranteed that the sum of n and the sum of m both does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5, ∑ m ≤ 2 ⋅ 10^5).

It is guaranteed that the answer for each letter does not exceed 2 ⋅ 10^9.

Output

For each test case, print the answer — 26 integers: the number of times you press the button 'a', the number of times you press the button 'b', ..., the number of times you press the button 'z'.

Example

Input


3
4 2
abca
1 3
10 5
codeforces
2 8 3 2 9
26 10
qwertyuioplkjhgfdsazxcvbnm
20 10 1 2 3 5 10 5 9 4


Output


4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0 
2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2 

Note

The first test case is described in the problem statement. Wrong tries are "a", "abc" and the final try is "abca". The number of times you press 'a' is 4, 'b' is 2 and 'c' is 2.

In the second test case, there are five wrong tries: "co", "codeforc", "cod", "co", "codeforce" and the final try is "codeforces". The number of times you press 'c' is 9, 'd' is 4, 'e' is 5, 'f' is 3, 'o' is 9, 'r' is 3 and 's' is 1.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class C {
    static final int MOD = 1000000007; // 1e9 + 7
    static final boolean AUTO_FLUSH = false; // slow if true
    // int = num(); // long = ll();
    // string = next(); // a string line = line();
    // ---------------------------------- \

    void main() {
        int t = num();
        while (t-- > 0) {
            int n = num(), m = num();
            char[] ch = line().toCharArray();
            int[] arr = new int[m], ans = new int[26], curr = new int[26];
            for (int i = 0; i < m; ++i) {
                arr[i] = num();
            }
            Arrays.sort(arr);
            int now = 0;
            for (int i = 0; i < n; ++i) {
                ++curr[ch[i] - 'a'];
                if (arr.length > now && i == arr[now] - 1) {
                    while (arr.length > now && i == arr[now] - 1) {
                        ++now;
                        for (int j = 0; j < 26; ++j) {
                            ans[j] += curr[j];
                        }
                    }
                }
            }
            for (int j = 0; j < 26; ++j) {
                ans[j] += curr[j];
            }
            out(ans[0]);
            for (int i = 1; i < 26; ++i) {
                out(" " + ans[i]);
            }
            outln();
        }
    }

    // ---------------------------------- \
    // #region
    public static void main(String[] args) {
        startTime();
        new C().main();
        boolean endsWithEnter = TO_BE_PRINTED.length() == 0 || TO_BE_PRINTED.charAt(TO_BE_PRINTED.length() - 1) == '\n';
        flush();
        if (!endsWithEnter)
            log('\n');
        logTime();
        logMem();
    }

    static Random RAND = new Random();

    static int random(int from, int to) {
        return RAND.nextInt(to - from + 1) + from;
    }

    static void logTime() {
        log("Time: " + getTime() + "ms");
    }

    static void logMem() {
        log("Memory (End): " + (int) (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1024
                + " KB");
    }

    static long ll() {
        return Long.parseLong(next());
    }

    static int num() {
        return Integer.parseInt(next());
    }

    static void generateInputMode() throws Exception {
        System.setOut(new PrintStream(new FileOutputStream("~/kode/input.txt")));
    }

    static String line() {
        if (!tokenize())
            return null;
        INPUT_STREAM.setLength(0);
        if (STRING_TOKENIZER.hasMoreTokens())
            INPUT_STREAM.append(STRING_TOKENIZER.nextToken());
        while (STRING_TOKENIZER.hasMoreTokens())
            INPUT_STREAM.append(' ').append(STRING_TOKENIZER.nextToken());
        return INPUT_STREAM.length() == 0 ? null : INPUT_STREAM.toString();
    }

    static void startTime() {
        TIME_COMPLEXITY = System.currentTimeMillis();
    }

    static long getTime() {
        return System.currentTimeMillis() - TIME_COMPLEXITY;
    }

    static void flush() {
        System.out.print(TO_BE_PRINTED.toString());
        TO_BE_PRINTED.setLength(0);
    }

    static void out(Object o) {
        TO_BE_PRINTED.append(o);
        if (AUTO_FLUSH)
            flush();
    }

    static void _log(String s) {
        System.err.print(s);
    }

    static void _logln(String s) {
        System.err.println(s);
    }

    static void _logln() {
        System.err.println();
    }

    static void outln(Object o) {
        out(o);
        outln();
    }

    static void outln() {
        out("\n");
    }

    static class Pair implements Comparable<Pair> {
        public int a, b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public static Pair of(int a, int b) {
            return new Pair(a, b);
        }

        @Override
        public int compareTo(Pair p) {
            if (a == p.a)
                return Integer.compare(b, p.b);
            return Integer.compare(a, p.a);
        }

        @Override
        public String toString() {
            return "[" + a + "," + b + "]";
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + a;
            result = prime * result + b;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            if (a != other.a)
                return false;
            if (b != other.b)
                return false;
            return true;
        }
    }

    static void logArr(Object val) {
        Class<?> valKlass = val.getClass();
        Object[] outputArray = null;
        for (Class<?> arrKlass : new Class<?>[] { int[].class, float[].class, double[].class, boolean[].class,
                byte[].class, short[].class, long[].class, char[].class }) {
            if (valKlass.isAssignableFrom(arrKlass)) {
                int arrlength = Array.getLength(val);
                outputArray = new Object[arrlength];
                for (int i = 0; i < arrlength; ++i)
                    outputArray[i] = Array.get(val, i);
                break;
            }
        }
        if (outputArray == null)
            outputArray = (Object[]) val;
        logArr0(outputArray);
    }

    static void logArr0(Object[] objs) {
        if (objs.length == 0) {
            _log("* \n");
            return;
        }
        _log("* " + objs[0]);
        for (int i = 1; i < objs.length; i++)
            _log(objs[i].toString().equals("\n") ? "\n>" : (" " + objs[i]));
        _logln();
    }

    static void log(Object... objs) {
        logArr0(objs);
    }

    static String next() {
        return tokenize() ? STRING_TOKENIZER.nextToken() : null;
    }

    static boolean tokenize() {
        if (STRING_TOKENIZER == null || !STRING_TOKENIZER.hasMoreTokens()) {
            try {
                STRING_TOKENIZER = new StringTokenizer(STREAM_READER.readLine());
            } catch (Exception _e) {
                return false;
            }
        }
        return true;
    }

    static long TIME_COMPLEXITY;
    static BufferedReader STREAM_READER = new BufferedReader(new InputStreamReader(System.in), 32768);
    static StringTokenizer STRING_TOKENIZER;
    static StringBuilder INPUT_STREAM = new StringBuilder(), TO_BE_PRINTED = new StringBuilder();
    // #endregion
}