//Problem: https://www.hackerrank.com/challenges/day-of-the-programmer
//Java 8
/*
Initial Thoughts:
Create two calendars (Julian pre 1918 and Gregorian post 1917)
then solve for the 256th day, which is the wrong approach. 
Relizing the problem outlined the conditions necessary to 
solve for different years I took those and created conditional 
statements out of them.

Time complexity: O(1) 
Space complexity: O(1)
*/
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static String solve(int year){
        String date = "";
        if(year < 1918) {                                                   //Julian check for leap year
            date += (year % 4 == 0) ? "12.09." + year : "13.09." + year;
        } else if(year == 1918) {                                           //Special case: transition year
            date += "26.09." + year;
        } else {                                                            //Gregorian check for leap year
            date += ((year % 400 == 0) ||                               
            (year % 4 == 0 && year % 100 != 0)) ? "12.09." + year : "13.09." + year;
        }
        return date;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int year = in.nextInt();
        String result = solve(year);
        System.out.println(result);
    }
}

/*
        Problem: https://www.hackerrank.com/challenges/day-of-the-programmer/problem
        C# Language Version: 6.0
        .Net Framework Version: 4.7
        Tool Version : Visual Studio Community 2017
        Thoughts :
           We need special handling for Gregorian calendar and Julian calendar based on input year.
           It is pretty straight forward to reach to correct answer if we follow the information given in the problem.
           Since it is a O(1) complexity problem so not much optimization is possible.

        Time Complexity:  O(1) //There are no loops.
        Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.

*/

using System;

class Solution
{
    static string Solve(int year)
    {
        //256th Day
        var programmerDate = "";
        if (year >= 1919)
            programmerDate = GetProgrammerDateForGregorianCalendar(year);
        else if (year <= 1917)
        {
            programmerDate = GetProgrammerDateForJulianCalendar(year);
        }
        else
        {
            //gregorian switch year
            programmerDate = "26.09.1918";// GetProgrammerDateForCalendarSwitchYear1918(year);
        }

        return programmerDate;
    }

    private static string GetProgrammerDateForCalendarSwitchYear1918(int year)
    {
        //1918 was a gregorian calendar after 1918 (it wasn't a leap year)
        var daysTillAug = 230;//  31 + 15 + 31 + 30 + 31 + 30 + 31 + 31
        var programmerDateInSeptember = 0;
        programmerDateInSeptember = 256 - daysTillAug;
        var dateWithFormat = programmerDateInSeptember + ".09." + year.ToString();
        return dateWithFormat;
    }

    private static string GetProgrammerDateForJulianCalendar(int year)
    {
        var daysTillAugInLeapYear = 244; //31 + 29 + 31 + 30 + 31 + 30 + 31 + 31
        var daysTillAugInNonLeapYear = 243; //31 + 28 + 31 + 30 + 31 + 30 + 31 + 31
        var programmerDateInSeptember = 0;
        programmerDateInSeptember = IsJulianLeapYear(year) ? 256 - daysTillAugInLeapYear : 256 - daysTillAugInNonLeapYear;
        var dateWithFormat = programmerDateInSeptember + ".09." + year.ToString();
        return dateWithFormat;
    }

    private static bool IsJulianLeapYear(int year)
    {
        if (year % 4 == 0)
            return true;

        return false;
    }

    private static string GetProgrammerDateForGregorianCalendar(int year)
    {
        var daysTillAugInLeapYear = 244; //31 + 29 + 31 + 30 + 31 + 30 + 31 + 31
        var daysTillAugInNonLeapYear = 243; //31 + 28 + 31 + 30 + 31 + 30 + 31 + 31
        var programmerDateInSeptember = 0;

        programmerDateInSeptember = IsGregorianLeapYear(year) ? 256 - daysTillAugInLeapYear : 256 - daysTillAugInNonLeapYear;
        var dateWithFormat = programmerDateInSeptember + ".09." + year.ToString();
        return dateWithFormat;
    }

    private static bool IsGregorianLeapYear(int year)
    {
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            return true;

        return false;
    }

    static void Main(String[] args)
    {
        var year = int.Parse(Console.ReadLine());
        var result = Solve(year);
        Console.WriteLine(result);
    }
}

//Problem: https://www.hackerrank.com/challenges/climbing-the-leaderboard
//JavaScript
/*
Initial Thoughts:
We want to build a dense ranking map based on the scores as 
we read them in

Using that and a pointer variables we can iterate 1 time
over the scores array, advancing  an unknown number of steps
for each score that Alice has.

Time Complexity: O(n) //We only iterate over the scores and alice's scores once
Space Complexity: O(n) //We store the ranking map
*/
process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var n = parseInt(readLine());
    scores = readLine().split(' ');
    scores = scores.map(Number);
    var m = parseInt(readLine());
    alice = readLine().split(' ');
    alice = alice.map(Number);

    let map = rankScores(scores),
        index = scores.length - 1;
    for (let score of alice) {
        if (scores.length === 0) {
            console.log("1");
        } else {
            for (let i = index; i >= 0; i--) {
                index = i;
                if (score < scores[i]) {
                    console.log(map.get(scores[i]) + 1);
                    break;
                } else if (score === scores[i]) {
                    console.log(map.get(scores[i]));
                    break;
                } else if (i === 0) {
                    console.log("1");
                } 
            } 
        }
    }
}

function rankScores (scores) {
    let map = new Map(),
        rank = 1;
    for (let leaderScore of scores) {
        if (!map.has(leaderScore)) {
            map.set(leaderScore, rank++);
        }
    }
    return map;
}

//Problem: https://www.hackerrank.com/challenges/magic-square-forming
//Java 8
/*
Initial Thoughts:
There are a limited number of ways a magic
square can be formed, so we can brute-force
check those solutions and choose the one that
it would take the smallest sum to obtain


Time Complexity: O(1) //There are only 9 combos to check no matter the arrangement
Space Complexity: O(1) //No dynamically allocated space
*/
import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        
        Scanner input = new Scanner(System.in);
        int[][][] possiblePermutations = {
            {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},// 1

            {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},// 2

            {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},// 3

            {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},// 4

            {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},// 5

            {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},// 6

            {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},// 7

            {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}},// 8
        };

        int[][] given = new int[3][3];
        for (int i = 0; i < 3; i++) 
        {
            for (int j = 0; j < 3; j++)
                given[i][j] = input.nextInt();
        }

        int minCost = Integer.MAX_VALUE;
        for (int permutation = 0; permutation < 8; permutation++) 
        {
            int permutationCost = 0;
            for (int i = 0; i < 3; i++) 
            {
                for (int j = 0; j < 3; j++)
                    permutationCost += Math.abs(given[i][j] - possiblePermutations[permutation][i][j]);
            }
            minCost = Math.min(minCost, permutationCost);
        }
        System.out.println(minCost);
    }
}

//Problem: https://www.hackerrank.com/challenges/happy-ladybugs
//Java 8
/*
number of ladybugs
number of swap spaces

if we dont have at least 2 of ever color
    NO

if no _ then
    NO
    aabbyy

we have 2 or more and at least 1 _
    YES
    
example:
ab_bgybgayryrbg
abb_gybgayryrbg
abbggybgayryrb_
abbggy_gayryrbb
abbgg_ygayryrbb
abbgggy_ayryrbb
abbgggyya_ryrbb
abbgggyy_aryrbb
abbgggyyyar_rbb
abbgggyyya_rrbb

example:
_bbgggyyyaarrbbr
bbbgggyyyaarrb_r
bbbgggyyyaarr_br
bbbgggyyyaarrrb_
_bbgggyyyaarrrbb



find frequencies of all letters

if all frequencies are >= 2 and a _ is present
    YES
else if they are >= 2 and no _ is present
    if it is already ordered
        YES
    else
        NO
else
    NO

*/



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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int Q = in.nextInt();
        
        tests:
        for(int a0 = 0; a0 < Q; a0++){
            int n = in.nextInt();
            String b = in.next();
            
            HashMap colorFreq = new HashMap<>();
            
            //Find frequencys of each Letter
            for(int i = 0; i < b.length(); i++)
            {
                Character letter = (Character) b.charAt(i);
                if(colorFreq.containsKey(letter))
                {
                    colorFreq.put(letter, colorFreq.get(letter)+1);
                }
                else
                {
                    colorFreq.put(letter, 1);
                }
            }
            
            //NO if we dont have at least 2 of ever color
            for(Map.Entry frequency : colorFreq.entrySet())
            {                
                if(frequency.getValue() < 2 && !frequency.getKey().equals((Character)'_'))
                {
                    System.out.println("NO");
                    continue tests;
                }
            }
            
            //If it has no _ we must check if it is already in order 
            if(!colorFreq.containsKey('_'))
            {
                int count = 0;
                char last = b.charAt(0);
                for(int i = 0; i < b.length(); i++)
                {
                    char curr = b.charAt(i);
                    
                    if(curr == last)
                    {
                        count++;
                    }
                    else
                    {
                        if(count < 2)
                        {
                            System.out.println("NO");
                            continue tests;
                        }
                        else{count = 1;}
                    }
                    last = curr;
                }
                System.out.println("YES");
            }
            else //It has an _ so it is YES
            {
                System.out.println("YES");
            }
        }
    }
}

/*
         Problem: https://www.hackerrank.com/challenges/two-characters/problem
         C# Language Version: 6.0
         .Net Framework Version: 4.7
         Tool Version : Visual Studio Community 2017
         Thoughts :
         - Get all unique characters present in the input string and their all possible combinations. e.g. for input string abdcab we need to find ab,ac,ad,bc,bd,cd combinations.
         - Now for each character pair found above iterate the entire string once and check if alternating pattern is possible or not.
            e.g. Let's say input string is "abdcab" and character pair is 'a','b'.
                Iteration need to be done carefully
                    - Track the alternating pattern by keeping a track about the last character. If 'a' had come last time then next time you should encounter b.
                    - Ignore any other character which is not part of pair being tracked e.g. d and c in the input string during the iteration.
                    - Track the pattern length every time you encounter any character from  the pair being tracked.
         - Print the longest altenating pattern length found.

         Time Complexity:  O(n)
         Space Complexity: O(n) //input string need to be stored in memory for repeatitive iteration to check character pair pattern
         
*/

using System.Collections.Generic;
using System;

