Problem: You are given three strings s, t and p consisting of lowercase Latin letters. You may perform any number (possibly, zero) operations on these strings.

During each operation you choose any character from p, erase it from p and insert it into string s (you may insert this character anywhere you want: in the beginning of s, in the end or between any two consecutive characters). 

For example, if p is aba, and s is de, then the following outcomes are possible (the character we erase from p and insert into s is highlighted):

  * aba → ba, de → ade; 
  * aba → ba, de → dae; 
  * aba → ba, de → dea; 
  * aba → aa, de → bde; 
  * aba → aa, de → dbe; 
  * aba → aa, de → deb; 
  * aba → ab, de → ade; 
  * aba → ab, de → dae; 
  * aba → ab, de → dea; 



Your goal is to perform several (maybe zero) operations so that s becomes equal to t. Please determine whether it is possible.

Note that you have to answer q independent queries.

Input

The first line contains one integer q (1 ≤ q ≤ 100) — the number of queries. Each query is represented by three consecutive lines.

The first line of each query contains the string s (1 ≤ |s| ≤ 100) consisting of lowercase Latin letters.

The second line of each query contains the string t (1 ≤ |t| ≤ 100) consisting of lowercase Latin letters.

The third line of each query contains the string p (1 ≤ |p| ≤ 100) consisting of lowercase Latin letters.

Output

For each query print YES if it is possible to make s equal to t, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Example

Input


4
ab
acxb
cax
a
aaaa
aaabbcc
a
aaaa
aabbcc
ab
baaa
aaaaa


Output


YES
YES
NO
NO

Note

In the first test case there is the following sequence of operation: 

  1. s =  ab, t =  acxb, p =  cax; 
  2. s =  acb, t =  acxb, p =  ax; 
  3. s =  acxb, t =  acxb, p =  a. 



In the second test case there is the following sequence of operation: 

  1. s =  a, t =  aaaa, p =  aaabbcc; 
  2. s =  aa, t =  aaaa, p =  aabbcc; 
  3. s =  aaa, t =  aaaa, p =  abbcc; 
  4. s =  aaaa, t =  aaaa, p =  bbcc. 

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.IntStream;
//Java Program to rearrange numbers in an Array
//such that no two numbers are adjacent

import java.util.Comparator;
import java.util.PriorityQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

