404518: GYM101522 J Juicy Candies

Alex enjoys eating snacks, in particular candies. Recently he discovered a brand of berry-themed juicy candies, with three flavors: blueberry (B), raspberry (R), and strawberry (S). For brevity, we would, for example, use the term B-candy to refer to blueberry-flavored candy.

Alex has B B-candies, R R-candies, and S S-candies. He now wants to form sequences of candies, such that:

• All Alex's candies are used
• Any two adjacent candies have different flavors

For each candy sequence, there is a string of length (B + R + S) corresponding to it. If the i-th candy in the sequence is strawberry-flavored, for example, then the i-th character of the string would be S. Similarly for blueberry- and raspberry-flavored candies.

Before enjoying the candies, Alex would like to solve the following challenge: among all strings which corresponds to a candy sequence, what is the K-th lexicographically smallest string?

For two strings s[1...L] and t[1...L], s is said to be lexicographically smaller than t, if there exists an index i (1 ≤ i ≤ L), such that s[j] = t[j] for 1 ≤ j < i, and s[i] < t[i]. We naturally use the character relation B  <  R  <  S.

The first and only line of input consists of four space-separated integers B, R, S, and K.

For all test cases, 1 ≤ B, R, S ≤ 200, 1 ≤ K ≤ 10¹⁸.

If the total number of strings is less than K, output None.

Otherwise, output the K-th lexicographically smallest string that corresponds to a candy sequence with B B-candies, R R-candies, and S S-candies.

1 1 1 1

BRS

3 1 1 1

BRBSB

1 4 1 1

None

2 3 4 40

SBRSRSBSR

7 7 7 777

BRBRBRSRSBSRSBRSBSBSR

7 7 7 7777

BRBRSRBSRSRBRBSRSBSBS

7 7 7 177777

RSBRBSRSRBSRBRSBSBSBR