class Solution
{
    static void Main(string[] args)
    {
        //No need to capture the size of string. We will use string's length property instead.
        Console.ReadLine();
        var inputString = Console.ReadLine();

        //first obtain all the possible combination of possible characters in the string
        //e.g. for input string abdcab we need to find ab,ac,ad,bc,bd,cd combinations
        var characterSet = new HashSet();
        var combinationList = new List>();
        //This loop runs fixed 25! times in worst case when the string is abcdefghijkl.....xyz. 
        //So it'll contribute O(1) for time efficiency of the algo.
        for (var i = 0; i < inputString.Length; i++)
        {
            if (!characterSet.Contains(inputString[i]))
            {
                //create all tuple combinations
                foreach (var character in characterSet)
                    combinationList.Add(new Tuple(inputString[i], character));
            }

            characterSet.Add(inputString[i]);
        }

        var maxPatternLength = 0;
        //In worst case we iterate the input string (of length n) n * 25! times in worst case
        //So overall efficiency will remain of order n.
        foreach (var alternatingCharPair in combinationList)
        {
            //process the entire input string once for each combination if it gives max length of alternating characters
            var nextExpectedChar = alternatingCharPair.Item2;
            var currentPatternLength = 1;
            var i = 0;
            while (inputString[i] != alternatingCharPair.Item1 && inputString[i] != alternatingCharPair.Item2)
                i++;

            if (inputString[i] == alternatingCharPair.Item2)
                nextExpectedChar = alternatingCharPair.Item1;

            i++;
            for (; i < inputString.Length; i++)
            {
                if (inputString[i] != alternatingCharPair.Item1 && inputString[i] != alternatingCharPair.Item2)
                    continue;

                if (inputString[i] == nextExpectedChar)
                {
                    currentPatternLength++;
                    nextExpectedChar = inputString[i] == alternatingCharPair.Item1 ? alternatingCharPair.Item2 : alternatingCharPair.Item1;
                }
                else
                    break;
            }

            if (i == inputString.Length && currentPatternLength > maxPatternLength)
                //it has valid alternating pattern
                maxPatternLength = currentPatternLength;

        }
        Console.WriteLine(maxPatternLength);
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/mini-max-sum/problem
    C# Language Version: 6.0
    .Net Framework Version: 4.7
    Tool Version : Visual Studio Community 2017
    Thoughts :
    1. Store all the input five numbers in an array.
    2. Let the highest and lowest number in the array be h and l. Initialize h to 0 and l to greatest possible number (max of
       the data type in the programming language).
    3. Let the sum of all five numbers in the array be s. Initialize s to 0.
    4. Iterate through five elements of array using a loop
       4.1 Let the current number be c.
       4.2 Increment s by c.
       4.3 If c is less than l then set l to c.
       4.4 If c is greater than h then set h to c.
       4.5 Repeat steps 4.1 through 4.4 for all five elements of the array.
    5. Print the outcome of s - h and s - l on the same line on console separated by space.

    Time Complexity:  O(1) //even though there is a for loop in the algorithm but the problem statement says that number of elements will always be fixed at 5. Since the number of input is not variable so complexity will be O(1). Since the number of input elements is fixed at 5 so the same solution can be implemented using few if-else statements also.
    Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
*/

using System;
using static System.Console;
using System.Linq;

class Solution
{

    static void Main(String[] args)
    {
        var numbers = ReadLine().Split(' ').Select(x => long.Parse(x)).ToList();
        var sumOfAllNumbers = 0L;
        var minimum = long.MaxValue;
        var maximum = 0L;
        for (int i = 0; i < 5; i++)
        {
            sumOfAllNumbers += numbers[i];
            if (numbers[i] < minimum)
                minimum = numbers[i];

            if (numbers[i] > maximum)
                maximum = numbers[i];

        }
        WriteLine(string.Format("{0} {1}", sumOfAllNumbers - maximum, sumOfAllNumbers - minimum));
    }
}

//Problem: https://www.hackerrank.com/challenges/designer-pdf-viewer
//JavaScript
/*
Initial Thoughts:
We can iterate through each letter in the string
converting the char into its charCode. Because we 
know all characters will be lower case we can subtract
97 to get a base 0 (i.e. 'a' = 0, 'b' = 1, ...). We find 
the tallest height then multiply that by the length of 
the string which will give us our desired area.

Time complexity: O(n)  //Iterate over the String 
Space complexity: O(n) //Store the string
*/
process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    let h = readLine().split(' ').map(Number),
        word = readLine(),
        maxHeight = 1;
    for (let letter of word) {
        maxHeight = Math.max(maxHeight, h[letter.charCodeAt(0) - 97]);
        if (maxHeight === 7) break;
    }
    console.log(maxHeight * word.length);
}

//Problem: https://www.hackerrank.com/challenges/sherlock-and-valid-string
//Java 8
/*
Initial Thoughts:
Get every chars' frequency 

If there are more than two different frequencies
    NO
if 1 frequency 
    YES
if 2 frequency
    if 1 occurs only once and frequency is 1
        yes
    else
        if their difference 1 and one has frequency 1
            yes
        else
            no

examples:

abcde       -> Y
a           -> Y
aabb        -> Y
aaaabbbbc   -> Y
aaaabbbbcd  -> N
aabbcd      -> N

Time Complexity: O(n) //We have to look at every char
Space Complexity: O(n) //We store frequencies in a Hashmap

*/


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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        
        Map frequencies = new HashMap<>();
        
        for(char letter : s.toCharArray())
        {
            if(frequencies.containsKey(letter))
                frequencies.put(letter, frequencies.get(letter) + 1);
            else
                frequencies.put(letter, 1);
        }
        
        
        
        Set st = new HashSet<>();
        for(int freq : frequencies.values())
        {
            st.add(freq);
        }
        
        if(st.size() > 2)//More than 2 frequencies
            System.out.println("NO");
        else if(st.size() == 1)
            System.out.println("YES");
        else//2 different frequencies
        {
            int f1 = 0;
            int f2 = 0;
            int f1Count = 0;
            int f2Count = 0;
            int i = 0;
            for(int n : st)
            {
                if(i == 0) f1 = n;
                else f2 = n;
                i++;
            }
            
            for(int freq : frequencies.values())
            {
                if(freq == f1) f1Count++;
                if(freq == f2) f2Count++;
            }
            
            
            
            if((f1 == 1 && f1Count == 1 ) || (f2 == 1 && f2Count == 1 ))
                System.out.println("YES");
            else if ((Math.abs(f1 - f2)  == 1) && (f1Count == 1 || f2Count == 1))
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

/*
  Problem: https://www.hackerrank.com/challenges/lisa-workbook/problem
  C# Language Version: 7.0
  .Net Framework Version: 4.7
  Tool Version : Visual Studio Community 2017
  Thoughts :
  1. Let the question of all arrays are stored in an array arr.
  2. Let the maximum number of questions possible on any page in the book be maxQ.
  3. Let the count of special questions in the book be sq. Initialize specialQ to 0.
  4. Let the current page number of the book be currP. Initialize currP to 0.
  5. Start a loop to iterate through elements of arr:
     5.1 Let the number of question in current chapter being iterated be n.
     5.2 Let the starting question number of any page for current chapter be qStart. Initialize qStart to 1-maxQ.
     5.3 Let the ending question number of any page for current chapter be be qEnd. Initialize qEnd to 0.
     5.4 Start a loop:
         5.4.1 increment currP by 1.
         5.4.2 increment qStart by maxQ.
         5.4.3 if n >= maxQ then increment qEnd by maxQ.
         5.4.4 if n < maxQ then increment qEnd by n.
         5.4.5 If currP is in the range [qStart,qEnd] then increment specialQ by 1.
         5.4.6 Decrement n by maxQ.
         5.4.7 If n <= 0 then break the loop.
         5.4.8 Continue the loop and keep repeating steps from 5.4.1 through 5.4.7 until loop doesn't break.
     5.5 Keep repeating the steps 5.1 through 5.4 untill all the chapters present in arr don't get processed.
 6. Print specialQ on console.

  Time Complexity:  O(n) //There is one for loop. The number of times nested while loop runs will be very random as it has no 
                         direct relationship with number of chapters in the book. So I've ignored the nested inner loop while calculating time complexity.
  Space Complexity: O(n) //Chapterwise problem counts have been stored in array for later processing. 
                     Space complexity doesn't match the optimal O(1) solution as in C#, you have to read the entire console line at a time (size n).
                     C# doesn't support to iteratively read in space delimited input on the go. If there had been a Scanner like class which exists in Java 
                     then it would have been possible to accomplish the same algorithm in O(1) space complexity.
  Optimal Space Complexity : O (1)
 */
using System;

class Solution
{

    static int Workbook(int maxQuestionsPerPage, int[] arr)
    {
        var currPageNumber = 0;
        var specialProblems = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            var currChapterQuesCount = arr[i];
            var questionStart = 1 - maxQuestionsPerPage;
            var questionEnd = 0;
            do
            {
                currPageNumber++;
                questionStart += maxQuestionsPerPage;
                if (currChapterQuesCount >= maxQuestionsPerPage)
                    questionEnd += maxQuestionsPerPage;
                else
                    questionEnd += currChapterQuesCount;

                if (currPageNumber >= questionStart && currPageNumber <= questionEnd)
                    specialProblems++;

                currChapterQuesCount -= maxQuestionsPerPage;
            } while (currChapterQuesCount > 0);
        }
        return specialProblems;
    }

    static void Main(String[] args)
    {
        var tokens_n = Console.ReadLine().Split(' ');
        //No need to capture the size of array. I use array's length property instead.
        var maxQuestionsPerPage = int.Parse(tokens_n[1]);
        var arr_temp = Console.ReadLine().Split(' ');
        var arr = Array.ConvertAll(arr_temp, Int32.Parse);
        var specialProblemsCount = Workbook(maxQuestionsPerPage, arr);
        Console.WriteLine(specialProblemsCount);
    }
}

//Problem: https://www.hackerrank.com/challenges/insertionsort1
//Java 8
//Time Complexity: O(n)
//Space Complexity: O(1)
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    

    public static void insertIntoSorted(int[] ar) {
        int tmp = ar[ar.length-1];
        for(int i = ar.length-2; i  >=0; i--){
            if(tmp >= ar[i]){//Found where it goes
                ar[i+1] = tmp;
                printArray(ar);
                break;
            }
            ar[i+1] = ar[i];//Shift to the right
            printArray(ar);
        }
        if(tmp < ar[0]){
          ar[0] = tmp;  
          printArray(ar);
        } 
        
    }
    
    
/* Tail starts here */
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int[] ar = new int[s];
         for(int i=0;i

/*
         Problem: https://www.hackerrank.com/challenges/insertionsort1/problem
         C# Language Version: 7.0
         .Net Framework Version: 4.7
         Tool Version : Visual Studio Community 2017
         Thoughts :
         1. Let the array containing all the sorted elements and one new element e at the end of the array be arr.
         2. let the total number of elements in the array be n.
         3. Initialize a value i = n-1.
         4. Initialize a counter j = i-1.
         5. Start a loop 
            5.1 if e < arr[j] then set arr[j + 1] = arr[j] and print the entire array elements separated by space character.
            5.2 if e >= arr[j] then break the loop.
            5.3 Decrement j by 1.
            5.4 Break the loop if j < 0.
            5.3 Keep repeating steps from 5.1 through 5.4 untill loop breaking condition isn't met.
         6. j+1 is the correct position where e needs to be inserted. Replace (j+1)th element of array with e.
         7. Print the entire array elements separated by space character one last time.

         Time Complexity:  O(n) //There is only one loop.
         Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
                
        */

using System;

class Solution
{

    static void InsertionSort(int[] arr)
    {
        var i = arr.Length - 1;
        var currElement = arr[i];
        var j = i - 1;
        for (; j >= 0; j--)
        {
            if (currElement < arr[j])
            {
                arr[j + 1] = arr[j];
                Console.WriteLine(String.Join(" ", arr));
            }
            else
                break;
        }

        arr[j + 1] = currElement;
        Console.WriteLine(String.Join(" ", arr));
    }

    static void Main(String[] args)
    {
        //No need to capture the size of array. We use array's length property instead.
        Console.ReadLine();
        var arr_temp = Console.ReadLine().Split(' ');
        var arr = Array.ConvertAll(arr_temp, int.Parse);
        InsertionSort(arr);
    }
}

//Problem: https://www.hackerrank.com/challenges/reduced-string
//Java 8
/*
We can simply compress by iterating left to right removing duplicates
then repeat the process until we can no longer compress

To accomplish this we just need to loop until we see no change
in our input and output after running the compression algorithm
*/


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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        String inputString = input.nextLine();
        StringBuilder lastOutput = new StringBuilder(inputString);
        
        
        while(true)
        {
            StringBuilder currentOutput = new StringBuilder("");
            String s = lastOutput.toString();
            char past = s.charAt(0);
            int count = 0;
            for(int i = 0; i < s.length(); i++)
            {
                char current = s.charAt(i);

                if(past == current)
                    count += 1;
                else if (count == 1)
                {
                    currentOutput.append(past);
                    count = 1;
                }
                else
                    count = 1;

                if(count == 2)
                    count = 0;

                past = current;
            }
            
            if(count == 1)
                currentOutput.append(s.charAt(s.length()-1));
            
            
            if(currentOutput.toString().equals(""))
            {
                System.out.println("Empty String");
                System.exit(0);
            }
            
            
            if(currentOutput.toString().equals(lastOutput.toString()))
                break;
            else
                lastOutput = new StringBuilder(currentOutput.toString());
        }
        
        System.out.println(lastOutput);
    }
}

//Problem: https://www.hackerrank.com/challenges/linkedin-practice-nested-logic
//Java 8
/*
Initial Thoughts:
We can solve this problem by simply using
a if statement that narrows down our checks
at each step to calculate the proper fine

Time Complexity: O(1); //Add return dates take the same amount of time
Space Complexity: O(1); //No dynamically allocated variables
*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int returnDay = input.nextInt();
        int returnMonth = input.nextInt();
        int returnYear = input.nextInt();
        
        int expectedDay = input.nextInt();
        int expectedMonth = input.nextInt();
        int expectedYear = input.nextInt();
        
        int hackosFine = 0;
        
        
        //if statement that checks starting at the years and proceeds based on equivalence
        //Year is off  - 10,000 hackos
        //Month is off - months * 500 hackos
        //Day is off   - days * 15 hackos
        
        if(expectedYear < returnYear)
        {
            hackosFine = 10000;
        }
        else if(expectedYear == returnYear )
        {
            if(expectedMonth < returnMonth)
            {
                hackosFine = (returnMonth-expectedMonth) * 500;
            }
            else if(expectedMonth == returnMonth)
            {
                if(expectedDay < returnDay)
                {
                    hackosFine = (returnDay - expectedDay) * 15;
                }
            } 
        }
        
        System.out.println(hackosFine);
    }
}

//Problem: https://www.hackerrank.com/challenges/making-anagrams
//Java 8
/*
Initial Thoughts:

Build a frequency map for each string

Compare the frequency maps, each time
adding the difference to a deletions variable

return deletions

*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        String s1 = input.nextLine();
        String s2 = input.nextLine();
        Map s1Frequency = new HashMap<>();
        Map s2Frequency = new HashMap<>();
        int deletions = 0;
        
        for(int i = 'a'; i <= 'z'; i++)
        {
            s1Frequency.put((char) i, 0);
            s2Frequency.put((char) i, 0);
        }
        
        for(char c : s1.toCharArray())
            s1Frequency.put(c, s1Frequency.get(c) + 1);
        
        for(char c : s2.toCharArray())
            s2Frequency.put(c, s2Frequency.get(c) + 1);
        
        for(char letter : s1Frequency.keySet())
        {
            int f1 = s1Frequency.get(letter);
            int f2 = s2Frequency.get(letter);
            
            deletions += Math.abs(f1 - f2);
        }
        
        System.out.println(deletions);
    }
}

//Problem: https://www.hackerrank.com/challenges/bigger-is-greater
//Java 8
import java.io.*;
import java.util.*;
import java.lang.StringBuilder;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        
        for(int i = 0; i < T; i++)
        {	
            String word = input.nextLine();
            if(word.length()==1) {System.out.println("no answer");continue;}
            
            
            int maxLexoC1 = 0; //The max lexocographical according to condition 1
            int maxLexoC2 = 0; //The max lexocographical according to condition 2
            
            
            
            //Find the largest index char that is weakly increasing such as g in hefg 
            for(int j = 1; j < word.length(); j++)
            {
                boolean condition1 = word.charAt(j) > word.charAt(j-1);
                    
                if(condition1)
                {
                    maxLexoC1 = (j > maxLexoC1) ? j : maxLexoC1;
                }
            }
            
            //if our only increasing is at point 0 then we are in the last permuation of our string
            if(maxLexoC1==0) {System.out.println("no answer");continue;}
            
            //maxLexoC2
            //Determine the right most char greater than the pivot in index and in lexo
            for(int j = maxLexoC1; j < word.length(); j++)
            {
                boolean condition2 = word.charAt(j) > word.charAt(maxLexoC1-1);
                    
                if(condition2)
                {
                    maxLexoC2 = j;
                }
            }
            
            StringBuilder wordSB = new StringBuilder(word);
            
            //Swap the pivot with maxLexoC2
            char tmp = wordSB.charAt(maxLexoC1-1);
            wordSB.setCharAt(maxLexoC1-1, wordSB.charAt(maxLexoC2));
            wordSB.setCharAt(maxLexoC2, tmp);
                        
            
            //Reverse starting at the element to the right of the pivot
            int left = maxLexoC1;
            int right = wordSB.length()-1;
            while(left < right)
            {
                //swap left with right
                tmp = wordSB.charAt(left);
                wordSB.setCharAt(left, wordSB.charAt(right));
                wordSB.setCharAt(right, tmp);
                left++;
                right--;
            }
            
            
            System.out.println(wordSB);
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/linkedin-practice-caesar-cipher
//Java 8
/*
Initial Thoughts: We can just treat the upper and lower
                  case alphabets like circular queues,
                  where we index them by char+k to get
                  the encrypted character
                  
Time Complexity: O(n) //We must convert each character in the input
Space Complexity: O(n) //Since we opt for a stringbuilder to increase IO runtime our SC is n
*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();input.nextLine();
        String word = input.nextLine();
        int rotation = input.nextInt();
        StringBuilder encryptedWord = new StringBuilder("");
        for(char c : word.toCharArray())
        {
            if(c >= 'a' && c <= 'z')
                encryptedWord.append((char) ('a'+(((c-'a')+rotation)%26)));
            else if(c >= 'A' && c <= 'Z')
                encryptedWord.append((char) ('A'+(((c-'A')+rotation)%26)));
            else
                encryptedWord.append(c);
                
        }
        System.out.println(encryptedWord);
    }
}

//Problem: https://www.hackerrank.com/challenges/linkedin-practice-bitwise-and
//Java 8
/*
Initial Thoughts: We can simple iterate over each element and
                  all the elements to the right of it and check 
                  if it satisfies our condition. 
                  
Optimization: There is a pattern to the highest potential &, so we
              can use this to determine the ma in O(1) time
              
Time Complexity: O(1)
Space Complexity: O(1)
*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        for(int t = 0; t < T; t++)
        {
            int max = 0;
            int n = input.nextInt();
            int k = input.nextInt();
            if (((k-1)|k) <= n) System.out.println(k-1);
            else System.out.println(k-2);
            
        }
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/tutorial-intro/problem
    C# Language Version: 6.0
    .Net Framework Version: 4.7
    Tool Version : Visual Studio Community 2017
    Thoughts :
    1. Let the value to be searched in array is v.
    2. Let the index of v in the array be i. Initialize i to 0.
    3. Start a loop:
    3.1 If the element in the array at index i is same as v then break the loop and go to step 4.
    3.2 increment i by 1.
    3.3 Keep repeating the steps from 3.1 through 3.2 untill loop breaking condition is not met.
    4. Print i on console.

    Time Complexity:  O(n) //one for loop to iterate array elements.
    Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
             
*/
using System;

class Solution
{
    static int IntroTutorial(int v, int[] arr)
    {
        var i = 0;
        for (; i < arr.Length; i++)
        {
            if (arr[i] == v)
                break;
        }
        return i;
    }

    static void Main(String[] args)
    {
        var v = int.Parse(Console.ReadLine());
        //no need to save the number of elements in the array.
        Console.ReadLine();
        var arr_temp = Console.ReadLine().Split(' ');
        var arr = Array.ConvertAll(arr_temp, Int32.Parse);
        var result = IntroTutorial(v, arr);
        Console.WriteLine(result);
    }
}

//Problem: https://www.hackerrank.com/challenges/bomber-man
//Java 8
/*
We can simply keep three sets of bombs
1 second bombs
2 second bombs
3 second bombs

Then iteratively detonate and plant bombs each cycle

Cycle: 2
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 3
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

Cycle: 4
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 5
.......
...O...
....O..
.......
OO.....
OO.....

Cycle: 6
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 7
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

Cycle: 8
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 9
.......
...O...
....O..
.......
OO.....
OO.....

Cycle: 10
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 11
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

Cycle: 12
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 13
.......
...O...
....O..
.......
OO.....
OO.....

Cycle: 14
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 15
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

Cycle: 16
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 17
.......
...O...
....O..
.......
OO.....
OO.....

Cycle: 18
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Cycle: 19
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

Cycle: 20
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO

Grouping based on pattern
1 | 2 | 3 | 4
5 | 6 | 7 | 8
9 | 10| 11| 12
13| 14| 15| 16
17| 18| 19| 20

We see there are only 4 cycles, and all even cycles are the same grid
so if we have a even cycle we can just print a full grid

If we have an odd cycle then there are two different grids to choose from
we can find which grid the number corresponds to by doing n % 4

Time Complexity: O(m*n) //We must build the result which is a m*n matrix
Space Complexity: O(m*n) //We store every bomb in a map so our Maps cumulative size is O(n*m)
*/

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

public class Solution {
    
    static Map> threeSecondBombs = new HashMap<>();
    static Map> twoSecondBombs = new HashMap<>();
    static Map> oneSecondBombs = new HashMap<>();
    static Map> damagedBombs = new HashMap<>();

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int row = input.nextInt();
        int col = input.nextInt();
        int n = input.nextInt();
        input.nextLine(); 
        
        if(n % 2 == 0)//If n is even we always have a full grid of bombs
        {
            n = 2;
        }
        else if(n > 3) //We are in a repeated pattern(See example above) so we only do either 5 or 7 iterations
        {
            n = (n % 4)+4;
        }
        
        //Initialze variables according to input grid
        char[][] grid = new char[row][col];
        
        for(int i = 0; i < row; i++)
        {
            String readRow  = input.nextLine();
            for(int j = 0; j < col; j++)
            {
                if(readRow.charAt(j) == 'O')
                {
                    if(threeSecondBombs.get(i) == null)
                    {
                        Map map = new HashMap();
                        threeSecondBombs.put(i, map);  
                        threeSecondBombs.get(i).put(j,0);
                    }
                    else
                    {
                        threeSecondBombs.get(i).put(j,0);
                    }
                }
                    
                    
                    
                grid[i][j] = readRow.charAt(j);
            }
        }
        
        
        int cycle = 2;
        
        //Plant all the 2 second bombs
        if(cycle <= n)//2 second cycle
        {
            
            plantBombs(twoSecondBombs, grid);
            cycle++;
            //System.out.println("Plant 2 sec bombs");
            //System.out.println("Cycle: 2");
            //printGrid(grid);
        }        
        
        if(cycle <= n)//3 second cycle
        {   
            detonateBombs(threeSecondBombs, grid);
            threeSecondBombs = new HashMap<>();
            cycle++;
            //System.out.println("Detonate 3 sec bombs");
            //System.out.println("Cycle: 3");
            //printGrid(grid);
        }
        
              
        //All future cycles
        
        //These will function as switches where false is place bomb and true is detonate bomb
        boolean one = false;
        boolean two = true;
        boolean three = false;
        
        while(cycle <= n)
        {
            //System.out.println("Cycle: "+cycle);
            
            if(cycle % 3 == 1)//One cycle
            {
                if(!one)
                {
                    plantBombs(oneSecondBombs, grid);
                    one = !one;
                    //System.out.println("Plant 1 sec bombs");
                    
                }
                else
                {
                    detonateBombs(oneSecondBombs, grid);
                    one = !one;
                    //System.out.println("Detonate 1 sec bombs");
                }
            }
            else if(cycle % 3 == 2)//Two cycle
            {
                if(!two)
                {
                    plantBombs(twoSecondBombs, grid);
                    two = !two;
                    //System.out.println("Plant 2 sec bombs");
                }
                else
                {
                    detonateBombs(twoSecondBombs, grid);
                    two = !two;
                    //System.out.println("Detonate 2 sec bombs");
                }
            }
            else if(cycle % 3 == 0)//Three cycle
            {
                if(!three)
                {
                    plantBombs(threeSecondBombs, grid);
                    three = !three;
                    //System.out.println("Plant 3 sec bombs");
                }
                else
                {
                    detonateBombs(threeSecondBombs, grid);
                    three = !three;
                    //System.out.println("Detonate 3 sec bombs");                    
                }
            }
            cycle++;
            //printGrid(grid); //Grid after each cycle
        }    
        
        //Print the output grid
        printGrid(grid);
    }
    
    //Plants a bomb on all open tiles
    static void plantBombs(Map> bombSet, char[][] grid)
    {
        for(int i = 0; i < grid.length; i++)
        {
            for(int j = 0; j < grid[0].length; j++)
            {
                if(grid[i][j] == '.')
                {
                    //System.out.println("Planting 2s Bomb");
                    if(bombSet.get(i) == null)
                    {
                        //System.out.println("No bomb in row "+i);
                        Map map = new HashMap();
                        bombSet.put(i, map);  
                        bombSet.get(i).put(j,0);
                    }
                    else
                    {
                        bombSet.get(i).put(j,0);
                    }
                    grid[i][j] = 'O';
                }
            }
        }
    }
    
    //Detonates bombs of a given Map updating the other maps and the grid
    static void detonateBombs(Map> bombSet, char[][] grid)
    {
        
        for(Map.Entry> x : bombSet.entrySet())
        {
            int px = x.getKey();
            for(Map.Entry y : x.getValue().entrySet())
            {
                removeDamage(px,y.getKey(),grid);
            }
        }

        for(Map.Entry> x : damagedBombs.entrySet())
        {
            int px = x.getKey();
            for(Map.Entry y : x.getValue().entrySet())
            {
                //System.out.println("Removing Bomb at("+px+","+y.getKey()+")");
                if(threeSecondBombs.get(px) != null)
                {
                    threeSecondBombs.get(px).remove(y.getKey());
                    //System.out.println("Removing 3s Bomb");
                }
                if(twoSecondBombs.get(px) != null)
                {
                    twoSecondBombs.get(px).remove(y.getKey());
                    //System.out.println("Removing 2s Bomb");
                }
                if(oneSecondBombs.get(px) != null)
                {
                    oneSecondBombs.get(px).remove(y.getKey());
                    //System.out.println("Removing 1s Bomb");
                }
            }
        }
        damagedBombs = new HashMap<>();//Remove the bombs now that we have removed all damage
    }
    
    //Replaces all surrounding O with . and adds surrounding to a list of damaged bombs
    static void removeDamage(int x, int y, char[][] grid)
    {
        grid[x][y] = '.';
        removeBomb(x, y);
        
        //Left
        if(y-1 >= 0)
        {
            grid[x][y-1] = '.';
            removeBomb(x, y-1);
        }
            
        //Right
        if(y+1 < grid[0].length)
        {
            grid[x][y+1] = '.';
            removeBomb(x, y+1);
        }
        
        //Up
        if(x-1 >= 0)
        {
            grid[x-1][y] = '.';
            removeBomb(x-1, y);
        }
        
        //Down
        if(x+1 < grid.length)
        {
            grid[x+1][y] = '.';
            removeBomb(x+1, y);
        }
    }
    
    //Adds a bomb to the Map of damaged bombs
    static void removeBomb(int x, int y)
    {
        if(damagedBombs.get(x) == null)
        {
            Map map = new HashMap();
            damagedBombs.put(x, map);  
            damagedBombs.get(x).put(y,0);
        }
        else
        {
            damagedBombs.get(x).put(y,0);
        }
    }
    
    static void printBombSet(Map> bombSet)
    {
        for(Map.Entry> x : bombSet.entrySet())
        {
            int px = x.getKey();
            for(Map.Entry y : x.getValue().entrySet())
            {
                System.out.println("("+px+","+y.getKey()+")");
            }
        }
    }
    
    static void printGrid(char[][] grid)
    {
        for(char[] l : grid)
        {
            for(char m : l)
            {
                System.out.print(m);
            }
            System.out.println("");
        }
        //System.out.println(""); //Uncomment if you are printing iteratively
    }
}

