Periodic Palindrome Construction
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef recently learned about concept of periodicity of strings. A string is said to have a period P, if P divides N and for each i, the i-th of character of the string is same as i-Pth character (provided it exists), e.g. "abab" has a period P = 2, It also has a period of P = 4, but it doesn't have a period of 1 or 3.
Chef wants to construct a string of length N that is a palindrome and has a period P. It's guaranteed that N is divisible by P. This string can only contain character 'a' or 'b'. Chef doesn't like the strings that contain all a's or all b's.
Given the values of N, P, can you construct one such palindromic string that Chef likes? If it's impossible to do so, output "impossible" (without quotes)
The first line of the input contains an integer T denoting the number of test cases.
The only line of each test case contains two space separated integers N, P.
For each test case, output a single line containing the answer of the problem, i.e. the valid string if it exists otherwise "impossible" (without quotes). If there are more than possible answers, you can output any.
- 1 ≤ T ≤ 20
- 1 ≤ P, N ≤ 105
- Subtask #1 (25 points) : P = N
- Subtask #2 (75 points) : No additional constraints
Input 5 3 1 2 2 3 3 4 4 6 3 Output impossible impossible aba abba abaaba
Example 1: The only strings possible are either aaa or bbb, which Chef doesn't like. So, the answer is impossible.
Example 2: There are four possible strings, aa, ab, ba, bb. Only aa and bb are palindromic, but Chef doesn't like these strings. Hence, the answer is impossible.
Example 4: The string abba is a palindrome and has a period of 4.
Example 5: The string abaaba is a palindrome and has a period of length 3.
|Tags||admin2, nov17, simple|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions