AT_arc069_b [ABC055D] Menagerie

[problemUrl]: https://atcoder.jp/contests/abc055/tasks/arc069_b すぬけくんは動物が好きなので動物園を作りました。 この動物園では $ 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_i $ が `o` ならば両隣の動物が同じ種類であると、`x` ならば異なる種類であると $ i $ 番の動物が言ったことを示します。 より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき `o` と答え、そうでないとき `x` と答えます。 狼は両隣の動物がどちらも羊あるいはどちらも狼のとき `x` と答え、そうでないとき `o` と答えます。 これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば `-1` を出力しなさい。

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

$ s $ と矛盾しないような各動物の種類の割当てが存在しないならば `-1` を出力してください。 存在するならば以下の形式で文字列 $ t $ を出力してください。 $ t $ で示される割り当てが $ s $ と矛盾しないならば正解となります。 - $ t $ は長さ $ N $ で `S` と `W` のみからなる文字列 - $ t_i $ が `S` ならば $ i $ 番の動物が羊であることを、`W` ならば狼であることを示す

### 制約 - $ 3\ ≦\ N\ ≦\ 10^{5} $ - $ s $ は `o` と `x` のみからなる長さ $ N $ の文字列 ### Sample Explanation 1 例えば $ 1,2,3,4,5,6 $ 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。 両隣が同じ種類の動物のとき羊は `o` と発言し、狼は `x` と発言すること、 両隣が異なる種類の動物のとき羊は `x` と発言し、狼は `o` と発言することに注意してください。 !\[b34c052fc21c42d2def9b98d6dccd05c.png\](https://atcoder.jp/img/arc069/b34c052fc21c42d2def9b98d6dccd05c.png) ### Sample Explanation 2 存在しない場合は `-1` を出力してください。