import java.util.Arrays;
import java.util.List;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.math.BigInteger;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class  Dragons{
   
	class Sol
	{
	    int countRev (String x)
	    {
	         Stack<Character> st=new Stack<Character>();
	            for(int i=0;i<x.length();i++){
	                
	                if(x.charAt(i)=='{'||x.charAt(i)=='('||x.charAt(i)=='['){
	                    st.add(x.charAt(i));
	                }else{
	                    if(st.size()>0){
	                    if(x.charAt(i)=='}' && st.peek()=='{'){
	                        st.pop();
	                    }else if(  x.charAt(i)==')' && st.peek()=='('){
	                        st.pop();
	                    }else if(x.charAt(i)==']' && st.peek()=='['){
	                    st.pop();
	                    }else{
	                       st.add(x.charAt(i));
	                    }
	                    }else{
	                       st.add(x.charAt(i));
	                    }
	                    
	                }
	                
	                
	            }
	             int count1=0;
	  int count2=0;
	            if(st.size()%2!=0){
	              return -1;
	            }else{
	                 Iterator value = st.iterator();
	 
	        while (value.hasNext()) {
	            if((char)value.next()=='}'){
	                count1++;
	            }
	        }
	        count2=st.size()-count1;
	        if(count1%2==0){
	            count1=count1/2;
	            
	        }else{
	            count1=count1/2;
	            count1+=2;
	            count2--;
	        }
	       
	        
	            }
	            return count1+((count2)/2);
	            
	    }
	}
	static ArrayList<ArrayList<Integer>> adjList;
	static boolean[] visit;
	static int max=0;
//	static ArrayList<ArrayList<Pair>> nodes;
	
	
    public static HashSet<Long> visited= new HashSet<>();
    public static long n;
    public static long m;
    public static boolean vis[][];
    public static ArrayList<ArrayList<Integer> > adj;
    
    static long decimalToBinary(long N)
    {
     long w=0;
       while(N!=1) {
    	   N=N/2;
    	   w++;
        }
       return w;
     
        
    }
    static Queue<Integer> queue;
  
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       sc.nextLine();
       while(n>0) {
    	 String s=sc.nextLine();
    	 String t=sc.nextLine();
    	 String p=sc.nextLine();
    	 
    	
    	 if(s.length()>t.length()) {
    		 System.out.println("NO");
    	 }else if(s.length()==t.length()){
    		 if(s.equals(t)) {
    			 System.out.println("YES");
    		 }else {
    			 System.out.println("NO");
    		 }
    	 }else {
    		 String j="";
    		 String y="";
    		 for(int i=0;i<s.length();i++) {
    			 y+=s.charAt(i);
    			 if(t.contains(y)) {
    				 j+=s.charAt(i);
    			 }else {
    				 j+='.';
    				 j+=s.charAt(i);
    				 y=s.charAt(i)+"";
    			 }
    		 }
//    		 HashMap<Character,Integer> hm=new HashMap<Character,Integer>();
//    		 HashMap<Character,Integer> pm=new HashMap<Character,Integer>();
//    		 for(int i=0;i<t.length();i++) {
//    			 if(hm.containsKey(t.charAt(i))) {
//    				 hm.put(t.charAt(i), hm.get(t.charAt(i))+1);
//    			 }else {
//    				 hm.put(t.charAt(i), 1);
//    			 }
//    		 }
//    		 String w=s+p;
//    		 for(int i=0;i<w.length();i++) {
//    			 if(pm.containsKey(w.charAt(i))) {
//    				 pm.put(w.charAt(i), pm.get(w.charAt(i))+1);
//    			 }else {
//    				 pm.put(w.charAt(i), 1);
//    			 }
//    		 }
//    		
    		 int a[]=new int[26];
    		 int b[]=new int[26];
    		 Arrays.fill(a, 0);
    		 Arrays.fill(b, 0);
    		 int x=97;
    		 for(int i=0;i<t.length();i++) {
    			 int d=t.charAt(i);
    			a[d-x]++; 
    		 }
    		 String w=s+p;
    		 for(int i=0;i<w.length();i++) {
    			 int d=w.charAt(i);
    			b[d-x]++; 
    		 }
    		
     	    if(isSubSequence(s,t,s.length(),t.length())) {
     	    	boolean flag=false;
     	    	for(int i=0;i<26;i++){
     	    		if(b[i]>=a[i]) {
     	    			continue;
     	    		}else {
     	    			flag=true;
     	    			
     	    			break;
     	    		}
     	    	}
     	    	if(!flag) {
     	    	System.out.println("YES");
     	    	}else {
     	    		System.out.println("NO");
     	    	}
     	    }else {
     	    	
     	    	System.out.println("NO");
     	    	
     	    }
    	 }
    	 
    	   
    	   
    	   
    	   n--;
       }
		
	}
	static boolean isSubSequence(String str1, String str2,
            int m, int n)
{
// Base Cases
if (m == 0)
return true;
if (n == 0)
return false;

// If last characters of two strings are matching
if (str1.charAt(m - 1) == str2.charAt(n - 1))
return isSubSequence(str1, str2, m - 1, n - 1);

// If last characters are not matching
return isSubSequence(str1, str2, m, n - 1);
}
	 static void reversequeue()
	    {
	        Stack<Integer> stack = new Stack<>();
	        while (!queue.isEmpty()) {
	            stack.add(queue.peek());
	            queue.remove();
	        }
	        while (!stack.isEmpty()) {
	            queue.add(stack.peek());
	            stack.pop();
	        }
	    }
		static long gcd1(long a, long b)
		{
			if (a == 0)
				return b;
			return gcd(b % a, a);
		}

		// Function to find gcd of array of
		// numbers
		static long findGCD(long[] arr, long n)
		{
			long result = 0;
			for (long element: arr){
				result = gcd1(result, element);

				if(result == 1)
				{
				return 1;
				}
			}

			return result;
		}
	static boolean isSubsetSum(int set[],
            int n, int sum)
{
// The value of subset[i][j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
boolean subset[][] = new boolean[sum + 1][n + 1];

// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;

// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;

// Fill the subset table in botton
// up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {

if (i >= set[j - 1]) {
 subset[i][j] = subset[i][j]
                || subset[i - set[j - 1]][j - 1];}else {
                	subset[i][j]=true;
                }
}
}

/* // uncomment this code to print table
for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
System.out.println (subset[i][j]);
} */

return subset[sum][n];
}
	static int  count(int a) {
	int b=0;
	while(a%2==0) {
		a=a/2;
		b++;
	}
	return b;
	}
	static long countDivisibles(long A, long B, long M)
    {
        // Add 1 explicitly as A is divisible by M
        if (A % M == 0)
            return (B / M) - (A / M) + 1;
 
        // A is not divisible by M
        return (B / M) - (A / M);
    }
	public static long findMax(long a) {
		long b=a;
		long max=Integer.MIN_VALUE;
		while(b>0) {
			max=Math.max(max,b%10);
			b=b/10;
			
		}
		
		return max;
	}
	public static long findMin(long a) {
		long b=a;
		long max=Integer.MAX_VALUE;
		while(b>0) {
			max=Math.min(max,b%10);
			b=b/10;
			
		}
		
		return max;
	}
	public static boolean check(int k,boolean []visited,int []arr) {
		for(int i=0;i<arr.length;i++) {
			if(!visited[arr[i]^k])
				return false;
		}
		return true;
	}
	static int Max(int arr[])
	{
		int max = arr[0];
		for(int i = 1; i < arr.length; i++)
			if(arr[i] > max)max = arr[i];
		
		return max;
	}
		
	// Function to return the maximum
	// count of pairs with equal sum
	static int maxCountSameSUM(int arr[], int n)
	{
		int maxi = Max(arr);
		
		// Create a map to store frequency
		int[] M = new int[2 * maxi + 1];
		
		
		for(int i = 0; i < M.length; i++)M[i] = 0;
	 
		// Store counts of sum of all
		// pairs in the map
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				M[(arr[i] + arr[j])] += 1;
			}}
		for(int i=0;i<M.length;i++) {
			System.out.print(M[i]+" ");
		}
		System.out.println();
		int max_count = 0;
	 
		// Find maximum count
		for (int i = 0; i < 2 * maxi; i++)
			if (max_count < M[i])
				max_count = M[i];
	 
		return max_count;
	}
