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.
2
2 2
yz
1 1
2 2
yz
1 1
 1
11 2
thisisatest
3 5

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 

 1 0 0 0 1 0 0 3 5 0 0 0 0 0 0 0 0 0 4 5 0 0 0 0 0 0 


import java.util.*;
import java.io.*;
import java.math.*;


/* Hepler Class Methods **only Few Imp Ones**

* int[][] getIntMatrix(String s,int r,int c)                //Works only for int and long
* char getCharacterValue(int i)
* int getIntegerValueOfCharacter(char c)
* boolean isPerfectSquare(int n)                            // works only for int and long
* int getLargestPrimeFactor(int n)                          //works only for int and long
* boolean isPrime(int n)                                    //works only for int and long
* void printArray(int a[]),                                 //works for all
* void printMatrix(int a[][]),                              //works for all
* void printNestedList(ArrayList<ArrayList<Integer>> a)     //works for all
* boolean isPalindrome                                      //works for all except Character
* T swap(T)                                                 //works only for int[],long[] and String
* T getArraySum(T[])                                        //works only for int[],long[],double[]
* T reverse(T)                                              //works only for String,int and long
* T[] getReverseArray(T[])                                  //works for all
* HashSet<T> getHashSet(T[])                                //works for int[],long[],char[],String[]
* T setBit(T,k,side)                                        //works only when n = int or long and k is always int **returns int or long**
* String setBitString(T,k,side)                             //works only when n = int or long and k is always int **returns String**
* int getSetBits(long n)									//Gives Number of sets bits in a number
* String cvtToBinary(T)
* int cvtToDecimal(String n)                                //Always returns Long
* boolean isPowerOf2(T)
* boolean isSafe(T [][], row,col)                           //Returns whether current row and col are under bounds
* T Log2(T num)                                             //Returns (Math.log(num) / Math.log(2))
* long nCr(long n,long r)                                   // Returns nCr value
* long nCrMod(long n,long r)                                // Returns nCr % MOD value
* */



public class A {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    static Helper sc = new Helper(br);
    static int MOD = 1000000007,INF = Integer.MAX_VALUE,NEG_INF = Integer.MIN_VALUE,SEM_INF = INF / 2;
    //BigInteger B = new BigInteger("1");
    //Scanner scanner = new Scanner(System.in);
    
    public static void main(String args[])
    {
        try {
            int t = sc.getInt(br.readLine());
            while (t-- > 0)
            {
            	testCase();
            }
            out.flush();
        }catch (Exception e){
            System.out.println("Exception Occured: " + e.getMessage());
            e.printStackTrace();
        }
    }

    private static void testCase() throws Exception
    {		
    	int n = sc.nextInt(),m = sc.nextInt();
    	String s = br.readLine();
    	int p[] = sc.getIntArray(br.readLine());
    	HashMap<Character,Integer> mainMap[] = new HashMap[n];
    	int hash[] = new int[26];
    	mainMap[0] = new HashMap<>();
    	mainMap[0].put(s.charAt(0),1);
    	
    	for(int x = 1;x < n;x++) {
    		mainMap[x] = new HashMap<>(mainMap[x - 1]);
    		mainMap[x].put(s.charAt(x),mainMap[x].getOrDefault(s.charAt(x),0) + 1);
    	}
    	for(int x = 0;x < p.length;x++) {
    		p[x]--;
    		fillHash(mainMap,p[x],hash);
    	}
    	fillHash(mainMap[n - 1],hash);
    	for(int x = 0;x < 26;x++)
    		write(hash[x] + " ");
    	writeln();
    }

	private static void fillHash(HashMap<Character, Integer> hashMap, int[] hash) {
		for(char key : hashMap.keySet()) {
			hash[key - 'a'] += hashMap.get(key);
		}
	}

	private static void fillHash(HashMap<Character, Integer>[] mainMap, int i, int[] hash) {
		fillHash(mainMap[i],hash);
	}

