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 ~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 Specification

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 ~1^{st}~ 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 ~1^{st}~ 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 ~1^{st}~ 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 ~1^{st}~ to ~N^{th}~ column.

Output Specification

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

Scoring

In test cases worth 40% of total points, it will hold that ~N \le 1\,000~.

Sample Input 1

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

Sample Output 1

DA

Explanation for Sample Output 1

Sample Input 2

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

Sample Output 2

NE