Un rompecabezas tiene un tornillo con un laberinto de \(R\) filas y una tuerca. Cada fila del laberinto y el interior de la tuerca son textos circulares binarios de largo \(C\): en la tuerca, 1 es una punta y 0 un espacio; en el laberinto, 1 es una pared y 0 un espacio.

La tuerca empieza separada, por encima de la fila \(1\) (la punta del tornillo). Cuando está en una fila, su posición es esa fila más una rotación; la posición es válida si ninguna punta coincide con una pared de esa fila. Los movimientos posibles son:

• girar un paso en cualquier sentido (rotación cíclica);
• bajar a la fila siguiente o subir a la anterior (manteniendo la rotación);
• mientras está separada del tornillo, girar libremente y también darla vuelta (invertir el sentido del texto circular).

Cada movimiento solo se puede hacer si la nueva posición es válida. El objetivo es pasar la última fila \(R\) y llegar a la cabeza del tornillo. Determina si el rompecabezas tiene solución.

Entrada

La primera línea tiene dos enteros \(R\) \((1 \le R \le 1000)\) y \(C\) \((3 \le C \le 100)\).

La segunda línea tiene el texto circular de la tuerca, de largo \(C\).

Cada una de las siguientes \(R\) líneas tiene el texto circular de una fila del laberinto, de arriba (la punta) hacia abajo (la cabeza).

Salida

Una línea con Y si el rompecabezas tiene solución, o N si no.

Ejemplo 1

Entrada

8 13
0110010000000
1100101110100
1001101000100
1100101110100
1000100010000
1010111011001
0000001010000
1001101111101
0001001100100

Salida

Y

Ejemplo 2

Entrada

1 3
100
101

Salida

Y

Ejemplo 3

Entrada

2 3
100
101
010

Salida

N

Ejemplo 4

Entrada

4 6
001000
011111
010001
010100
110111

Salida

Y

Ejemplo 5

Entrada

1 6
001011
001011

Salida

Y
The picture below explains the first sample.
Images on the left represent 3D views of
different stages of the game. In the middle, the images are flattened 2D versions of the corre-
sponding 3D views. Finally, images on the right represent the stages of the game according to
the described model (although for the sake of clarity, each character “1” has been replaced by
a given symbol, and each character “0” is shown as an empty space).
It can be seen in the top three images that the nut (having three pins) and the bolt start
separated. The second group of three images shows the situation of the game after the nut
has been moved four rows down (towards the head of the bolt). Then the nut is rotated one
position, moved down two more rows, rotated four positions in the opposite direction, and
finally moved down three rows, which solves the puzzle. Note that in this case the nut has not
been flipped, nor moved up (away from the head of the bolt).

Regional Latinoamericana 2022 del ICPC, problema M («Maze in Bolt»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.