Description

Dina 和 Dima 是年轻的考古学家，他们正在多瑙河三角洲（今多布罗加地区）探索一座被认为属于达契亚文化（可能是国王德切巴鲁斯本人）的古老马赛克阶梯。

每个台阶上都覆盖着 8 块马赛克，每块马赛克要么是白色（W），要么是红色（R）。每天早上，他们都会从上往下挖掘恰好一个台阶。

每天下午吃完午饭后，当他们沿着阶梯走向工作区域时，他们会玩一个游戏。他们会（非常小心地）将一块手帕放在最顶层的台阶上。然后由 Dina 先手，两人轮流移动手帕。每次移动时，玩家可以将手帕向下移动若干个台阶。只有当两个台阶之间的距离小于或等于它们共同马赛克块数（相同位置颜色相同的马赛克对数）时，才允许将手帕从一个台阶移动到另一个较低的台阶。无法移动的玩家将输掉当天的游戏。

例如，在上图中，Dina 可以将手帕从最顶层移动到中间台阶（因为 $1 \le 7$），或者移动到底部台阶（因为 $2 \le 6$）。

对于每个下午的游戏，如果双方都采取最优策略，请判断谁会获胜。

Input Format

第一行包含一个整数 $n$（$1 \le n \le 300\,000$）——阶梯的高度。

接下来的 $n$ 行，每行包含 8 个字符 W 或 R——从上到下描述每个台阶的马赛克图案。

Output Format

输出一行包含 $n$ 个数字，每个数字对应一个下午的游戏结果。1 表示 Dina 获胜，2 表示 Dima 获胜。

3
WWWWWWWW
RRRRRRRR
WWWWWWWW

221

7
WWWWRRWW
WWWRRRWW
WWWRRWWW
WWRRRWWW
WWRRWWWW
WRRRWWWW
WRRWWWWW

2111121

Hint

翻译由 DeepSeek V3 完成