{"raw_statement":[{"iden":"statement","content":"Dani and Mike are two kids ,They are playing games all day and when they don't find a game to play they invent a game . There is about an hour to arrive to school, because they love playing with strings Dani invented a game , Given a string and the winner is the first who form a palindrome string using all letters of this string according to the following sample rules :  1- player can rearrange letters to form a string .  2- the formed string must be palindrome and use all letters of the given string.  3- if there is more than one string chose the lexicographically smallest string .  EX: string is \"abacb\" player can form :   \"abcba\" and \"bacab\" ,but \"abcba\" is the lexicographically smallest.   Mike asked you to write a Program to compute the palindrome string so he can beat Dani.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  1000). Every test case on one line contain one string ,the length of the string will not exceed 1000 lower case English letter.\n\nFor each test case print a single line containing the lexicographically smallest palindrome string according to the rules above. If there is no such string print \"impossible\"\n\nPalindrome string is a string which reads the same backward or forward.\n\nLexicographic order means that the strings are arranged in the way as they appear in a dictionary. \n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  1000). Every test case on one line contain one string ,the length of the string will not exceed 1000 lower case English letter."},{"iden":"output","content":"For each test case print a single line containing the lexicographically smallest palindrome string according to the rules above. If there is no such string print \"impossible\""},{"iden":"examples","content":"Input4abacbacmicpcaabaabbsbttxsOutputabcbaimpossibleaabbaabstxtsb"},{"iden":"note","content":"Palindrome string is a string which reads the same backward or forward.Lexicographic order means that the strings are arranged in the way as they appear in a dictionary. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k < n \\leq 10^5 $.  \n- Let $ X = (x_0, x_1, \\dots, x_{n-1}) $ be a strictly increasing sequence of integers with $ 0 \\leq x_i \\leq 10^9 $, representing hole positions.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown bound} $ (implied by input format).  \n2. For each test case: $ 1 \\leq k < n \\leq 100000 $, and $ x_0 < x_1 < \\dots < x_{n-1} $.  \n\n**Objective**  \nFind the minimum value $ \\ell \\in \\mathbb{R}^+ $ such that there exists a set of $ k $ intervals (strips), each of length at most $ \\ell $, that collectively cover all $ n $ holes.  \n\nEquivalently:  \nMinimize $ \\ell $ such that $ X $ can be covered by $ k $ intervals $ [a_j, a_j + \\ell] $, $ j = 1, \\dots, k $, where each $ x_i \\in \\bigcup_{j=1}^k [a_j, a_j + \\ell] $.","simple_statement":"Youssef has n holes on a 1D roof at given positions (sorted). He can buy exactly k strips to cover all holes. Each strip covers a continuous range. He pays based on the longest strip used. Find the minimum possible length of the longest strip needed to cover all holes with exactly k strips.","has_page_source":false}