#!/bin/python3
'''
Problem: https://www.hackerrank.com/challenges/richie-rich
Python 3

Thoughts: Not a problem with elegant solution. 
Lots of edge cases and if else's required. 
First pass turning the string into palindrome by 
converting mismatch digit to larger of the two mismatch digits.
marking with '-' to keep track of flipped digits.

Taking second pass to maximise the number, turning digits to '9'
and keeping track of number of flips based on already flipped count.

Time Complexity:  O(N)
Space Complexity: O(N)
'''
import sys


n,k = input().strip().split(' ')
n,k = [int(n),int(k)]
num = input().strip()

def make_palin(n, k, number):
    number_str = str(number)
    number = [number_str[i] for i in range(len(number_str))]
    if n == 1 and k > 0:
        print('9')
        return
    for i in range(int(n/2)):
        if number[i] != number[n-i-1]:
            max_num = max(int(number[i]),int(number[n-i-1]))
            number[i] = str(-1 * max_num)
            number[n-i-1] = str(max_num)
            k = k-1
            if k<0 :
                print('-1')
                return
    flips_available = k
    for i in range(int(n/2)):
        dig_1 = int(number[i])
        dig_2 = int(number[n-i-1])
        if dig_1 < 0 and flips_available > 0:
            decrement = 1
            if dig_2 == 9:
                decrement = 0
            number[i] = str(9)
            number[n-i-1] = str(9)
            flips_available = flips_available - decrement
        elif flips_available > 0:
            decrement = 2
            if dig_1 == 9:
                decrement = decrement - 1
            if dig_2 == 9:
                decrement = decrement - 1
            if flips_available >= decrement:
                number[i] = str(9)
                number[n-i-1] = str(9)
                flips_available = flips_available - decrement
        elif dig_1 < 0 and flips_available <= 0:
            number[i] = str(-1 * dig_1)
    if n%2 != 0 and flips_available>0:
        number[int(n/2)] = str(9)
    print(''.join(number))


make_palin(n , k, num)

/*
         Problem: https://www.hackerrank.com/challenges/picking-numbers/problem
         C# Language Version: 6.0
         .Net Framework Version: 4.5.2
         Thoughts :

        1. Sort the input array containing n integers in ascending order.
        2. Initialize a variable maxSetCount to 0.
        3. Start processing the elements in the sorted array using a loop:
            3.1 Let the index of current element be i.
            3.2 If the current element is equal to its previous element so it is already processed. skip it.
            3.3 If the current element is not equal to its previous element then process it with below steps.
                3.3.1 Start iterating the sorted array from index i+1 of the sorted array in a new loop.
                3.3.2 Initialize a variable currentSetCount = 1
                3.3.3 Increment currentSetCount by 1 if absolute difference of current element in outer loop and current 
                        element in inner loop is less than or equal to 1.
                3.3.4 Quit the inner loop if absolute difference of current element in outer loop and current 
                        element in inner loop is greater than 1.
                3.3.5 Set maxSetCount to currentSetCount if currentSetCount is greater than maxSetCount.
            3.4 Process all elements of the sorted array using steps 2.1 through 2.3.
        4. Print maxSetCount on console.
                
         
         Time Complexity:  O(n)
         Space Complexity: O(n) //we require an addtional array to keep all the input numbers in sorted order.
        */ 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
            Console.ReadLine();
            var a_temp = Console.ReadLine().Split(' ');
            var a = Array.ConvertAll(a_temp, Int32.Parse);
            var maxCount = 0;
            var sortedList = a.OrderBy(x => x).ToList();

            for (int i = 0; i < sortedList.Count; i++)
            {
                var currentCount = 1;
                if (i > 0)
                    if (sortedList[i] == sortedList[i-1])
                        continue;

                for (int j = i+1; j < sortedList.Count; j++)
                {
                    if (Math.Abs(sortedList[j]-sortedList[i]) <=1)
                        currentCount++;
                    else
                        break;
                }

                if (currentCount > maxCount)
                    maxCount = currentCount;
            }
            Console.WriteLine(maxCount);
    }
}

//Problem: https://www.hackerrank.com/challenges/cut-the-sticks
//Java 8
import java.io.*;
import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int [] sticks = new int[N];
        
        for(int i = 0; i < N; i++)
        {
            sticks[i] = input.nextInt();
        }
        
        //QuickSort sticks in ascending order
        //The built in sort function performs a dual pivot quick sort that rarely degrades to n^2
        Arrays.sort(sticks);
        
        
        int sticksLeft = N;
        
        int curr = sticks[0];
        int currCount = 0;
        System.out.println(N);
        
        //Works by decrementing sticksLeft by the frequency of the smallest stick each time
        for(int i = 0; i < N; i++)
        {
            if(curr == sticks[i])
            {
                currCount++;
            }
            else
            {
                sticksLeft -= currCount;
                currCount = 1;
                curr = sticks[i];
                System.out.println(sticksLeft);
            }
        }
        
        
    }
}

/*
         Problem: https://www.hackerrank.com/challenges/drawing-book/problem
         C# Language Version: 6.0
         .Net Framework Version: 4.5.2
         Thoughts :
         1. Let total number of pages in the book be totalPagesInBook and the page number we want to open is targetPageNumber.
         2. Let the minimum number of pages which are to be turned to reach targetPageNumber is minimumPagesToTurn.
         3. Set minimumPagesToTurn to 0
         4. There are three cases in which user will not have to turn even a single page
            - If targetPageNumber is 1 OR
            - If targetPageNumber is equal to totalPagesInBook OR
            - If totalPagesInBook is an odd number and targetPageNumber is totalPagesInBook-1
            If either of the above three conditions are met then jump to step 7.
         5. If totalPagesInBook is an even number then
            - if targetPageNumber is less than or equal to half of totalPagesInBook then starting from front will be beneficial.
              Set minimumPagesToTurn to half of targetPageNumber.
            - otherwise starting from end will be beneficial.
              Set minimumPagesToTurn to half of difference between totalPagesInBook and targetPageNumber. If the operation
              results in a decimal value then round it off to its nearest higher integer.
         6. If totalPagesInBook is an odd number then
            - If targetPageNumber is the exact median of totalPagesInBook and totalPagesInBook in book
                is exacly one less than the nearest multiple of 4 then starting from end will be beneficial.
                Set minimumPagesToTurn to half of difference of totalPagesInBook and targetPageNumber.
            - If targetPageNumber is less than, equal to or one more than half of totalPagesInBook then starting from front will be beneficial.
              Set minimumPagesToTurn to half of targetPageNumber.
            - otherwise starting from back will be beneficial.
              Set minimumPagesToTurn to half of difference between totalPagesInBook and targetPageNumber. 
          7. Print minimumPagesToTurn

         Time Complexity:  O(1)
         Space Complexity: O(1)
                
        */
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static int solve(int totalPagesInBook, int targetPageNumber){
        var minimumPagesToTurn = 0;

            if (targetPageNumber == 1 || targetPageNumber == totalPagesInBook)
                return minimumPagesToTurn;

            if (totalPagesInBook % 2 != 0 && targetPageNumber == totalPagesInBook - 1)
                return minimumPagesToTurn;


            if (totalPagesInBook % 2 == 0)
            {
                //even number of total pages e.g. 10
                if (targetPageNumber <= totalPagesInBook / 2)
                {
                    //start from front
                    minimumPagesToTurn = targetPageNumber / 2;
                }
                else
                {
                    //start from end
                    double d = ((double)(totalPagesInBook - targetPageNumber)) / 2;
                    minimumPagesToTurn = (int)Math.Ceiling(d);
                }
            }
            else
            {
                //total number of pages are odd

                //special handling for exactly middle number when total number of pages are like 3,7,11,15...and so on

                if (targetPageNumber == (totalPagesInBook/2)+1 && totalPagesInBook % 4 == 3)
                {
                    //this requires special handling as this median will be close to the end instead
                    minimumPagesToTurn = (totalPagesInBook - targetPageNumber) / 2;
                }
                else
                {
                    if (targetPageNumber <= ((totalPagesInBook / 2) + 1))
                    {
                        //start from front
                        minimumPagesToTurn = targetPageNumber / 2;
                    }
                    else
                    {
                        //start from end
                        minimumPagesToTurn = (totalPagesInBook - targetPageNumber) / 2;
                    }
                }

            }
            return minimumPagesToTurn;
    }

    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        int p = Convert.ToInt32(Console.ReadLine());
        int result = solve(n, p);
        Console.WriteLine(result);
    }
}

//Problem: https://www.hackerrank.com/challenges/strange-advertising
//Java 8
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        
        //We can intialize to day 1 values since 1<= n <= 50
        int peopleReached = 2, peopleSharing = 2;
        for(int i = 1; i < n; i++)
        {
            peopleReached += (peopleSharing * 3) / 2;
            peopleSharing = (peopleSharing * 3) / 2;
        }
        System.out.println(peopleReached);
    }
}

/*
     Problem: https://www.hackerrank.com/challenges/minimum-distances/problem
     C# Language Version: 7.0
     .Net Framework Version: 4.7
     Tool Version : Visual Studio Community 2017
     Thoughts :
     1. Let the array be arr containing all input integers.
     2. Let minimum distance value to be found be minDist. Initialize minDist with -1.
     3. Let there be a hash map which can contain integers as key-value pairs. Let its name be hm.
     4. Start iterating arr in a loop:
        4.1 Let the current integer being iterated is n.
        4.2 Let the index of n in the array be i.
        4.3 Check whether n is present as key in hm or not:
            4.3.1 If it is not present then add (n,i) as key value pair into hm.
            4.3.2 If it is present then check if minDist is still set to -1:
                4.3.2.1 If yes then set minDist to difference of i and value corresponding to n key in hm.
                4.3.2.2 If no then check whether difference of i and value corresponding to n key in hm is less than minDist.
                        If it is true then set minDist to difference of i and value corresponding to n key in hm.
        4.4 Keep repeating steps from 4.1 through 4.3 until entire array gets iterated.
    5. Print minDist on console.

     Time Complexity:  O(n) Array of integers has to iterated at least once in entirety.
     Space Complexity: O(n) I'm maintaining an extra hash map having index of unique elements in the array.
        
*/

using System;
using System.Collections.Generic;
class Solution
{
    static int MinimumDistances(int[] arr)
    {
        var minimumDist = -1;
        var numberMap = new Dictionary();
        for (var i = 0; i < arr.Length; i++)
        {
            if (numberMap.ContainsKey(arr[i]))
            {
                if (minimumDist == -1)
                {
                    minimumDist = i - numberMap[arr[i]];
                    continue;
                }

                if (i - numberMap[arr[i]] < minimumDist)
                    minimumDist = i - numberMap[arr[i]];
            }
            else
                numberMap.Add(arr[i], i);
        }
        return minimumDist;
    }

    static void Main(String[] args)
    {
        //No need to capture the size of array. I use array's length property instead.
        Console.ReadLine();
        var a_temp = Console.ReadLine().Split(' ');
        var a = Array.ConvertAll(a_temp, Int32.Parse);
        var result = MinimumDistances(a);
        Console.WriteLine(result);
    }
}

/*
 Problem: https://www.hackerrank.com/challenges/the-time-in-words/problem
 C# Language Version: 7.0
 .Net Framework Version: 4.7
 Tool Version : Visual Studio Community 2017
 Thoughts :
 1. Let the input values of hours and minutes be h and m respectively.
 2. Declare an array hw containing string values of numbers from 1 to 11.
 3. Declare an array mw containing string values of numbers from 1 to 29.
 4. Print the appropriate string representation of time using hw and mw arrays based on the values of h and m.

 Time Complexity:  O(1) //there are no loops at all.
 Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
*/

using System;

class Solution
{
    static void Main(String[] args)
    {
        var h = int.Parse(Console.ReadLine());
        var m = int.Parse(Console.ReadLine());
        var hourWords = new[] { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven" };
        var minuteWords = new[] { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
                                    , "eleven", "twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty"
                                    , "twenty one", "twenty two", "twenty three", "twenty four", "twenty five", "twenty six", "twenty seven", "twenty eight","twenty nine" };


        if (m == 0)
            Console.Write($"{hourWords[h - 1]} o' clock");

        if ((m > 0 && m < 15) || (m > 15 && m < 30))
            Console.Write($"{minuteWords[m - 1]} minutes past {hourWords[h - 1]}");

        if ((m > 30 && m < 45) || (m > 45 && m < 60))
            Console.Write($"{minuteWords[60 - m - 1]} minutes to {hourWords[h]}");

        if (m == 15)
            Console.Write($"quarter past {hourWords[h - 1]}");

        if (m == 30)
            Console.Write($"half past {hourWords[h - 1]}");

        if (m == 45)
            Console.Write($"quarter to {hourWords[h]}");
    }
}

//Problem: 
//Java 8
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        
        for(int i = 0; i < T; i++)
        {
            int n = input.nextInt()-1;//Minus 1 to account for 0 starting stone
            int a = input.nextInt();
            int b = input.nextInt();
            
            //Edge case where no iterations are required
            if(a == b)
            {
                System.out.println(a*n + " ");
                continue;
            }
            
            //make sure a is our min
            int tmp = a;
            a = Math.min(a,b);
            //If b was the min then set it to old value of a
            b = (a == b) ? tmp : b;
            
            int min = a*n;
            int max = b*n;
            
            //We only need to increment by difference because there are only two stones to choose from each time
            for(int finalSteps = min; finalSteps <= max; finalSteps += (b-a))
            {
                System.out.print(finalSteps + " ");
            }
            
            System.out.println();
            
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/save-the-prisoner
//Java 8
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        
        for(int i = 0; i < T; i++)
        {
            int N = input.nextInt();//Number of prisoners
            int M = input.nextInt();//Number of sweets
            int S = input.nextInt();//First prisoner to be served
            
            int poisonedPrisoner = (S + M - 1) % N;
            if(poisonedPrisoner == 0){poisonedPrisoner=N;}
            System.out.println(poisonedPrisoner);
        }
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/electronics-shop
    Language: C# 
    Thoughts:
        1. Let Monica has total money MTotal.
        2. Let maximum money spendable on electronics be MaxMoneySpendable. Initialize it to -1.
        3. Consider ArrayKeyboardPrices and ArrayDrivePrices.
        4. Sort ArrayKeyboardPrices in descending order.
        5. Sort ArrayDrivePrices in ascending order.
        6. Start iterating the elements in the sorted ArrayKeyboardPrices. Let the keyboard price being iterated is kbCurrent.
        7. For kbCurrent start iterating the elements of sorted ArrayDrivePrices.
            - let the drive price being iterated is driveCurrent.
            - if sum of driveCurrent and kbCurrent is greater than MTotal then stop iterating sorted ArrayDrivePrices
            - if sum of driveCurrent and kbCurrent is less than or equal to MTotal 
                then set MaxMoneySpendable to  sum of driveCurrent and kbCurrent
                and move to next element in sorted ArrayDrivePrices
        8. Repeat step 7 for all elements of sorted ArrayKeyboardPrices
        9. Print MaxMoneySpendable.

        Time Complexity:  
        Worst case : O(n^2)
        Best case : O(nlog n)
        Space Complexity: O(1)        
*/

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
        static int getMoneySpent(int[] keyboards, int[] drives, int totalMoneyAvailable)
        {
            var sortedKeyboardPrices = from keyboard in keyboards
                                 orderby keyboard descending
                                 select keyboard;
            var sortedDrivePrices = from drive in drives
                              orderby drive ascending
                              select drive;
            //default if not able to purchase anything
            var maxMoneySpendable = -1;

            foreach (var keyboard in sortedKeyboardPrices)
            {
                foreach (var drive in sortedDrivePrices)
                {
                    if (keyboard + drive <= totalMoneyAvailable)
                    {
                        if (keyboard + drive > maxMoneySpendable)
                            maxMoneySpendable = keyboard + drive;
                    }
                    else
                        break;
                }
            }
            return maxMoneySpendable;
        }

    static void Main(String[] args) {
        string[] tokens_s = Console.ReadLine().Split(' ');
        int s = Convert.ToInt32(tokens_s[0]);
        string[] keyboards_temp = Console.ReadLine().Split(' ');
        int[] keyboards = Array.ConvertAll(keyboards_temp,Int32.Parse);
        string[] drives_temp = Console.ReadLine().Split(' ');
        int[] drives = Array.ConvertAll(drives_temp,Int32.Parse);
        //  The maximum amount of money she can spend on a keyboard and USB drive, or -1 if she can't purchase both items
        int moneySpent = getMoneySpent(keyboards, drives, s);
        Console.WriteLine(moneySpent);
    }
}

//Problem: https://www.hackerrank.com/challenges/angry-professor
//Java 8
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        
        testCases: 
        for(int i = 0; i < T; i++)
        {
            int n = input.nextInt();
            int k = input.nextInt();
            int onTime = 0;
            for(int j = 0; j < n; j++)
            {
                int arrivalTime = input.nextInt();
                if(arrivalTime <= 0)
                {
                    onTime++;
                }
            }
            if(onTime >= k)
            {
                System.out.println("NO");
            }
            else
            {
                System.out.println("YES");   
            }
        }
    }
}

/*
Problem: https://www.hackerrank.com/challenges/strange-advertising/problem
C# Language Version: 6.0
.Net Framework Version: 4.5.2
Thoughts :

1. Let the number of days for advertisement strategy runs be n.
2. Let total advertisement likes in n days be l. Set l = 0.
3. Let people who received advertisement on day 1 by m. Set m = 5
4. Start a loop which run n times with below steps in each iteration:
    4.1 Set l = l + floor(m/2)
    4.2 m = floor(m/2)*3
5. Print l


Time Complexity:  O(n) 
Space Complexity: O(1) 

*/

using System;

class Solution
{
    static void Main(String[] args)
    {
        var numberOfDays = int.Parse(Console.ReadLine());
        var totalLikes = 0D;
        var AdShareCount = 5.0;
        for (int i = 0; i < numberOfDays; i++)
        {
            totalLikes += Math.Floor(AdShareCount / 2);
            AdShareCount = Math.Floor(AdShareCount / 2) * 3;
        }
        Console.WriteLine(totalLikes);
    }
}

//Problem: https://www.hackerrank.com/challenges/sock-merchant
//Java 8
/*
Thoughts: Since we only care about the number of pairs, we can iterate over the
		  input and check if we have already seen a matching sock. To do this, 
		  once we see a new sock we store it in a hash map with the value 1 and
		  if we see that sock a again we simply set its' value to 0 and increase
		  our pair count by 1. After iterating all the socks we will have a total
		  number of pairs.


Time Complexity: O(n) //We iterate over the input
Space Complexity: O(n) //At most every input is unique in our hashmap
*/
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.HashMap;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        HashMap inventory = new HashMap();
        
        int matchingPairs = 0;
        
        for(int i=0; i < n; i++)
        {
            int color = in.nextInt();
            
            //This checks if we already have 1 sock of that color and if we do then we increment matchingPairs and set unmatched               //socks of that color back to 0
            if(inventory.containsKey(color) && inventory.get(color).equals(new Integer(1)))
            {
                inventory.put(color,0);
                matchingPairs++;
                continue;
            }
            inventory.put(color,1);
        }
        System.out.println(matchingPairs);
    }
}

/*
     Problem: https://www.hackerrank.com/challenges/chocolate-feast/problem
     C# Language Version: 7.0
     .Net Framework Version: 4.7
     Tool Version : Visual Studio Community 2017
     Thoughts :
     1. Let the number of trips to the shop be t.
     2. Start with a loop which runs t times:
        2.1 Let the dollar amount, cost of choclate and wrapper offer in the current trip be n,c and m respectively.
        2.2 Let the running total count of choclates bought in the current trip be cc. 
        2.3 Let the running count of wrappers obtained from the choclates being bought be wc.
        2.3 Initialize cc and wc both to n/c.
        2.4 Now run a loop until the value of wc >= m
            2.4.1 add  the count of choclates bought from the wrappers i.e. wc/m to cc.
            2.4.2 update the count of wrappers with wrappers obtained from next set of choclates along with wrappers
                  which went unused in step 2.4.1
            2.4.3 Continue iterating the steps from 2.4.1 to 2.4.2 until the loop condition is true.
        2.5 print the value of cc on a new line on console.

     Time Complexity:  O(log(n)) //base of logarithm is m. 
                                 // Base of logarithmic time complexity is m as the number of wrappers obtained 
                                 // in first purchase get reduced to n/m in each iteration while getting processed using a loop
     Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.

*/

using System;

class Solution
{
    static void Main(String[] args)
    {
        var t = int.Parse(Console.ReadLine());
        for (int a0 = 0; a0 < t; a0++)
        {
            var tokens_n = Console.ReadLine().Split(' ');
            var n = int.Parse(tokens_n[0]);
            var c = int.Parse(tokens_n[1]);
            var m = int.Parse(tokens_n[2]);

            var totalChoclates = n / c;
            var wrappersFromChoclates = totalChoclates;
            while (wrappersFromChoclates >= m)
            {
                totalChoclates += wrappersFromChoclates / m;
                wrappersFromChoclates = (wrappersFromChoclates / m) + (wrappersFromChoclates % m);//add unused wrappers.
            }
            Console.WriteLine(totalChoclates);
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/chocolate-feast
//Java 8

/*
We have n dollars
Chocolate cost c dollars
you can trade m wrappers for 1 chocolate

Example
m = 2
n = 4
c = 1


Buy 4 chocolates
trade 4 wrappers for 2 chocolates
trade 2 wrappers for 1 chocolate

Ate 7 chocolates 

Chocolates ate = 0

chocolatesValue = money / cost per chocolate

ate += CV

while(chocolate value > 0)
chocolatesValue = chocolatesValue / wrapperExchangeRate + modulus
are += CV

can we determine based on initial wrappers how many possibly candies can
be gotten taking into account future exchanges?

10 wrappers and 2 ER

10 5 3 2 0

3

10 4 2

11 5 3 0

So far I don't see a way so lets code a implementation and see what we can learn

runtime O(n/2) O(n)
*/


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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        
        for(int i = 0; i < t; i++)
        {
            int n = input.nextInt();
            int c = input.nextInt();
            int m = input.nextInt();
            
            int ate = 0;
            
            int chocolates = n / c;
            
            ate += chocolates;

            while(chocolates >= m)
            {
                ate += chocolates / m;
                chocolates = (chocolates / m) + (chocolates % m);
            }
            System.out.println(ate);
        }
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/find-digits/problem
    C# Language Version: 6.0
    .Net Framework Version: 4.7
    Tool Version : Visual Studio Community 2017
    Thoughts :
    1. Initialize a variable count c to 0.
    2. Let the input number be n.
    3. Start iterating each digit of the number n in a loop
        3.1 Get next digit of the number n. Let it be d.
        3.2 If d divides n leaving no remainder then increment c by 1.
    4. print c

    Time Complexity:  O(n) //dependent upon the number of digits in the input number
    Space Complexity: O(1) //dynamically allocated variables remain constant irrespective of the size of the input.

*/

using System;

class Solution
{
    static void Main(String[] args)
    {
        var numberOfTestCases = int.Parse(Console.ReadLine());
        for (int a0 = 0; a0 < numberOfTestCases; a0++)
        {
            var n = Console.ReadLine();
            var number = int.Parse(n);
            var digitCount = 0;
            foreach (var item in n)
            {
                if (item == '0')
                    continue;

                if (number % (int)char.GetNumericValue(item) == 0)
                    digitCount++;
            }
            Console.WriteLine(digitCount);
        }
    }
}

/*
         Problem: https://www.hackerrank.com/challenges/utopian-tree/problem
         C# Language Version: 6.0
         .Net Framework Version: 4.5.2
         Thoughts :

         1. Start processing each input test case one by one.
         2. Let number of growth cycles in current test case be N.
         3. Set initial height H of sapling to 1.
         4. Set a boolean isSpring to true. It represents that in any year, first we hit spring season.
         5. Start a loop which runs N times. During each iteration in the loop :
            - If isSpring is true (spring season) then set H to H * 2 and isSpring to false.
            - If isSpring is false (summer season) then set H to H + 1 and isSpring to true.
         6. Print H.
         7. Repeat step 2 through 6 for each test case.

         Time Complexity:  O(n)
         Space Complexity: O(1)
                
        */
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        var t = int.Parse(Console.ReadLine());
            for (int a0 = 0; a0 < t; a0++)
            {
                var numberOfCycles = int.Parse(Console.ReadLine());
                var finalHeightOfSapling = 1;
                bool isSpring = true;
                while (numberOfCycles > 0)
                {
                    if (isSpring)
                    {
                        finalHeightOfSapling *= 2;
                        isSpring = false;
                    }
                    else
                    {
                        finalHeightOfSapling++;
                        isSpring = true;
                    }
                    numberOfCycles--;
                }
                Console.WriteLine(finalHeightOfSapling);
            }
    }
}

//Problem: https://www.hackerrank.com/challenges/two-characters
//Java 8
/*
Examples: 
beabeefeab  -> babab -> 5
bbbbbaaaaa  ->       -> 0
a           ->       -> 1
aa          ->       -> 0
abb         ->       -> 1


We test every combination of 2 characters
and we keep a running max of the longest that satisfies

Summation: (1*n-1)...(1*1)
n^2 * n -> n^3

Optimizations:
Remove any char that has a double contiguous 
Start with the largest


Tradeoff:
Use memory to track multiple char combinations at once
beabeefeab
ab
ae
af
be
bf
ef

if you passes then we check against our max

run in O(n) but would use O(n^2)


Since we are limited to the alphabet which we know to 
be constant we can come up with a better solution

We can iterate through every character pair which is 
(26 * 25) / 2 = 325 pairs

for each of those iterations we will run through the string 
checking if it fits the pattern and return the largest


Time Complexity: O(n)
Space Complexity: O(1)


*/

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        String s = in.next();
        int maxPattern = 0;
        
        if(s.length() == 1)//Edge case where length is 1
        {
            System.out.println(maxPattern);
            System.exit(0);
        }
        
        //Loop through all letter pairs
        for(int i = 0; i < 26; i++)
        {
            nextLetter:
            for(int j = i + 1; j < 26; j++)
            {
                char one = (char) ('a' + i); //First char in pair
                char two = (char) ('a' + j); //Second char in pair
                char lastSeen = '\u0000';
                int patternLength = 0;
                
                for(char letter : s.toCharArray())
                {
                    if(letter == one || letter == two)
                    {
                        if(letter == lastSeen)//Duplicate found
                        {
                            continue nextLetter;
                        }
                        //Not a duplicate
                        patternLength++;
                        lastSeen = letter;
                    }
                }//for char : s
                
                maxPattern = (patternLength > maxPattern) ? patternLength : maxPattern; //Keep a running max
                
            }//for j
        }//for i
        
        System.out.println(maxPattern);
        
    }
}

//Problem: https://www.hackerrank.com/challenges/repeated-string
//Java 8
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        long n = in.nextLong();
        
        long countForSubstring = 0;
        long totalCount = 0;
        
        //Determines how many a's are in a substring
        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) == 'a')
            {
                countForSubstring++;
            }
        }
        
        
        //Determines how many complete substrings we will analyze
        long divisor = n / s.length();
        
        totalCount += divisor * countForSubstring;
        
        
        //Determines how many characters in we will analyze towards the end of our n range
        long remainder = n % s.length();
        
        for(int i = 0; i < remainder; i++)
        {
            if(s.charAt(i) == 'a')
            {
                totalCount++;
            }
        }
        
        System.out.println(totalCount);
    }
}

/*
 Problem: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem
 C# Language Version: 6.0
 .Net Framework Version: 4.5.2
 Thoughts :
 1. Get an array of n player scores. Iterate through all player scores and create a new array 
    which doesn't contain any repeated player scores. Let us call the new array, playerScores.
 2. Let total levels to be played by Alice is m.
 3. Let Alice's score after first round be S.
 4. Let Alice's initial rank R be 0.
 5. Start iterating playerScores array from the rear end untill you get a player score whose score is less than S.
 6. Set R to rank of the player found in step 5.
 7. Reduce m by 1.
 8. Print R.
 9. Now start processing Alice's score in all subsequent levels inside a loop
    9.1 Set S to Alice's next level score.
    9.2 Start iterating playerScores array from the player whose rank is R-1 towards the front end.
    9.3 Continue iteration untill you get a player whose score is less than S.
    9.4 Set R to rank of the player found in above step.
    9.5 Reduce m by 1.
    9.6 Print R.
    9.7 Go to step 9.1 if there are more levels left to be played (i. e m>0).

 Time Complexity:  O(n+m) - One scan required to get non-duplicate scores (n). m iterations required to decide
                        Alice's rank after each level.
 Space Complexity: O(n) - An additional array for entire input set is required to store non-duplicate scores.
        
*/

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
       
        Console.ReadLine();
            var scores_temp = Console.ReadLine().Split(' ');
            var playerScoresWithRepeats = Array.ConvertAll(scores_temp, long.Parse);
            var playerScores = new long[playerScoresWithRepeats.Length];
            playerScores[0] = playerScoresWithRepeats[0];
            int k = 0;
            for (int j = 1; j < playerScoresWithRepeats.Length; j++)
            {
                if (playerScoresWithRepeats[j] < playerScores[k])
                {
                    playerScores[++k] = playerScoresWithRepeats[j];
                }
            }

            var totalLevelsToPlay = int.Parse( Console.ReadLine());
            var alice_temp = Console.ReadLine().Split(' ');
            var aliceScores = Array.ConvertAll(alice_temp, long.Parse);


            var currentRoundRank = 0;
            var aliceScoreIndex = 0;
            var nextAliceScore = aliceScores[aliceScoreIndex];

            if (nextAliceScore < playerScores[playerScores.Length - 1])
            {
                currentRoundRank = playerScores.Length + 1;
            }
            else
            {
                for (int i = 0; i < playerScores.Length; i++)
                {
                    if (nextAliceScore >= playerScores[i])
                    {
                        currentRoundRank++;
                        break;
                    }
                    currentRoundRank++;
                }
            }
            totalLevelsToPlay--;
            Console.WriteLine(currentRoundRank);



            while (totalLevelsToPlay > 0)
            {
                nextAliceScore = aliceScores[++aliceScoreIndex];
                var temp = currentRoundRank - 2;

                while (temp > -1)
                {
                    var nextHigherRankedPlayerScore = playerScores[temp--];
                    if (nextAliceScore >= nextHigherRankedPlayerScore)
                    {
                        currentRoundRank--;
                        continue;
                    }
                    else
                        break;
                }
                Console.WriteLine(currentRoundRank);
                totalLevelsToPlay--;
            }
        
    }
}

//Problem: https://www.hackerrank.com/challenges/fair-rations
//Java 8
/*



Examples: 
[1 1 1 2 1 2 1 2 1 1 2 2 1 2]

[2 2 1 2 1 2 1 2 1 1 2 2 1 2] 2

[2 2 2 3 1 2 1 2 1 1 2 2 1 2] 2

[2 2 2 4 2 2 1 2 1 1 2 2 1 2] 2

[2 2 2 4 2 2 2 3 1 1 2 2 1 2] 2

[2 2 2 4 2 2 2 4 2 1 2 2 1 2] 2

[2 2 2 4 2 2 2 4 2 2 3 2 1 2] 2

[2 2 2 4 2 2 2 4 2 2 4 3 1 2] 2

[2 2 2 4 2 2 2 4 2 2 4 4 2 2] 2
                              16

[2 3 4 5 6]

[2 4 5 5 6] 2

[2 4 6 6 6] 2
            4

[1 1 1 1 1 1 1 1 1 1 1 1]  solvable

[1 1 1 1 1 1 1 1 1 1 1 1 1] unsolvable


Time: O(n)
Space: O(1)


*/



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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
               
        int bread = 0;
        int currentBread = 0;
        
        for(int i = 0; i < N; i++)
        {
            currentBread += in.nextInt();
            if(i == N-1)//We have reached the last person
            {
                if(currentBread % 2 == 1) //If last person ended with odd bread it is not possible
                {
                    System.out.println("NO");
                    System.exit(0);
                }
                else
                {
                    System.out.println(bread);
                    System.exit(0);
                }
            }
            
            
            if(currentBread % 2 == 1) //The current person has odd bread give them and the next person bread
            {
                currentBread = 1;
                bread += 2;
                continue;
            }
            currentBread = 0; // No extra bread was given out
        }
        
    }
}

//Problem: https://www.hackerrank.com/challenges/morgan-and-a-string
//Java 8 
/*
Initial thoughts:
Since we can only pull from the top of each 
letter stack each time, we simply need to just
compare the letters at the top of each stack

In each comparison we just need to choose the
letter that is lexicographically smaller than
the other and print it out and continue this 
until 1 of the stacks is empty.

If we have equivalent characters, we have to decide 
which one to pick

When they are equivalent, we choose the one from the 
stack that is overall lexicographically smaller
Read inline comments for better understanding of how
I handle this

Then if we have finished 1 string early we just need 
to add letters from the other stack to the end of the 
string we built

Time Complexity: O(|a|+|b|^2)   //We only view each letter once
Space Complexity: O(|a| + |b|)  //We store out output in a SB to speed up run time
*/

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        
        for(int a0 = 0; a0 < t; a0++)
        {
            StringBuilder s1 = new StringBuilder(input.next()); s1.append("z");//Denote end
            StringBuilder s2 = new StringBuilder(input.next()); s2.append("z");//Denote end
            StringBuilder output = new StringBuilder("");
            
            int i = 0, j = 0;//Index into each string
            while(i < s1.length() && j < s2.length())
            {
                ////////////Simple cases/////////////
                if(s1.charAt(i) < s2.charAt(j))
                {
                    output.append(s1.charAt(i));
                    i++;
                }
                else if(s1.charAt(i) > s2.charAt(j))
                {
                    output.append(s2.charAt(j));
                    j++;
                }
                //////////////////////////////////////
                
                
                
                ///////Characters are different///////
                else 
                {
                    if(s1.charAt(i) == 'z'){i++; j++; continue;}//End has been reached

                    
                    int startingI = i;
                    int startingJ = j;
                    
                    //Find the point at which their equality diverges
                    while(s1.charAt(i) == s2.charAt(j))
                    {
                        i++;
                        j++;
                        if(i >= s1.length() && j >= s2.length()) //They are the same string
                        {
                            i = startingI;
                            j = startingJ;
                            break;  
                        }
                        else if(i >= s1.length()) //String 1 is shorter than string 2
                        {
                            //We append all chars that are in a decreasing sequence 
                            ////////ex: gdbad would return gdba
                            char prev = s2.charAt(startingJ);
                            while(s2.charAt(startingJ) <= prev)
                            {
                                output.append(s2.charAt(startingJ));
                                prev = s2.charAt(startingJ);
                                startingI++;
                            }
                            i = startingI;
                            j = startingJ;
                        }
                        else if(j >= s2.length()) //String 2 is shorter than string 1
                        {
                            char prev = s1.charAt(startingI);
                            while(s1.charAt(startingI) <= prev)
                            {
                                output.append(s1.charAt(startingI));
                                prev = s1.charAt(startingI);
                                startingI++;
                            }
                            i = startingI;
                            j = startingJ;
                        }
                    }
                    
                    
                    //They are different strings
                    
                    //String 1 is lexicographically smaller than String 2
                    if(s1.charAt(i) <= s2.charAt(j))
                    {
                        char prev = s1.charAt(startingI);
                        while(s1.charAt(startingI) <= prev)
                        {
                            output.append(s1.charAt(startingI));
                            prev = s1.charAt(startingI);
                            startingI++;
                        }
                        i = startingI;
                        j = startingJ;
                    }
                    
                    //String 2 is lexicographically smaller than String 1
                    if(s1.charAt(i) > s2.charAt(j))
                    {
                        char prev = s2.charAt(startingJ);
                        while(s2.charAt(startingJ) <= prev)
                        {
                            output.append(s2.charAt(startingJ));
                            prev = s2.charAt(startingJ);
                            startingJ++;
                        }
                        i = startingI;
                        j = startingJ;
                    }
                }
            }
            
            
            //We reached the end of 1 string
            //Add rest of string 1
            while(i < s1.length())
            {
                output.append(s1.charAt(i));
                i++;
            } 
            
            //Add rest of string 2
            while(j < s2.length())
            {
                output.append(s2.charAt(j));
                j++;
            }
            
            
            //Print the output
            System.out.println(output);
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/palindrome-index
//Java 8
/*
Initial Thoughts:
We can use pointers from the beggining and
end to iterate through the string

If they pointers' chars match then when advance 
each one

If they don't match we check if the element to
the right of the left pointer matches the right
pointer and if not we check if the pointer to the
left of the right pointer matches the left pointer
if neither is true then return -1 else if 1 is true
we advance the corresponding pointer and store its
prev index

If we have non matching pointers after something was
already removed we just return -1

It is possible to delete the wrong one when
checking ahead, so we check the other branch if
our first branch fails


*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); input.nextLine();
        
        tests:
        for(int t = 0; t < n; t++)
        {
            
            String s = input.nextLine();
            int outputIndex = -1;
            boolean removal = false;
            
            for(int i = 0, j = s.length()-1; i < j; i++, j--)
            {
                
                if(s.charAt(i) != s.charAt(j))
                {

                    if(removal)
                    {
                        removal = false;
                        outputIndex = -1;
                        break;
                    }
                    
                    if(s.charAt(i+1) == s.charAt(j))
                    {
                        removal = true; 
                        outputIndex = i;
                        i++;
                    }
                    else if(s.charAt(i) == s.charAt(j-1))
                    {
                        removal = true; 
                        outputIndex = j;
                        j--;
                    }
                    else
                    {
                        removal = false;
                        outputIndex = -1;
                        break;
                    }
                }
            }
            if(outputIndex != -1)
            {
                System.out.println(outputIndex); continue tests;    
            }
            
            
            //Case where we made the wrong removal decision and we could have made a palindrome
            
            for(int i = 0, j = s.length()-1; i < j; i++, j--)
            {
                
                if(s.charAt(i) != s.charAt(j))
                {

                    if(removal)
                    {
                        System.out.println(-1); continue tests;
                    }
                    
                    if(s.charAt(i) == s.charAt(j-1))
                    {
                        removal = true; 
                        outputIndex = j;
                        j--;
                    }
                    else if(s.charAt(i+1) == s.charAt(j))
                    {
                        removal = true; 
                        outputIndex = i;
                        i++;
                    }
                    else
                    {
                        System.out.println(-1); continue tests;
                    }
                }
            }
            System.out.println(outputIndex);
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/alternating-characters
//Java 8
/*
Initial thoughts:
Remove all duplicates and problem is solved

*/

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        
        tests:
        for(int t = 0; t < T; t++)
        {
            String s = input.nextLine();
            int deletions = 0;
            int currentCount = 1;
            for(int i = 1; i < s.length(); i++)
            {
                if(s.charAt(i) != s.charAt(i-1))
                {
                    deletions += currentCount - 1;
                    currentCount = 1;
                    continue;
                }
                currentCount++;
            }
            deletions += currentCount - 1;
            System.out.println(deletions);
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/two-strings
//Java 8
/*
Initial Thoughts:
Since a substring can be a minimum of size 1
and at max the size of the smallest substring,
then we can derive that if they have a letter in
common they have a substring in common

Algorithm:
Form a set for each string made up of its' characters
Intersect the sets
if size of intersection is > 0
    YES
else
    NO
    
    
Time complexity: O(|a| + |b|)    //We iterate through each input string
Space complexity: O(1)           //Our sets can be at most 2 x character set in size
*/

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int pairs = input.nextInt(); input.nextLine();
        
        tests:
        for(int t = 0; t < pairs; t++)
        {
            String a = input.nextLine();
            String b = input.nextLine();
            
            Set aLetterSet = new HashSet<>();
            Set bLetterSet = new HashSet<>();
            
            //Populate the sets
            for(int i = 0; i < a.length(); i++)
                aLetterSet.add(a.charAt(i));
            
            for(int i = 0; i < b.length(); i++)
                bLetterSet.add(b.charAt(i));
            
            //Perform the intersection of the two sets
            aLetterSet.retainAll(bLetterSet);
                
            if(aLetterSet.size() > 0)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

/*
        Problem: https://www.hackerrank.com/challenges/camelcase/problem
        C# Language Version: 6.0
        .Net Framework Version: 4.7
        Tool Version : Visual Studio Community 2017
        Thoughts :
        1. Keep a counter initialized at 1.
        2. We need to iterate the entire string chracter by character. Increment the counter by 1 everytime you encounter
        an upper case character in the string.
         
    We're using .NET's built-in method char.IsUpper to check whether the current character is an upper case character or
    not. This is an O(1) operation. We can also keep a dictionary (HashSet in C# is best fit as we need to store only keys)
    to check it in O(1) time.

        Time Complexity:  O(n)
        Space Complexity: O(1) //dynamically allocated variables are fixed for any length of input.
         
*/
using System;

class Solution
{
    private static int CamelCase()
    {
        var wordCount = 1;
        var nextChar = Console.Read();
        //This is a special condition for hacker rank execution environment
        //while running it in Visual Studio I was comparing it with 13 which is the ASCII code of enter key.
        while (nextChar != -1)
        {
            if (char.IsUpper((char)nextChar))
                wordCount++;
            nextChar = Console.Read();
        }
        return wordCount;
    }

    static void Main(string[] args)
    {
        var result = CamelCase();
        Console.WriteLine(result);
    }
}

/*
        Problem: https://www.hackerrank.com/challenges/funny-string/problem
        C# Language Version: 6.0
        .Net Framework Version: 4.7
        Tool Version : Visual Studio Community 2017
        Thoughts :
         - Here we have to iterate through the string and keep checking the difference between adjacent characters
         - The only trick is that we can check the difference both in forward and reverse direction at the same time and compare them in single go. So, we don't require two iteration.

        Time Complexity:  O(n) //we need to iterate the entire string once.
        Space Complexity: O(n) //we need to store entire string in memory to process both in forward and reverse direction at the same time.

*/
using System;
class Solution
{
    static void Main(string[] args)
    {
        var testCount = int.Parse(Console.ReadLine());
        for (var j = 0; j < testCount; j++)
        {
            var inputString = Console.ReadLine();
            var i = 0;
            for (; i < inputString.Length - 1; i++)
            {
                var diffForwardSeries = Math.Abs(inputString[i] - inputString[i + 1]);
                var diffBackwardSeries = Math.Abs(inputString[inputString.Length - 1 - i] - inputString[inputString.Length - 1 - i - 1]);
                if (diffForwardSeries != diffBackwardSeries)
                    break;
            }

            if (i == inputString.Length - 1)
                Console.WriteLine("Funny");
            else
                Console.WriteLine("Not Funny");
        }
    }
}

/*
 Problem: https://www.hackerrank.com/challenges/separate-the-numbers/problem
 C# Language Version: 6.0
 .Net Framework Version: 4.7
 Tool Version : Visual Studio Community 2017
 Thoughts :
 - Basic strategy is to split the input string into strings of width starting from 1,2,3 and so on. For each width check if each subsequent number is a successor of the previous number.
    e.g. 111213
    for this first we take width = 1 - Numbers thus found are 1,1,1,2,1,3. It fails at second split itself as the series should go like 1,2,3,4,....
    then we take width = 2 - Numbers thus found are 11,12,13 which is a proper increasing series. We print YES 11 in this case.
 - Handling for conditions given in the problem statement need to be done i.e. if a part contains leading zero then we need to reject the series.

 Gotchas: Following things require special handling
 - Handling for switch over of digit width. e.g. the string 91011. You start with width 1 but you've to suddenly jumnp to 2 as 9 is largest one digit number
 - Int32 is not sufficient. We need to use Int64 i.e. long
 - Special handling for boundary case of short strings e.g. 90190290

 Time Complexity:  O(n) //if we do a manual calculation then for each test case the loop runs are in the order of ~ O(3n)
                        //e.g. for n = 32 the loop runs 111 times
                               for n = 16  the loop runs 46 times and so on.
 Space Complexity: O(n) we save the input string in memory to process it.

*/
using System;

class Solution
{
    private static void SeparateNumbers(string inputText)
    {
        var numberWidth = 1;
        var found = false;
        while (numberWidth <= inputText.Length / 2)
        {
            var textPart = inputText.Substring(0, numberWidth);
            if (IsFirstCharZero(textPart))
            {
                numberWidth++;
                continue;
            }

            //handling for big numbers. Int64 is being used
            var previousNum = long.Parse(textPart);
            var firstNum = previousNum;
            var j = numberWidth;
            var widthChangeFactor = 0;

            //handling for width change over. e.g. in number 91011. the number series is 9,10,11. Width being extracted will change at 10 from 1 to 2 as 9 is largest one digit number
            if (IsItLargestNDigitNumber(textPart, numberWidth))
                widthChangeFactor++;

            //special handling: step block of for loop has been left empty. It is being done inside the for loop itself as it will vary depending upon condition.
            for (; j < inputText.Length;)
            {
                //handling for short strings. e.g. 90190290 will break in last triplet as it consists of 901,902,90
                if (j + numberWidth + widthChangeFactor > inputText.Length)
                    break;
                else
                    textPart = inputText.Substring(j, numberWidth + widthChangeFactor);

                if (IsFirstCharZero(textPart))
                    break;

                var currentNum = long.Parse(textPart);
                if (currentNum - previousNum != 1)
                    break;

                if (IsItLargestNDigitNumber(textPart, numberWidth + widthChangeFactor))
                {
                    widthChangeFactor++;
                    j += numberWidth;
                }
                else
                    j += numberWidth + widthChangeFactor;

                previousNum = currentNum;
            }

            if (j >= inputText.Length)
            {
                found = true;
                Console.WriteLine("YES {0}", firstNum);
                break;
            }

            numberWidth++;
        }
        if (!found)
            Console.WriteLine("NO");
    }

    static void Main(string[] args)
    {
        var queryCount = int.Parse(Console.ReadLine());
        for (var i = 0; i < queryCount; i++)
        {
            var inputText = Console.ReadLine();
            SeparateNumbers(inputText);
        }
    }

    private static bool IsFirstCharZero(string textPart)
    {
        return textPart[0] == '0' ? true : false;
    }

    private static bool IsItLargestNDigitNumber(string textPart, int numberWidth)
    {
        var isLargest = true;
		for (var i = 0; i < textPart.Length; i++)
		{
			if (textPart[i] != '9')
			{
				isLargest = false;
				break;
			}
		}
		return isLargest;
    }
}

/*
        Problem: https://www.hackerrank.com/challenges/caesar-cipher-1/problem
        C# Language Version: 6.0
        .Net Framework Version: 4.7
        Tool Version : Visual Studio Community 2017
        Thoughts :
            - we only have to process a character in the input text if it is an alphabet else print it directly on console.
            - produce the encoded character for each alphabet in input text by moving it in the alphabet series shift factor steps. 
            - A cautionary step is when the shift factor is > 26. If it is the case then get the shift factor by doing a modulus
                so that it becomes <= 26.

        Time Complexity:  O(n) //iteration of whole input text is required once. 
        Space Complexity: O(n) //we need to store the entire input text in memory to process it.

*/

using System;

class Solution
{
    static void Main(string[] args)
    {
        //No need to capture the size of string. We can use string's length property instead.
        Console.ReadLine();
        var inputText = Console.ReadLine();
        var shiftFactor = int.Parse(Console.ReadLine());
        if (shiftFactor > 26)
            shiftFactor = shiftFactor % 26;

        for (var i = 0; i < inputText.Length; i++)
        {
            var asciiCode = (int)inputText[i];
            if (asciiCode <= 122 && asciiCode > 96)
            {
                //small case alphabets
                if (asciiCode + shiftFactor <= 122)
                    //we're within range. Replace the encoded character
                    Console.Write((char)(((int)inputText[i]) + shiftFactor));
                else
                {
                    var offset = shiftFactor - (122 - asciiCode);
                    Console.Write((char)(96 + offset));
                }
            }
            else if (asciiCode <= 90 && asciiCode > 64)
            {
                //upper case alphabets
                if (asciiCode + shiftFactor <= 90)
                    //we're within range. Replace the encoded character
                    Console.Write((char)(((int)inputText[i]) + shiftFactor));
                else
                {
                    var offset = shiftFactor - (90 - asciiCode);
                    Console.Write((char)(64 + offset));
                }
            }
            else
                Console.Write(inputText[i]);

        }

    }
}

//Problem: https://www.hackerrank.com/challenges/absolute-permutation
//Java 8
/*
Find every perumation
Do a linear traversal of each perm checking if condition holds

we know that the only permutations we care about are ones that satistfy
absolute

for example
1 2 3 4 5 if k is 1 we know for every point we can only have a number 1 greater or 1 less

_ 1 2 3 4
2 3 4 5 _  

so any combinations of those values at those points

the underscore means we only have 1 choice at those points

Example:

10 2
_ _ _ _ _ _ _ _ _ _
3 _ _ _ _ _ _ _ _ 8
3 4 _ _ _ _ _ _ 7 8
3 4 1 _ _ _ _ 10 7 8
3 4 1 2 _ _ 9 10 7 8
3 4 1 2 _ _ 9 10 7 8 neither is available so failed

so it appears we can solve this in O(n) time by
working from outside in until we hit an impossibility

we want to loop n/2 times and each time check the left most
untouched index and the right most untouched index

we will also need to track what numbers we have already used

left most
check if index - k is in bounds if it is check if it is used if not use it
else if check if i + k is in bounds and is used if it is and is not use it
else not possible

right most
check if index plus k is in bounds if it is check it it is used if not use it
else check if i - k is in bounds and is used if it is and is not use it
else not possible

*/


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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        tests :
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int k = in.nextInt();
            int[] array = new int[n];
            Set used = new HashSet<>();
            
            //Iterate from left and right filling in the array according to the algorithm above
            for(int i = 0; i < n/2; i++)
            {
                int leftMost = i + 1;
                int rightMost = n - i;
                //Left most
                if(leftMost - k > 0 && !used.contains(leftMost-k))
                {
                    array[i] = leftMost-k;
                    used.add(leftMost-k);
                }
                else if(i + 1 + k <= n && !used.contains(leftMost+k))
                {
                    array[i] = leftMost+k;
                    used.add(leftMost+k);
                }
                else
                {
                    System.out.println("-1");
                    continue tests;
                }
                
                //Right most
                if(rightMost + k <= n && !used.contains(rightMost+k))
                {
                    array[n-1-i] = rightMost+k;
                    used.add(rightMost+k);                    
                }
                else if(rightMost - k > 0 && !used.contains(rightMost-k))
                {
                    array[n-1-i] = rightMost-k;
                    used.add(rightMost-k);
                }
                else
                {
                    System.out.println("-1");
                    continue tests;
                }
            }
            
            //if it is odd check to see if we have a number for the middle index
            if(n % 2 == 1)
            {
                int middle = (n/2) + 1;
                
                if(!used.contains(middle+k) || !used.contains(middle-k))
                {
                    if(!used.contains((n/2) +1 + k) && middle + k <= n)
                    {
                        array[(n/2)] = (n/2) + 1 + k;
                    }
                    else if(!used.contains((n/2) +1 - k) && middle - k > 0)
                    {
                        array[(n/2)] = (n/2) + 1 - k;
                    }
                    else
                    {
                        System.out.println("-1");
                        continue tests;    
                    }
                }
                else
                {
                    System.out.println("-1");
                    continue tests;
                }
            }
            
            //Print the results of a success
            for(int num : array)
            {
                System.out.print(num+" ");
            }
            System.out.println("");
            
        }
    }
}

