Matrix Reconstruction from Directional Observations

You are given a square matrix of size \(N \times N\). Some cells are blocked and some are empty. An observer records, for each row and each column, the number of consecutive empty cells seen before the first blocked cell when observed from four directions.

• Left observation (per row): For each row, when observed from the left, record the number of empty cells before the first blocked cell. If no blocked cell is encountered in the row, record \(-1\).
• Right observation (per row): For each row, when observed from the right, record the number of empty cells before the first blocked cell. If no blocked cell is encountered, record \(-1\).
• Top observation (per column): For each column, when observed from the top, record the number of empty cells before the first blocked cell. If no blocked cell is encountered, record \(-1\).
• Bottom observation (per column): For each column, when observed from the bottom, record the number of empty cells before the first blocked cell. If no blocked cell is encountered, record \(-1\).

Thus, there are \(4N\) numbers provided. Unfortunately, the original matrix was destroyed and only these observations remain. Your task is to determine whether there exists an \(N \times N\) matrix that can yield the given observations.

Note: In each row, if one observation is \(-1\) (indicating the row is completely empty), then the other observation must also be \(-1\). Similarly for each column. For a row with at least one blocked cell, let \(L[i]\) be the observation from the left and \(R[i]\) (\(\ge 0\)) be the observation from the right. Then the first blocked cell from the left appears at column index \(L[i]\) (0-indexed) and the first blocked cell from the right appears at column index \(N-1-R[i]\). It is necessary that \(L[i] \le N-1-R[i]\). Similar conditions hold for the top and bottom observations in each column.

If all these conditions can be met simultaneously (including cross-checking between row and column forced empty and blocked cells), then the observations are valid; otherwise, they contain an error.

inputFormat

The input begins with an integer \(N\) (the size of the matrix). The next four lines each contain \(N\) space-separated integers:

• The first line represents the left observations for each row.
• The second line represents the right observations for each row.
• The third line represents the top observations for each column.
• The fourth line represents the bottom observations for each column.

Each observation is either a non-negative integer or \(-1\) (indicating no blocked cell seen).

outputFormat

Output a single line containing either YES or NO indicating whether it is possible to reconstruct an \(N \times N\) matrix consistent with the given observations.

Output YES if such a matrix exists, and NO otherwise.

sample

3
-1 1 0
-1 1 0
2 1 2
0 1 0

YES