K-Length Lexicographic Permutations

Given a string S and an integer k, print all the k-length permutations of S in lexicographically sorted order.

For example, for S = "HACK" and k = 2, the expected output is:

AC
AH
AK
CA
CH
CK
HA
HC
HK
KA
KC
KH

The solution should read from standard input and write the result to standard output.

Note: Use the formula for the number of k-length permutations as \(P(n,k)=\frac{n!}{(n-k)!}\) if needed.

inputFormat

The input consists of a single line containing the string S and the integer k separated by a space.

Example: HACK 2

outputFormat

Output all distinct k-length permutations of S in lexicographic order, each on a new line.

## sample

HACK 2

AC
AH
AK
CA
CH
CK
HA
HC
HK
KA
KC
KH

</p>