//	
//	 static void compare(Pair arr[], long n2)
//	    {
//	        // Comparator to sort the pair according to second element
//	        Arrays.sort(arr, new Comparator<Pair>() {
//	            @Override public int compare(Pair p1, Pair p2)
//	            {
//	                return (int) (p1.a - p2.a);
//	            }
//	        });
//	  
//	    }
	public static long gcdExtended(long brr, long arr, long x, long y)
    {
        // Base Case
        if (brr == 0)
        {
            x = 0;
            y = 1;
            return arr;
        }
 
        int x1=1, y1=1; // To store results of recursive call
        long gcd = gcdExtended(arr%brr, brr, x1, y1);
 
        // Update x and y using results of recursive
        // call
        x = y1 - (arr/brr) * x1;
        y = x1;
 
        return gcd;
    }
	public static long bs(ArrayList<Long> arr, long x , int l , long r) {
		
		while(l<=r) {
		int m = (int) ((l+r)/2);
		if(arr.get(m)>=x) {
			r = m-1;
		}else {
			l = m+1;
		}
		}
		return l;
		
	}
	public static long gs(ArrayList<Long> arr, long x , long l , long r) {
		
		while(l<=r) {
		int m = (int) ((l+r)/2);
		if(arr.get(m)<=x) {
			r = m+1;
		}else {
			l = m-1;
		}
		}
		return r;
		
	}
	 public static HashMap<Integer, Integer>
	    insertPF(HashMap<Integer, Integer> primeFact,
	             long fact)
	    {
	        if (primeFact.containsKey(fact)) {
	 
	            int freq;
	            freq = primeFact.get(fact);
	            primeFact.replace((int) fact, ++freq);
	        }
	        else {
	            primeFact.put((int) fact, 1);
	        }
	        return primeFact;
	    }
	 
	    // A utility function to find all
	    // prime factors of a given number N
	    public static HashMap<Integer, Integer>
	    primeFactors(long n)
	    {
	 
	        HashMap<Integer, Integer> primeFact
	            = new HashMap<>();
	 
	        // Insert the number of 2s
	        // that divide n
	        while (n % 2 == 0) {
	            primeFact = insertPF(primeFact, 2);
	            n /= 2;
	        }
	 
	        // n must be odd at this point.
	        // So we can skip one element
	        for (int i = 3; i <= Math.sqrt(n);
	             i += 2) {
	 
	            // While i divides n, insert i
	            // and divide n
	            while (n % i == 0) {
	                primeFact = insertPF(primeFact, i);
	                n /= i;
	            }
	        }
	 
	        // This condition is to handle
	        // the case when n is a prime
	        // number greater than 2
	        if (n > 2)
	            primeFact = insertPF(primeFact, n);
	 
	        return primeFact;
	    }
	 
	    // Function to check if a number
	    // is a perfect cube
	    public static boolean perfectCube(long n)
	    {
	 
	        HashMap<Integer, Integer> primeFact;
	        primeFact = primeFactors(n);
	 
	        // Using values() for iteration
	        // over keys
	        for (int freq : primeFact.values()) {
	            if (freq % 3 != 0)
	                return false;
	        }
	        return true;
	    }
	static String fixthisstring(String p,int n) {
		StringBuilder sb=new StringBuilder(p);
		if(p.length()>2) {
		for(int i=0;i<sb.length();i++) {
			
			if(i==0&& sb.charAt(i)=='?') {
				if(sb.charAt(i+1)=='0') {
					sb.setCharAt(i,'1');
				}else if(sb.charAt(i+1)=='1'){
					sb.setCharAt(i,'0');
				}else {
					if(sb.charAt(i+2)=='0') {
						sb.setCharAt(i,'0');
					}else if(sb.charAt(i+2)=='1') {
						sb.setCharAt(i,'1');
					}else {
						sb.setCharAt(i,'1');
					}
				}
			}else if(i==sb.length()-1 && sb.charAt(i)=='?') {
				if(sb.charAt(i-1)=='0') {
					sb.setCharAt(i,'1');
				}else {
					sb.setCharAt(i,'0');
				}
			}else if(sb.charAt(i)=='?'){
				if(sb.charAt(i+1)=='0') {
					
						sb.setCharAt(i,'1');
					
				}else if(sb.charAt(i+1)=='1'){
					sb.setCharAt(i,'0');
				}else if(sb.charAt(i+1)=='?') {
				
					if(sb.charAt(i-1)=='0') {
						sb.setCharAt(i,'1');
					}else {
						sb.setCharAt(i,'0');
					}
				}
			}
		}
		}else {
			if(p.contains("?") && p.length()==1) {
				return "0";
			}else if(p.contains("?")){
				return "01";
			}
		}
		return sb.toString();
		
	}
	 static void addEdge(ArrayList<ArrayList<Integer> > adj,
             int u, int v)
{
adj.get(u).add(v);

}

	static long binomialCoeff(long n, long l) {
        long res = 1;
        
        if (l > n - l) l = n - l;
        
        for (var i = 0; i < l; ++i) {
            res *= 1L*(n - i);
            res /= 1L*(i + 1);
        }
        
        return res;
    }
	static long nCr(long n, long r)
	{
	    return fact(n) / (fact(r) *
	                  fact(n - r));
	}
	static long fact(long n)
	{
	    long res = 1;
	    for (int i = 2; i <= n; i++)
	        res = res * i;
	    return res;
	}
	 

	static void  dfs(int m) {
		
		
		
		
		for(int i=0;i<adj.get(m).size();i++) {
			int v=adj.get(m).get(i);
			
			
				if(v!=m) {
				max++;
				}else {
					return;
				}
			 dfs(v);
			
			 
		}
		
		
	}
	static boolean dividetwothree(long n) {
		while(n!=1) {
			if(n%2==0) {
				n=n/2;
			}else if(n%3==0){
				n=n/3;
			}else {
				return false;
			}
			
			
		}
		return true;
	}
	static boolean isLuckyNumber(int n){
		while(n>0) {
			int y=n%10;
			n=n/10;
			if(y!=4 && y!=7) {
				return false;
			}
		}
		return true;
	}
	static boolean isInteger(double N)
	{
	 
	    // Convert float value
	    // of N to integer
	    long X = (long)N;
	    double temp2 = N - X;
	 
	    // If N is not equivalent
	    // to any integer
	    if (temp2 > 0)
	    {
	        return false;
	    }
	    return true;
	}
	static long isrecursive(long p) {
		if(p==0) {
			return 0;
		}else if(p%2==0) {
			return isrecursive(p/2);
		}else {
			return isrecursive(p/2)+1;
		}
		
	}
	static boolean islucky(long  r) {
		String temp = Long.toString(r);
		long[] newGuess = new long[temp.length()];
		long tu=0;
		boolean flag=false;
		
		for (int i = 0; i < temp.length(); i++)
		{
		    newGuess[i] = temp.charAt(i) - '0';
		    if(newGuess[i]==4 || newGuess[i]==7) {
		    	continue;
		    }else {
		    	flag=true;
		    	break;
		    }
		}
		if(flag) {
			return false;
		}
		return  true;
	}
	static int distance(long l,long m) {
		return (int) (Math.pow(l,2)+Math.pow(m,2));
	}
	static int findSmallest(int N)
	{
	  
	    // Base case
	    if (N == 0)
	        return 2;
	    if (N == 1)
	        return 1;
	  
	    int prime = N, counter = 0;
	    boolean found = false;
	  
	    // Loop continuously until isPrime returns
	    // true for a number greater than n
	    while (!found) {
	        if (isPrime(prime))
	            found = true;
	        else {
	  
	            // If the number is not a prime, then
	            // increment the number by 1 and the
	            // counter which stores the number
	            // to be added
	            prime++;
	            counter++;
	        }
	    }
	  
	    return counter;
	}
	static boolean isPrime(int n)
	{
	    // Base cases
	    if (n <= 1)
	        return false;
	    if (n <= 3)
	        return true;
	  
	    // This is checked so that we can skip
	    // middle five numbers in below loop
	    if (n % 2 == 0 || n % 3 == 0)
	        return false;
	  
	    // For all the remaining numbers, check if
	    // any number is a factor if the number
	    // or not
	    for (int i = 5; i * i <= n; i = i + 6)
	        if (n % i == 0 || n % (i + 2) == 0)
	            return false;
	  
	    // If none of the above numbers are the
	    // factors for the number, then the
	    // given number is prime
	    return true;
	}
	
	
		static int mod(int a, int m)
		{
		    return (a%m + m) % m;
		}
		
	static long getSum(long y)
    {
       long sum = 0;
 
        while (y != 0) {
            sum = sum + y % 10;
            y = y / 10;
        }
 
        return sum;
    }
	static boolean detect(int arr[],int x) {
		long sum=0;
		for(int i=0;i<arr.length;i++) {
			sum+=arr[i];
			if(sum==x) {
				return true;
			}
			
		}
		return false;
	}
	
    static class Node {
        String s;
        int val;
 
        public Node(String a, int v) {
            val = v;
            s = a;
        }
    }
	  
	 public static HashMap<Integer,Integer> sortByValue(HashMap<Integer,Integer> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<Integer,Integer> > list =
	               new LinkedList<Map.Entry<Integer,Integer> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<Integer,Integer> >() {
				@Override
				public int compare(Entry<Integer,Integer> o1, Entry<Integer,Integer> o2) {
					return (o1.getValue()-o2.getValue());
				}
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<Integer,Integer> temp = new LinkedHashMap<Integer,Integer>();
	        for (Map.Entry<Integer,Integer> aa : list) {
	            temp.put(aa.getKey(), aa.getValue());
	        }
	        return temp;
	    }
	
	 static long lcm(long a, long b)
	    {
	        return (a / gcd(a, b)) * b;
	    }
static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
//static void reduceFraction(int x, int y) 
//{ 
//    int d; 
//    d = gcd(x, y); 
//  
//    x = x / d; 
//    y = y / d; 
//  if(x>0 && y<0) {
//	  x=-x;
//	  y=-y;
//  }
//    System.out.println(y); 
//} 
	
	static long gcd(long a, long b) {
		return a%b == 0 ? b : gcd(b,a%b);
	}
	 static int getSum(int n)
	    {
	        int sum = 0;
	 
	        while (n != 0) {
	            sum = sum + n % 10;
	            n = n / 10;
	        }
	 
	        return sum;
	    }
	
	static boolean[] sieve(int n) {
		
		
		boolean isPrime[] = new boolean[n+1];
		for(int i = 2; i <= n; i++) {
			if(isPrime[i]) continue;
			for(int j = 2*i; j <= n; j+=i) {
				isPrime[j] = true;
			}
		
		} 
		return isPrime;
		
	}
	public static long SubString(String str, int n,long count)
	{
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j <= n; j++) {
			
				String y=fixthisstring(str.substring(i, j),str.substring(i, j).length());
				
				if(y.length()==1) {
					count++;
				}else if(y.contains("00")||y.contains("11") ) {
					continue;
				}else {
					count++;
				}
		}
	}
	return count;
	}