	public static void writeln() throws Exception
    {
        out.write("\n");
    }
    public static void write(Object o) throws Exception
    {
        out.write(String.valueOf(o));
    }
    public static void writeln(Object o) throws Exception
    {
        out.write(String.valueOf(o) + "\n");
    }
    public static void println()
    {
        System.out.println();
    }
	public static void print(Object o)
    {
        System.out.print(String.valueOf(o));
    }
    public static void println(Object o)
    {
        System.out.println(String.valueOf(o));
    }
   
    
    static class Helper
    {
        FastReader fr;

        /*Constructor*/

        public Helper(BufferedReader br)
        {
            try{
                fr = new FastReader(br);
            }catch (Exception e){
                System.out.println("Exception Occured: " + e.getMessage());
                e.printStackTrace();
            }
        }


        /* Inputs*/

        public String next() throws Exception
        {
        	return fr.next();
        }
        public int nextInt() throws Exception
        {
            return fr.nextInt();
        }

        public long nextLong() throws Exception
        {
            return fr.nextLong();
        }

        public String trimLine() throws Exception
        {
            return fr.trimLine();
        }

        public String rawLine() throws Exception
        {
            return fr.nextLine();
        }

        public double nextDouble() throws Exception
        {
            return fr.nextDouble();
        }

        public float nextFloat() throws Exception
        {
            return fr.nextFloat();
        }

        public int  [] getIntArray( String s) throws Exception
        {
            String input[] = s.split(" ");
            int res[] = new int[input.length];
            for(int x = 0;x < res.length;x++)
                res[x] = getInt(input[x]);

            return res;
        }
        

        public long  [] getLongArray( String s) throws Exception
        {
            String input[] = s.split(" ");
            long res[] = new long[input.length];
            for(int x = 0;x < res.length;x++)
                res[x] = getLong(input[x]);

            return res;
        }

        public double  [] getDoubleArray( String s) throws Exception
        {
            String input[] = s.split(" ");
            double res[] = new double[input.length];
            for(int x = 0;x < res.length;x++)
                res[x] = getDouble(input[x]);

            return res;
        }

        public int[][] getIntMatrix(String s,int r,int c)
        {
            int i = 0;int mat[][] = new int[r][c];
            String st[] = s.split(" ");
            for(int x = 0;x < r;x++)
                for(int y =0 ;y < c;y++)
                    mat[x][y] = Integer.parseInt(st[i++]);
            return mat;

        }

        public long[][] getlongMatrix(String s,int r,int c)
        {
            int i = 0;long mat[][] = new long[r][c];
            String st[] = s.split(" ");
            for(int x = 0;x < r;x++)
                for(int y =0 ;y < c;y++)
                    mat[x][y] = Long.parseLong(st[i++]);
            return mat;

        }

        public int getInt(String s)
        {
            return Integer.parseInt(s);
        }
        public long getLong(String s)
        {
            return Long.parseLong(s);
        }
        public float getFloat(String s)
        {
            return Float.parseFloat(s);
        }
        public double getDouble(String s)
        {
            return Double.parseDouble(s);
        }

        /*Some basic hepler methods*/

        public char getCharacterValue(int i)
        {
            return (char)i;
        }
        public int getIntegerValueOfCharacter(char c)
        {
            return (int)c;
        }

        public int Log2(int num)
        {
            return (int)(Math.log(num) / Math.log(2));
        }

        public long Log2(long num)
        {
            return (long) (Math.log(num) / Math.log(2));
        }

        public double Log2(double num)
        {
            return (double) (Math.log(num) / Math.log(2));
        }
        
        public long nCr(long n,long r)
        {
            if(r > n - r)
                r = n - r;
            long res = 1;
            for(long x = 0;x < r;x++) {
            	res *= (n - x);
                res /= (x + 1);
            }
            return res;
        }
        
        public long nCrMod(long n,long r,long md)
        {
            if(r > n - r)
                r = n - r;
            long res = 1;
            for(long x = 0;x < r;x++) {
            	res = (res * (n - x)) % md;
                res /= (x + 1);
            }
            return res % md;
        }
        
