Problem Statement

String S is a SP-string if some non-empty prefix of S is also a suffix of S. The prefix (the suffix) can't be the whole string. For example, strings "AA" and "ABCABC" are SP-strings, but strings "AB", "ABCB" are not. String S is a N-string if it satisfies the following conditions:

• It contains only letters from the first N letters of the alphabet.
• If we append any single letter from the first N letters of the alphabet to S, the resulting string will be a SP-string.

For example, "ABBA" is a 2-string because it contains only the first 2 letters of the alphabet, and both "ABBAA" and "ABBAB" are SP-strings. There is an infinite number of N-strings, but in this problem we will consider only N-strings of minimal length (that is, N-strings of length L such that no N-string of length less than L exists).

You will be given two ints - N and K. Build all the shortest possible N-strings and sort them alphabetically. Return the substring of the K-th string from index leftIdx (inclusive) to index rightIdx (exclusive). Return "" if the K-th string contains less than rightIdx characters or the K-th string doesn't exist.

Definition

Class:              InterestingStrings
Method:             findSubstring
Parameters:         int, int, int, int
Returns:            string
Method signature:   string findSubstring(int N, int K, int leftIdx, int rightIdx)
(be sure your method is public)

Notes

• K, leftIdx, rightIdx are 0-based.
• All letters in this problem are uppercase.

Constraints

• N will be between 1 and 26, inclusive.
• K will be between 0 and 1000000000, inclusive.
• leftIdx will be between 0 and 1000000000, inclusive.
• rightIdx will be between (leftIdx + 1) and (leftIdx + 1000), inclusive.

Examples

0)

1
0
3
Returns: "BAB"

1)

1
0
0
1
Returns: "A"

2)

2
0
1
3
Returns: "BA"

3)

4
0
7
9
Returns: "DA"

4)

3
1
0
7
Returns: "ACABACA"

5)

5
1000
99999999
100000000
Returns: ""

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.