Post It DNA Sequences

All submissions for this problem are available.
Adele is doing research in the field of computational biology this summer. She has a DNA sequence D, which is made of a smaller sequence S concatenated K times, i.e, D = S + S + S + ... (K times). Now, she needs to generate the sequence D using a smaller sequence, T of length M, of which she will make N copies. Doing this she'll get F = T + T + ... (N times).
Each DNA sequence can be represented as a string made up of lowercase latin characters.
After she gets F, she can extract out each individual component from the sequence(i.e, characters) and join them together(in some order) to make a new sequence which is equal to D.
Now, she wonders, given S, K and M what would be the minimum no. of copies N, of T, she will have to make in order to find T such that she can get D. She wants your help.
For given DNA sequence S, the number of it's copies, K and the length of the sequnce T as M, print the minimum number of copies, N, of T which you will have to create and also print the lexicographic smallest such sequence T. Print 1, if not possible.
Input
The input contains 2 lines:
 The first line contains the string S, the DNA sequence.
 The second line contains two space separated numbers integers K and M, denoting the number of copies of S in D and the length of the sequence T.
Output
 First line containing an integer N and string T, denoting the minimum number of copies.
 Second line containing the string T.
 Print 1 in one line if it's not possible to find such N and T.
Subtask #1 (20 points)
 1 ≤ S ≤ 100
 1 ≤ K ≤ 10
 1 ≤ M ≤ 1000
Subtask #2 (80 points)
 1 ≤ S ≤ 10^{4}
 1 ≤ K ≤ 10^{14}
 1 ≤ M ≤ 10^{5}
Sample
Input 1: mama 2 4 Output 1: 2 aamm Input 2: aab 2 2 Output 2: 4 ab Input 3: tomato 2 2 Output 3: 1
Explanation
Sample 1: S = mama, K = 2. D = mamamama. For T = aamm and N = 2, we can get F = aammaamm.
The characters of F can be used to make a copy of T here.
Sample 2: S = aab, K = 2. D = aabaab. For T = ab and N = 4, we can get F = abababab.
The characters of F can be used to make a copy of T here.
Author:  lonerunner 
Tags  lonerunner 
Date Added:  26052016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions