금속 막대 정육면체

시간 제한1초메모리 제한512 MB

요약

N×N 격자의 왼쪽, 오른쪽, 위, 아래에서 본 네 가지 관측값이 주어질 때, 막힌 칸을 적절히 배치해 그 값을 정확히 만들 수 있는지 판별한다.

난이도: 어려움10점 중 8점
유형: 그리디, 구현, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

아침 일찍 아이들의 놀이터를 지켜보던 출제자는 흥미로운 물체를 발견했다. 금속 막대로 만든 정육면체인데, 이 정육면체는 금속 막대로 만든 단위 정육면체 여러 개로 이루어져 있다.

정육면체를 관찰하던 중 출제자는 흥미로운 문제를 떠올렸다. 3차원 물체를 다루는 문제를 좋아하는 사람은 없으니, 여기서는 문제의 2차원 버전을 소개한다.

$N \times N$ 행렬이 주어진다. 정사각형의 일부 칸은 막혀 있고 일부는 비어 있다. 출제자는 정사각형을 네 방향에서 관찰했다. 먼저 정사각형을 왼쪽에서 보면서, $N$ 개의 각 행마다 보이는 첫 번째 막힌 칸 앞에 있는 빈 칸의 개수를 적었다. 어떤 행에도 막힌 칸이 없으면 -1을 적었다. 그런 다음 오른쪽, 위, 아래 방향에서 같은 과정을 순서대로 반복했다.

이렇게 하면 정사각형의 각 변마다 $N$ 개의 수를 적으므로 모두 $4N$ 개의 수를 적게 된다. 그런데 정체불명의 악당들이 정사각형을 파괴했고, 남은 것은 출제자가 적어 둔 수들뿐이었다. 출제자는 이 수들이 말이 되는지, 즉 서술한 과정을 거쳐 같은 수열을 얻을 수 있는 정사각형이 존재하는지 궁금해한다.

입력

첫째 줄에 정사각형의 한 변의 길이 $N$ 이 주어진다. ( $1 \le N \le 100\,000$ )

둘째 줄에 왼쪽에서 정사각형을 보며 1번째 행부터 $N$ 번째 행까지 차례로 얻은 $N$ 개의 정수 $L_i$ 가 주어진다. ( $-1 \le L_i < N$ )

셋째 줄에 오른쪽에서 정사각형을 보며 1번째 행부터 $N$ 번째 행까지 차례로 얻은 $N$ 개의 정수 $R_i$ 가 주어진다. ( $-1 \le R_i < N$ )

넷째 줄에 위에서 정사각형을 보며 1번째 열부터 $N$ 번째 열까지 차례로 얻은 $N$ 개의 정수 $U_i$ 가 주어진다. ( $-1 \le U_i < N$ )

다섯째 줄에 아래에서 정사각형을 보며 1번째 열부터 $N$ 번째 열까지 차례로 얻은 $N$ 개의 정수 $D_i$ 가 주어진다. ( $-1 \le D_i < N$ )

출력

주어진 조건을 만족하는 정사각형을 만들 수 있으면 “DA”를, 만들 수 없으면 “NE”를 출력한다.

예제2

예제 1
입력
```
3
-1 2 0
-1 0 1
2 2 1
0 0 1
```
예상 출력
```
DA
```
예제 2
입력
```
3
-1 0 1
-1 2 1
-1 2 -1
1 0 -1
```
예상 출력
```
NE
```