There is a $2\times n$ grid, where the cell at row $i$ and column $j$ is denoted as $(i,j)\ (1\leq i\leq 2,\ 1\leq j\leq n)$. Some of these cells contain a person.

In each operation, you can choose one of the following:

• Choose a row $i$ and align all people in that row to the left. That is, if there are $x$ people in row $i$, change the occupied cells in that row to all $(i,j)\ (1\leq j\leq x)$.
• Choose a row $i$ and align all people in that row to the right. That is, if there are $x$ people in row $i$, change the occupied cells in that row to all $(i,n-j+1)\ (1\leq j\leq x)$.
• Choose a column $j$ and align all people in that column to the top. That is, if there are $x$ people in column $j$, change the occupied cells in that column to all $(i,j)\ (1\leq i\leq x)$.
• Choose a column $j$ and align all people in that column to the bottom. That is, if there are $x$ people in column $j$, change the occupied cells in that column to all $(2-i+1,j)\ (1\leq i\leq x)$.

Given an initial state and a final state (i.e., whether each cell contains a person, with the total number of people guaranteed to be the same), determine if it is possible to transform the initial state into the final state using at most $10^6$ operations. If possible, provide a sequence of operations.

Input

The first line contains an integer $n$.

The second line contains a binary string of length $n$, where the $j$-th character is $1$ if and only if there is a person at $(1,j)$ in the initial state.

The third line contains a binary string of length $n$, where the $j$-th character is $1$ if and only if there is a person at $(2,j)$ in the initial state.

The fourth line contains a binary string of length $n$, where the $j$-th character is $1$ if and only if there is a person at $(1,j)$ in the final state.

The fifth line contains a binary string of length $n$, where the $j$-th character is $1$ if and only if there is a person at $(2,j)$ in the final state.

Output

If there is no solution, output NO.

Otherwise, output YES, followed by:

The first line: an integer $m$, representing the number of operations, where $0\leq m\leq 10^6$.

The next $m$ lines: each contains two integers, representing the operation type (numbered $1, 2, 3, 4$ according to the order in the problem description) and the row/column index.

Examples

Input

6
010100
110001
010001
100011

Output

YES
3
2 1
3 2
4 5

Input

6
000100
000000
001000
000000

Output

NO

Subtasks

For all data: $1\leq n\leq 10^5$.

$\text{Subtask 1}\ (2\%)$: Guaranteed to have no solution.

$\text{Subtask 2}\ (13\%)$: $n\leq 10$.

$\text{Subtask 3}\ (15\%)$: The number of people is at most $10$.

$\text{Subtask 4}\ (20\%)$: Guaranteed to have a solution.

$\text{Subtask 5}\ (10\%)$: The number of people is at most $n$, and the $j$-th person in the initial state is at $(1,j)$.

$\text{Subtask 6}\ (20\%)$: The number of people is at most $n$.

$\text{Subtask 7}\ (20\%)$: No special restrictions.