在 RedBlue 市，每两座建筑物之间都有一条红色的或蓝色的道路。从红色道路切换到蓝色道路（或反之）需要花费一张票。路线的长度定义为所访问建筑物的数量。例如，以下路线长度为 5，花费一张票：

$1 \xrightarrow{\text{蓝}} 2 \xrightarrow{\text{蓝}} 3 \xrightarrow{\text{红}} 4 \xrightarrow{\text{红}} 3$

如果我们想在第二次访问顶点 3 后再次在蓝色道路上行驶，我们需要另一张票，总共需要两张票：

$1 \xrightarrow{\text{蓝}} 2 \xrightarrow{\text{蓝}} 3 \xrightarrow{\text{红}} 4 \xrightarrow{\text{红}} 3 \xrightarrow{\text{蓝}} 2$

你是一名访问 RedBlue 市的旅行推销员，你希望至少访问每座建筑物一次，同时尽量减少对同一建筑物的重复访问。你还没有决定从哪座建筑物开始你的路线，所以你想规划出所有可能的路线。此外，你只有一张票。对于每座建筑物，你都想找到一条最短的路线，该路线从该建筑物出发，至少访问所有建筑物一次，并且最多使用一张票。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 2000$)，表示 RedBlue 市中建筑物的数量。

第 2 行到第 $N$ 行，每行包含一个字符串。第 $i$ 行包含字符串 $C_i$，表示与建筑物 $i$ 相连的道路颜色。字符串 $C_i = C_{i,1}C_{i,2}\dots C_{i,i-1}$ 的长度为 $i-1$，仅由字符 R 和 B 组成。如果 $C_{i,j}$ 为 R，则建筑物 $i$ 和 $j$ 之间的道路为红色。否则，道路为蓝色。

输出格式

输出 $2N$ 行。对于 $1 \le i \le N$，第 $2i-1$ 行应包含一个整数 $M_i$，表示从建筑物 $i$ 出发的旅行计划的长度。第 $2i$ 行应包含 $M_i$ 个空格分隔的整数，描述从建筑物 $i$ 出发访问建筑物的顺序。

子任务

对于你的每一个旅行计划，都会计算一个分数。设 $K_i$ 为从每座建筑物出发的最优路线长度，$M_i$ 为你的路线长度。如果 $M_i > 2K_i$，则你的得分为 0，并将收到“答案错误”（Wrong Answer）的判决。如果 $M_i = K_i$，则你的得分为 25。否则，你的得分为 $\lfloor 8 + 8 \times \frac{2K_i - M_i}{K_i - 1} \rfloor$。该测试用例的得分为每个旅行计划得分的最小值。

如果你的任何计划无效，你的得分为 0，并将收到“答案错误”（Wrong Answer）的判决。

你的提交得分为所有测试用例得分的最小值。

样例

输入 1

4
R
RR
BRB

输出 1

5
1 4 2 1 3
6
2 3 1 2 3 4
5
3 1 2 3 4
4
4 3 1 2

说明 1

RedBlue 市的结构如下：

从建筑物 3 出发的路线，通过按 3, 2, 1, 4 的顺序访问建筑物，其最优长度为 4。该解的路线长度为 5，意味着得分为 $\lfloor 8 + 8 \times \frac{2 \times 4 - 5}{4 - 1} \rfloor = 16$。