本题没有可用的提交语言。

问题描述

Stephen Wolfram在《一种新科学》中描述了一种特殊的元胞自动机。这些自动机由若干行方块组成，每个方块根据前一行的状态决定是否填充。生成新行时，自动机根据预设的“规则”决定输出行的方块是否着色。

例如，下图展示了应用“规则254”生成的“输出”：

该自动机初始化为仅有一个黑色方块的输入行。通过反复应用规则254，生成了上述黑色三角形。

对于此规则，每个框的顶行表示一个细胞（中间细胞）及其两个邻居（细胞的左右邻居）的八种可能颜色组合。框的底行指定中心细胞在下一步的颜色。基于此排列，共有255种不同的生成规则或自动机，编号如下：

**有界自动机**

与《一种新科学》中的自动机不同，本题的自动机在“有界空间”中运行。即：

1. 自动机输出的每行恰好包含$n$个方块。
2. 输出的首尾方块始终为白色（无论自动机规则如何）。这意味着自动机在计算新的第二和倒数第二字符时可以检查输入行的首尾方块，但输出行时不能改变首尾方块的颜色。

程序要求

对于输入中的每一行，确定是否有任何255种可能的自动机从标准初始状态开始，在给定步数内生成了该特定行。如果没有自动机能在给定步数内生成该序列，则输出"NONE"。如果有多个自动机生成了该行，则按规则编号升序输出所有符合条件的自动机。

输入格式

输入每行包含两个字段：

1. 最大步数（$max\_step$）：自动机运行的最大步数（最多32位整数）。
2. 一个奇数长度的字符串：表示行上的“方块”（长度不超过256）。'W'表示白色方块，'B'表示黑色方块。

如果输入字符串包含非'W'或'B'的字符，或不符合有界条件（首尾非白色或长度非奇数），则输出"LINE # NONE"。

输入以"END OF INPUT"结束，该行不处理。

输出格式

输出格式为"LINE # (rule, step)"，其中：

• $rule$是生成该输出的自动机编号（0到255）。
• $step$是首次生成该输出的步数（1到$max\_step$）。

如果有多个规则生成该输出，按规则编号升序输出所有对。若无匹配，输出"LINE # NONE"。

示例输入与输出

输入示例：

3 WBWBWBWBW
1000 WBWBWBWBBBW
5235 WBWWBWWBBBBWWBBWWWWWWBBWWWBBWWWWWWBBWWBBBBWWBWWBW
5 WBWBDCWBW
END OF INPUT

输出示例：

LINE 1 (91,3)
LINE 2 (15,8) (158,11) (159,14) (243,8)
LINE 3 (129,84) (161,84)
LINE 4 NONE

数据来源

Pacific Northwest 2004