Kocka

I'm again in the cube! I'm again in the cube!

Ενώ παρακολουθούσε την παιδική χαρά τις πρώτες πρωινές ώρες, ο συντάκτης αυτού του προβλήματος είδε ένα ενδιαφέρον αντικείμενο: έναν κύβο από μεταλλικές ράβδους, που αποτελείται από πολλούς κύβους μεγέθους μίας μονάδας, κατασκευασμένους από μεταλλικές ράβδους.

Παρατηρώντας τον κύβο, του ήρθε στο μυαλό ένα ενδιαφέρον πρόβλημα. Ακολουθεί η δισδιάστατη έκδοση του προβλήματος, καθώς σε κανέναν δεν αρέσουν τα προβλήματα που αφορούν τρισδιάστατα αντικείμενα:

Σας δίνεται ένας ~N \times N~ πίνακας (τετράγωνο για αναφορά). Κάποια από τα πεδία του τετραγώνου είναι μπλοκαρισμένα και κάποια είναι άδεια. Ο συγγραφέας παρακολουθούσε το τετράγωνο καθεμιάς από τις 4 πλευρές του. Αρχικά, κοίταξε το τετράγωνο από την αριστερή του πλευρά και για κάθε μία από τις ~N~ σειρές του έγραψε πόσα κενά πεδία υπήρχαν στη σειρά μπροστά από το πρώτο μπλοκαρισμένο πεδίο που μπορούσε να δει. Αν δεν υπήρχαν μπλοκαρισμένα πεδία στη σειρά, έγραφε τον αριθμό -1. Στη συνέχεια επανέλαβε την ίδια διαδικασία κοιτάζοντας το τετράγωνο από τη δεξιά, πάνω και κάτω πλευρά του, με αυτή τη σειρά.

Με αυτόν τον τρόπο, έγραψε συνολικά ~4N~ αριθμούς, γράφοντας ~N~ αριθμούς για κάθε πλευρά του τετραγώνου. Ωστόσο, άγνωστοι κακοί κατέστρεψαν το τετράγωνό του και το μόνο που απέμενε ήταν οι αριθμοί που είχε γράψει. Ο συντάκτης του προβλήματος αναρωτιέται εάν αυτοί οι αριθμοί έχουν κάποιο νόημα, δηλαδή εάν είναι δυνατό να σχηματιστεί ένα τετράγωνο για το οποίο θα ληφθεί η ίδια ακολουθία αριθμών κάνοντας την περιγραφόμενη διαδικασία.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο αριθμό ~N (1 \le N \le 100\,000)~, τη διάσταση του τετραγώνου.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~L_i (-1 \le L_i \le N)~, αριθμούς που λαμβάνονται κοιτώντας το τετράγωνο από την αριστερή του πλευρά, με σειρά από την 1η έως την ~N~οστή σειρά.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~R_i (-1 \le R_i \le N)~, που λαμβάνονται κοιτώντας το τετράγωνο από τη δεξιά του πλευρά, με σειρά από την 1η έως τη ~N~-οστή σειρά.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους ~U_i (-1 \le U_i < N)~, αριθμούς που λαμβάνονται κοιτώντας το τετράγωνο από την επάνω πλευρά του, με σειρά από την 1η έως τη ~N~-οστή στήλη.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~D_i (-1 \le D_i < N)~, αριθμούς που λαμβάνονται κοιτώντας το τετράγωνο από την κάτω πλευρά του, με σειρά από την 1η έως τη ~N~-οστή στήλη.

Έξοδος

Εάν είναι δυνατόν, από ένα τετράγωνο που ικανοποιεί τις δεδομένες προϋποθέσεις, τυπώστε "DA" (το "ΝΑΙ" στα Κροατικά, χωρίς εισαγωγικά), διαφορετικά τυπώστε "NE" (το "ΟΧΙ" στα Κροατικά).

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 40% των συνολικών πόντων, θα ισχύει ότι ~N \le 1\,000~.

Παραδείγματα

input

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

output

DA

Επεξήγηση του 1ου παραδείγματος:

input

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

output

NE