AtCoder Beginner Contest 055

D - Menagerie


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 500

問題文

すぬけくんは動物が好きなので動物園を作りました。

この動物園では 1,2,3, ..., N の番号を割り振られた N 匹の動物が円環状に並べられています。 i (2≦i≦N-1) 番の動物は i-1 番の動物と i+1 番の動物と隣り合っています。また、1 番の動物は N 番の動物と 2 番の動物と隣り合っており、N 番の動物は N-1 番の動物と 1 番の動物と隣り合っています。

動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の 2 種類の動物がいます。

すぬけくんには羊と狼の区別がつかないので、それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、i 番目の動物は s_i と答えました。s_io ならば両隣の動物が同じ種類であると、x ならば異なる種類であると i 番の動物が言ったことを示します。

より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき o と答え、そうでないとき x と答えます。 狼は両隣の動物がどちらも羊あるいはどちらも狼のとき x と答え、そうでないとき o と答えます。

これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば -1 を出力しなさい。

制約

  • 3 ≦ N ≦ 10^{5}
  • sox のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
s

出力

s と矛盾しないような各動物の種類の割当てが存在しないならば -1 を出力してください。 存在するならば以下の形式で文字列 t を出力してください。 t で示される割り当てが s と矛盾しないならば正解となります。

  • t は長さ NSW のみからなる文字列
  • t_iS ならば i 番の動物が羊であることを、W ならば狼であることを示す

入力例 1

6
ooxoox

出力例 1

SSSWWS

例えば 1,2,3,4,5,6 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。

両隣が同じ種類の動物のとき羊は o と発言し、狼は x と発言すること、 両隣が異なる種類の動物のとき羊は x と発言し、狼は o と発言することに注意してください。

b34c052fc21c42d2def9b98d6dccd05c.png

入力例 2

3
oox

出力例 2

-1

存在しない場合は -1 を出力してください。


入力例 3

10
oxooxoxoox

出力例 3

SSWWSSSWWS

Score : 500 points

Problem Statement

Snuke, who loves animals, built a zoo.

There are N animals in this zoo. They are conveniently numbered 1 through N, and arranged in a circle. The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1. Also, the animal numbered 1 is adjacent to the animals numbered 2 and N, and the animal numbered N is adjacent to the animals numbered N-1 and 1.

There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.

Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i. Here, if s_i is o, the animal said that the two neighboring animals are of the same species, and if s_i is x, the animal said that the two neighboring animals are of different species.

More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise. Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.

Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1.

Constraints

  • 3 ≤ N ≤ 10^{5}
  • s is a string of length N consisting of o and x.

Input

The input is given from Standard Input in the following format:

N
s

Output

If there does not exist an valid assignment that is consistent with s, print -1. Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s.

  • t is a string of length N consisting of S and W.
  • If t_i is S, it indicates that the animal numbered i is a sheep. If t_i is W, it indicates that the animal numbered i is a wolf.

Sample Input 1

6
ooxoox

Sample Output 1

SSSWWS

For example, if the animals numbered 1, 2, 3, 4, 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.

Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x. If the neiboring animals are of different species, a sheep answers x and a wolf answers o.

b34c052fc21c42d2def9b98d6dccd05c.png

Sample Input 2

3
oox

Sample Output 2

-1

Print -1 if there is no valid assignment of species.


Sample Input 3

10
oxooxoxoox

Sample Output 3

SSWWSSSWWS

Submit提出する