Piegirl is buying stickers for a project. Stickers come on sheets, and each sheet of stickers contains exactly n stickers. Each sticker has exactly one character printed on it, so a sheet of stickers can be described by a string of length n. Piegirl wants to create a string s using stickers. She may buy as many sheets of stickers as she wants, and may specify any string of length n for the sheets, but all the sheets must be identical, so the string is the same for all sheets. Once she attains the sheets of stickers, she will take some of the stickers from the sheets and arrange (in any order) them to form s. Determine the minimum number of sheets she has to buy, and provide a string describing a possible sheet of stickers she should buy.


-----Input-----

The first line contains string s (1 ≤ |s| ≤ 1000), consisting of lowercase English characters only. The second line contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

On the first line, print the minimum number of sheets Piegirl has to buy. On the second line, print a string consisting of n lower case English characters. This string should describe a sheet of stickers that Piegirl can buy in order to minimize the number of sheets. If Piegirl cannot possibly form the string s, print instead a single line with the number -1.


-----Examples-----
Input
banana
4

Output
2
baan

Input
banana
3

Output
3
nab

Input
banana
2

Output
-1



-----Note-----

In the second example, Piegirl can order 3 sheets of stickers with the characters "nab". She can take characters "nab" from the first sheet, "na" from the second, and "a" from the third, and arrange them to from "banana".

Difficulty: interview

Starter code:

Solutions:
from collections import Counter

s = input()
n = int(input())

d = Counter()

for c in s:
    d[c] += 1

if len(d) > n:
    print(-1)
else:
    left = 0
    right = 10**10
    s = ""
    lastok = ("", 0)
    while left + 1 < right:
        mid = (left + right) // 2
        s = ""
        for (c, cnt) in list(d.items()):
            cntnow = (cnt - 1) // mid + 1
            s += c * cntnow
        if len(s) < n:
            s += 'a' * (n - len(s))
        if len(s) == n:
            lastok = (s, mid)
            right = mid
        else:
            left = mid
    print(lastok[1])
    print(lastok[0])


s = input()
n = int(input())
freq = [0 for i in range(0, 300)]
raport = [0 for i in range(0, 300)]
differentLetters = 0
tickets = 0
sol = ''

for c in s: freq[ord(c)] += 1
for i in freq:
    if i > 0: differentLetters += 1

if differentLetters > n:
    print('-1')
    return

for i in 'abcdefghijklmnopqrstuvwxyz':
    if freq[ord(i)] == 0: continue
    sol += i
    freq[ord(i)] -= 1
    raport[ord(i)] = freq[ord(i)]


for i in range(differentLetters, n):
    #pun litera cu cea mai mare frecventa

    maxRaport = raport[ord('z')]
    chosenLetter = 'z'
    for j in 'abcdefghijklmnopqrstuvwxyz':
        if raport[ord(j)] > maxRaport:
            maxRaport = raport[ord(j)]
            chosenLetter = j


    sol += chosenLetter
    raport[ord(chosenLetter)] = freq[ord(chosenLetter)] / sol.count(chosenLetter)
    

