F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Square Distance

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 721    Accepted Submission(s): 248


Problem Description
A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not.

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Peter has a string $s=s_{1}s_{2}...s_{n}$ of even length. He wants to find a lexicographically smallest square string $t=t_{1}t_{2}...t_{n}$ that the hamming distance between $s$ and $t$ is exact $m$. In addition, both $s$ and $t$ should consist only of lowercase English letters.
 

Input
There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first contains two integers $n$ and $m$ $(1 \le n \le 1000, 0 \le m \le n, n \text{ is even})$ -- the length of the string and the hamming distance. The second line contains the string $s$.
 

Output
For each test case, if there is no such square string, output "Impossible" (without the quotes). Otherwise, output the lexicographically smallest square string.
 

Sample Input
3 4 1 abcd 4 2 abcd 4 2 abab
 

Sample Output
Impossible abab aaaa
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 23:42:33, Gzip enabled