ZZPERM - Zig-Zag Permutation

no tags 

In the following we will deal with nonempty words consists only of lower case letters 'a', 'b' ... 'j' and we will use the natural 'a' < 'b' < ... < 'j' ordering. Your task is to write a program that generates almost all zig-zag words (zig-zag permutations) from a given collection of letters.

We say that a word W = W(1)W(2)...W(n) is zig-zag iff n = 1 or W(i) > W(i+1) and W(j) < W(j+1) for all odd 0 < i < n and for all even 0 < j < n or W(i) > W(i+1) and W(j) < W(j+1) for all even 0 < i < n and for all odd 0 < j < n.

For example: "aabcc" is not zig-zag, "acacb" is zig-zag, "cac" is zig-zag, "abababc" is not zig-zag.

If you imagine all possible zig-zag permutations of a word in increasing lexicographic order, you can assign a serial number (rank) to each one. For example: the word "aabcc" generates the sequence:

  1. "acacb",
  2. "acbca",
  3. "bacac",
  4. "bcaca",
  5. "cabac",
  6. "cacab".

Input

The input file consists several test cases. Each case contains a word (W) not longer than 64 letters and one positive number (D). The letters of each word are in increasing order. Input terminated by EOF.

Output

For each case in the input file, the output file must contain all of the zig-zag permutations of W whose zig-zag serial is divisible by D, in increasing lexicographic order - one word per line. In the next line you have to print the total number of zig-zag permutations of W. There is no case that produces more than 365 lines of output. Print an empty line after each case.

Example

Input:
j 1
abc 2
aaabc 1
aaabb 2
aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbcccdd 123456

Output:
j
1

bac
cab
4

abaca
acaba
2

1

babacbcabacabadabababababababababadab
213216


hide comments
Min_25: 2014-05-06 12:39:32

Some test cases have extra spaces at the end of the line.

Last edit: 2014-05-06 14:36:17
Voyage: 2012-05-23 00:21:50

Is BigInteger required for calculations? Plus, what's the limit of D?
-> no need of BigInt
-> the only role of D is to diminish the output, it fits to int.

Last edit: 2012-05-28 09:35:14

Added by:czylabsonasa
Date:2005-05-05
Time limit:1.516s
Source limit:12345B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Folklore