//Problem: https://www.hackerrank.com/domains/algorithms/strings
//Java 8
/*
Initial Thoughts:
We could use a greedy approach and starting from the
left everytime we see a 010 replace the last 0 with a 1
and continue

Examples:
01010
01110 -> 1

0100101010
0110101010
0110111010
0110111011 -> 3


*/


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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        input.nextLine();
        String s = input.nextLine();
        int switches = 0;
        
        for(int i = 0; i < s.length()-2; i++)
        {
            if(s.charAt(i) == '0' && s.charAt(i+1) == '1' && s.charAt(i+2) == '0')
            {
                switches++;
                i += 2;
            }
        }
        System.out.println(switches);
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/equality-in-a-array/problem
    C# Language Version: 6.0
    .Net Framework Version: 4.7
    Tool Version : Visual Studio Community 2017
    Thoughts :
    1. Let all the numbers are stored in an array of length n.
    2. Create a hash map which will store the frequency of occurrence of every number appearing in the array.
    3. Iterate through the array using a loop:
    3.1 Let the current number be cn.
    3.2 If cn key is absent in hash map then add a new key-value pair into the hashmap with key = cn and value = 1.
    3.3 If cn key is present in hash map then increment the value of the dictionary entry by 1 where key = cn.
    3.4 Repeat steps 3.1 through 3.3 for all the elements of the array.
    4. Iterate through hash map and get the highest value present across all dictionary entries. Let it is be vMax.
    5. Print the difference of n and vMax on console.

    Time Complexity:  O(n) //actually it is O(2n) which becomes O(n) ignoring constants as per Big O notation.
    Space Complexity: O(n) //we are creating an additional hash map to store the frequency of numbers appearing in the input array.
                
*/
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        var hashMap = new Dictionary();
        //no need of storing the number count as I use length of the array property.
        ReadLine();
        var ar_temp = ReadLine().Split(' ');
        var numbers = Array.ConvertAll(ar_temp, int.Parse);

        for (int i = 0; i < numbers.Length; i++) //O(n)
        {
            if (hashMap.ContainsKey(numbers[i]))
                hashMap[numbers[i]]++;
            else
                hashMap.Add(numbers[i], 1);
        }

        var maxFrequency = hashMap.Values.Max(); //O(n)
        WriteLine(numbers.Length - maxFrequency);
    }
}

//Problem: https://www.hackerrank.com/challenges/camelcase
//Java 8
/*
If we handle the edge cases all we need to do is count the capital letters
*/


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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        
        if(s.isEmpty())
        {
            System.out.println("0");
            System.exit(0);
        }
        
        int words = 1;
        
        for(char letter : s.toCharArray())
        {
            if(letter < 91 && letter > 64 )
            {
                words++;
            }
        }
        System.out.println(words);
    }
}

//Problem: https://www.hackerrank.com/challenges/funny-string
//Java 8
/*
Simply use the same string but iterate from
beginning and end
*/

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        
        tests:
        for(int i = 0; i < T; i++)
        {
            String s = input.nextLine();
            for(int j = 1; j < (s.length()/2)+1; j++)
            {
                int left = Math.abs(s.charAt(j) - s.charAt(j-1));
                int right = Math.abs(s.charAt(s.length()-1-j) - s.charAt(s.length()-j));
                if( left != right)
                {
                    System.out.println("Not Funny");
                    continue tests;
                }
            }
            System.out.println("Funny");
        }
    }
}

/*
    Problem: https://www.hackerrank.com/challenges/extra-long-factorials/problem
    C# Language Version: 6.0
    .Net Framework Version: 4.7
    Tool Version : Visual Studio Community 2017
    Thoughts :
    1. Let the input number be n.
    2. Initialize a big integer number fact to 1.
    3. Start a for loop which runs from 1 to n
    3.1 Let current loop counter be c.
    3.2 set fact = fact * c.
    4. print fact.

    Time Complexity:  O(n)
    Space Complexity: O(1)
                
        */
using System;
using System.Numerics;

class Solution
{
    static void Main(String[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var factorial = BigInteger.One;
        for (int i = 1; i <= n; i++)
            factorial = factorial * i;

        Console.WriteLine(factorial);
    }
}

/*
         Problem: https://www.hackerrank.com/challenges/weighted-uniform-string/problem
         C# Language Version: 7.0
         .Net Framework Version: 4.7
         Tool Version : Visual Studio Community 2017
         Thoughts :
          - first create a hash set of sum of all possible uniform strings as we iterate through the string char by char
          - for each query, just check if the uniform sum being queried is present in the hash set or not (contributes O(1) as searching
            in hashset is contant operation)

         Time Complexity:  O(n) //one iteration is required to create set of weights of uniform stings
         Space Complexity: O(n) //space for has set of weights of uniform strings.
                
*/
using System;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        var currentChar = Console.Read();
        var previousChar = -1;
        var uniformStringSum = 0;
        var uniformWeightSet = new HashSet();
        //special handling for hacker rank execution environment
        //while running it on my own Windows based computer, I compare it with ascii code of carriage return ('\r') which is 13.
        while (currentChar != 10)
        {
            if (currentChar != previousChar)
                uniformStringSum = currentChar - 96;
            else
                uniformStringSum += currentChar - 96;

            uniformWeightSet.Add(uniformStringSum);
            previousChar = currentChar;
            currentChar = Console.Read();
        }
        //skipping '\n' character as new line character in windows is combination of \r and \n
        //Commented as it is not required for HackerRank execution environment.
        //Console.Read();
        var queryCount = int.Parse(Console.ReadLine());

        while (queryCount > 0)
        {
            var uniformWeight = int.Parse(Console.ReadLine());
            if (uniformWeightSet.Contains(uniformWeight))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}

//Problem: https://www.hackerrank.com/challenges/game-of-thrones
//Java 8
/*
A palindrome has the unique property that
the frequency of only one character can
be odd, so we can simply count the
frequency of characters and check if
there is more than 1 that is odd

Example:
aaabbbb

a: 3
b: 4
1 odd

cdefghmnopqrstuvw
c:1
d:1
e:1
f:1
g:1
h:1
m:1
n:1
o:1
p:1
q:1
r:1
s:1
t:1
u:1
v:1
w:1
18 odds

cdcdcdcdeeeef
c:4
d:4
e:4
f:1
1 odd

Time Complexity: O(n) //In the size of the string
Space Complexity: O(1) //We have a fixed number of different characters


*/


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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        
        Map letters = new HashMap<>();
        for(char c : s.toCharArray())
        {
            if(letters.containsKey(c))
                letters.put(c, letters.get(c) + 1);
            else
                letters.put(c, 1);
        }
        
        int odd = 0;
        int even = 0;
        for(Integer frequency : letters.values())
        {
            if(frequency % 2 == 1)
            {
                odd++;
                continue;
            }
                
            if(frequency % 2 == 0)
                even++;
        }
        
        if(odd > 1) 
            System.out.println("NO");
        else
            System.out.println("YES");
        
    }
}

//Problem: https://www.hackerrank.com/challenges/two-arrays
//Java 8
/*
Initial Thoughts: We can sort array A ascending and sort
                  array B descending, and then because they
                  are sorted we know that we are matching 
                  the highest possible from B with the lowest 
                  possible from A each time and if 1 of 
                  those fails then we know  it is not 
                  possible. The reason we know this is true 
                  is because they are inversely sorted, so 
                  we have already made the optimal decision 
                  at each stage in terms of the amount of 
                  absolute difference we have 'wasted/extra' 
                  thus leaving us with the tightest bounding
                  number to k for each index.
                  
Optimization: If we want to sort a int array in descending 
              order using the built in libraries, we have to
              change it to an Integer[] which takes up 16 bytes
              per element compared to 4. So instead what we can
              do is sort the int[] ascending and just traverse
              it in reverse when comparing to view the elements
              in descending order
                  
Time Complexity: O(n log(n)) //We must sort the input arrays
Space Complexity: O(n) //We must store the input arrays 

*/

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

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int Q = input.nextInt();
        //Store answer to each query
        StringBuilder output = new StringBuilder("");

        queries:
        for(int q = 0; q < Q; q++)
        {
            int n = input.nextInt();
            int k = input.nextInt();
            
            //Initialize Input
            int[] A = new int[n];
            int[] B= new int[n];
            for(int i = 0; i < n; i++)
                A[i] = input.nextInt();
            for(int i = 0; i < n; i++)
                B[i] = input.nextInt();
            
            Arrays.sort(A);//Sort ascending
            Arrays.sort(B);//Sort acending      
          
            for(int i = 0; i < n; i++)
            {
                //Traverse A ascending and B descending
                if(A[i]+B[B.length-1-i] < k) //Failed check
                {
                    output.append("NO\n");
                    continue queries;
                }
            }
            
            //Permutation exist
            output.append("YES\n");
            
        }
        //Print the answers to all queries
        System.out.println(output);
    }
}