        public int getGCD(int a,int b)
        {
            if(b == 0)
                return a;
            return getGCD(b,a % b);
        }
        public long getGCD(long a,long b)
        {
            if(b == 0)
                return a;
            return getGCD(b,a % b);
        }
        public double getGCD(double a,double b)
        {
            if(b == 0)
                return a;
            return getGCD(b,a % b);
        }
        public float getGCD(float a,float b)
        {
            if(b == 0)
                return a;
            return getGCD(b,a % b);
        }

        public int getLCM(int a,int b)
        {
            return ((a * b) / getGCD(a,b));
        }
        public long getLCM(long a,long b)
        {
            return ((a * b) / getGCD(a,b));
        }
        public double getLCM(double a,double b)
        {
            return ((a * b) / getGCD(a,b));
        }
        public float getLCM(float a,float b)
        {
            return ((a * b) / getGCD(a,b));
        }
        
        public boolean isSafe(int a[][],int x,int y)
        {
            if(x >=0 && y >= 0 && x < a.length && y < a[0].length)
                return true;
            return false;
        }
        public boolean isSafe(long a[][],int x,int y)
        {
            if(x >=0 && y >= 0 && x < a.length && y < a[0].length)
                return true;
            return false;
        }
        public boolean isSafe(double a[][],int x,int y)
        {
            if(x >=0 && y >= 0 && x < a.length && y < a[0].length)
                return true;
            return false;
        }

        public boolean isSafe(char a[][],int x,int y)
        {
            if(x >=0 && y >= 0 && x < a.length && y < a[0].length)
                return true;
            return false;
        }

        public boolean isPerfectSquare(int n)
        {
            if(n == 0 || n == 1)
                return true;
            if(n == 2 || n == 3)
                return false;
            double d = Math.sqrt(n);

            return (d - Math.floor(d) == 0);
        }

        public boolean isPerfectSquare(long n)
        {
            if(n == 0 || n == 1)
                return true;
            if(n == 2 || n == 3)
                return false;
            double d = Math.sqrt(n);

            return (d - Math.floor(d) == 0);
        }

        public boolean isPowerOf2(long n)
        {
            return n != 0 && (n & (n - 1)) == 0;
        }


        public long fastPow(long n,long p)
        {
            long res = 1;
            while(p > 0){
                if(p % 2 != 0)
                    res = res * n;
                p = p / 2;
                n = n * n;
            }
            return res;
        }
        public long modPow(long n,long p,long md)
        {
            long res = 1;
            n = n % md;
            if(n == 0)
                return 0;
            while(p > 0){
                if(p % 2 != 0)
                    res = ((res % md) * (n % md)) % md;
                p = p / 2;
                n = ((n % md) * (n % md)) % md;
            }
            return (res % md);
        }

        public boolean isPalindrome(int n)
        {
            StringBuilder sb = new StringBuilder(n + "");
            return (Integer.parseInt(sb.reverse().toString()) == n);
        }



        public boolean isPalindrome(long n)
        {
            StringBuilder sb = new StringBuilder(n + "");
            return (Long.parseLong(sb.reverse().toString()) == n);
        }

        public boolean isPalindrome(String s)
        {
            StringBuilder sb = new StringBuilder(s + "");
            return (sb.reverse().toString().equals(s));
        }


        public int getSmallestPrimeFactor(int n)
        {
            if(n == 1 || n == 0)
                return n;
            if(n % 2 == 0)
                return 2;
            else if(n % 3 == 0)
                return 3;
            int pf = -1;
            for(int x = 3;x <= Math.sqrt(n);x += 2)
                if(n % x == 0)
                    return x;
            return n;
        }

        public int getLargestPrimeFactor(int n)
        {
            int pf = -1;

            if(n == 1 || n == 2 || n == 3 || n == 0)
                return n;
            while(n % 2 == 0){
                pf = 2;
                n /= 2;
            }
            for(int x = 3;x <= Math.sqrt(n);x += 2)
                while (n % x == 0){
                    pf = x;
                    n /= x;
                }
            if(n > 2)
                pf = n;
            return pf;
        }

        public long getSmallestPrimeFactor(long n)
        {
            if(n == 1 || n == 0)
                return n;

            if(n % 2 == 0)
                return 2;
            else if(n % 3 == 0)
                return 3;
            for(long x = 3;x <= Math.sqrt(n);x += 2)
                if(n % x == 0)
                    return x;
            return n;
        }

