Fun Pipe Puzzle

Interview

Time limit1sMemory limit2048 MB

Summary

Given a 2-row grid of I and L pipes, decide whether rotating them can connect a path from cell (1, 1) to cell (2, N).

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Implementation
Solved: No attempts yet

Problem

Jinheung is solving a fun pipe puzzle. The puzzle is 2 cells tall and $N$ cells wide. The cell that is $i$ -th from the top and $j$ -th from the left is written as $(i, j)$ .

Every cell except $(1, 1)$ and $(2, N)$ has one pipe installed. There are two kinds of pipes: the I-shaped pipe and the L-shaped pipe. Jinheung wants to rotate these pipes in place as needed to connect a pipe path from $(1, 1)$ to $(2, N)$ .

Figure 1. An I-shaped pipe can be rotated to form the two shapes above.

Figure 2. An L-shaped pipe can be rotated to form the four shapes above.

Given the type of pipe installed in each cell, determine whether Jinheung can connect a pipe path from $(1, 1)$ to $(2, N)$ .

Figure 3. One way to connect a pipe path from $(1, 1)$ to $(2, N)$ .

Input

The first line contains the width $N$ of the puzzle.

The second line contains a string of length $N$ that gives the pipe types in the top row.

The third line contains a string of length $N$ that gives the pipe types in the bottom row.

In each string, X is given at $(1, 1)$ and $(2, N)$ . An I-shaped pipe is given as I, and an L-shaped pipe is given as L.

Output

If Jinheung can connect a pipe path from $(1, 1)$ to $(2, N)$ by rotating the pipes appropriately, print YES. Otherwise, print NO.

Constraints

$2 \le N \le 200\,000$

Examples2

Example 1
Input
```
5
XLLIL
LILIX
```
Expected output
```
YES
```
Example 2
Input
```
4
XLII
LILX
```
Expected output
```
NO
```