← 返回题目列表

AtCoder · arc069_b

D. 动物园

中文机器翻译题面 查看原题

分数: 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 is W,表示该动物编号为 i 是一只狼。

示例输入 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