Metal Bar Cube

Time limit1sMemory limit512 MB

Summary

Given the four viewing counts from left, right, top and bottom of an N by N grid, decide whether any placement of blocked cells can produce exactly those counts.

Level: Hard8 of 10
Topics: Greedy, Implementation, Math, Brute force
Solved: No attempts yet

Problem

I’m again in the cube!
I’m again in the cube!

While watching the kids’ playground in the early morning hours, the author of this task caught sight of an interesting object: a cube made out of metal bars, composed of many unit-sized cubes made out of metal bars.

While observing the cube, an interesting problem came to his mind. Here follows the two-dimensional version of the problem, since nobody likes problems involving 3D objects:

You’re given an $N \times N$ matrix (square for reference). Some of the fields in the square are blocked and some are empty. The author was watching the square from each of its 4 sides. Firstly, he looked at the square from its left side, and for each of its $N$ rows he wrote how many empty fields there were in the row in front of the first blocked field he could see. If there were no blocked fields in a row, he wrote down the number -1. Then he repeated the same procedure looking at the square from its right, top and bottom side, in that order.

By doing so, he wrote $4N$ numbers in total, as he wrote $N$ numbers for each side of the square. However, unknown villains destroyed his square and the only thing left were the numbers he had written down. The author of the task wonders if those numbers make any sense, i.e. if it is possible to form a square for which the same sequence of numbers will be obtained by doing the described procedure.

Input

The first line contains a positive integer $N$ ( $1 \le N \le 100\,000$ ), dimension of the square.

The second line contains $N$ integers $L_i$ ( $-1 \le L_i < N$ ), numbers obtained by watching the square from its left side, in order from 1st to $N$ th row.

The third line contains $N$ integers $R_i$ ( $-1 \le R_i < N$ ), numbers obtained by watching the square from its right side, in order from 1st to $N$ th row.

The fourth line contains $N$ integers $U_i$ ( $-1 \le U_i < N$ ), numbers obtained by watching the square from its top side, in order from 1st to $N$ th column.

The fifth line contains $N$ integers $D_i$ ( $-1 \le D_i < N$ ), numbers obtained by watching the square from its bottom side, in order from 1st to $N$ th column.

Output

If it is possible to form a square which satisfies the given conditions, print “DA” (Croatian for yes, without quotation marks), otherwise print “NE” (Croatian for no).

Examples2

Example 1
Input
```
3
-1 2 0
-1 0 1
2 2 1
0 0 1
```
Expected output
```
DA
```
Example 2
Input
```
3
-1 0 1
-1 2 1
-1 2 -1
1 0 -1
```
Expected output
```
NE
```