亚德里亚海海岸和岛屿上点缀着各种形状和大小的迷人海滩。然而，许多海滩无法乘车抵达。为了满足日益增长的需求，海岸附近的一片巨大空地已被改造成一个停车场。由于所有参与设计的建筑师都具有电子工程背景，因此停车场的布局类似于设计电路时常用的串并联图。
停车场由停车位和连接它们的双向道路组成。每条道路连接两个不同的停车位，每对停车位之间最多由一条道路连接。在任何时刻，每个停车位最多只能被一辆车占用。其他车辆无法通过已被占用的停车位。
图 1：构建 splot 的规则，每条规则在下方对应条款中说明
混联停车场（也称为 splot）是一种具有两个特殊停车位（分别称为源点（source）和汇点（terminal））的停车场，它是通过串联和并联组合规则由单个停车位构建而成的。每个 splot 都可以通过其编码来指定——这是一个描述其结构和已停放车辆位置的字符序列。合法的 splot 及其编码递归定义如下：
- 仅由单个停车位且无道路组成的停车场是一个合法的 splot。这个单一的停车位既是该 splot 的源点也是汇点。如果该停车位为空，则该 splot 的编码仅为小写字母
o；如果该停车位被车辆占用，则编码为小写字母x。 - 如果 $G_1$ 和 $G_2$ 是两个合法的 splot，它们的串联组合 $G$ 也是一个 splot。串联组合是通过在 $G_1$ 的汇点和 $G_2$ 的源点之间增加一条道路得到的。新得到的 splot $G$ 的源点是 $G_1$ 的源点，而 $G$ 的汇点是 $G_2$ 的汇点。如果 $E_1$ 和 $E_2$ 分别是 splot $G_1$ 和 $G_2$ 的编码，那么 $G$ 的编码为
SE1E2#。换句话说，该编码是通过将大写字母S、被组合的 splot 的编码以及井号字符#拼接而成的。 - 如果 $G_1$ 和 $G_2$ 是两个合法的 splot，它们的并联组合 $G$ 也是一个合法的 splot。并联组合是通过增加两个名为 $s$ 和 $t$ 的新停车位，并在 $s$ 与 $G_1$ 和 $G_2$ 的源点之间增加道路，以及在 $t$ 与 $G_1$ 和 $G_2$ 的汇点之间增加道路而得到的。新得到的 splot $G$ 的源点是新增加的停车位 $s$，而汇点是新增加的停车位 $t$。如果 $E_1$ 和 $E_2$ 分别是 splot $G_1$ 和 $G_2$ 的编码，且 $E_s$ 和 $E_t$ 分别是源点 $s$ 和汇点 $t$ 的编码（如果对应车位为空则为小写字母
o，否则为小写字母x），那么 $G$ 的编码为PEs|E1E2|Et#。换句话说，该编码是通过将大写字母P、源点停车位的编码、竖线字符|、被组合的 splot 的编码、另一个竖线字符|、汇点停车位的编码以及最后的井号字符#拼接而成的。
图 2：对应第一个样例的 splot
例如，上图中给出的 splot 的编码为 Po|Px|Sxo#Soo#|o#Soo#|o#。请注意，splot $G$ 的编码中小写字母的数量总是与 $G$ 中的停车位数量相同，并且 $G$ 中的停车位与其编码中的小写字母之间存在一一对应关系。
整个停车场恰好有一个出口，它直接连接到整个 splot 的源点停车位。如果一辆车能够离开 splot，即它可以通过某条由道路和空车位组成的路径到达源点停车位，我们就说这辆车未被阻塞。例如，在上面的 splot 中，两辆车都没有被阻塞，但如果我们要在该 splot 的汇点（最右侧的节点）停放一辆车，那么其中一辆车就会被阻塞。允许在 splot 的源点停车位停放车辆，然而，如果我们这样做，splot 中的所有其他车辆都将被阻塞。
任务
停车场的管理员希望安排驶入的车辆，使得没有任何车辆被阻塞。假设给我们一个可能已经停放了一些车辆的 splot，且这些已有的车辆都没有被阻塞。编写一个程序，计算在不移动任何已有车辆、且没有任何车辆被阻塞的前提下，该 splot 中最多可以停放的车辆总数（包括已有的车辆）。此外，你的程序还应该找出一种达到该最大车辆数的车辆安排方案。
输入格式
输入的第一行包含一个长度至少为 1 且最多为 100,000 的字符序列——即给定 splot 的编码。序列中出现的字符仅限于大写字母 P 和 S、小写字母 o 和 x，以及字符 #（ASCII 35）和 |（ASCII 124）。输入将是符合上述规则的 splot 编码。输入中 splot 里已有的车辆均未被阻塞。
输出格式
输出应包含 2 行。
第一行应包含一个整数 $M$——如上所述，splot 中最多可以停放的车辆数量。
第二行应包含一个字符序列——具有最优车辆安排方案的 splot 编码。该序列应恰好包含 $M$ 个字母 x，并且必须能够通过将输入序列中的某些字母 o 替换为 x 来得到。
可能存在多种最优安排方案，你的程序可以输出其中任意一种。
子任务
- 如果输出不正确或不完整，但输出的第一行（最大车辆数）是正确的，则该测试点将获得 80% 的分数。
- 在总分值为 30 分的测试点中，splot 中的总停车位数量最多为 20。
- 在另外总分值为 40 分的测试点中，splot 是空的，即输入中不包含字母
x。
样例
输入样例 1
Po|Px|Sxo#Soo#|o#Soo#|o#
输出样例 1
3 Po|Px|Sxo#Sox#|o#Soo#|o#
输入样例 2
Po|SPo|oo|o#Px|oo|o##Po|Sxo#Po|ox|o#|o#|o#
输出样例 2
7 Po|SPo|xx|o#Px|ox|o##Po|Sxx#Po|ox|o#|o#|o#
工具支持
一个名为 splot_tool 的可执行文件（可通过竞赛系统下载）可以帮助你可视化测试输入和输出。该工具接受一个文件名作为参数——可以是格式合法的输入文件，也可以是该任务的输出文件，并生成一个描绘文件中编码的 splot 的 SVG 图像。生成的图像可以使用网页浏览器查看。该工具的使用示例如下：
$ ./splot_tool splot.dummy.out.1 splot.dummy.out.1 parsed (10 parking spaces). splot.dummy.out.1.svg created. $ chromium splot.dummy.out.1.svg
该工具将检查 splot 是否格式正确，否则会给出相应的错误信息。它不会进行任何其他合法性检查——即使解决方案不正确，文件也可能正常渲染。
该工具仅适用于编码长度最多为 200 个字符的 splot。