Maximizing Draw Luck in Card Grouping

In this problem, you are given a sequence of cards each having a fixed luck value. The i-th card has luck value \(a_i\). There are two types of draws:

• Single draw: When you draw a card individually, you add that card's luck value to your total.
• Consecutive draw: When you perform a consecutive draw (of exactly \(c\) cards), you add only the luck value of the first card of the group to your total (the other \(c-1\) cards do not contribute).

YYF wants to draw exactly \(n\) consecutive draws (each drawing exactly \(c\) cards) and \(m\) single draws, for a total of \(c \times n + m\) cards drawn in the fixed order given. However, to avoid exhaustion, he does not want to perform more than \(d\) single draws in a row (he is allowed to do exactly \(d\) singles consecutively).

Your task is to determine the maximum possible sum of luck values by choosing which cards to draw as part of a consecutive draw versus as a single draw, while using every card exactly once (and preserving the order). In addition, you must output one corresponding valid draw plan. In the plan, for every card you should output a character according to the following rules:

• If the card is drawn as a single draw, output S.
• If the card is the first card of a consecutive group, output G.
• If the card is drawn as part of a consecutive group but is not the first card, output g.

The plan must satisfy:

• There are exactly \(n\) consecutive groups (each consisting of \(c\) consecutive cards, with the first marked as G and the remaining \(c-1\) marked as g).
• There are exactly \(m\) cards drawn as singles (S).
• In the final string, there must be no more than \(d\) consecutive S characters.

The input begins with four integers \(n, m, c, d\) and is followed by \(c\times n + m\) integers representing \(a_1, a_2, \dots, a_{c\times n+m}\) (the luck values in order). The output should have two lines:

1. The maximum total luck value that can be achieved.
2. A string of length \(c\times n+m\) representing a valid draw plan that achieves this maximum.

Note: If there are multiple valid solutions, you may output any one of them.

inputFormat

The first line contains four integers \(n, m, c, d\) separated by spaces.

The second line contains \(c\times n + m\) integers \(a_1, a_2, \dots, a_{c\times n+m}\) separated by spaces, representing the luck values of the cards in order.

outputFormat

Output two lines:

1. A single integer: the maximum total luck value achievable.
2. A string of length \(c\times n + m\) consisting of the characters S, G, and g representing a valid draw plan as described above.

sample

1 2 2 1
5 1 3 2

8
SGSg

</p>