for i in sol:
    a = s.count(i)
    b = sol.count(i)

    if a%b == 0: tickets = max(tickets, int(a//b))
    else: tickets = max(tickets, int(a//b) + 1)

print(tickets)
print(sol)
        




import math
from fractions import Decimal
S=input()

N=int(input())
Srep={}
ansrep={}
for item in "abcdefghijklmnopqrstuvwxyz":
    Srep[item]=0
    ansrep[item]=0

for item in S:
    Srep[item]+=1
    ansrep[item]+=1

Q=list(set(S))

if(len(Q)>N):
    print(-1)

else:
    n=len(Q)
    ans=list(S)
    num=1
    req=1
    n=len(ans)
    while(len(ans)>N):
        n=len(ans)
        minn=req+1005
        removal=ans[0]
        k=True
        for item in ans:
            if(ansrep[item]==1):
                continue
            if(math.ceil(Srep[item]/(ansrep[item]-1))>req):
                if(minn>math.ceil(Srep[item]/(ansrep[item]-1))):
                    minn=math.ceil(Srep[item]/(ansrep[item]-1))
                    removal=str(item)
                continue
            else:
                ansrep[item]-=1
                ans.remove(item)
                k=False
                break
        if(k):
            ansrep[removal]-=1
            req=math.ceil(Srep[removal]/ansrep[removal])
            ans.remove(removal)
    g=""
    if(len(ans)<N):
        g=S[0]*(N-len(ans))
    print(req)
    for item in ans:
        print(item,end="")
    print(g)
        
        
        
        
    
    
    




s = input()
n = int(input())

symb_cnt = {}
for c in s:
	symb_cnt[c] = symb_cnt[c] + 1 if c in symb_cnt else 1
for cnt in range(1, len(s) + 1):
	s1 = ""
	for c in symb_cnt:
		s1 += c * ((symb_cnt[c] + cnt - 1) // cnt)
	if len(s1) <= n:
		for i in range(n - len(s1)):
			s1 += 'a'
		print(cnt)
		print(s1)
		return
print(-1)


s = input()
n = int(input())

d = {}
for c in s:
    if c not in d: d[c] = 0
    d[c] += 1
    
dcl = list(d.values())

found = False
for x in range(1,1001):
    if sum([(dc-1)//x+1 for dc in dcl]) <= n:
        found = True
        print(x)
        s = ''.join([key*((d[key]-1)//x+1) for key in sorted(d.keys())])
        s += (n-len(s))*'a'
        print(s)
        break
if not found:
    print(-1)


from math import ceil
p = {i: 0 for i in 'abcdefghijklmnopqrstuvwxyz'}
t = input()
for i in t: p[i] += 1
p = {i: p[i] for i in p if p[i] > 0}
n = int(input())
if len(p) > n: print(-1)
elif len(t) > n:
    r = [[p[i], p[i], 1, i] for i in p]
    for i in range(n - len(p)):
        j = max(r)
        j[2] += 1
        j[0] = j[1] / j[2]
    print(ceil(max(r)[0]))
    print(''.join(j[3] * j[2] for j in r))     
else: print('1\n' + t * (n // len(t)) + t[: n % len(t)])  

from collections import Counter
from heapq import heappushpop


def main():
    cnt, n = Counter(input()), int(input())
    if n < len(cnt):
        print(-1)
        return
    h = list((1 / v, 1, c) for c, v in cnt.most_common())
    res = list(cnt.keys())
    _, v, c = h.pop(0)
    for _ in range(n - len(cnt)):
        res.append(c)
        v += 1
        _, v, c = heappushpop(h, (v / cnt[c], v, c))
    print((cnt[c] + v - 1) // v)
    print(''.join(res))


def __starting_point():
    main()

__starting_point()

s = input()

n = int(input())



d = {}

for c in s:

    if c not in d: d[c] = 0

    d[c] += 1

    

dcl = list(d.values())



found = False

for x in range(1,1001):

    if sum([(dc-1)//x+1 for dc in dcl]) <= n:

        found = True

        print(x)

        s = ''.join([key*((d[key]-1)//x+1) for key in sorted(d.keys())])

        s += (n-len(s))*'a'

        print(s)

        break

if not found:

    print(-1)



import sys
import math
sys.setrecursionlimit(100000)

#sys.stdin = open("INP.txt", 'r')
# sys.stdout = open("OUT.txt", 'w')


def main():
    s = input()
    n = int(input())
    M = dict()
    for char in s:
        if char in M:
            M[char] += 1
        else:
            M[char] = 1
    if n < len(M):
        print(-1)
    else:
        l = 1
        r = len(s)
        while l != r:
            k = l+(r-l)//2
            smallest_n = 0
            for it in list(M.values()):
                tmp = math.ceil(it/k)
                smallest_n += tmp
            if smallest_n <= n:
                r = k
            else:
                l = k+1
        sticker = ''
        for char, occ in zip(list(M.keys()), list(M.values())):
            sticker += (char*math.ceil(occ/l))

        if len(sticker) < n:
            sticker += (n-len(sticker))*list(M.keys())[0]
        print("{}\n{}".format(l, sticker))


main()


s = input()
n = int(input())
cnt = {}
for c in s:
    if cnt.get(c) == None:
        cnt[c] = 1
    else:
        cnt[c] += 1

if (n < len(cnt)):
    print(-1)
else:
    ansNum = 0;
    while(True):
        ansNum+=1
        l = 0;
        char = []
        for c, v in cnt.items():
            need = (v + ansNum -1)//ansNum
            l+= need
            char.append((c, need))
        if (l > n):
            continue
        print(ansNum)
        ans = "".join([str(c[0])*c[1] for c in char])
        ans = ans + 'a'*(n - len(ans))
        print(ans)
        break

s = input()
n = int(input())
cnt = {}
for c in s:
    if cnt.get(c) == None:
        cnt[c] = 1
    else:
        cnt[c] += 1
 
if (n < len(cnt)):
    print(-1)
else:
    ansNum = 0;
    while(True):
        ansNum+=1
        l = 0;
        char = []
        for c, v in cnt.items():
            need = (v + ansNum -1)//ansNum
            l+= need
            char.append((c, need))
        if (l > n):
            continue
        
        print(ansNum)
        ans = "".join([str(c[0])*c[1] for c in char])
        ans = ans + 'a'*(n - len(ans))
        print(ans)
        break

s = input()
n = int(input())
cnt = {}
for c in s:
    if cnt.get(c) == None:
        cnt[c] = 1
    else:
        cnt[c] += 1
 
if (n < len(cnt)):
    print(-1)
else:
    ansNum = 0;
    while(True):
        ansNum+=1
        l = 0;
        char = []
        for c, v in cnt.items():
            need = (v + ansNum -1)//ansNum
            l+= need
            char.append((c, need))
        if (l > n):
            continue
        
        
        print(ansNum)
        ans = "".join([str(c[0])*c[1] for c in char])
        ans = ans + 'a'*(n - len(ans))
        print(ans)
        break

import math
from sys import stdin
from math import ceil

def __starting_point():
    s = input()
    n = int(input())
    dictionary = {}

    for i in s:
        if i in dictionary:
            dictionary[i] = dictionary[i] + 1
        else:
            dictionary[i] = 1

    if len(dictionary) > n:
        print(-1)
    else:
        if len(s) < n:
            print(1)
            newS = s
        else:
            lengthS = len(s) // n
            newLength = len(s)
            while lengthS < newLength:
                mid = (lengthS + newLength) // 2
                total = 0
                for i in dictionary:
                    total = total + ceil(dictionary[i] / mid)
                if total > n:
                    lengthS = mid + 1
                else:
                    newLength = mid
            print(lengthS)
            newS = ''
            for i in dictionary:
                for j in range(ceil(dictionary[i] / lengthS)):
                    newS = newS + i
        for i in range(n - len(newS)):
            newS = newS + s[0]
        print(newS)

__starting_point()

def check(mid):
    ans = []
    res = 0
    for c, count in d:
        tmp = count // mid
        if (count % mid != 0):
            tmp += 1
        ans.append((c, tmp))
        res += tmp
    return res <= n, ans
        

a = input()
n = int(input())
d = dict()
t = 0
for i in a:
    if i not in d:
        d[i] = 1
        t += 1
    else: d[i] += 1
ans = []
res = ""
for i in d:
    ans.append(i)
    res = i
if n >= len(a):
    print(1)
    print(a, end = '')
    n -= len(a)
    for u in range(n):
        print(res, end ='')
else:
    d = (sorted(d.items(), key = lambda d:(d[1], d[0])))
    l = 1
    r = len(a)
    res = []
    count_res = 0
    while (l <= r):
        mid = (l + r) // 2
        flag, tmp = check(mid)
        if (flag):
            r = mid - 1
            count_res = mid
            res = tmp
        else:
            l = mid + 1
        #print(l, r, tmp)
    if (len(res) == 0):
        print(-1)
    else:
        ttt = 0
        print(count_res)
        for c, sl in res:
            for j in range(sl):
                print(c, end = '')
                ttt += 1
        n -= ttt
        for i in range(n):
            print(a[0], end = '')

 
    



s = input()
n = int(input())

from collections import Counter
c = Counter(s)
out = Counter()
contrib = Counter()

for letter in c:
    out[letter] = 1
    contrib[letter] = c[letter]

sum_vals = sum(out.values())
from math import ceil
from fractions import Fraction

if sum_vals > n:
    print(-1)
else:
    while sum_vals < n:
        el, _ = contrib.most_common(1)[0]
        out[el] += 1
        sum_vals += 1
        contrib[el] = ceil(Fraction(c[el], out[el]))

    print(max(contrib.values()))
    print(''.join(out.elements()))
        
    
    


s = input()
n = int(input())
d = {}
r = 0
for a in s:
    d.setdefault(a, 0)
    d[a] += 1
    if(d[a] > r):
        r = d[a]
if (len(d) > n):
    print(-1)
else:
    l = 0
    while r - l > 1:
        k = (l + r) // 2
        cur = 0
        for x in d.values():
            cur += (x+k-1) // k
        if cur > n:
            l = k
        else:
            r = k
    print(r)
    s = ''
    for a in d.keys():
        s += a * ((d[a] + r - 1) // r)
    l=len(s)
    s += 'a' * (n-len(s))
    print(s)