金州幼儿园的 Gamer Bellalabella 十分喜欢旋转水管小游戏,这类游戏的目标是通过旋转游戏中的管道使得水流的输入口与输出口联通。
最近 Bellalabella 发现了一款特殊的旋转水管游戏,这款游戏中水管只包含 I 形水管与 L 形水管,并且支持自定义游戏!Bellalabella 立即创造了 T 个属于自己的旋转水管游戏:
整个游戏构成一个 4 × m 的矩形。
第一行仅包含一个位于第 x 列的水流输入口,水流自输入口向下流出。
游戏第二、三行有 m 列水管,第 i 行 j 列为 I 或者 L 表示水管的形状。
第四行仅包含一个位于第 y 列的水流输出口,水流输出口仅接受向下流出的水流。
以样例第一个游戏为例,初始状态如左图所示,经过旋转 (2, 2),(2, 3),(3, 2) 的水管得到如右图所示
的状态即可让水流输入口输出口联通。
Bellalabella 想知道自己创造出的 T 个旋转水管游戏是否存在一个旋转方案使得输入口与输出口联通,然而 Bellalabella 的游戏中水管太多了,自己不能解决,于是 Bellalabella 将问题交给了正在旁观的你。