/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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_i が o ならば両隣の動物が同じ種類であると、x ならば異なる種類であると i 番の動物が言ったことを示します。
より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき o と答え、そうでないとき x と答えます。
狼は両隣の動物がどちらも羊あるいはどちらも狼のとき x と答え、そうでないとき o と答えます。
これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。存在するならば一例を示し、存在しないならば -1 を出力しなさい。
制約
- 3 ≦ N ≦ 10^{5}
- s は
oとxのみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
s と矛盾しないような各動物の種類の割当てが存在しないならば -1 を出力してください。
存在するならば以下の形式で文字列 t を出力してください。 t で示される割り当てが s と矛盾しないならば正解となります。
- t は長さ N で
SとWのみからなる文字列 - t_i が
Sならば i 番の動物が羊であることを、Wならば狼であることを示す
入力例 1
6 ooxoox
出力例 1
SSSWWS
例えば 1,2,3,4,5,6 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。
両隣が同じ種類の動物のとき羊は o と発言し、狼は x と発言すること、
両隣が異なる種類の動物のとき羊は x と発言し、狼は o と発言することに注意してください。
入力例 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
oandx.
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
SandW. - If t_i is
S, it indicates that the animal numbered i is a sheep. If t_i isW, 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.
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