Goats and Sheep Grazing Game

Two ancient foes, goats and sheep, have long contested over grazing fields. In order to settle the disputes peacefully, the leaders of both teams agree to decide the outcome by a game. The game is played by a total of N animals arranged in a circle (the order is pre‐determined by the leaders). The play proceeds cyclically: after animal i (1 ≤ i ≤ N-1) the next move is made by animal i+1, and after animal N the turn goes back to animal 1.

The rules of the game are as follows:

• The animal that starts the game may say any positive integer j from the interval \([1, K]\) as long as j \lt M.
• If the previous animal said the number j, then the next animal must say a number in the interval \([j+1, j+K]\), subject to the condition that the number is strictly less than M.
• If a player is forced to say M (i.e. no safe move exists), then that animal’s team immediately loses the game.

Assume that both teams play optimally. For each starting position i (1 ≤ i ≤ N), determine the winning team (either goats or sheep) for the field if the game is initiated by the i^th animal.

Note: The game is essentially a misère subtraction game. In state with current number j and turn belonging to animal p, the animal may choose any number \(x\) with \[ j+1 \le x \le \min(j+K, M-1), \] provided such a move exists. If no such move exists, the animal must say \(M\) and loses.

inputFormat

The input consists of two lines. The first line contains three integers N, K, and M \((1 \le N, K, M \le \text{constraints})\), where N is the number of animals, K is the maximum increment allowed, and M is the losing number. The second line contains a string of length N consisting of characters 'G' and 'S'. 'G' indicates that the corresponding animal belongs to the goats team, and 'S' indicates the sheep team.

The game is played separately for each starting animal. That is, for each i (1 ≤ i ≤ N), consider the game with initial state (no number has been said yet) and with animal i starting.

outputFormat

Output a single line with N space‐separated words. For each starting position i (in order from 1 to N), print the name of the team (goats or sheep) that will win the game if the i^th animal starts, assuming optimal play by both teams.

sample

3 2 10
GSG

sheep goats sheep