//	public static void substring(String str, int n)
//    {
//       for (int i = 0; i < n; i++)
//           for (int j = i+1; j <= n; j++)
//            
//               if(str.substring(i,j).contains())
//    }
    // Function to rearrange numbers in array such
    // that no two adjacent numbers are same
    static boolean rearrangeArray(int[] arr)
    {
        int n = arr.length;
 
        // Store frequencies of all elements
        // of the array
        int[] count = new int[10000];
        int visited[] = new int[10000];
 
        for (int i = 0; i < n; i++)
            count[arr[i]]++;
 
        // Insert all characters with their frequencies
        // into a priority_queue
        PriorityQueue<Key> pq
            = new PriorityQueue<>(new KeyComparator());
 
        // Adding high freq elements in descending order
        for (int i = 0; i < n; i++)
        {
            int val = arr[i];
 
            if (count[val] > 0 && visited[val] != 1)
                pq.add(new Key(count[val], val));
            visited[val] = 1;
        }
 
        // 'result[]' that will store resultant value
        int result[] = new int[n];
 
        // work as the previous visited element
        // initial previous element will be ( '-1' and
        // it's frequency will also be '-1' )
        Key prev = new Key(-1, -1);
 
        // Traverse queue
        int l = 0;
        while (pq.size() != 0)
        {
            // pop top element from queue and add it
            // to result
            Key k = pq.peek();
            pq.poll();
            result[l] = k.num;
 
            // If frequency of previous element is less
            // than zero that means it is useless, we
            // need not to push it
            if (prev.freq > 0)
                pq.add(prev);
 
            // make current element as the previous
            // decrease frequency by 'one'
            (k.freq)--;
            prev = k;
            l++;
        }
 
        // If length of the resultant array and original
        // array is not same then the array is not valid
        if (l != result.length)
        {
           return false;
        }
        // Otherwise Print the result array
        else
        	{int j=0;
            for (int i : result)
            {
                arr[j++]=i;
            }
            return true;
        }
    }
  
}
class KeyComparator implements Comparator<Key>
{
 
    // Overriding compare()method of Comparator
    public int compare(Key k1, Key k2)
    {
        if (k1.freq < k2.freq)
            return 1;
        else if (k1.freq > k2.freq)
            return -1;
        return 0;
    }
}
 
// Object of num and its freq
class Key
{
    int freq; // store frequency of character
    int num;
    Key(int freq, int num)
    {
        this.freq = freq;
        this.num = num;
    }
}
 class Pair {
    int a;
    int b;
    public Pair(int a, int b){
        this.a=a;
        this.b=b;
    }
}
class PairComparator implements Comparator<Pair>
{
 
    // Overriding compare()method of Comparator
    public int compare(Pair k1, Pair k2)
    {
      if(k1.a==k2.a) {
    	  if(k1.b>k2.b) {
    		  return 1;
    	  }else {
    		  return -1;
    	  }
      }else if(k1.a>k2.a) {
    	  return 1;
      }else {
    	  return -1;
      }
    }
}