Problem: On a strip of land of length n there are k air conditioners: the i-th air conditioner is placed in cell a_i (1 ≤ a_i ≤ n). Two or more air conditioners cannot be placed in the same cell (i.e. all a_i are distinct).

Each air conditioner is characterized by one parameter: temperature. The i-th air conditioner is set to the temperature t_i.

<image> Example of strip of length n=6, where k=2, a=[2,5] and t=[14,16].

For each cell i (1 ≤ i ≤ n) find it's temperature, that can be calculated by the formula $$$min_{1 ≤ j ≤ k}(t_j + |a_j - i|),$$$

where |a_j - i| denotes absolute value of the difference a_j - i.

In other words, the temperature in cell i is equal to the minimum among the temperatures of air conditioners, increased by the distance from it to the cell i.

Let's look at an example. Consider that n=6, k=2, the first air conditioner is placed in cell a_1=2 and is set to the temperature t_1=14 and the second air conditioner is placed in cell a_2=5 and is set to the temperature t_2=16. In that case temperatures in cells are:

  1. temperature in cell 1 is: min(14 + |2 - 1|, 16 + |5 - 1|)=min(14 + 1, 16 + 4)=min(15, 20)=15; 
  2. temperature in cell 2 is: min(14 + |2 - 2|, 16 + |5 - 2|)=min(14 + 0, 16 + 3)=min(14, 19)=14; 
  3. temperature in cell 3 is: min(14 + |2 - 3|, 16 + |5 - 3|)=min(14 + 1, 16 + 2)=min(15, 18)=15; 
  4. temperature in cell 4 is: min(14 + |2 - 4|, 16 + |5 - 4|)=min(14 + 2, 16 + 1)=min(16, 17)=16; 
  5. temperature in cell 5 is: min(14 + |2 - 5|, 16 + |5 - 5|)=min(14 + 3, 16 + 0)=min(17, 16)=16; 
  6. temperature in cell 6 is: min(14 + |2 - 6|, 16 + |5 - 6|)=min(14 + 4, 16 + 1)=min(18, 17)=17. 



For each cell from 1 to n find the temperature in it.

Input

The first line contains one integer q (1 ≤ q ≤ 10^4) — the number of test cases in the input. Then test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first line contains two integers n (1 ≤ n ≤ 3 ⋅ 10^5) and k (1 ≤ k ≤ n) — the length of the strip of land and the number of air conditioners respectively.

The second line contains k integers a_1, a_2, …, a_k (1 ≤ a_i ≤ n) — positions of air conditioners on the strip of land.

The third line contains k integers t_1, t_2, …, t_k (1 ≤ t_i ≤ 10^9) — temperatures of air conditioners.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case output n integers separated by space: temperatures of air in cells.

Example

Input


5

6 2
2 5
14 16

10 1
7
30

5 5
3 1 4 2 5
3 1 4 2 5

7 1
1
1000000000

6 3
6 1 3
5 5 5


Output


15 14 15 16 16 17 
36 35 34 33 32 31 30 31 32 33 
1 2 3 4 5 
1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 
5 6 5 6 6 5 

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 t=sc.nextInt();
      while(t>0) {
    	  
    	  int n=sc.nextInt();
    	  int q=sc.nextInt();
    	  int arr[]=new int[q+1];
    	  int brr[]=new int[q+1];
    	  for(int i=1;i<=q;i++) {
    		  arr[i]=sc.nextInt();
    		  
    	  }
    	  for(int i=1;i<=q;i++) {
    		  brr[i]=sc.nextInt();
    	  }
    	  
    	  int left[]=new int[n+1];
    	  int right[]=new int[n+1];
    	  Arrays.fill(left,Integer.MAX_VALUE-1);
    	  Arrays.fill(right,Integer.MAX_VALUE-1);
    	  for(int i=1;i<=q;i++) {
    		  left[arr[i]]=brr[i];
    	  }
    	  
    	  for(int i=1;i<=q;i++) {
    		  right[arr[i]]=brr[i];
    	  }
    	  
    	  for(int i=2;i<=n;i++) {
    		  left[i]=Math.min(left[i],left[i-1]+1);
    	  }
    	  for(int i=n-1;i>=1;i--) {
    		  right[i]=Math.min(right[i+1]+1, right[i]);
    	  }
    	  for(int i=1;i<=n;i++) {
    		  System.out.print(Math.min(left[i], right[i])+" ");
    	  }
    	  System.out.println();
    	  
    	  
    	  
    	  
    	  t--;
      }
   
	}
	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<String,Integer> sortByValue(HashMap<String,Integer> hm)
	    {
	        // Create a list from elements of HashMap
	        List<Map.Entry<String,Integer> > list =
	               new LinkedList<Map.Entry<String,Integer> >(hm.entrySet());
	 
	        // Sort the list
	        Collections.sort(list, new Comparator<Map.Entry<String,Integer> >() {
				
				@Override
				public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
					return -(o1.getValue()-o2.getValue());
				}
	        });
	         
	        // put data from sorted list to hashmap
	        HashMap<String,Integer> temp = new LinkedHashMap<String,Integer>();
	        for (Map.Entry<String,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;
      }
    }
}