        public long getLargestPrimeFactor(long n)
        {
            long pf = -1;
            if(n == 1 || n == 2 || n == 3 || n == 0)
                return n;
            while(n % 2 == 0){
                pf = 2;
                n /= 2;
            }
            for(long x = 3;x <= Math.sqrt(n);x += 2)
                while (n % x == 0){
                    pf = x;
                    n /= x;
                }
            if(n > 2)
                pf = n;
            return pf;
        }

        public boolean isPrime(int n)
        {
            if(n == 0 || n == 1)
                return false;
            if(getLargestPrimeFactor(n) == n)
                return true;
            return false;
        }

        public boolean isPrime(long n)
        {
            if(n == 0 || n == 1)
                return false;
            if(getLargestPrimeFactor(n) == n)
                return true;
            return false;
        }

        public int getSetBits(long n)
        {
            int count = 0;
            while (n > 0){
                count += n % 2;
                n /= 2;
            }
            return count;
        }

        public int setBit(int n,int k,String side) throws Exception
        {
            if(side.equalsIgnoreCase("r") || side.equalsIgnoreCase("right")){
                return ((1 << k) | n);
            }else if(side.equalsIgnoreCase("l") || side.equalsIgnoreCase("left")){
                return (int)cvtToDecimal(setBitString(n,k,"l"));
            }else
                throw new Exception("Unknown Side of shift! side must be l,left,r,right");

        }

        public long setBit(long n,int k,String side) throws Exception
        {
            if(side.equalsIgnoreCase("r") || side.equalsIgnoreCase("right")){
                return ((1 << k) | n);
            }else if(side.equalsIgnoreCase("l") || side.equalsIgnoreCase("left")){
                return cvtToDecimal(setBitString(n,k,"l"));
            }else
                throw new Exception("Unknown Side of shift! side must be l,left,r,right");


        }

        public String setBitString(int n,int k,String side) throws Exception
        {
            StringBuilder sb = new StringBuilder(cvtToBinary(n) + "");
            if(side.equalsIgnoreCase("r") || side.equalsIgnoreCase("right")){
                sb.setCharAt(sb.length() - 1 - k,'1');
            }else if(side.equalsIgnoreCase("l") || side.equalsIgnoreCase("left")){
                sb.setCharAt(k,'1');
            }else
                throw new Exception("Unknown Side of shift! side must be l,left,r,right");
            return sb.toString();
        }

        public String setBitString(long n, int k,String side) throws Exception
        {
            StringBuilder sb = new StringBuilder(cvtToBinary(n) + "");
            if(side.equalsIgnoreCase("r") || side.equalsIgnoreCase("right")){
                sb.setCharAt(sb.length() - 1 - k,'1');
            }else if(side.equalsIgnoreCase("l") || side.equalsIgnoreCase("left")){
                sb.setCharAt(k,'1');
            }else
                throw new Exception("Unknown Side of shift! side must be l,left,r,right");
            return sb.toString();
        }

        public long cvtToDecimal(String n)
        {
            String num = n;
            long dec_value = 0;

            // Initializing base value to 1,
            // i.e 2^0
            long base = 1;

            int len = num.length();
            for (int i = len - 1; i >= 0; i--) {
                if (num.charAt(i) == '1')
                    dec_value += base;
                base = base * 2;
            }

            return dec_value;
        }

        public String cvtToBinary(int n)
        {
            if(n == 0 || n == 1)
                return "" + n;
            StringBuilder sb = new StringBuilder();
            while (n > 1){
                if(n % 2 == 0)
                    sb.append(0);
                else
                    sb.append(1);
                n /= 2;
            }
            if(n == 1)
                sb.append(1);
            return sb.reverse().toString();
        }

        public String cvtToBinary(long n)
        {
            if(n == 0 || n == 1)
                return "" + n;
            StringBuilder sb = new StringBuilder();
            while (n > 1){
                if(n % 2 == 0)
                    sb.append(0);
                else
                    sb.append(1);
                n /= 2;
            }
            if(n == 1)
                sb.append(1);
            return sb.reverse().toString();
        }

