题目描述

亚得里亚海的海岸线和岛屿拥有各种形状和大小的迷人海滩。然而，许多海滩无法通过汽车到达。为了满足日益增长的需求，海岸附近的一大片场地被改建成了停车场。由于所有参与设计的建筑师都有电气工程背景，停车场的布局类似于设计电路时常用的串并联图。

停车场由停车位和连接它们的双向道路组成。每条道路连接两个不同的停车位，且每对停车位之间最多只有一条道路。任何时候，每个停车位最多只能停放一辆车。其他车辆不能通过被占用的停车位行驶。

图1：构建串并联停车场的规则

串并联停车场是指具有两个特殊停车位——源点和终点——的停车场，通过串联和并联组合规则从单个停车位构建而成。每个串并联停车场可以通过其编码来指定。

编码规则

有效的串并联停车场及其编码递归定义如下：

1. 单个停车位

   • 由单个停车位和无道路组成
   • 该停车位既是源点也是终点
   • 编码：
     • 停车位为空：o
     • 停车位被占用：x

2. 串联组合

   • 将两个串并联停车场 (G_1) 和 (G_2) 组合
   • 在 (G_1) 的终点和 (G_2) 的源点之间添加一条道路
   • 新源点 = (G_1) 的源点，新终点 = (G_2) 的终点
   • 编码：S + (E_1) + (E_2) + #
     • 其中 (E_1, E_2) 是子停车场的编码

3. 并联组合

   • 将两个串并联停车场 (G_1) 和 (G_2) 组合
   • 添加两个新的停车位 (s) 和 (t)
   • 连接 (s) 到 (G_1) 和 (G_2) 的源点
   • 连接 (t) 到 (G_1) 和 (G_2) 的终点
   • 新源点 = (s)，新终点 = (t)
   • 编码：P + (E_s) + | + (E_1) + (E_2) + | + (E_t) + #
     • 其中 (E_s, E_t) 是源点和终点的编码（o 或 x）

图2：对应于第一个样例的串并联停车场

示例：图中停车场的编码为：Po|Px|Sxo#Soo#|o#Soo#|o#

---

问题描述

停车场只有一个出口，直接连接到整个停车场的源点。

• 称一辆车未被阻挡，如果它可以通过空闲停车位组成的路径到达出口（源点）
• 初始状态保证所有已有车辆都未被阻挡
• 允许在源点停车，但如果这样做，其他所有车辆都会被阻挡

任务：

1. 计算在不阻挡任何车辆且不移动现有车辆的情况下，能停放的最大车辆总数
2. 找出一种达到该最大值的停车方案

---

输入格式

输入包含一个字符串，表示串并联停车场的编码。

字符串中只包含：大写字母 P, S；小写字母 o, x；字符 #, |。

编码保证符合上述规则，且初始车辆都未被阻挡。

---

输出格式

输出包含两行：

• 第一行：一个整数 (M)，表示最大车辆数
• 第二行：一个字符串，表示最优安排后的编码
  • 必须恰好包含 (M) 个 x
  • 只能通过将输入中的 o 改为 x 得到
  • 如有多解，输出任意一种即可

---

评分规则

• 如果方案错误但最大车辆数正确，获得该测试点 80% 的分数

---

数据范围

• 编码长度至少为 1，至多为 (10^5)
• 30% 数据：停车位总数 ≤ 20
• 40% 数据：初始为空（无 x）

---

样例

输入：

Po|Px|Sxo#Soo#|o#Soo#|o#

输出：

3
Po|Px|Sxo#Sox#|o#Soo#|o#

---