分数: 500 点
问题陈述
热爱动物的斯努克建造了一座动物园。
有 N 这个动物园里的动物。它们方便地编号 1 通过 N,并排列成一个圆圈。 动物编号 i (2≤i≤N-1) 与编号的动物相邻 i-1 和 i+1。另外,动物编号 1 与编号的动物相邻 2 和 N,动物编号 N 与编号的动物相邻 N-1 和 1.
这个动物园里有两种动物:只说真话的诚实羊和只说谎话的说谎狼。
Snuke 无法区分这两个物种,并询问每只动物以下问题:“你们的邻居是同一物种吗?”动物编号 i 已回答 s_i。在这里,如果 s_i is o,动物表示相邻的两个动物是同一物种,如果 s_i is x,动物说这两个相邻的动物是不同的物种。
更正式地说,一只羊回答了 o 如果相邻的两只动物都是羊或者都是狼,则回答 x 否则。
同样,狼也回答了 x 如果相邻的两只动物都是羊或者都是狼,则回答 o 否则。
Snuke 想知道是否存在与这些响应一致的有效动物物种分配。如果有这样的作业,请显示一项这样的作业。否则,打印 -1.
约束
- 3 ≤ N ≤ 10^{5}
- s 是一个长度为的字符串 N 组成
o和x.
输入
输入由标准输入按以下格式给出:
N s
输出
如果不存在与以下内容一致的有效分配 s,打印 -1。
否则,打印一个字符串 t 采用以下格式。如果由以下描述的分配,则输出被认为是正确的 t 与 s.
- t 是一个长度为的字符串 N 组成
S和W. - If t_i is
S,表示该动物编号为 i 是一只羊。如果 t_i isW,表示该动物编号为 i 是一只狼。
示例输入 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