Tôi lại trong khối lập phương! Tôi lại trong khối lập phương!

Trong khi quan sát sân chơi của trẻ em vào giờ sáng sớm, tác giả của nhiệm vụ này bắt gặp một đối tượng thú vị: một khối lập phương được làm từ các thanh kim loại, bao gồm nhiều khối lập phương với kích thước đơn vị được làm từ các thanh kim loại. Trong khi quan sát khối lập phương, một vấn đề thú vị xuất hiện trong tâm trí của tác giả. Dưới đây là phiên bản hai chiều của vấn đề, vì không ai thích các vấn đề liên quan đến các đối tượng ba chiều:

Bạn được cho một ma trận ~N \times N~ (vuông để tham khảo). Một số ô trong hình vuông bị chặn và một số trống rỗng. Tác giả đã quan sát hình vuông từ mỗi phía của nó. Trước tiên, ông nhìn vào hình vuông từ phía trái, và đối với mỗi hàng trong ~N~ hàng của nó, ông viết số lượng ô trống trong hàng trước ô chặn đầu tiên ông có thể thấy. Nếu không có ô bị chặn trong một hàng, ông ghi số -1. Sau đó, ông lặp lại cùng một thủ tục nhìn vào hình vuông từ phía phải, trên và dưới của nó, theo thứ tự đó.

Bằng cách làm như vậy, ông viết tổng cộng ~4N~ số, vì ông viết N số cho mỗi phía của hình vuông. Tuy nhiên, các tên tội phạm không xác định đã phá hủy hình vuông của ông và chỉ còn lại những số ông đã ghi lại. Tác giả của nhiệm vụ tự hỏi liệu những số đó có ý nghĩa gì không, tức là liệu có thể tạo ra một hình vuông mà cùng một chuỗi số sẽ được thu được bằng cách thực hiện thủ tục được mô tả.

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \leq N \leq 100,000)~, kích thước của hình vuông.
• Dòng thứ hai chứa ~N~ số nguyên ~L_i~ ~(-1 \leq L_i < N)~, các số được thu được bằng cách quan sát hình vuông từ phía trái của nó, theo thứ tự từ hàng ~1~ đến hàng ~N~.
• Dòng thứ ba chứa ~N~ số nguyên ~R_i~ ~(-1 \leq R_i < N)~, các số được thu được bằng cách quan sát hình vuông từ phía phải của nó, theo thứ tự từ hàng ~1~ đến hàng ~N~.
• Dòng thứ tư chứa ~N~ số nguyên ~U_i~ ~(-1 \leq U_i < N)~, các số được thu được bằng cách quan sát hình vuông từ phía trên của nó, theo thứ tự từ cột ~1~ đến cột ~N~.
• Dòng thứ năm chứa ~N~ số nguyên ~D_i~ ~(-1 \leq D_i < N)~, các số được thu được bằng cách quan sát hình vuông từ phía dưới của nó, theo thứ tự từ cột ~1~ đến cột ~N~.

Onput

Nếu có thể tạo ra một hình vuông thỏa mãn các điều kiện đã cho, in ~DA~. Nếu không in ra ~NE~.

Chú ý

~40 \%~ tổng số điểm, sẽ thỏa mãn điều kiện ~N \leq 1000~.

Sample Input 1

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

Sample Output 1

DA

Sample Input 2

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

Sample Output 2

NE

Giải thích

Trong test thứ nhất: