题目描述

因为喜欢动物，すぬけくん建造了一个动物园。

在这个动物园中，有 $1,2,3,...,N$ 编号的 $N$ 只动物按环状排列。编号为 $i$（$2 \le i \le N-1$）的动物与编号 $i-1$ 和 $i+1$ 的动物相邻。而 $1$ 号动物与 $N$ 号和 $2$ 号动物相邻，$N$ 号动物与 $N-1$ 号和 $1$ 号动物相邻。

在动物园中有两类动物：只说真话的“羊”，以及只说假话的“狼”。

すぬけくん无法分辨谁是“羊”谁是“狼”，于是向每只动物询问它的左右邻居是否为同一种类。第 $i$ 只动物的回答为 $s_i$。若 $s_i$ 为 o，表示第 $i$ 只动物说自己的两侧邻居是同一种类，若为 x，表示为不同种类。

更正式地说，当一只“羊”的左右邻居同为“羊”，或同为“狼”时，它会说 o，否则说 x。当一只“狼”的左右邻居同为“羊”或同为“狼”时，它会说 x，否则说 o。

すぬけくん很好奇，是否存在一种动物种类的分配方式，不与这些回答相矛盾。如果存在，请给出一种方案；如果不存在，请输出 -1。

输入格式

输入通过标准输入给出，格式如下：

$N$ $s$

输出格式

如果不存在与 $s$ 不矛盾的动物种类分配方式，请输出 -1。

如果存在，请输出一个仅由 S（羊）和 W（狼）组成的长度为 $N$ 的字符串 $t$。$t_i$ 为 S 表示第 $i$ 只动物为“羊”，为 W 表示为“狼”。只要输出的方案与 $s$ 不矛盾，即视为正确答案。

样例 1

输入

6
ooxoox

输出

SSSWWS

样例 2

输入

3
oox

输出

-1

样例 3

输入

10
oxooxoxoox

输出

SSWWSSSWWS

说明/提示

约束条件

• $3 \le N \le 10^5$
• $s$ 是仅由 o 和 x 组成的、长度为 $N$ 的字符串

样例解释 1

例如编号 $1,2,3,4,5,6$ 的动物分别为羊、羊、羊、狼、狼、羊时，与所有动物的发言均不矛盾。或如“狼、羊、狼、羊、狼、狼”的分配也不矛盾。要注意，若一只羊的两侧邻居相同，则说 o，若不同则说 x；而狼正好相反。

样例解释 2

如果不存在满足条件的方案，请输出 -1。

由 ChatGPT 5 翻译