        /*Printing Arena*/

        public void print(BufferedWriter out,Object s) throws Exception
        {
            out.write(String.valueOf(s));
        }

        public void println(BufferedWriter out,Object s) throws Exception
        {
            out.write(String.valueOf(s));
        }

        public void printArray(int a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(String.valueOf(a[x]) + " ");
            if(nextLine)
                System.out.println();

        }

        public void printArray(long a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(String.valueOf(a[x]) + " ");
            if(nextLine)
                System.out.println();

        }

        public void printArray(char a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(String.valueOf(a[x]) + " ");
            if(nextLine)
                System.out.println();

        }

        public void printArray(double a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(String.valueOf(a[x]) + " ");
            if(nextLine)
                System.out.println();

        }
        public void printArray(String a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(String.valueOf(a[x]) + " ");
            if(nextLine)
                System.out.println();

        }

        public void printArray(Object a[],int s,int e,boolean nextLine)
        {
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + s + ", " + e + "] Array Size: " + a.length);
            for(int x = s;x <= e;x++)
                System.out.print(a[x].toString() + " ");
            if(nextLine)
                System.out.println();

        }


        public void printMatrix(int a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(a[x][y] + " ");
                System.out.println();
            }

        }

        public void printMatrix(long a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(String.valueOf(a[x][y]) + " ");
                System.out.println();
            }

        }
        public void printMatrix(char a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(String.valueOf(a[x][y]) + " ");
                System.out.println();
            }

        }
        public void printMatrix(double a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(String.valueOf(a[x][y]) + " ");
                System.out.println();
            }

        }

        public void printMatrix(String a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(String.valueOf(a[x][y]) + " ");
                System.out.println();
            }

        }

        public void printMatrix(Object a[][])
        {
            for(int x = 0;x < a.length;x++){
                for (int y = 0;y < a[0].length;y++)
                    System.out.print(a[x][y].toString() + " ");
                System.out.println();
            }

        }


        public void printIntNestedList(ArrayList<ArrayList<Integer>> a)
        {
            for(int x = 0;x < a.size();x++){
                ArrayList<Integer> al = a.get(x);
                for(int y = 0;y < al.size();y++)
                    System.out.print(String.valueOf(al.get(y)) + " ");
                System.out.println();
            }
        }
        public void printLongNestedList(ArrayList<ArrayList<Long>> a)
        {
            for(int x = 0;x < a.size();x++){
                ArrayList<Long> al = a.get(x);
                for(int y = 0;y < al.size();y++)
                    System.out.print(String.valueOf(al.get(y)) + " ");
                System.out.println();
            }
        }

        public void printCharNestedList(ArrayList<ArrayList<Character>> a)
        {
            for(int x = 0;x < a.size();x++){
                ArrayList<Character> al = a.get(x);
                for(int y = 0;y < al.size();y++)
                    System.out.print(String.valueOf(al.get(y)) + " ");
                System.out.println();
            }
        }

        public void printStringNestedList(ArrayList<ArrayList<String>> a)
        {
            for(int x = 0;x < a.size();x++){
                ArrayList<String> al = a.get(x);
                for(int y = 0;y < al.size();y++)
                    System.out.print(String.valueOf(al.get(y)) + " ");
                System.out.println();
            }
        }

        public String swap(String st,int i,int j)
        {
            StringBuilder sb = new StringBuilder(st);
            sb.setCharAt(i,st.charAt(j));
            sb.setCharAt(j,st.charAt(i));
            return sb.toString();
        }

        public int [] swap(int a[],int i,int j)
        {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            return a;
        }

        public long[] swap(long a[],int i,int j)
        {
            long t = a[i];
            a[i] = a[j];
            a[j] = t;
            return a;
        }

        public long getArraySum(int a[],int s,int e)
        {
            long sum = 0;
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + e + ", " + s + "]");
            for(int x = s;x <= e;x++)
                sum += a[x];
            return sum;

        }

        public long getArraySum(long a[],int s,int e)
        {
            long sum = 0;
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + e + ", " + s + "]");
            for(int x = s;x <= e;x++)
                sum += a[x];
            return sum;

        }

        public double getArraySum(double a[],int s,int e)
        {
            double sum = 0;
            if(e >= a.length || s < 0)
                throw new ArrayIndexOutOfBoundsException("Array Index Out Of Bounds " + "[" + e + ", " + s + "]");
            for(int x = s;x <= e;x++)
                sum += a[x];
            return sum;
        }

        public int reverse(int n)
        {
            StringBuilder sb = new StringBuilder(n + "");
            return Integer.parseInt(sb.reverse().toString());
        }

        public long reverse(long n)
        {
            StringBuilder sb = new StringBuilder(n + "");
            return Long.parseLong(sb.reverse().toString());
        }

        public String reverse(String s)
        {
            StringBuilder sb = new StringBuilder(s + "");
            return sb.reverse().toString();
        }



        public Object[] getReverseArray(Object a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                Object o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }

        public int[] getReverseArray(int a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                int o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }

        public double[] getReverseArray(double a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                double o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }
        public char[] getReverseArray(char a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                char o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }

        public long[] getReverseArray(long a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                long o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }

        public String[] getReverseArray(String a[])
        {
            int i = 0,j = a.length - 1;
            while (i <= j)
            {
                String o = a[i];
                a[i] = a[j];
                a[j] = o;
                i++;j--;
            }
            return a;
        }



        public HashSet<Integer> getHashSet(int a[])
        {
            HashSet<Integer> set = new HashSet<>();
            for(int x = 0;x < a.length;x++)
                set.add(a[x]);
            return set;
        }

        public HashSet<Long> getHashSet(long a[])
        {
            HashSet<Long> set = new HashSet<>();
            for(int x = 0;x < a.length;x++)
                set.add(a[x]);
            return set;
        }

        public HashSet<Character> getHashSet(char a[])
        {
            HashSet<Character> set = new HashSet<>();
            for(int x = 0;x < a.length;x++)
                set.add(a[x]);
            return set;
        }

        public HashSet<String> getHashSet(String a[])
        {
            HashSet<String> set = new HashSet<>();
            for(int x = 0;x < a.length;x++)
                set.add(a[x]);
            return set;
        }

        public int getMax(int a[])
        {
            int max = Integer.MIN_VALUE;
            for(int x = 0;x < a.length;x++)
                max = Math.max(max,a[x]);
            return max;
        }

        public long getMax(long a[])
        {
            long max = Long.MIN_VALUE;
            for(int x = 0;x < a.length;x++)
                max = Math.max(max,a[x]);
            return max;
        }

        public double getMax(double a[])
        {
            double max = Double.MIN_VALUE;
            for(int x = 0;x < a.length;x++)
                max = Math.max(max,a[x]);
            return max;
        }

        public int getMin(int a[])
        {
            int min = Integer.MAX_VALUE;
            for(int x = 0;x < a.length;x++)
                min = Math.min(min,a[x]);
            return min;
        }

        public long getMin(long a[])
        {
            long min = Long.MAX_VALUE;
            for(int x = 0;x < a.length;x++)
                min = Math.min(min,a[x]);
            return min;
        }

        public double getMin(double a[])
        {
            double min = Double.MAX_VALUE;
            for(int x = 0;x < a.length;x++)
                min = Math.min(min,a[x]);
            return min;
        }

        private class FastReader
        {
            BufferedReader br;
            StringTokenizer st;

            public FastReader(BufferedReader br) throws Exception {
                this.br = br;
            }

            public String next() throws Exception
            {
                if(st == null || !st.hasMoreElements())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            }

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

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

            public String trimLine() throws Exception
            {
                try{
                    return br.readLine().trim();
                }catch (Exception e){
                    System.out.println("Exception Occured: " + e.getMessage());
                    e.printStackTrace();
                    return null;
                }
            }

            public String nextLine() throws Exception
            {
                try{
                    return br.readLine();
                }catch (Exception e){
                    System.out.println("Exception Occured: " + e.getMessage());
                    e.printStackTrace();
                    return null;
                }

            }

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

            public float nextFloat() throws Exception
            {
                return Float.parseFloat(next());
            }


        }

    }

}



